刷穿力扣（hot100）

1. 两数之和

---

• 哈希表
  • 遍历数组，同时用 HashMap 维护已出现过的数及其下标
  • 若当前的数 nums[i] 满足 target - nums[i] 曾经出现过，则直接返回
  • 否则将其加入到哈希表中。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> st = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int t = target - nums[i];
            if (st.containsKey(t)) {
                return new int[] {i, st.get(t)};
            }
            st.put(nums[i], i);
        }
        return null;
    }
}

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> vis;
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++) {
            int t = target - nums[i];
            if (vis.find(t) != vis.end()) {
                ans.push_back(i);
                ans.push_back(vis[t]);
                return ans;
            } else {
                vis[nums[i]] = i;
            }
        }
        return ans;
    }
};

---

49. 字母异位词分组

---

• 哈希表
  • 遍历集合的 strs，对每个遍历到的字符串按照字典序进行排序
  • 因此具有相同的字典序的字符串是同一组的异位词
  • 利用哈希表用字典序映射对应组的下标
  • 每次遍历将排序后的字符串在哈希表中找到其所属组的映射，然后加入该组即可

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new ArrayList<>();
        HashMap<String, Integer> vis = new HashMap<>();
        int idx = 0;
        for (String str : strs) {
            char[] s = str.toCharArray();
            Arrays.sort(s);
            String st = new String(s);
            if (vis.containsKey(st)) {
                ans.get(vis.get(st)).add(str);
            } else {
                List<String> cnt = new ArrayList<>();
                cnt.add(str);
                ans.add(cnt);
                vis.put(st, idx++);
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        int idx = 0;
        map<string, int> vis;
        for (auto &p : strs) {
            string t = p;
            sort(t.begin(), t.end());
            if (vis.find(t) != vis.end()) {
                ans[vis[t]].push_back(p);
            } else {
                vector<string> st;
                st.push_back(p);
                ans.push_back(st);
                vis[t] = idx++;
            }
        }
        return ans;
    }
};

---

128. 最长连续序列

---

• 哈希
  • 用 Set 对原数组内元素去重
  • 遍历 Set，如果当前 num - 1 不存在于 Set 中，说明该 num 可能为连续序列的起始点
  • 则不断判断 num++ 是否存在于 Set，并更新最大长度

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> st = new HashSet<>();
        for (int num : nums) st.add(num);
        int ans = 0;
        for (int num : nums) {
            if (!st.contains(num - 1)) {
                int t = num;
                int cnt = 1;
                while (st.contains(t + 1)) {
                    t++;
                    cnt++;
                }
                ans = Math.max(cnt, ans);
            }
        }
        return ans;
    }
}

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        set<int> st;
        for (auto &p : nums) st.insert(p);
        int ans = 0;
        for (auto &p : st) {
            if (st.find(p - 1) == st.end()) {
                int t = p;
                int cnt = 1;
                while (st.find(t + 1) != st.end()) {
                    t++;
                    cnt++;
                }
                ans = max(cnt, ans);
            }
        }
        return ans;
    }
};

---

283. 移动零

• 双指针
  • 用 j 表示当前为 0 的位置，i 表示走到的不为 0 的位置
  • 如果 i 向后遍历到某个位置不为 0，则交换 nums[i] 和 nums[j]
  • 交换后，j++
  • 初始化 j = i = 0，即使 nums[j] != 0，交换后的 j++ 会后移到 0 的位置

class Solution {
    public void moveZeroes(int[] nums) {
        for (int i = 0, j = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
                j++;
            }
        }
    }
}

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for (int i = 0, j = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                swap(nums[i], nums[j]);
                j++;
            }
        }
    }
};

---

11. 盛最多水的容器

---

朴素版本：

• 模拟
  • 以 i 为左边界，j 为右边界，遍历取 ans 最大值
  • 若 height[i] * (j - i) < ans 说明 j 左移不存在比 ans 大的值，直接 break

class Solution {
    public int maxArea(int[] height) {
        int ans = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = height.length - 1; j > i; j--) {
                if (height[i] * (j - i) < ans) break;
                ans = Math.max(ans, Math.min(height[i], height[j]) * (j - i));
            }
        }
        return ans;
    }
}

优化：

• 双指针
  • 以 l 为左边界，r 为右边界
  • 取当 t = min(l, r)，则若（l 向右移存在 height[l] > t）或（r 向左移存在 height[r] > t）说明 ans 可能增大

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int l = 0, r = n - 1;
        int ans = Math.min(height[l], height[r]) * (r - l);
        while (l < r) {
            int t = Math.min(height[l], height[r]);
            while (l < r && height[l] <= t) l++;
            while (l < r && height[r] <= t) r--;
            ans = Math.max(ans, Math.min(height[r], height[l]) * (r - l));
        }
        return ans;
    }
}

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int l = 0, r = n - 1;
        int ans = min(height[l], height[r]) * (r - l);
        while (l < r) {
            int t = min(height[l], height[r]);
            while (l < r && height[l] <= t) l++;
            while (l < r && height[r] <= t) r--;
            ans = max(ans, min(height[l], height[r]) * (r - l));
        }
        return ans;
    }
};

