面试算法汇总

本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。

Hot100 ​

哈希 ​

1. 两数之和 ​

python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = defaultdict(int)
        for i, x in enumerate(nums):
            if target - x in d:
                return [d[target - x], i]
            d[x] = i
java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (mp.containsKey(target - nums[i])) {
                return new int[]{i, mp.get(target - nums[i])} ;
            }
            mp.put(nums[i], i);
        }
    }
}

49. 字母异位词分组 ​

python
class Solution:
  def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    d = defaultdict(list)
    for s in strs:
      d[''.join(sorted(s))].append(s)
    return list(d.values())
java
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> mp = new HashMap<>();
        for (String str : strs) {
            char[] s = str.toCharArray();
            Arrays.sort(s);
            // mp.computeIfAbsent(Arrays.toString(s), k -> new ArrayList<>()).add(str);
            String key = Arrays.toString(s);
            if (mp.containsKey(key)) {
                mp.get(key).add(str);
            } else {
                List<String> tmp = new ArrayList<String>();
                tmp.add(str);
                mp.put(key, tmp);
            }
        }
        return new ArrayList<List<String>>(mp.values());
    }
}

128. 最长连续序列 ​

python
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        ans = 0
        st = set(nums)
        for num in st:
            if num - 1 in st:
                continue
            tmp = num + 1
            while tmp in st:
                tmp += 1
            ans = max(ans, tmp - num)
        return ans
java
class Solution {
    public int longestConsecutive(int[] nums) {
        int ans = 0;
        Set<Integer> st = new HashSet<>();
        for (int num : nums) {
            st.add(num); // 把 nums 转成哈希集合
        }
        for (int x : st) { // 遍历哈希集合
            if (st.contains(x - 1)) {
                continue;
            }
            // x 是序列的起点
            int y = x + 1;
            while (st.contains(y)) { // 不断查找下一个数是否在哈希集合中
                y++;
            }
            // 循环结束后，y-1 是最后一个在哈希集合中的数
            ans = Math.max(ans, y - x); // 从 x 到 y-1 一共 y-x 个数
        }
        return ans;
    }
}

双指针 ​

283. 移动零 ​

python
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = 0
        for j in range(len(nums)):
            if nums[j]:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
java
class Solution {
    public void moveZeroes(int[] nums) {
        int left = 0, right = 0;
        while (right < nums.length) {
            if (nums[right] != 0) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
                left += 1;
            }
            right += 1;
        }
    }
}

11. 盛最多水的容器 ​

python
class Solution:
    def maxArea(self, nums: List[int]) -> int:
        ans, left, right = 0, 0, len(nums) - 1
        while left < right:
            ans = max(ans, min(nums[left], nums[right]) * (right - left))
            if nums[left] >= nums[right]: right -= 1
            else: left += 1
        return ans
java
class Solution {
    public int maxArea(int[] height) {
        int ans = 0, left = 0, right = height.length - 1;
        while (left < right) {
            ans = Math.max(ans, Math.min(height[left], height[right]) * (right - left));
            if (height[left] >= height[right]) right--;
            else left++;
        }
        return ans;
    }
}

15. 三数之和 ​

python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n, ans = len(nums), []
        for i in range(n):
            if i > 0 and nums[i] == nums[i - 1]: continue
            target = -nums[i]
            left, right = i + 1, n - 1
            while left < right:
                if nums[left] + nums[right] == target:
                    ans.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]: left += 1
                    while left < right and nums[right] == nums[right - 1]: right -= 1
                    left += 1
                    right -= 1
                elif nums[left] + nums[right] < target:
                    left += 1
                else:
                    right -= 1
        return ans
java
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int n = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = n - 1;
            while (l < r) {
                int s = nums[i] + nums[l] + nums[r];
                if (s == 0) {
                    ans.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                }
                else if (s < 0) l++;
                else r--;
            }
        }
        return ans;
    }
}

42. 接雨水 ​

python
class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        st = []
        for i, x in enumerate(height):
            while st and x >= height[st[-1]]:
                tmp = st.pop()
                if not st: break
                ans += (min(x, height[st[-1]]) - height[tmp]) * (i - st[-1] - 1)
            st.append(i)
        return ans
