Atopos's Blog

One step at a time!

0%

LeetCode Hot100

发表于 更新于 分类于
本文字数： 29k 阅读时长 ≈ 27 分钟
LeetCode Hot100

题目一：两数之和

两数之和

标签

数组、哈希表

题解

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        for(int i = 0; i < nums.length; i ++) {
            for(int j = i + 1; j < nums.length; j ++) {
                if(nums[i] + nums[j] == target) 
                    return new int[]{i, j};
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> arr;
        for(int i=0;i < nums.size() - 1; i++){
            for(int j = i + 1;j< nums.size(); j++){
                if(nums[i]+nums[j] == target){
                    arr.push_back(i);
                    arr.push_back(j);
                    break;
                }
            }
        }
        return arr;
    }
};

题目二：两数相加

两数相加

标签

递归、链表、数学

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l3 = new ListNode(-1, null);
        ListNode a = l3;
        ListNode q = l1;
        ListNode p = l2;
        int t = 0;  // 保存进位
        while(q != null && p != null) {
            int x = q.val + p.val + t;
            t = x / 10;
            a.next = new ListNode(x % 10, null);
            a = a.next;
            q = q.next;
            p = p.next;
        }
        while(q != null) {
            int x = q.val + t;
            t = x / 10;
            a.next = new ListNode(x % 10, null);
            a = a.next;
            q = q.next;
        }
        while(p != null) {
            int x = p.val + t;
            t = x / 10;
            a.next = new ListNode(x % 10, null);
            a = a.next;
            p = p.next;
        }
        if(t != 0) a.next = new ListNode(t, null);
        return l3.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        auto dummy = new ListNode(-1);//生成一个新的头节点，指向结果
        auto cur = dummy; //一个指针，指向结果链表的尾节点
        int t = 0;//用来保存进位
        while(l1 || l2 || t){
            if(l1) t += l1 -> val, l1 = l1 -> next;
            if(l2) t += l2 -> val, l2 = l2 -> next;
            cur -> next = new ListNode(t % 10);//取出个位加入生成新节点
            cur = cur -> next; //更新尾指针
            t /= 10;  //去除进位
        }
        return dummy -> next;
    }
};

题目三：无重复字符的最长子串

无重复字符的最长子串

标签

哈希表、字符串、滑动窗口

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.equals("")) return 0;
        Set<Character> hashSet = new HashSet<>();
        int l = 0, r = 0;
        int ans = 0;
        hashSet.add(s.charAt(0));
        for(int i = 1; i < s.length(); i ++) {
            if(!hashSet.contains(s.charAt(i))) {  // 当前元素不存在
                hashSet.add(s.charAt(i));
                r ++;
            } else {
                ans = Math.max(ans, hashSet.size());
                while(!hashSet.isEmpty() && hashSet.contains(s.charAt(i))) { // 存在，一直出
                    hashSet.remove(s.charAt(l ++));
                }
                hashSet.add(s.charAt(i));
                r ++;
            }
        }
        ans = Math.max(ans, hashSet.size());
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> head;
        int res = 0;
        // 挨个遍历，将结果存入haspmap中，若出现重复，则依次退出直至重复的数也推出
        // 例如  出现   abcdefc ,遍历到第二个c时，出现重复，则j从0开始，也就是从字符a开始退出（j++）,直到退出至第一个c为之，则队列中不在出现重复。
        for(int i = 0, j = 0; i < s.length(); i ++){
            head[s[i]]++;
            while(head[s[i]] > 1) head[s[j++]]--;
            res = max(res, i - j + 1);
        }
        return res;
    }
};

题目四：寻找两个正序数组的中位数

寻找两个正序数组的中位数

标签