---

15. 三数之和

---

• 双指针
  • 首先对 nums 从小到大排序，使得其从小到大单调
  • 遍历 nums[i]，对于每个 nums[i]，设 nums[i] 为三数之和中最小的数
  • 利用双指针在 nums[i] 的右侧区间寻找符合条件的两个数
  • 设左指针为 l = i + 1，右指针 r = nums.length - 1
  • 若 nums[i] + nums[l] + nums[r] > 0，说明 r 需要向左移动，否则 l 需要向右移动
  • 若 nums[i] + nums[l] + nums[r] == 0，说明是一个答案，需要记录
  • 特别地，当 nums[i] > 0 时，由于数组已排序，右侧元素均大于 0，三个正数相加不可能为 0，因此不存在答案
  • 注意，在记录答案后需要不断移动 i，l 和 r，对相同的值去重

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > 0) return ans;
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int t = nums[i] + nums[l] + nums[r];
                if (t < 0) l++;
                else if (t > 0) r--;
                else {
                    List<Integer> res = new ArrayList<>();
                    res.add(nums[i]);
                    res.add(nums[l]);
                    res.add(nums[r]);
                    ans.add(res);
                    while (l + 1 < r && nums[l] == nums[l + 1]) l++;
                    while (r - 1 > l && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                }
            }
            while (i + 1 < nums.length && nums[i] == nums[i + 1]) i++;
        }
        return ans;
    }
}

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) return ans;
            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                int t = nums[i] + nums[l] + nums[r];
                if (t > 0) r--;
                else if (t < 0) l++;
                else {
                    vector<int> res;
                    res.push_back(nums[i]);
                    res.push_back(nums[l]);
                    res.push_back(nums[r]);
                    ans.push_back(res);
                    while (l + 1 < r && nums[l] == nums[l + 1]) l++;
                    while (r - 1 > l && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                }
            }
            while (i + 1 < nums.size() && nums[i] == nums[i + 1]) i++;
        }
        return ans;
    }
};

---

42. 接雨水

---

• 双指针
  • 首先，用 idx 从左向右找到第一个不是 0 的位置，设其为蓄水池左边界
  • 设 i 为蓄水池右边界，i 不断向右移动，如果 height[i] >= height[idx]，说明后续的池子将以 height[i] 为左边界蓄水
  • 此时，需要更新 idx 到 i 之间接到的雨水，设当前左边界高度为 t = height[idx]，不断循环 ans += t - height[idx++]
  • 若 idx < height.length，说明存在某个位置 height[idx] 为最低点，导致后续蓄水池不再以此边界更新，因此需要倒着再来一遍

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int idx = 0;
        while (idx + 1 < height.length && height[idx] == 0) idx++;
        for (int i = idx; i < height.length; i++) {
            if (height[i] >= height[idx]) {
                int t = height[idx];
                while (idx < i) {
                    ans += t - height[idx++];
                }
            }
        }
        if (idx < height.length) {
            int r = height.length - 1;
            while (r - 1 > idx && height[r] == 0) r--;
            for (int i = r; i >= idx; i--) {
                if (height[i] >= height[r]) {
                    int t = height[r];
                    while (r > i) {
                        ans += t - height[r--];
                    }
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        int idx = 0;
        while (idx + 1 < height.size() && height[idx] == 0) idx++;
        for (int i = idx; i < height.size(); i++) {
            if (height[i] >= height[idx]) {
                int t = height[idx];
                while (idx < i) {
                    ans += t - height[idx++];
                }
            }
        }
        if (idx < height.size()) {
            int r = height.size() - 1;
            while (r - 1 > idx && height[r] == 0) r--;
            for (int i = r; i >= idx; i--) {
                if (height[i] >= height[r]) {
                    int t = height[r];
                    while (r > i) {
                        ans += t - height[r--];
                    }
                }
            }
        }
        return ans;
    }
};

---

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

---

• 滑动窗口
  • 设 vis 存储当前窗口中已经存在的元素
  • 令 j 为窗口的左边界，i 为窗口的右边界
  • 循环向右移动 i，每次都将 s.charAt(i) 加入 vis
  • 如果 vis 中在加入之前已经存在 s.charAt(i)，说明窗口中已经重复
  • 因此需要不断缩小左边界，直到将某个 s.charAt(j) == s.charAt(i) 移出窗口
  • 每次循环都要更新 vis 的最大长度即为答案

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() <= 1) return s.length();
        Set<Character> vis = new HashSet<>();
        int ans = 1;
        for (int i = 0, j = 0; i < s.length(); i++) {
            if (vis.contains(s.charAt(i))) {
                while (j <= i && vis.contains(s.charAt(i))) {
                    vis.remove(s.charAt(j++));
                }
            }
            vis.add(s.charAt(i));
            ans = Math.max(ans, vis.size());
        }
        return ans;
    }
}

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() <= 1) return s.size();
        int vis[200] = {0};
        int ans = 1;
        int idx = 0;
        for (int i = 0, j = 0; i < s.size(); i++) {
            if (vis[s[i]] == 1) {
                while (j <= i && vis[s[i]] == 1) {
                    vis[s[j++]]--;
                    idx--;
                }
            }
            vis[s[i]]++;
            idx++;
            ans = max(ans, idx);
        }
        return ans;
    }
};