java
class Solution {
    public int trap(int[] height) {
        int ans = 0;
        Deque<Integer> st = new LinkedList<>();
        for (int i = 0; i < height.length; i++) {
            while (!st.isEmpty() && height[i] > height[st.peek()]) {
                int tmp = st.pop();
                if (st.isEmpty()) {
                    break;
                }
                ans += (Math.min(height[i], height[st.peek()]) - height[tmp]) * (i - st.peek() - 1);
            }
            st.push(i);
        }
        return ans;
    }
}

滑动窗口 ​

3. 无重复字符的最长子串 ​

python
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        d = {}
        left, ans = 0, 0
        for right, c in enumerate(s):
            if c in d:
                left = max(left, d[c] + 1)
            d[c] = right
            ans = max(ans, right - left + 1)
        return ans
java
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] cnt = new int[128];
        int left = 0, ans = 0;
        for (int right = 0; right < s.length(); right++) {
            ++cnt[s.charAt(right)];
            if (cnt[s.charAt(right)] == 1) {
                ans = ans < right - left + 1 ? right - left + 1 : ans;
            }
            else {
                while (cnt[s.charAt(right)] > 1) {
                    --cnt[s.charAt(left)];
                    ++left;
                }
            }
        }
        return ans;
    }
}

438. 找到字符串中所有字母异位词 ​

python
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n, m = len(s), len(p)
        if n < m: return []
        ans = []
        sCount, pCount = [0] * 26, [0] * 26
        for i in range(m):
            pCount[ord(p[i]) - ord('a')] += 1
            sCount[ord(s[i]) - ord('a')] += 1
        if sCount == pCount:
            ans.append(0)
        for i in range(n - m):
            sCount[ord(s[i]) - ord('a')] -= 1
            sCount[ord(s[i + m]) - ord('a')] += 1
            if sCount == pCount:
                ans.append(i + 1)
        return ans
java
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int n = s.length(), m = p.length();
        if (n < m) return new ArrayList<Integer>();

        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < m; i++) {
            ++pCount[p.charAt(i) - 'a'];
            ++sCount[s.charAt(i) - 'a'];
        }
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int i = 0; i < n - m; i++) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + m) - 'a'];
            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }
        return ans;
    }
}

子串 ​

560. 和为 K 的子数组 ​

python
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        cnt = defaultdict(int, {0: 1})
        ans = tmp = 0
        for num in nums:
            tmp += num
            ans += cnt[tmp - k]
            cnt[tmp] += 1
        return ans
java
class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> mp = new HashMap<>();
        mp.put(0, 1);
        int ans = 0, tmp = 0;
        for (int num : nums) {
            tmp += num;
            ans += mp.getOrDefault(tmp - k, 0);
            mp.put(tmp, mp.getOrDefault(tmp, 0) + 1);
        }
        return ans;
    }
}

239. 滑动窗口最大值 ​

python
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []
        q = deque()
        for i, x in enumerate(nums):
            while q and x >= nums[q[-1]]:
                q.pop()
            q.append(i)
            while q[0] <= i - k:
                q.popleft()
            if i >= k - 1:
                ans.append(nums[q[0]])
        return ans
java
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> q = new LinkedList<>();
        int[] ans = new int[nums.length - k + 1];
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!q.isEmpty() && nums[i] >= nums[q.peekLast()]) {
                q.removeLast();
            }
            q.addLast(i);
            while (q.peek() <= i - k) {
                q.removeFirst();
            }
            if (i >= k - 1) {
                ans[j] = nums[q.peek()];
                j++;
            }
        }
        return ans;
    }
}

76. 最小覆盖子串 ​

python
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        cnt = Counter(t)
        need, cur = len(t), len(s)
        l = 0
        ans = ""
        for r, c in enumerate(s):
            if cnt[c] > 0: need -= 1
            cnt[c] -= 1
            if need == 0:
                while cnt[s[l]] != 0:
                    cnt[s[l]] += 1
                    l += 1
                if r - l <= cur:
                    cur = r - l
                    ans = s[l: r + 1]
                cnt[s[l]] += 1
                need += 1
                l += 1
        return ans