数组、二分查找、分治

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[] nums = new int[n + m];
        System.arraycopy(nums1, 0, nums, 0, n);
        System.arraycopy(nums2, 0, nums, n, m);
        Arrays.sort(nums);
        if((n + m) % 2 != 0) {  // 奇数
            return nums[(n + m) / 2];
        } else {
            return ((double) nums[(n + m) / 2] + (double) nums[(n + m) / 2 - 1]) / 2;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<double> arr;
        int i=0,j=0;
        while(i < nums1.size() && j < nums2.size()){
            if(nums1[i] <= nums2[j])
                arr.push_back(nums1[i++]);
            else
                arr.push_back(nums2[j++]);
        }
        while(i < nums1.size()) arr.push_back(nums1[i++]);
        while(j < nums2.size()) arr.push_back(nums2[j++]);
        
        int len = arr.size();
        for(int k = 0; k<arr.size();k++) cout<<arr[k]<<" ";
        if(len % 2 != 0){
            return arr[len / 2];
        }
        else{
            return (arr[len / 2] + arr[len / 2 - 1]) / 2;
        }
    }
};

知识点

System.arraycopy(srcArr, srcStartIndex, dstArr, dstStartIndex, length)函数：

  • 第一个参数：源数组
  • 第二个参数：在源数组中，被复制的数字开始复制的下标
  • 第三个参数：目标数组
  • 第四个参数：在目标数组中，从第几个下标开始放入复制的数据
  • 第五个参数：从源数组中，一共拿几个数值放到目标数组中。

例如：System.arraycopy(nums2, 0, nums, n, m);是从nums2数组中的下标为 0 的位置开始复制，复制到nums数组中从下标为n开始的位置，复制长度为m

题目五：最长回文串

最长回文串

标签

字符串、动态规划

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public String longestPalindrome(String s) {
        // 遍历回文串中间的数字
        int x = 0, y = 0;
        for(int i = 0; i < s.length(); i ++) {
            int l = i - 1, r = i + 1;
            while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
                l --;
                r ++;
            }
            if(y - x + 1 < r - l + 1) {
                x = l; y = r;
            }

            l = i; r = i + 1;
            while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
                l --;
                r ++;
            }
             if(y - x + 1 < r - l + 1) {
                x = l; y = r;
             }
        }
        System.out.println(x + " " + y);
        return s.substring(x + 1, y);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        for(int i=0;i<s.size();i++){
            int l = i - 1, r = i + 1;//回文串为偶数个的情况
            while(l >= 0 && r <= s.size() && s[l] == s[r]) l --, r ++;
            if(res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);

            l = i, r = i + 1; //回文串为奇数个的情况
            while(l >= 0 && r <= s.size() && s[l] == s[r]) l --, r ++;
            if(res.size() < r - l -1) res = s.substr(l + 1, r - l -1);
        }
        return res;
    }
};

题目六：正则表达式匹配❗

正则表达式匹配

标签