---

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

---

• 滑动窗口
  • 首先，用 res 数组统计 p 中每个字符的数量
  • 设 j 为窗口的左边界，i 为窗口的右边界，用 vis 数组统计当前窗口中的每个字符数量
  • 让 i 不断向右移动，每次移动都使得 vis[s.charAt(i)]++
  • 如果 i - j + 1 > p.length() 说明窗口过大，需要收缩左边界，同时将窗口 vis 统计的左边界字符移除一个，即 vis[s.charAt(j++)]--;
  • 如果 i - j + 1 == p.length()，则需要判断窗口内包含的每个字符数量和 p 是否相等，即循环判断 vis 和 res 每个字符数量即可

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] res = new int[26];
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < p.length(); i++) {
            res[p.charAt(i) - 'a']++;
        }
        int[] vis = new int[26];
        for (int i = 0, j = 0; i < s.length(); i++) {
            vis[s.charAt(i) - 'a']++;
            if (i - j + 1 > p.length()) {
                vis[s.charAt(j++) - 'a']--;
            }
            if (i - j + 1 == p.length()) {
                int flag = 0;
                for (int k = 0; k < 26; k++) {
                    if (res[k] != vis[k]) {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0) ans.add(j);
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int res[26] = {0}, vis[26] = {0};
        vector<int> ans;
        for (auto op : p) res[op - 'a']++;
        for (int i = 0, j = 0; i < s.size(); i++) {
            vis[s[i] - 'a']++;
            if (i - j + 1 > p.size()) vis[s[j++] - 'a']--;
            if (i - j + 1 == p.size()) {
                bool flag = 1;
                for (int k = 0; k < 26; k++) {
                    if (vis[k] != res[k]) {
                        flag = 0;
                        break;
                    }
                }
                if (flag) ans.push_back(j);
            }
        }
        return ans;
    }
};

---

560. 和为 K 的子数组

---

• 前缀和
  • 遍历 nums，用 cnt += nums[i] 记录前 i 个元素的和及其数量
  • 判断之前是否已经存在前缀和的值为 cnt - k，若存在则说明存在连续的某个区间符合条件
  • 答案为这个值的前缀和数量相加

class Solution {
    public int subarraySum(int[] nums, int k) {
        int ans = 0, cnt = 0;
        HashMap<Integer, Integer> vis = new HashMap<>();
        vis.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            cnt += nums[i];
            if (vis.containsKey(cnt - k)) {
                ans += vis.get(cnt - k);
            }
            vis.put(cnt, vis.getOrDefault(cnt, 0) + 1);
        }
        return ans;
    }
}

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans = 0, cnt = 0;
        map<int, int> vis;
        vis[0] = 1;
        for (auto p : nums) {
            cnt += p;
            ans += vis[cnt - k];
            vis[cnt]++;
        }
        return ans;
    }
};

---

239. 滑动窗口最大值

---

• 优先队列
  • 利用优先队列存储当前窗口中的元素
  • 用 Pair 对值和下标排序，优先最大的值，其次最小的下标
  • 每次遍历，将窗口的右边界加入优先队列
  • while 检查优先队列的队头，将下标超出窗口范围的值出队
  • 队头元素即为当前窗口中的最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            return a[0] != b[0] ? b[0] - a[0] : b[1] - a[1];
        });
        for (int i = 0; i < k; i++) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; i++) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < k; i++) {
            pq.push({nums[i], i});
        }
        ans.push_back(pq.top().first);
        for (int i = k; i < nums.size(); i++) {
            pq.push({nums[i], i});
            while (pq.top().second <= i - k) {
                pq.pop();
            }
            ans.push_back(pq.top().first);
        }
        return ans;
    }
};

---

76. 最小覆盖子串

---

• 滑动窗口
  • 用 vis 数组记录 t 中每个字符的出现次数
  • 设 j 为当前窗口的左边界，i 为右边界
  • i 不断向右移动，用 res 记录当前子串 j ~ i 中每个字符的出现次数
  • 当 res 中左边界字符 s.charAt(j) 的数量大于 vis 中该字符的数量时，说明该字符在当前窗口中已超量，应收缩左边界 j 以尝试缩短子串
  • 判断符合题意的条件：res 中包含 vis 中所有字符，且每个字符的数量均不少于 vis 中的数量