java
class Solution {
    public String minWindow(String s, String t) {
        int[] cnt = new int[128];
        int need = t.length(), cur = s.length();
        int l = 0;
        String ans = "";
        for (int i = 0; i < need; i++) {
            cnt[t.charAt(i)]++;
        }
        for (int r = 0; r < s.length(); r++) {
            if (cnt[s.charAt(r)] > 0) {
                need--;
            }
            cnt[s.charAt(r)]--;
            if (need == 0) {
                while (cnt[s.charAt(l)] != 0) {
                    cnt[s.charAt(l)]++;
                    l++;
                }
                if (r - l <= cur) {
                    cur = r - l;
                    ans = s.substring(l, r + 1);
                }
                cnt[s.charAt(l)]++;
                need++;
                l++;
            }
        }
        return ans;
    }
}

不同数组 ​

53. 最大子数组和 ​

56. 合并区间 ​

189. 旋转数组 ​

238. 除自身以外数组的乘积 ​

41. 缺失的第一个正数 ​

矩阵 ​

73. 矩阵置零 ​

54. 螺旋矩阵 ​

48. 旋转图像 ​

240. 搜索二维矩阵 II ​

链表 ​

160. 相交链表 ​

206. 反转链表 ​

234. 回文链表 ​

141. 环形链表 ​

142. 环形链表 II ​

21. 合并两个有序链表 ​

2. 两数相加 ​

19. 删除链表的倒数第 N 个节点 ​

24. 两两交换链表中的节点 ​

25. K 个一组翻转链表 ​

138. 复制带随机指针的链表 ​

148. 排序链表 ​

23. 合并 K 个升序链表 ​

146. LRU 缓存机制 ​

二叉树 ​

94. 二叉树的中序遍历 ​

104. 二叉树的最大深度 ​

226. 翻转二叉树 ​

101. 对称二叉树 ​

543. 二叉树的直径 ​

102. 二叉树的层序遍历 ​

108. 将有序数组转换为二叉搜索树 ​

98. 验证二叉搜索树 ​

230. 二叉搜索树中第 K 小的元素 ​

199. 二叉树的右视图 ​

114. 二叉树展开为链表 ​

105. 从前序与中序遍历序列构造二叉树 ​

437. 路径总和 III ​

236. 二叉树的最近公共祖先 ​

124. 二叉树中的最大路径和 ​

图论 ​

200. 岛屿数量 ​

994. 腐烂的橘子 ​

207. 课程表 ​

208. 实现 Trie (前缀树) ​

回溯 ​

46. 全排列 ​

78. 子集 ​

17. 电话号码的字母组合 ​

39. 组合总和 ​

22. 括号生成 ​

79. 单词搜索 ​

131. 分割回文串 ​

51. N 皇后 ​

二分查找 ​

35. 搜索插入位置 ​

74. 搜索二维矩阵 ​

34. 在排序数组中查找元素的第一个和最后一个位置 ​

33. 搜索旋转排序数组 ​

153. 寻找旋转排序数组中的最小值 ​

4. 寻找两个正序数组的中位数 ​

栈 ​

20. 有效的括号 ​

155. 最小栈 ​

394. 字符串解码 ​

739. 每日温度 ​

84. 柱状图中最大的矩形 ​

堆 ​

215. 数组中的第 K 个最大元素 ​

347. 前 K 个高频元素 ​

295. 数据流的中位数 ​

贪心 ​

121. 买卖股票的最佳时机 ​

55. 跳跃游戏 ​

45. 跳跃游戏 II ​

763. 划分字母区间 ​

动态规划 ​

70. 爬楼梯 ​

118. 杨辉三角 ​

198. 打家劫舍 ​

279. 完全平方数 ​

322. 零钱兑换 ​

139. 单词拆分 ​

300. 最长递增子序列 ​

152. 乘积最大子数组 ​

416. 分割等和子集 ​

32. 最长有效括号 ​

多维动态规划 ​

62. 不同路径 ​

64. 最小路径和 ​

5. 最长回文子串 ​

1143. 最长公共子序列 ​

72. 编辑距离 ​

技巧 ​

136. 只出现一次的数字 ​

169. 多数元素 ​

75. 颜色分类 ​

31. 下一个排列 ​