递归、字符串、动态规划

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        // dp[i][j]表示s的前i个字符和p的前j个字符是否能够匹配成功
        boolean[][] dp = new boolean[m + 1][n + 1];  
        dp[0][0] = true;
        for(int i = 0; i <= m; i ++) {
            for(int j = 1; j <= n; j ++) {
                // 需要注意，dp数组为前j个字符，实际应该是p字符串的j-1位
                if(p.charAt(j - 1) != '*') {  // 如果p[j - 1] 不是*
                    if(matches(s, p, i, j)) { // 如果p[j - 1] =='.' 或者p[j - 1] == s[i - 1] 
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                    // 否则直接为false
                } else {  // 如果p[j - 1] == '*'
                    dp[i][j] = dp[i][j - 2]; // *不匹配任何东西
                    if(matches(s, p, i, j - 1)) { // 如果p[j - 2] == '.' 或者p[j - 2] == s[i - 1],例如：s: a  p: a*/.*
                        dp[i][j] = dp[i - 1][j] || dp[i][j];
                    }
                }
            }
        }
        return dp[m][n];
    }

    /*
     * 判断字符串s的第i个位置和字符串p的第j个位置是否相等
     */
    public boolean matches(String s, String p, int i, int j) {
        if(i == 0) return false;
        if(p.charAt(j - 1) == '.') return true;
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    bool matches(string s, string p, int i, int j){
        if(i == 0) return false;
        if(p[j - 1] == '.') return true;
        return s[i - 1] == p[j - 1];
    }

    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();

        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[0][0] = true;
        for(int i = 0; i <= m; i ++) {
            for(int j = 1; j <= n; j ++) {
                if(p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2];
                    if(matches(s, p, i, j - 1)) {
                        dp[i][j] |= dp[i - 1][j];
                    }
                }
                else {
                    if(matches(s, p, i, j)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }
        return dp[m][n];
    }
};

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
以一个例子详解动态规划转移方程：
S = abbbbc
P = ab*d*c
1. 当 i, j 指向的字符均为字母（或 '.' 可以看成一个特殊的字母）时，
   只需判断对应位置的字符即可，
   若相等，只需判断 i,j 之前的字符串是否匹配即可，转化为子问题 f[i-1][j-1].
   若不等，则当前的 i,j 肯定不能匹配，为 false.
   
       f[i-1][j-1]   i
            |        |
   S [a  b  b  b  b][c] 
   
   P [a  b  *  d  *][c]
                     |
                     j
   

2. 如果当前 j 指向的字符为 '*'，则不妨把类似 'a*', 'b*' 等的当成整体看待。
   看下面的例子

            i
            |
   S  a  b [b] b  b  c  
   
   P  a [b  *] d  *  c
            |
            j
   
   注意到当 'b*' 匹配完 'b' 之后，它仍然可以继续发挥作用。
   因此可以只把 i 前移一位，而不丢弃 'b*', 转化为子问题 f[i-1][j]:
   
         i
         | <--
   S  a [b] b  b  b  c  
   
   P  a [b  *] d  *  c
            |
            j
   
   另外，也可以选择让 'b*' 不再进行匹配，把 'b*' 丢弃。
   转化为子问题 f[i][j-2]:

            i
            |
   S  a  b [b] b  b  c  
    
   P [a] b  *  d  *  c
      |
      j <--

3. 冗余的状态转移不会影响答案，
   因为当 j 指向 'b*' 中的 'b' 时, 这个状态对于答案是没有用的,
   原因参见评论区 稳中求胜 的解释, 当 j 指向 '*' 时,
   dp[i][j]只与dp[i][j-2]有关, 跳过了 dp[i][j-1].

状态表示：dp[i][j]表示字符串s的前i个字符和字符串p的前j个字符是否匹配。其中对应的是字符串s的第i-1个字符，和字符串p的第j-1个字符

状态转移：

  • 如果 p[j - 1] != '*'：
    • 如果p[j - 1] == '.' || p[j - 1] == s[i - 1]：则dp[i][j] = dp[i - 1][j - 1]
    • 否则：dp[i][j] = false
  • 如果 p[j - 1] == '*'：
    • dp[i][j] = dp[i][j - 2]，代表 * 不匹配任何字符
    • 如果p[j - 2] == '.' || p[j - 2] == s[i - 1]：则dp[i][j] = dp[i - 1][j] || dp[i][j - 2]

知识点

C++中定义二维容器vector时指定大小的方法：vector<vector<int>> arr(m, vector<int>(n))，定义了一个m行n列的容器

题目七：盛最多水的容器⭐

盛最多水的容器

标签

贪心、数组、双指针

题解

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int res = 0;
        while(l < r) {
            res = Math.max(res, Math.min(height[l], height[r]) * (r - l));
            if(height[l] < height[r]) l ++;
            else r --;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        int len = height.size();
        for(int i = 0, j = len - 1; i < j;){
            res = max(res, min(height[i], height[j]) * (j - i));
            if(height[i] > height[j]) j--;
            else i++;
        }
        return res;
    }
};

题目八：三数之和

三数之和

标签