class Solution {
    public String minWindow(String s, String t) {
        int[] vis = new int[128];
        for (int i = 0; i < t.length(); i++) vis[t.charAt(i)]++;
        int[] res = new int[128];
        String ans = "";
        for (int i = 0, j = 0; i < s.length(); i++) {
            res[s.charAt(i)]++;
            while (j < i && res[s.charAt(j)] > vis[s.charAt(j)]) {
                res[s.charAt(j)]--;
                j++;
            }
            boolean flag = true;
            for (int k = 0; k < 128; k++) {
                if (res[k] < vis[k]) {
                    flag = false;
                    break;
                }
            }
            if (flag && (ans.length() == 0 || ans.length() > i - j + 1)) {
                ans = s.substring(j, i + 1);
            }
        }
        return ans;
    }
}

class Solution {
public:
    string minWindow(string s, string t) {
        int vis[256] = {0};
        for (auto p : t) vis[p]++;
        int res[256] = {0};
        string ans = "";
        for (int i = 0, j = 0; i < s.size(); i++) {
            res[s[i]]++;
            while (res[s[j]] > vis[s[j]] && j <= i) res[s[j++]]--;
            bool flag = 1;
            for (int k = 'A'; k <= 'z'; k++) {
                if (res[k] < vis[k]) {
                    flag = 0;
                    break;
                }
            }
            if (flag) {
                if (ans == "" || ans.size() > i - j + 1) ans = s.substr(j, i - j + 1);
            }
        }
        return ans;
    }
};

---

53. 最大子数组和

---

• 前缀和
  • 和 560 的思路很像，用 cnt 记录 0 到当前位置的前缀和
  • 用 res 记录之前前缀和的最小值
  • 若使得连续的子数组和最大，则为 Math.max(ans, cnt - res)

class Solution {
    public int maxSubArray(int[] nums) {
        int res = 0;
        int ans = Integer.MIN_VALUE;
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            cnt += nums[i];
            ans = Math.max(ans, cnt - res);
            res = Math.min(cnt, res);
        }
        return ans;
    }
}

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = -0x3f3f3f3f;
        int res = 0;
        int cnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            cnt += nums[i];
            ans = max(ans, cnt - res);
            res = min(res, cnt);
        }
        return ans;
    }
};

---

56. 合并区间

---

• 区间合并板子题
  • 首先对每个子区间的左端点从小到大排序
  • 设正在合并中区间两端分别为 l 和 r，初始化为第一个区间的端点
  • 遍历排序后的区间，若 r >= intervals[i][0] 说明可以进行合并，更新 r = Math.max(r, intervals[i][1])
  • 否则说明无法继续向后合并，将当前区间 [l, r] 加入答案，重置 l = intervals[i][0], r = intervals[i][1]

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        List<int[]> ans = new ArrayList<>();
        int l = intervals[0][0], r = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (r >= intervals[i][0]) r = Math.max(r, intervals[i][1]);
            else {
                ans.add(new int[]{l, r});
                l = intervals[i][0];
                r = intervals[i][1];
            }
        }
        ans.add(new int[]{l, r});
        return ans.toArray(new int[ans.size()][]);
    }
}

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<pair<int, int>> st;
        for (auto p : intervals) st.push_back({p[0], p[1]});
        sort(st.begin(), st.end());
        vector<vector<int>> ans;
        int l = st[0].first, r = st[0].second;
        for (int i = 1; i < st.size(); i++) {
            if (r >= st[i].first) r = max(r, st[i].second);
            else {
                ans.push_back({l, r});
                l = st[i].first, r = st[i].second;
            }
        }
        ans.push_back({l, r});
        return ans;
    }
};

---

189. 轮转数组

---

• 模拟
  • 先翻转整个数组
  • 然后分别翻转 0 ~ k，和 k ~ nums.length 个元素

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length);
        reverse(nums, 0, k);
        reverse(nums, k, nums.length);
    }

    private void reverse(int[] nums, int l, int r) {
        r--;
        while (l < r) {
            int t = nums[l];
            nums[l++] = nums[r];
            nums[r--] = t;
        }
    }
}

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

---

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

---

• 前缀积
  • 对于每个 nums[i]，用 ans[i] 维护其左侧不包含 nums[i] 的元素的前缀积
  • 即，对于 ans[i]，表示为 nums[0] * nums[1] * ... * nums[i - 1]
  • 那么，以同样的方式反过来再求一遍后缀积，然后把后缀积和前缀积相乘即为答案
  • 对于后缀积，从 nums[nums.length - 2] 开始计算

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] ans = new int[nums.length];
        ans[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            ans[i] = ans[i - 1] * nums[i - 1];
        }
        int cnt = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            cnt *= nums[i + 1];
            ans[i] *= cnt;
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ans(nums.size());
        ans[0] = 1;
        for (int i = 1; i < nums.size(); i++) {
            ans[i] = ans[i - 1] * nums[i - 1];
        }
        int cnt = 1;
        for (int i = nums.size() - 2; i >= 0; i--) {
            cnt *= nums[i + 1];
            ans[i] *= cnt;
        }
        return ans;
    }
};

---

41. 缺失的第一个正数

---