287. 寻找重复数 ​

Classic Algorithm ​

Sort ​

Data Structure ​

146. LRU 缓存机制 ​

双向链表存储数据状态，哈希表更新数据。

python
class Node:

    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.key_to_node = defaultdict(int)
        self.dummy = Node()
        self.dummy.prev = self.dummy
        self.dummy.next = self.dummy

    def get_node(self, key: int) -> Optional[Node]:
        if key not in self.key_to_node:
            return None
        node = self.key_to_node[key]
        self.remove(node)
        self.push_front(node)
        return node

    def get(self, key: int) -> int:
        node = self.get_node(key)
        return node.value if node else -1

    def put(self, key: int, value: int) -> None:
        node = self.get_node(key)
        if node:
            node.value = value
            return
        self.key_to_node[key] = node = Node(key, value)
        self.push_front(node)
        if len(self.key_to_node) > self.capacity:
            back_node = self.dummy.prev
            self.remove(back_node)
            del self.key_to_node[back_node.key]

    def remove(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def push_front(self, node: Node) -> None:
        node.prev = self.dummy
        node.next = self.dummy.next
        node.prev.next = node
        node.next.prev = node

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
java
class LRUCache {

    private static class Node {
        private int key, value;
        private Node prev, next;

        Node (int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Node dummy = new Node(0, 0);
    private final Map<Integer, Node> keyToNode = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.prev = dummy;
        dummy.next = dummy;
    }

    public int get(int key) {
        Node node = getNode(key);
        return node != null ? node.value: -1;
    }

    public void put(int key, int value) {
        Node node = getNode(key);
        if (node != null) {
            node.value = value;
            return;
        }
        node = new Node(key, value);
        keyToNode.put(key, node);
        pushFirst(node);
        if (keyToNode.size() > capacity) {
            Node backNode = dummy.prev;
            keyToNode.remove(backNode.key);
            remove(backNode);
        }
    }

    private Node getNode(int key) {
        if (!keyToNode.containsKey(key)) {
            return null;
        }
        Node node = keyToNode.get(key);
        remove(node);
        pushFirst(node);
        return node;
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void pushFirst(Node node) {
        node.prev = dummy;
        node.next = dummy.next;
        node.prev.next = node;
        node.next.prev = node;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

460. LFU 缓存 ​

双向链表存储数据状态，哈希表更新数据，不同频率的数据存储在不同的双向链表中。

python
class Node:

    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.freq = 1

class LFUCache:

    def __init__(self, capacity: int):
        def new_list():
            dummy = Node()
            dummy.prev = dummy
            dummy.next = dummy
            return dummy
        self.capacity = capacity
        self.key_to_node = defaultdict(int)
        self.freq_to_dummy = defaultdict(new_list)

    def get_node(self, key: int) -> Optional[Node]:
        if key not in self.key_to_node:
            return None
        node = self.key_to_node[key]
        self.remove(node)
        dummy = self.freq_to_dummy[node.freq]
        if dummy.prev == dummy:
            del self.freq_to_dummy[node.freq]
            if self.min_freq == node.freq:
                self.min_freq += 1
        node.freq += 1
        self.push_front(self.freq_to_dummy[node.freq], node)
        return node

    def get(self, key: int) -> int:
        node = self.get_node(key)
        return node.value if node else -1

    def put(self, key: int, value: int) -> None:
        node = self.get_node(key)
        if node:
            node.value = value
            return
        if len(self.key_to_node) == self.capacity:
            dummy = self.freq_to_dummy[self.min_freq]
            back_node = dummy.prev
            del self.key_to_node[back_node.key]
            self.remove(back_node)
            if dummy.prev == dummy:
                del self.freq_to_dummy[self.min_freq]
        self.key_to_node[key] = node = Node(key, value)
        self.min_freq = 1
        self.push_front(self.freq_to_dummy[self.min_freq], node)

    def remove(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def push_front(self, dummy: Node, node: Node) -> None:
        node.prev = dummy
        node.next = dummy.next
        node.prev.next = node
        node.next.prev = node

# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
java
class LFUCache {

    private static class Node {
        private int key, value, freq = 1;
        private Node prev, next;

        Node (int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<Integer, Node> keyToNode = new HashMap<>();
    private final Map<Integer, Node> freqToDummy = new HashMap<>();
    private int minFreq;

    public LFUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = getNode(key);
        return node != null ? node.value: -1;
    }

    public void put(int key, int value) {
        Node node = getNode(key);
        if (node != null) {
            node.value = value;
            return;
        }
        if (keyToNode.size() == capacity) {
            Node dummy = freqToDummy.get(minFreq);
            Node backNode = dummy.prev;
            keyToNode.remove(backNode.key);
            remove(backNode);
            if (dummy.prev == dummy) {
                freqToDummy.remove(minFreq);
            }
        }
        node = new Node(key, value);
        keyToNode.put(key, node);
        minFreq = 1;
        pushFirst(minFreq, node);
    }

    private Node getNode(int key) {
        if (!keyToNode.containsKey(key)) {
            return null;
        }
        Node node = keyToNode.get(key);
        remove(node);
        Node dummy = freqToDummy.get(node.freq);
        if (dummy.prev == dummy) {
            freqToDummy.remove(node.freq);
            if (minFreq == node.freq) {
                minFreq++;
            }
        }
        pushFirst(++node.freq, node);
        return node;
    }

    private Node newList() {
        Node dummy = new Node(0, 0);
        dummy.prev = dummy;
        dummy.next = dummy;
        return dummy;
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void pushFirst(int freq, Node node) {
        Node dummy = freqToDummy.computeIfAbsent(freq, k -> newList());
        node.prev = dummy;
        node.next = dummy.next;
        node.prev.next = node;
        node.next.prev = node;
    }

}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

1206. 设计跳表 ​

python
class SkiplistNode():

    def __init__(self, val: int, max_level=32):
        self.val = val
        self.forward = [None] * max_level

class Skiplist:

    max_level = 32
    p_factor = 0.5

    def __init__(self):
        self.head = SkiplistNode(-1)
        self.level = 0

    def random_level(self):
        level = 1
        while level < self.max_level and random.random() < self.p_factor:
            level += 1
        return level

    def search(self, target: int) -> bool:
        cur = self.head
        for i in range(self.level - 1, -1, -1):
            while cur.forward[i] and cur.forward[i].val < target:
                cur = cur.forward[i]
        cur = cur.forward[0]
        return cur is not None and cur.val == target

    def add(self, num: int) -> None:
        update = [self.head] * self.max_level
        cur = self.head
        for i in range(self.level - 1, -1, -1):
            while cur.forward[i] and cur.forward[i].val < num:
                cur = cur.forward[i]
            update[i] = cur

        level = self.random_level()
        self.level = max(self.level, level)
        node = SkiplistNode(num, level)

        for i in range(level):
            node.forward[i] = update[i].forward[i]
            update[i].forward[i] = node


    def erase(self, num: int) -> bool:
        update = [None] * self.max_level
        cur = self.head
        for i in range(self.level - 1, -1, -1):
            while cur.forward[i] and cur.forward[i].val < num:
                cur = cur.forward[i]
            update[i] = cur
        cur = cur.forward[0]

        if cur is None or cur.val != num:
            return False

        for i in range(self.level):
            if update[i].forward[i] != cur:
                break
            update[i].forward[i] = cur.forward[i]

        while self.level > 1 and self.head.forward[self.level - 1] is None:
            self.level -= 1
        return True


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)
java
class SkiplistNode {

    int val;
    SkiplistNode[] forward;

    public SkiplistNode(int val, int maxLevel) {
        this.val = val;
        this.forward = new SkiplistNode[maxLevel];
    }

}

class Skiplist {

    int level = 0;
    int maxLevel = 32;
    SkiplistNode head = new SkiplistNode(-1, maxLevel);

    private int randomLevel() {
        int lv = 1;
        Random random = new Random();
        while (lv < maxLevel && random.nextInt(2) == 0) {
            lv++;
        }
        return lv;
    }

    public boolean search(int target) {
        SkiplistNode cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.forward[i] != null && cur.forward[i].val < target) {
                cur = cur.forward[i];
            }
        }
        cur = cur.forward[0];
        return cur != null && cur.val == target;
    }

    public void add(int num) {
        SkiplistNode[] update = new SkiplistNode[maxLevel];
        SkiplistNode cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.forward[i] != null && cur.forward[i].val < num) {
                cur = cur.forward[i];
            }
            update[i] = cur;
        }

        int lv = randomLevel();
        if (lv > level) {
            for (int i = level; i < lv; i++) {
                update[i] = head;
            }
            level = lv;
        }

        SkiplistNode node = new SkiplistNode(num, lv);
        for (int i = 0; i < lv; i++) {
            node.forward[i] = update[i].forward[i];
            update[i].forward[i] = node;
        }
    }

    public boolean erase(int num) {
        SkiplistNode[] update = new SkiplistNode[maxLevel];
        SkiplistNode cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.forward[i] != null && cur.forward[i].val < num) {
                cur = cur.forward[i];
            }
            update[i] = cur;
        }
        cur = cur.forward[0];

        if (cur == null || cur.val != num) {
            return false;
        }

        for (int i = 0; i < level && update[i].forward[i] == cur; i++) {
            update[i].forward[i] = cur.forward[i];
        }

        while (level > 0 && head.forward[level - 1] == null) {
            level--;
        }
        return true;
    }
}

/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist obj = new Skiplist();
 * boolean param_1 = obj.search(target);
 * obj.add(num);
 * boolean param_3 = obj.erase(num);
 */

Other ​

  • 最长回文子串
  • lc40 组合总和 II
  • 给定一个字符数组，和一个字符串，在字符串里找到任意一个完全由字符数组组成的子串，字符顺序无所谓（滑动窗口）

笔试 ​

网易互娱（2025.3.22）

编程题（100，100，100），a了前两道

  1. 股票交易，N天，M只股票，初始资金K，交易次数不限制，股票数额可不为整数

    贪心，当天与次天比较，计算利润，排序后取利润最大的一只股票，买入卖出，不存在则空仓

  2. 实现2048游戏

    模拟，上下左右移动，合并相同的数字

  3. ax + by + cz + dw == k, 0 <= x, y, z, w, k <= 10 ** 9, 0 <= a, b, c, d <= 2500, 求系数的最小字典序组合

    哈希，预处理a，b，再枚举c，d，查找k - c _ z - d _ w是否存在，直接比较字典序

美团二笔（2025.3.22）

选择题30分，编程题70分（20, 20, 30） 编程题前两题a了，最后一道60%

  1. 镜像大写字母的回文串

    双指针，判断是否为镜像大写字母，判断是否为回文串

  2. 中位数位于奇数长度数组正中间的数组为好数组，求好数组的个数

    枚举中位数，左右两边的数的个数相等

  3. 青蛙从k开始按指令跳跃，'L’向左跳，'R’向右跳，'?'随机跳，求终点的可能位置，跃出边界时保持不变

    贪心，先执行’L’和’R’指令，并计算’?'的个数，枚举每个位置，条件判断是否能够到达

拼多多 (2025.3.23)

编程题（100，100，100，100），除了第二道暴力拿了40%，其他都a了

  1. 走迷宫，按照指令走，求最终位置是否为（0，0）

    模拟

  2. 给定左右边界，判断是否一个数的子串是3的倍数，求这种数的个数

    数论，鸽巢原理，长度超过3的子串必有3的倍数，子串前缀和可以解释，小于1000直接特判

  3. 给定一个数组，求每个位置能够观察到的元素个数之和

    单调栈，加入哨兵，从右往左

  4. 给定两个字符串，A和B，还有一个下标数组idx，A[idx[i]] = B[i]，B和idx中顺序随意调换，求字典序最小的A

    贪心，保留idx中不同的元素，idx和B排序，再次遍历idx，将B中对应的元素放入A中

bilibili (2025.3.23)

选择题40分，多选题15分，编程题45分（20，25） 第一道80%，第二道a了

  1. 给定数组，划分成k个子序列，求最大的子序列的最大差值的和

    双指针，贪心，排序后，每次取最大值和最小值

  2. 分水果m个，相邻元素差值不超过1，每个元素大于0，求下标k的最大值

    二分查找，数列求和判断是否大于m

Common Resources for Materials Calculation