数组、双指针、排序

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length < 3) return res;
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 2; i ++) {
            if(i == 0 || i != 0 && nums[i] != nums[i - 1]){
                
                int l = i + 1, r = nums.length - 1;
                while(l < r) {
                    if(nums[i] + nums[l] + nums[r] == 0) {
                        List<Integer> arr = new ArrayList<>();
                        arr.add(nums[i]);
                        arr.add(nums[l]);
                        arr.add(nums[r]);
                        res.add(arr);
                        boolean flag = false;
                        for(int k = l + 1; k < r; k ++) {
                            if(nums[k] != nums[l]) {
                                l = k;
                                flag = true;
                                break;
                            }
                        }
                        if(!flag) break;
                    }
                    if(nums[i] + nums[l] + nums[r] > 0) r --;
                    else l ++;
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.size() < 3 ) return res;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size() - 2; i ++){
            if(i ==0 || i != 0 && nums[i] != nums[i - 1]){
                cout << i << endl;
                int a = 0 - nums[i];
                int l = i + 1, r = nums.size() - 1;
                while(l < r) {
                    if(nums[l] + nums[r] < a){
                        l ++;
                    }
                    else if(nums[l] + nums[r] > a){
                        r --;
                    }
                    else {
                        cout << i << endl;
                        vector<int> arr;
                        arr.push_back(nums[i]);
                        arr.push_back(nums[l]);
                        arr.push_back(nums[r]);
                        res.push_back(arr);
                        bool flag = false;
                        for(int k = l + 1; k < r; k++){ // 往后找到第一个不和左边界相等的点。
                            if(nums[k] != nums[l]){
                                l = k;
                                flag = true;
                                break;
                            }
                        }
                        if(!flag) break;  //找到右边界仍然没有找到。
                    }
                }
            }
        }
        return res;
    }
};

题目九：电话号码的字母组合

电话号码的字母组合

标签

哈希表、字符串、回溯

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    List<String> res = new LinkedList<>();
    String[] strs = new String[]{
        "", "abc", "def",
        "ghi", "jkl", "mno",
        "pqrs", "tuv", "wxyz"
    };
    public void dfs(String digits, int len, StringBuilder path) {
        if(len >= digits.length()) res.add(path.toString());
        else {
            int x = digits.charAt(len) - '0' - 1;
            for(char str : strs[x].toCharArray()) {
                dfs(digits, len + 1, path.append(str));
                path.deleteCharAt(path.length() - 1);
            }
            
        }
    }

    public List<String> letterCombinations(String digits) {
        if("".equals(digits)) return res;
        StringBuilder path = new StringBuilder();
        dfs(digits, 0, path);
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<string> ans;
    string str[10] = {
        "", "", "abc",
        "def", "ghi", "jkl",
        "mno", "pqrs", "tuv", "wxyz",
    };
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) return ans;
        dfs(digits, 0, "");
        return ans;
    }

    void dfs(string& digits, int u, string path){
        if(u >= digits.size()) ans.push_back(path);
        else{
            int t = digits[u] - '0';
            for(auto c : str[t]){
                dfs(digits, u + 1, path + c);
            }
        }
    }
};

题目十：删除链表的倒数第N个节点

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

标签

链表、双指针

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int len = 0;
        ListNode p = head;
        while(p != null) {
            p = p.next;
            len ++;
        }
        n = len - n;
        if(n == 0) head = head.next;  // 删除的是头节点
        else {  // 删除的是其他节点，找到需要删除节点的前一节点即可
            p = head;
            n --;
            while(n != 0){
                p = p.next;
                n --;
            }
            p.next = p.next.next;
        }
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *p = head;
        int num = 0;
        while(p){
            num ++;
            p = p ->next;
        }
        int x = num - n;
        p = head;
        ListNode *q = head;
        if(x == 0){
            head = p ->next;
        }else{
            while(x --){
                q = p;
                p = p->next;
            }
            q->next = p->next;
        }
        
        return head;
    }
};

题目十一：有效的括号

有效的括号

标签

栈、字符串

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isValid(String s) {
        if(s.length() == 1) return false;
        Stack<Character> stk = new Stack<>();

        for(int i = 0; i < s.length(); i ++) {
            char ch = s.charAt(i);
            if(ch == '(' || ch == '{' || ch == '[') stk.push(ch);
            else if(stk.empty() != true && ch == ')' && stk.peek() == '(') stk.pop();
            else if(stk.empty() != true && ch == '}' && stk.peek() == '{') stk.pop();
            else if(stk.empty() != true && ch == ']' && stk.peek() == '[') stk.pop();
            else {
                return false;
            }
        }
        return stk.empty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    bool isValid(string s) {
        stack<char> sta;
        if(s.size()==1){
            return false;
        }
        for(int i=0;i<s.size();i++){
            if(s[i] == '(' || s[i] == '[' || s[i] == '{'){ //匹配到左括号
                sta.push(s[i]);
            }else if(sta.size()!=0){  //栈内有左括号
                char c = sta.top();
                sta.pop();
                if(c == '[' && s[i] == ']' || c == '{' && s[i] == '}' || c == '(' && s[i] == ')'){
                    continue;
                }else{
                    return false;
                }
            }else if(sta.size()==0){  //栈内已经没有左括号了，但是来了右括号。
                return false;
            }
        }
        if(sta.size()!=0){ // 还有左括号未匹配
            return false;
        }
        return true;
    }
};