• 模拟
  • 将数组本身视作哈希表
  • 首先遍历整个数组，将所有 nums[i] <= 0 和 nums[i] > n 的数变为 nums[i] = n + 1，因为超过范围的数一定不存在该哈希表中
  • 第二次遍历数组，对于 nums[i] 取其绝对值 t = Math.abs(nums[i])，如果 t <= n，说明这个值在哈希表中，将 nums[t - 1] 位置更新为 nums[t - 1] = -Math.abs(nums[t - 1])
  • 这样做的原因是：nums[i] 为负数，说明 i + 1 这个数存在过，但是 nums[i] 的绝对值对应的下标不变
  • 在第二次遍历完成后，出现过的数其数值下标的对应位置的值全部为负数，即对于 x 若出现过，则 nums[x - 1] < 0
  • 因此再次遍历数组，第一个找到的大于 0 的值的下标 i + 1 即为未出现过的第一个正数

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] > n || nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; i++) {
            int t = Math.abs(nums[i]);
            if (t <= n) {
                nums[t - 1] = -Math.abs(nums[t - 1]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] > n || nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; i++) {
            int t = abs(nums[i]);
            if (t <= n) {
                nums[t - 1] = -abs(nums[t - 1]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

---

73. 矩阵置零

---

• 哈希
  • 用两个 Set 分别存储需要置为 0 的横坐标和纵坐标
  • 之后分别遍历两个 Set，对其标记的坐标行和列循环置零即可

class Solution {
    public void setZeroes(int[][] matrix) {
        HashSet<Integer> x = new HashSet<>();
        HashSet<Integer> y = new HashSet<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    x.add(i);
                    y.add(j);
                }
            }
        }
        for (Integer p : x) {
            for (int j = 0; j < matrix[0].length; j++) matrix[p][j] = 0;
        }
        for (Integer p : y) {
            for (int i = 0; i < matrix.length; i++) matrix[i][p] = 0;
        }
    }
}

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        set<int> x, y;
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[i].size(); j++) {
                if (matrix[i][j] == 0) {
                    x.insert(i);
                    y.insert(j);
                }
            }
        }
        for (auto p : x) {
            for (int j = 0; j < matrix[0].size(); j++) matrix[p][j] = 0;
        }
        for (auto p : y) {
            for (int i = 0; i < matrix.size(); i++) matrix[i][p] = 0;
        }
    }
};

---

54. 螺旋矩阵

---

• 模拟
  • 偏移量数组，标记已经走过的位置
  • 每次移动判断是否在矩阵范围内，且没有走过
  • 否则改变方向，和偏移量数组的偏移值相照应

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        boolean[][] vis = new boolean[n][m];
        int[] dx = new int[]{0, 1, 0, -1}, dy = new int[]{1, 0, -1, 0};
        int l = 0, r = 0, dr = 0;
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n * m; i++) {
            ans.add(matrix[l][r]);
            vis[l][r] = true;
            int x = l + dx[dr], y = r + dy[dr];
            if (x < 0 || x >= n || y < 0 || y >= m || vis[x][y]) {
                dr = (dr + 1) % 4;
            }
            l += dx[dr];
            r += dy[dr];
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
        set<pair<int, int>> st;
        int dr = 0, n = matrix.size(), m = matrix[0].size();
        vector<int> ans;
        int l = 0, r = 0;
        for (int i = 0; i < n * m; i++) {
            ans.push_back(matrix[l][r]);
            st.insert({l, r});
            int x = l + dx[dr], y = r + dy[dr];
            if (x < 0 || x >= n || y < 0 || y >= m || st.find({x, y}) != st.end()) {
                dr = (dr + 1) % 4;
            }
            l += dx[dr], r += dy[dr];
        }
        return ans;
    }
};

• 矩阵转置
  • 用线性代数的知识，先将矩阵转置，再翻转即可
  • 将矩阵 \(A\) 的行换成同序数的列得到的新矩阵，叫做 \(A\) 的转置矩阵，记作 \(A^T\)
  • 转置运算公式：matrix[i][j] 与 matrix[j][i] 互换

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                swap(matrix[i][j], matrix[i][n - 1 - j]);
            }
        }
    }
};

---

240. 搜索二维矩阵 II

---

• 二分
  • 由于矩阵的每一行都是单调递增的
  • 因此遍历矩阵的每一行，逐行二分即可

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length, m = matrix[0].length;
        for (int i = 0; i < n; i++) {
            int l = 0, r = m - 1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (matrix[i][mid] == target) return true;
                if (matrix[i][mid] < target) l = mid + 1;
                else r = mid - 1;
            }
        }
        return false;
    }
}

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size(), m = matrix[0].size();
        for (int i = 0; i < n; i++) {
            int l = 0, r = m - 1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (matrix[i][mid] == target) return true;
                if (matrix[i][mid] < target) l = mid + 1;
                else r = mid - 1;
            }
        }
        return false;
    }
};

---

160. 相交链表

---

• 分别遍历两个链表
  • 若 a 先到达链表尾部，则使得 a = headB 开始重新遍历
  • 若 b 先到达链表尾部，则使得 b = headA 开始重新遍历
  • 当 a == b 时，说明要么两者遍历到了相交的节点，或者说明同时遍历到了链表的尾部节点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode a = headA, b = headB;
        while (a != b) {
            a = (a == null ? headB : a.next);
            b = (b == null ? headA : b.next);
        }
        return a;
    }
}

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) return nullptr;
        ListNode *a = headA, *b = headB;
        while (a != b) {
            a = (a == nullptr ? headB : a->next);
            b = (b == nullptr ? headA : b->next);
        }
        return a;
    }
};

---

206. 反转链表

---

• 设节点 r 为当前节点，其前一个节点为 l
  • 由于翻转后需要保留下一个需要翻转的节点的指向，因此用 t 暂存
  • 则翻转的过程为：
    • 令节点 t 指向 r 的后一个节点，即 t = r.next
    • 令当前节点指向它的前一个节点，即令 r 指向 l，r.next = l
  • 此时，当前节点已经翻转完成，需要将 l 和 r 向后移动，翻转下一个节点
  • 因此，需要对 l 和 r 进行更新：
    • 令 l 为下一个需要翻转的节点的前一个节点，即之前翻转过的节点 r，l = r
    • 令 r 为下一个需要翻转的节点，即 l 的下一个节点，r = t
  • 注意需要先更新 l 才能更新 r，否则 l 会丢失

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode l, r, t;
        l = null;
        r = head;
        while (r != null) {
            t = r.next;
            r.next = l;
            l = r;
            r = t;
        }
        return l;
    }
}

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *l, *r, *t;
        r = head, l = nullptr;
        while (r != nullptr) {
            t = r->next;
            r->next = l;
            l = r;
            r = t;
        }
        return l;
    }
};

---

234. 回文链表

---

• 首先找到链表中点
  • 将后半部分链表进行翻转
  • 同时遍历前后两端链表，判断对应的节点值是否相等

class Solution {
    public boolean isPalindrome(ListNode head) {
        int len = 0;
        for (ListNode i = head; i != null; i = i.next) len++;
        if (len == 1) return true;
        len = (len + 1) >> 1;
        ListNode l = head, r, t;
        for (int i = 0; i < len - 1; i++) l = l.next;
        r = l.next;
        l.next = null;
        while (r != null) {
            t = r.next;
            r.next = l;
            l = r;
            r = t;
        }
        ListNode p = head, q = l;
        for (int i = 0; i < len; i++) {
            if (p.val != q.val) return false;
            p = p.next;
            q = q.next;
        }
        return true;
    }
}

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        int len = 0;
        for (ListNode *i = head; i != nullptr; i = i->next) len++;
        if (len == 1) return true;
        len = (len + 1) >> 1;
        ListNode *l = head, *r, *t;
        for (int i = 0; i < len - 1; i++) l = l->next;
        r = l->next;
        l->next = nullptr;
        while (r != nullptr) {
            t = r->next;
            r->next = l;
            l = r;
            r = t;
        }
        ListNode *p = head, *q = l;
        for (int i = 0; i < len; i++) {
            if (p->val != q->val) return false;
            p = p->next, q = q->next;
        }
        return true;
    }
};

---

141. 环形链表

---

• 利用快慢指针进行判断
  • 令快指针每次移动两个单位，慢指针每次移动一个单位
  • 若链表存在环，则在慢指针进入到环进行循环时，一定能和快指针相遇

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode a = head, b = head.next;
        while (a != b) {
            if (b == null || b.next == null) return false;
            a = a.next;
            b = b.next.next;
        }
        return true;
    }
}

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) return false;
        ListNode *a = head, *b = head->next;
        while (a != b) {
            if (b == nullptr || b->next == nullptr) return false;
            a = a->next;
            b = b->next->next;
        }
        return true;
    }
};

---

142. 环形链表 II

---

• 哈希表
  • 存储所有已经遍历过的节点地址
  • 若遍历的过程中遇到已经遍历过的节点地址，说明该点就是环的起始节点

public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> st = new HashSet<>();
        for (ListNode i = head; i != null; i = i.next) {
            if (st.contains(i)) return i;
            else st.add(i);
        }
        return null;
    }
}

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode *> st;
        for (ListNode *i = head; i != nullptr; i = i->next) {
            if (st.find(i) != st.end()) return i;
            else st.insert(i);
        }
        return nullptr;
    }
};

---

21. 合并两个有序链表

---