题目十二：合并两个有序链表

合并两个有序链表

标签

递归、链表

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        else if(list2 == null) return list1;
        else if(list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }
        else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *list = new ListNode(-1);
        ListNode *head = list;
        ListNode *p = list1;
        ListNode *q = list2;
        while(p && q){
            if(p -> val <= q -> val){
                ListNode *x = new ListNode(p->val);
                head->next = x;
                head = head->next;
                p = p->next;
            }
            else {
                ListNode *x = new ListNode(q->val);
                head->next = x;
                head = head->next;
                q = q->next;
            }
        }
        while(p){
            ListNode *x = new ListNode(p->val);
            head->next = x;
            head = head->next;
            p = p->next;
        }
        while(q){
            ListNode *x = new ListNode(q->val);
            head->next = x;
            head = head->next;
            q = q->next;
        }
        return list->next;
    }
};

题目十三：括号生成⭐

括号生成

标签

字符串、动态规划、回溯

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    List<String> res = new LinkedList<>();
    public void dfs(int n, int l, int r, StringBuilder str) {
        if(r == n && l == n) {
            res.add(str.toString());
            return ;
        }
        if(l < n) {
            dfs(n, l + 1, r, str.append("("));
            str.deleteCharAt(str.length() - 1);
        }
        if(r < n && r < l) {
            dfs(n, l, r + 1, str.append(")"));
            str.deleteCharAt(str.length() - 1);
        }
    }
    public List<String> generateParenthesis(int n) {
        StringBuilder str = new StringBuilder();
        dfs(n, 0, 0, str);
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<string> res;
    
    void dfs(string str, int lc, int rc, int n){
        if(lc == n && rc == n) res.push_back(str);
        else{
            if(lc < n) dfs(str + "(", lc + 1, rc, n);
            if(rc < n && lc > rc) dfs(str + ")", lc, rc + 1, n);
        }
    }


    vector<string> generateParenthesis(int n) {
        dfs("", 0, 0, n);
        return res;
    }
};

题目十四：合并K个升序链表❗

合并K个升序链表

标签