• 链表合并板子
  • 同时循环遍历两个链表
  • 如果两个节点都存在，比较节点值的大小，将取值小的节点加入新链表，并使其指针后移
  • 否则有一方不存在，说明已经走到了链表的结尾，将剩下链表的值不断加入新链表即可

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode ans = new ListNode(0);
        ListNode head = ans;
        while (list1 != null || list2 != null) {
            if (list1 != null && list2 != null) {
                if (list1.val <= list2.val) {
                    ans.next = new ListNode(list1.val);
                    list1 = list1.next;
                } else {
                    ans.next = new ListNode(list2.val);
                    list2 = list2.next;
                }
                ans = ans.next;
            } else {
                if (list1 != null) {
                    ans.next = new ListNode(list1.val);
                    list1 = list1.next;
                    ans = ans.next;
                }
                if (list2 != null) {
                    ans.next = new ListNode(list2.val);
                    list2 = list2.next;
                    ans = ans.next;
                }
            }
        }
        return head.next;
    }
}

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *head = new ListNode(0);
        ListNode *ans = head;
        while (list1 != nullptr || list2 != nullptr) {
            if (list1 != nullptr && list2 != nullptr) {
                if (list1->val <= list2->val) {
                    head->next = new ListNode(list1->val);
                    head = head->next;
                    list1 = list1->next;
                } else {
                    head->next = new ListNode(list2->val);
                    head = head->next;
                    list2 = list2->next;
                }
            } else {
                if (list1 != nullptr) {
                    head->next = new ListNode(list1->val);
                    head = head->next;
                    list1 = list1->next;
                }
                if (list2 != nullptr) {
                    head->next = new ListNode(list2->val);
                    head = head->next;
                    list2 = list2->next;
                }
            }
        }
        return ans->next;
    }
};

---

2. 两数相加

---

• 大整数相加模板
  • 由于链表已经翻转过，因此答案也不需要再处理
  • 利用 base 存储进位，同时遍历两个链表
  • 如果两个节点的值都存在，则新链表的节点值为 (base + l1.val + l2.val) % 10，更新进位的值为 (base + l1.val + l2.val) / 10
  • 否则说明某个链表已经遍历完毕，将剩下的进位和剩余没有相加完的链表继续遍历相加完毕即可
  • 最后判断 base 是否还保留进位，如果有也要加上

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int base = 0;
        ListNode head = new ListNode(0);
        ListNode ans = head;
        while (l1 != null || l2 != null) {
            if (l1 != null && l2 != null) {
                int t = base + l1.val + l2.val;
                head.next = new ListNode(t % 10);
                head = head.next;
                l1 = l1.next;
                l2 = l2.next;
                base = t / 10;
            } else {
                if (l1 != null) {
                    int t = base + l1.val;
                    head.next = new ListNode(t % 10);
                    head = head.next;
                    l1 = l1.next;
                    base = t / 10;
                }
                if (l2 != null) {
                    int t = base + l2.val;
                    head.next = new ListNode(t % 10);
                    head = head.next;
                    l2 = l2.next;
                    base = t / 10;
                }
            }
        }
        if (base != 0) {
            head.next = new ListNode(base);
        }
        return ans.next;
    }
}

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0;
        ListNode *dummyHead = new ListNode(0);
        ListNode *current = dummyHead;
        while (l1 != nullptr || l2 != nullptr) {
            if (l1 != nullptr && l2 != nullptr) {
                int sum = carry + l1->val + l2->val;
                current->next = new ListNode(sum % 10);
                current = current->next;
                l1 = l1->next;
                l2 = l2->next;
                carry = sum / 10;
            } else {
                if (l1 != nullptr) {
                    int sum = carry + l1->val;
                    current->next = new ListNode(sum % 10);
                    current = current->next;
                    l1 = l1->next;
                    carry = sum / 10;
                }
                if (l2 != nullptr) {
                    int sum = carry + l2->val;
                    current->next = new ListNode(sum % 10);
                    current = current->next;
                    l2 = l2->next;
                    carry = sum / 10;
                }
            }
        }
        if (carry) {
            current->next = new ListNode(carry);
        }
        return dummyHead->next;
    }
};

---

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

---

• 双指针
  • 初始化两个指针 left 和 right，都指向虚拟头节点
  • 先让 right 指针向前移动 n 步
  • 然后同时移动 left 和 right，直到 right 指向链表末尾（nullptr）
  • 此时 left 指向的正是待删除节点的前一个节点
  • 删除操作：将 left.next 更新为 left.next.next

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode ans = new ListNode(0, head);
        ListNode l = ans, r = ans;
        for (int i = 0; i < n + 1; i++) r = r.next;
        while (r != null) {
            l = l.next;
            r = r.next;
        }
        l.next = l.next.next;
        return ans.next;
    }
}

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* ans = new ListNode(0, head);
        ListNode* l = ans, *r = ans;
        for (int i = 0; i < n + 1; i++) r = r->next;
        while (r != nullptr) {
            l = l->next;
            r = r->next;
        }
        l->next = l->next->next;
        return ans->next;
    }
};

---

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

---