链表、分治、堆（优先队列）、归并排序

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    // 进行分治
    public ListNode merge(ListNode[] lists, int l, int r) {
        if(l == r) return lists[l];
        else if(l > r) return null;
        int mid = (l + r) >> 1;
        // 向下一直划分，直到最后两个两个一组
        return mergeTwoList(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    // 基础的两个有序链表合并
    public ListNode mergeTwoList(ListNode l1, ListNode l2){
        if(l1 == null) return l2;
        else if(l2 == null) return l1;
        else if(l1.val < l2.val) {
            l1.next = mergeTwoList(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoList(l1, l2.next);
            return l2;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }

    ListNode* merge(vector<ListNode*> &lists, int l, int r) {
        if(l == r) return lists[l];
        else if(l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoList(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeTwoList(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr) return l2;
        else if(l2 == nullptr) return l1;
        else if(l1->val < l2->val) {
            l1->next = mergeTwoList(l1->next, l2);
            return l1;
        }
        else {
            l2->next = mergeTwoList(l1, l2->next);
            return l2;
        }
    }
};

题目十五：下一个排列❗

下一个排列

标签

数组、双指针

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public void nextPermutation(int[] nums) {
        int l = -1, r = 0;
        // 寻找较小的数
        for(int i = nums.length - 2; i >= 0; i --) {
            if(nums[i] < nums[i + 1]) {
                l = i;
                break;
            }
        }
        if(l != -1) {
            // 寻找较大的数
            for(int i = nums.length - 1; i > l; i --) {
                if(nums[i] > nums[l]) {
                    r = i;
                    break;
                }
            }
            // 交换较大的数和较小的数
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
        }
        // 将较小的数后面的元素倒置
        for(int i = l + 1, j = nums.length - 1; i < j; i ++, j --) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int l = -1, r = 0;
        // 从后往前找第一满足nums[i] < nums[i + 1] 的位置，则nums[i]为较小的数
        for(int i = nums.size() - 2; i >= 0; i --) {
            if(nums[i] < nums[i + 1]) {
                l = i;
                break;
            }
        } 
        // 若l == -1,则表示当前数组是从大到小排列的，直接倒置数组即可
        if(l != -1) {
            // 从后往前找第一个满足nums[i] > nums[l] 的位置，则nums[i]为较大的数
            for(int i = nums.size() - 1; i > l; i --) {
                if(nums[i] > nums[l]) {
                    r = i;
                    break;
                }
            }
            // 交换较小的数和较大的数
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
        }
        // 将从[l + 1, n - 1]的数倒置
        for(int i = l + 1, j = nums.size() - 1; i < j; i ++, j --) {
            swap(nums[i], nums[j]);
        }
    }
};

思路

对于长度为n的排列a：

  1. 首先从后向前查找第一个顺序对(i, i + 1)，满足a[i] < a[i + 1]。这样【较小数】即为a[i]。此时[i + 1, n)必然是下降序列。
  2. 如果找到了顺序对，那么在区间[i + 1, n)中从后向前查找第一个元素j满足a[i] < a[j]。这样【较大数】即为a[j]。
  3. 交换a[i]与a[j]，此时可以证明区间[i + 1, n)必为降序。我们可以直接使用双指针反转区间[i + 1, n)使其变为升序，而无需对该区间进行排序。

题目十六：最长有效括号❗

最长有效括号

标签

栈、字符串、动态规划

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length();
        int[] dp = new int[len + 1];  // dp[i]表示以下标i为结尾的最长有效括号子串长度
        dp[0] = 0;
        for(int i = 1; i < s.length(); i ++) {
            if(s.charAt(i) == '(') dp[i] = 0;  //
            else { // 当前字符是)
                if(s.charAt(i - 1) == '(') { // 前一个字符是左括号
                    dp[i] = dp[i - 1] + 2;
                    if(i - 2 >= 0) dp[i] += dp[i - 2]; // 判断两个括号是不是并列
                }
                else {  // 前一个字符是右括号
                    int x = dp[i - 1];
                    if(x == 0 || i - x - 1 < 0) dp[i] = 0; // 以前一个字符结尾的最长有效子串长度是0
                    else if(s.charAt(i - x - 1) == '(') {
                        dp[i] = dp[i - 1] + 2;
                        if(i - x - 2 >= 0) dp[i] += dp[i - x - 2]; 
                    }
                }
            }
        }
        int maxRes = 0;
        for(int i = 0; i < s.length(); i ++) {
            System.out.println(dp[i]);
            maxRes = Math.max(maxRes, dp[i]);
        }
        return maxRes;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int longestValidParentheses(string s) {
        int len = s.size();
        int dp[30010]{0};  // 不初始化，提交代码会出错，但是运行测试代码不会出错
        dp[0] = 0;
        for(int i = 1; i < s.size(); i ++) {
            if(s[i] == '(') dp[i] = 0;  // 当前字符是 (
            else {  // 当前字符是 ) 
                if(s[i - 1] == '(') {  // 前一字符是 (
                    dp[i] = dp[i - 1] + 2;
                    if(i - 2 >= 0) dp[i] += dp[i - 2]; // 考虑前面是否存在并列有效括号
                } 
                else {  // 前一字符是 )
                    int x = dp[i - 1];
                    if(x == 0 || i - x - 1 < 0)  // 以前一字符结尾的有效括号的最长长度是0 || 没有与当前字符对应的  (
                        dp[i] = 0;
                    else if(s[i - x - 1] == '('){
                        dp[i] = dp[i - 1] + 2;
                        if(i - x - 2 >= 0) dp[i] += dp[i - x - 2]; 
                    }
                }
            }
        }
        int maxRes = 0;
        for(int i = 0; i < s.size(); i ++) {
            // cout << maxRes << endl;
            maxRes = max(maxRes, dp[i]);
        }
        return maxRes;
    }
};

思路

状态表示：dp[i] 表示以第i个字符结尾的有效括号的长度。

状态转移：

  • dp[i] == '('：则直接让dp[i] = 0
  • dp[i] == ')'：
    • dp[i - 1] == '('，本身就组成了一个有效括号子串，然后需要判断前面是否存在其他括号子串和其并列，最后的状态方程为：dp[i] = dp[i - 2] + 2；
    • dp[i - 1] == ')'，需要获得以前一个字符结尾的有效括号子串长度x = dp[i - 1]
      • x == 0 || i - x - 1，则说明当前右括号为孤立括号 则dp[i] = 0
      • s[i - x - 1] == '('，这说明当前右括号有对应的左括号，同时需要判断该左括号前是否有其他有效括号与其并列，则状态方程为 dp[i] = dp[i - 1] + 2 + dp[i - x - 2]

知识点

在LeetCode中，C++定义数组没有初始化，则可能会提交错误。

题目十七：搜索旋转排序数组⭐

搜索旋转排序数组

标签

数组、二分查找

题解

1
2
3
4
5
6
7
8
class Solution {
    public int search(int[] nums, int target) {
        for(int i = 0; i < nums.length; i ++) {
            if(nums[i] == target) return i;
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int search(vector<int>& nums, int target) {
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == target) return i;
        }
        return -1;
    }
};

题目十八： 在排序数组中查找元素的第一个和最后一个位置

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

标签

数组、二分查找、二分查找模板题

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0) return new int[]{-1, -1};
        // 二分查找模板1
        int l = 0, r = nums.length - 1;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(nums[mid] < target) l = mid + 1;
            else r = mid;
        }
        if(nums[l] != target) return new int[]{-1, -1};
        int i = l;
        // 二分查找模板2
        l = 0; r = nums.length - 1;
        while(l < r) {
            int mid = (l + r + 1) >> 1;
            if(nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        return new int[]{i, r};
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res;
        if(nums.size() == 0){
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }
        int l = 0, r = nums.size() - 1;
        while(l < r){  //第一个模板
            int mid = (l + r) >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if(nums[l] != target){
            res.push_back(-1);
            res.push_back(-1);
        }else{
            res.push_back(l);
            l = 0, r = nums.size() - 1;
            while(l < r){  // 第二个模板
                int mid = (l + r + 1) >> 1;
                if(nums[mid] <= target) l = mid;
                else r = mid - 1;
            }
            res.push_back(r);
        }
        return res;
    }
};

题目十九：组合总和

组合总和

标签

数组、回溯

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    private List<List<Integer>> res = new ArrayList<List<Integer>>();
    private List<Integer> arr = new ArrayList<>();
    public void dfs(int target, int sum, int[] candidates, int idx) {
        if(sum == target) {
            res.add(new ArrayList<Integer>(arr));
        }
        else if(sum > target) return ;
        else {
            for(int i = idx; i < candidates.length; i ++) {
                sum += candidates[i];
                arr.add(candidates[i]);
                dfs(target, sum, candidates, i);
                sum -= arr.get(arr.size() - 1);
                arr.remove(arr.size() - 1);
            }
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(target, 0, candidates, 0);
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> res;
    void dfs(vector<int>& arr, int target, int sum, vector<int>& candidates, int idx){
        if(sum == target) res.push_back(arr);
        else if(sum > target) return ;
        else{
            for(int i = idx; i < candidates.size(); i++){
                sum += candidates[i];
                arr.push_back(candidates[i]);
                dfs(arr, target, sum, candidates, i);
                sum -= arr[arr.size() - 1];
                arr.pop_back();
                
            }
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> arr;
        dfs(arr, target, 0, candidates, 0);
        return res;
    }
};

知识点

在Java中将List<>插入List<List>>的方法，例如：

1
2
3
4
5
private List<List<Integer>> res = new ArrayList<List<Integer>>();
private List<Integer> arr = new ArrayList<>();

....
res.add(new ArrayList<Integer>(arr));

ArrayList删除第i个元素的方法：arr.remove(i)。获取第i个元素的方法arr.get(i)

题目二十：接雨水❗

接雨水

标签

栈、数组、双指针、动态规划、单调栈

题解

题目二十一：全排列

全排列

标签

数组、回溯

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    boolean[] st;

    void dfs(List<Integer> arr, int[] nums) {
        if(arr.size() == nums.length) {
            res.add(new ArrayList<Integer>(arr));
            return;
        }
        for(int i = 0; i < nums.length; i ++){
            if(!st[i]) {
                arr.add(nums[i]);
                st[i] = true;
                dfs(arr, nums);
                st[i] = false;
                arr.remove(arr.size() - 1);
            }
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        st = new boolean[n];
        List<Integer> arr = new ArrayList<>();
        dfs(arr, nums);
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> res;
    vector<bool> used;  // 记录被使用过的数字
    void dfs(vector<int>& arr, vector<int>& nums){
        if(arr.size() == nums.size()) res.push_back(arr); // 出口
        else{
            for(int i = 0; i < nums.size(); i++){
                if(!used[i]){
                    arr.push_back(nums[i]);
                    used[i] = true;
                    dfs(arr, nums);
                    used[i] = false;  // 回溯
                    arr.pop_back();
                }
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> arr;
        for(int i = 0; i < nums.size(); i++){
            used.push_back(false);
        }
        dfs(arr, nums);
        return res;
    }
};

题目二十二：旋转图像

旋转图像

标签

数组、数学、矩阵

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    // [i, j]-->[j, size - i - 1] -->[size - i - 1, size - j - 1] --> [size - j - 1, i] -->[i, j]
    public void rotate(int[][] matrix) {
        // [i, j]----->[j, size - i - 1]
        int len = matrix.length;
        for(int i = 0; i < len / 2; i++){
            for(int j = i; j < len - i - 1; j++){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[len - j - 1][i];
                matrix[len - j - 1][i] = matrix[len - i - 1][len - j - 1];
                matrix[len - i - 1][len - j - 1] = matrix[j][len - i - 1];
                matrix[j][len - i - 1] = tmp;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        // [i, j]----->[j, size - i - 1]
        int len = matrix.size();
        for(int i = 0; i < len / 2; i++){
            for(int j = i; j < len - i - 1; j++){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[len - j - 1][i];
                matrix[len - j - 1][i] = matrix[len - i - 1][len - j - 1];
                matrix[len - i - 1][len - j - 1] = matrix[j][len - i - 1];
                matrix[j][len - i - 1] = tmp;
            }
        }
    }

};

题目二十三：字母异位词分组

字母异位词分组

标签

数组、哈希表、字符串、排序

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hsp = new HashMap<>();

        for(String str : strs) {
            char[] arr = str.toCharArray();  // 将String转为char数组
            Arrays.sort(arr);  // 数组排序
            String key = new String(arr);  // char数组转为String
            List<String> list = hsp.getOrDefault(key, new ArrayList<String>());  //getOrDefault 如果存在key，则返回对应的value，否则返回给定的默认值
            list.add(str);
            hsp.put(key, list);
        }
        return new ArrayList<List<String>>(hsp.values());  // 将HashMap的所有value返回
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> hashMap;
        for(int i = 0; i < strs.size(); i++){
            string str = strs[i];
            sort(str.begin(), str.end());
            if(hashMap.empty() || hashMap.find(str) == hashMap.end()){
                vector<string> arr;
                arr.push_back(strs[i]);
                hashMap[str] = arr;
            }
            else{
                hashMap[str].push_back(strs[i]);
            }
        }
        for(unordered_map<string, vector<string>>::iterator iter = hashMap.begin(); iter != hashMap.end(); iter++){
            res.push_back(iter->second);
        }
        return res;
    }
};

知识点

  1. 在java中，String类型字符转排序需要先转为char[]，然后使用数组排序的方法进行排序，最后再转为String
1
2
3
4
String str = "azxcadfasd";
char[] arr = str.toCharArray();  //String转为char[]数组
Arrays.sort(arr);  // 数组排序
String key = new String(arr);  // char[] 转为String
  1. HashMap中的getOrDefault(key, default value)方法是如果存在key，则返回value，否则返回给定的默认值
  2. HashMap中的values()方法是返回map中所有的value
正在加载今日诗词....