• 模拟
  • 利用三个指针 t，l，r
  • 初始化 l 为 head，t 为 l 的前一个节点，r 为 l 的后一个节点
  • 交换的顺序为：
    1. 使 l 指向 r 的下一个节点，即 l.next = r.next
    2. 使 r 指向 l，即 t 指向的节点 r.next = t.next
    3. 使 t 指向交换后的节点 r，即 t.next = r
  • 之后需要向后移动三个指针：
    1. 先把 t 指向下一次需要交换的第一个节点之前，即 t = l
    2. 将 l 指向下一次需要交换的第一个节点，即 l = l.next
    3. 之后 r 指向 l 的后一个节点，r = l.next
  • 注意在更新 r 的指向时，需要先判断后一个节点是否存在

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode ans = new ListNode(0, head);
        ListNode l = head;
        if (l == null) return head;
        ListNode r = head.next, t = ans;
        while (r != null) {
            l.next = r.next;
            r.next = t.next;
            t.next = r;
            t = l;
            l = l.next;
            if (l == null) break;
            else r = l.next;
        }
        return ans.next;
    }
}

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *ans = new ListNode(0, head);
        ListNode *t = ans, *l = head;
        if (l == nullptr) return head;
        ListNode *r = l->next;
        while (r != nullptr) {
            l->next = r->next;
            r->next = t->next;
            t->next = r;
            t = l;
            l = l->next;
            if (l == nullptr) break;
            r = l->next;
        }
        return ans->next;
    }
};

---

25. K 个一组翻转链表

---

• 模拟
  • 首先判断是否存在连续的 k 长度的组
  • 若存在，则对组内的 k 个节点进行翻转即可

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode ans = new ListNode(0, head);
        ListNode t = ans, st = findNode(t, k);
        while (t.next != null && st.next != null) {
            ListNode l = t.next, r = st.next;
            for (int i = 0; i < k; i++) {
                ListNode temp = l.next;
                l.next = r;
                r = l;
                l = temp;
            }
            ListNode temp = t.next;
            t.next = r;
            temp.next = l;
            t = temp;
            st = findNode(t, k);
        }
        return ans.next;
    }

    private ListNode findNode(ListNode head, int k) {
        for (int i = 0; i < k - 1; i++) {
            if (head.next != null) head = head.next;
            else break;
        }
        return head;
    }
}

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* ans = new ListNode(0, head);
        ListNode* t = ans;
        ListNode* st = findNode(t, k);
        while (t->next != nullptr && st->next != nullptr) {
            ListNode* l = t->next;
            ListNode* r = st->next;
            for (int i = 0; i < k; i++) {
                ListNode* temp = l->next;
                l->next = r;
                r = l;
                l = temp;
            }
            ListNode* temp = t->next;
            t->next = r;
            temp->next = l;
            t = temp;
            st = findNode(t, k);
        }
        return ans->next;
    }

private:
    ListNode* findNode(ListNode* head, int k) {
        for (int i = 0; i < k - 1; i++) {
            if (head->next != nullptr)
                head = head->next;
            else
                break;
        }
        return head;
    }
};

---

138. 随机链表的复制

---

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> visited = new HashMap<>();
        for (Node i = head; i != null; i = i.next) {
            visited.put(i, new Node(i.val));
        }
        Node dummy = new Node(0);
        Node current = dummy;
        for (Node i = head; i != null; i = i.next) {
            current.next = visited.get(i);
            current.next.next = visited.get(i.next);
            current.next.random = visited.get(i.random);
            current = current.next;
        }
        return dummy.next;
    }
}

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> visited;
        for (Node* i = head; i != nullptr; i = i->next) {
            Node* node = new Node(i->val);
            visited[i] = node;
        }
        Node* dummy = new Node(0);
        Node* current = dummy;
        for (Node* i = head; i != nullptr; i = i->next) {
            current->next = visited[i];
            current->next->next = visited[i->next];
            current->next->random = visited[i->random];
            current = current->next;
        }
        return dummy->next;
    }
};

---

148. 排序链表

---

• 将链表的节点值拷贝到数组中
  • 对数组排序后，将节点值重新赋予即可

class Solution {
    public ListNode sortList(ListNode head) {
        List<Integer> num = new ArrayList<>();
        for (ListNode i = head; i != null; i = i.next) {
            num.add(i.val);
        }
        Collections.sort(num);
        int idx = 0;
        for (ListNode i = head; i != null; i = i.next) {
            i.val = num.get(idx++);
        }
        return head;
    }
}

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        vector<int> num;
        for (ListNode* i = head; i != nullptr; i = i->next) {
            num.push_back(i->val);
        }
        sort(num.begin(), num.end());
        int idx = 0;
        for (ListNode* i = head; i != nullptr; i = i->next) {
            i->val = num[idx++];
        }
        return head;
    }
};

---

23. 合并 K 个升序链表

---

• 将链表的节点值拷贝到数组中
  • 对数组排序后，将节点值重新赋予即可

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> num = new ArrayList<>();
        for (int i = 0; i < lists.length; i++) {
            for (ListNode j = lists[i]; j != null; j = j.next) {
                num.add(j.val);
            }
        }
        Collections.sort(num);
        ListNode ans = new ListNode(0);
        ListNode st = ans;
        for (int i = 0; i < num.size(); i++) {
            st.next = new ListNode(num.get(i));
            st = st.next;
        }
        return ans.next;
    }
}

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<int> num;
        for (auto p : lists) {
            for (auto q = p; q != nullptr; q = q->next) {
                num.push_back(q->val);
            }
        }
        ListNode* ans = new ListNode(0);
        ListNode* st = ans;