力扣Hot100

1.两数之和 Easy

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

1
输入：nums = [2,7,11,15], target = 9
2
输出：[0,1]
3
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

xxxxxxxxxx
2
1
输入：nums = [3,2,4], target = 6
2
输出：[1,2]

示例 3：

xxxxxxxxxx
2
1
输入：nums = [3,3], target = 6
2
输出：[0,1]

提示：

• 2 <= nums.length <= 104

• -109 <= nums[i] <= 109

• -109 <= target <= 109

• 只会存在一个有效答案

xxxxxxxxxx
23
1
class Solution {
2
    public int[] twoSum(int[] nums, int target) {
3
        int[] res = new int[2];
4
        //讨论特殊情况
5
        if (nums == null || nums.length == 0) {
6
            return res;
7
        }
8
        //使用一个Map来记录数组的值和索引值
9
        Map<Integer,Integer> map = new HashMap<>();
10
        for (int i = 0; i < nums.length; i++) {
11
            //定义一个临时变量
12
            int temp = target  - nums[i];
13
            //更新res数组
14
            if (map.containsKey(temp)){
15
                res[0] = i;
16
                res[1] = map.get(temp);
17
                break;//结束循环
18
            }
19
            map.put(nums[i],i);
20
        }
21
        return res;
22
    }
23
}

2.两数相加 Medium

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

xxxxxxxxxx
3
1
输入：l1 = [2,4,3], l2 = [5,6,4]
2
输出：[7,0,8]
3
解释：342 + 465 = 807.

示例 2：

xxxxxxxxxx
2
1
输入：l1 = [0], l2 = [0]
2
输出：[0]

示例 3：

xxxxxxxxxx
2
1
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
2
输出：[8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围 [1, 100] 内

• 0 <= Node.val <= 9

• 题目数据保证列表表示的数字不含前导零

Related Topics

• 递归

• 链表

• 数学

xxxxxxxxxx
35
1
class Solution {
2
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
3
        //辅助的哑节点
4
        ListNode pre = new ListNode(-1);
5
        //辅助遍历的节点
6
        ListNode cur = pre;
7
        //carry表示十位，要么是1要么是0，这里的十位是指两个指针指向的两个数相加后的十位
8
        int carry = 0;
9
        while (l1 != null || l2 != null){
10
            //获取节点值，如果节点为空，就是0
11
            int x = l1 == null ? 0 : l1.val;
12
            int y = l2 == null ? 0 : l2.val;
13
            int sum = x + y +carry;
14
            //计算十位
15
            carry = sum / 10;
16
            //计算个位
17
            sum = sum % 10;
18
            //添加节点
19
            cur.next = new ListNode(sum);
20
            //节点往后移
21
            cur = cur.next;
22
            if (l1 != null){
23
                l1 = l1.next;
24
            }
25
            if (l2 != null){
26
                l2 = l2.next;
27
            }
28
        }
29
        //如果到最后十位还是1的话，得补一个节点
30
        if (carry == 1){
31
            cur.next = new ListNode(carry);
32
        }
33
        return pre.next;
34
    }
35
}

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

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

xxxxxxxxxx
3
1
输入: s = "abcabcbb"
2
输出: 3 
3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

xxxxxxxxxx
3
1
输入: s = "bbbbb"
2
输出: 1
3
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

xxxxxxxxxx
4
1
输入: s = "pwwkew"
2
输出: 3
3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
4
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104

• s 由英文字母、数字、符号和空格组成

Related Topics

• 哈希表

• 字符串

• 滑动窗口

​x
1
class Solution {
2
    public static int lengthOfLongestSubstring(String s) {
3
        //特殊情况，字符串长度为0
4
        if (s.length() == 0) return 0;
5
        //使用map记录当前滑动窗口是否存在当前遍历到的字符
6
        Map<Character,Integer> map = new HashMap<>();
7
        //转为数组
8
        char[] chars = s.toCharArray();
9
        int res = 0;
10
        //滑动窗口左边界
11
        int left = 0;
12
        //右边界
13
        int right = 0;
14
        while (right < chars.length){
15
            //不包含当前字符，我们就记录一下，右边界右移
16
            if (!map.containsKey(chars[right]) ){
17
                map.put(chars[right],1);
18
                right++;
19
            }else {
20
                //说明包含了，map先删除这个字符
21
                //左边界右移
22
                map.remove(chars[left]);
23
                left++;
24
            }
25
            //记录滑动窗口的最大值
26
            //因为前面right已经++了，所以这里right-left不用+1
27
            res = Math.max(res,right-left);
28
        }
29
        return res;
30
    }
31
}
32

xxxxxxxxxx
23
1
//对上一个方法进行优化，上一个方法里是left的更新比较慢，因为一旦遇到重复之后就需要更新left到重复字符的下一个位置，所以在这里对这个细节进行优化
2
//举个例子，假设字符串是 "abcba"：当遍历到第二个 "b" 时，发现它在位置 3 和位置 1 都出现过，此时需要更新 start 的值。通过 map.get(c) 可以得到最近一次 "b" 出现的位置为 1，那么通过 Math.max(map.get(c), start) 就可以得到新的 start 值为 1+1 = 2，即重复字符的下一个位置。
3
class Solution {
4
    public static int lengthOfLongestSubstring(String s) {
5
        if (s.length() == 0) return 0;
6
        Map<Character,Integer> map = new HashMap<>();
7
        //左边界
8
        int start = 0;
9
        int res = 0;
10
        //end右边界
11
        for (int end = 0; end < s.length();end++){
12
            char c = s.charAt(end);
13
            if (map.containsKey(c)){
14
                //左边界直接跳到右边界
15
                start = Math.max(map.get(c),start);
16
            }
17
            res = Math.max(res,end-start+1);
18
            //end+1是表示记录当前字符索引的下一位，这样就能直接跳到重复字符的下一位了
19
            map.put(s.charAt(end),end+1);
20
        }
21
        return res;
22
    }
23
}

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

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

xxxxxxxxxx
3
1
输入：nums1 = [1,3], nums2 = [2]
2
输出：2.00000
3
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

xxxxxxxxxx
3
1
输入：nums1 = [1,2], nums2 = [3,4]
2
输出：2.50000
3
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

• nums1.length == m

• nums2.length == n

• 0 <= m <= 1000

• 0 <= n <= 1000

• 1 <= m + n <= 2000

• -106 <= nums1[i], nums2[i] <= 106

Related Topics

• 数组

• 二分查找

• 分治

xxxxxxxxxx
29
1
//合并数组，但只要合并到中间位置就可以了
2
class Solution {
3
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
4
        int m = nums1.length, n = nums2.length;
5
        int l = m + n;
6
        int i = 0, j = 0;
7
        double[] res = new double[l];
8
        int index = 0;
9
        while (i < m && j < n && i + j <= l / 2){
10
            if (nums1[i] <= nums2[j]){
11
                res[index++] = nums1[i++];
12
            }else {
13
                res[index++] = nums2[j++];
14
            }
15
        }
16
        //有可能只是一个数组元素很少，遍历完了，但是还没遍历到合并数组的中间位置
17
        while (i == m && i + j <= l /2){
18
            res[index++] = nums2[j++];
19
        }
20
        while (j == n && i + j <= l /2){
21
            res[index++] = nums1[i++];
22
        }
23
        if (l %2 == 0){
24
            return (res[l/2] + res[l/2 - 1]) / 2;
25
        }else {
26
            return res[l/2];
27
        }
28
    }
29
}

5.最长回文子串 Medium

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

xxxxxxxxxx
3
1
输入：s = "babad"
2
输出："bab"
3
解释："aba" 同样是符合题意的答案。

示例 2：

xxxxxxxxxx
2
1
输入：s = "cbbd"
2
输出："bb"

提示：

• 1 <= s.length <= 1000

• s 仅由数字和英文字母组成

Related Topics

• 字符串

• 动态规划

xxxxxxxxxx
48
1
class Solution {
2
    public String longestPalindrome(String s) {
3
        int len = s.length();
4
        //特殊情况:如果字符串长度只有1，那一定是回文子串
5
        if (len < 2) return s;
6
        //dp表示在s[i...j]范围内是否是回文子串
7
        boolean[][] dp = new boolean[len][len];
8
        //初始化：根据dp的含义，而且我们知道单个字符肯定是回文子串
9
        for (int i = 0; i < len; i++) {
10
            dp[i][i] = true;
11
        }
12

13
        char[] chars = s.toCharArray();
14

15
        int begin = 0;//记录回文子串的起始位置
16
        int maxLen = 1;//记录回文子串的最大长度
17

18
        //遍历
19
        //用动态规划dp[i][j]是否为true，是取决于dp[i+1][j-1]的
20
        //所以这里我们先遍历列，再遍历行
21
        for (int j = 1; j < len; j++) {
22
            for (int i = 0; i < j; i++) {
23
                //两个字符不同，那肯定不是回文
24
                if (chars[i] != chars[j]){
25
                    dp[i][j] = false;
26
                }else {
27
                    //dp[i][j]是否为true，是取决于dp[i+1][j-1]的
28
                    //判断一下边界条件，(j-1)-(i+1)+1 >= 2 才能用状态转移方程
29
                    //不然的话，如果长度小于2,要么为1要么为0，再加上当前i和j的字符是相同的
30
                    //那么dp[j][j]肯定是true了
31
                    if (j - i < 3){
32
                        dp[i][j] = true;
33
                    }else {
34
                        dp[i][j] = dp[i+1][j-1];
35
                    }
36
                }
37
                //如果当前是回文子串，并且长度也是大于maxLen
38
                //那么就更新begin 和 maxLen
39
                if (dp[i][j] && j - i + 1 > maxLen){
40
                    maxLen = j - i + 1;
41
                    begin = i;
42
                }
43
            }
44
        }
45

46
        return s.substring(begin,begin+maxLen);
47
    }
48
}

6.正则表达式匹配 Hard

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

• '.' 匹配任意单个字符

• '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：

xxxxxxxxxx
3
1
输入：s = "aa", p = "a"
2
输出：false
3
解释："a" 无法匹配 "aa" 整个字符串。

示例 2:

xxxxxxxxxx
3
1
输入：s = "aa", p = "a*"
2
输出：true
3
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

xxxxxxxxxx
3
1
输入：s = "ab", p = ".*"
2
输出：true
3
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

提示：

• 1 <= s.length <= 20

• 1 <= p.length <= 20

• s 只包含从 a-z 的小写字母。

• p 只包含从 a-z 的小写字母，以及字符 . 和 *。

• 保证每次出现字符 * 时，前面都匹配到有效的字符

Related Topics

• 递归

• 字符串

• 动态规划

动态规划：https://www.bilibili.com/video/BV1jd4y1U7kE/?spm_id_from=333.337.search-card.all.click&vd_source=92cb5cb9faa01574e9b1f82bf91d080d

https://www.iamshuaidi.com/2032.html

xxxxxxxxxx
30
1
class Solution {
2
    public boolean isMatch(String s, String p) {
3
        if (s == null || p == null){
4
            return true;
5
        }
6
        int n = s.length();
7
        int m = p.length();
8
        boolean[][] dp = new boolean[n+1][m+1];
9
        dp[0][0] = true;
10
        for (int j = 1; j <= m ; j++) {
11
            if (p.charAt(j-1) == '*'){
12
                dp[0][j] = dp[0][j-2];
13
            }
14
        }
15
        for(int i = 1; i <= n; i++){
16
            for(int j = 1; j <= m; j++){
17
                if(p.charAt(j-1)=='.'||p.charAt(j-1)==s.charAt(i-1))
18
                    dp[i][j] = dp[i-1][j-1];
19
                else if(p.charAt(j-1)=='*'){
20
                    if(j!=1&&p.charAt(j-2)!='.'&&p.charAt(j-2)!=s.charAt(i-1)){
21
                        dp[i][j] = dp[i][j-2];
22
                    }else{
23
                        dp[i][j] = dp[i][j-2] || dp[i][j-1]||dp[i-1][j];
24
                    }
25
                }
26
            }
27
        }
28
        return dp[n][m];
29
    }
30
}

7.盛最多水的容器 Medium

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

xxxxxxxxxx
3
1
输入：[1,8,6,2,5,4,8,3,7]
2
输出：49 
3
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

xxxxxxxxxx
2
1
输入：height = [1,1]
2
输出：1

提示：

• n == height.length

• 2 <= n <= 105

• 0 <= height[i] <= 104

Related Topics

• 贪心

• 数组

• 双指针

xxxxxxxxxx
27
1
class Solution {
2
    public int maxArea(int[] height) {
3
        //考虑特殊情况
4
        if (height.length < 2) return 0;
5
        //返回的结果
6
        int res = 0;
7
        //双指针
8
        int left = 0, right = height.length-1;
9
        while (left < right){
10
            //h是高
11
            int h = Math.min(height[left],height[right]);
12
            //计算面积
13
            int area = h * (right - left);
14
            //更新res
15
            res = Math.max(res,area);
16
            //如果左指针对应的高度比h低的话，指针右移
17
            while (left < right && height[left] <= h){
18
                left++;
19
            }
20
            //如果右指针对应的高度比h低的话，指针左移
21
            while (left < right && height[right] <= h){
22
                right--;
23
            }
24
        }
25
        return res;
26
    }
27
}

8.三数之和 Medium

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

xxxxxxxxxx
8
1
输入：nums = [-1,0,1,2,-1,-4]
2
输出：[[-1,-1,2],[-1,0,1]]
3
解释：
4
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
5
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
6
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
7
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
8
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

xxxxxxxxxx
3
1
输入：nums = [0,1,1]
2
输出：[]
3
解释：唯一可能的三元组和不为 0 。

示例 3：

xxxxxxxxxx
3
1
输入：nums = [0,0,0]
2
输出：[[0,0,0]]
3
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000

• -105 <= nums[i] <= 105

Related Topics

• 数组

• 双指针

• 排序

xxxxxxxxxx
48
1
class Solution {
2
    public List<List<Integer>> threeSum(int[] nums) {
3
        List<List<Integer>> res = new LinkedList<>();
4
        //排序，从小到大
5
        Arrays.sort(nums);
6
        //数组长度
7
        int n = nums.length;
8
        //遍历第一个数，只需要到n-2，n-1是第三个数在遍历
9
        for (int i = 0; i < n - 2; i++) {
10
            //跳过重复数字
11
            if (i > 0 && nums[i] == nums[i-1]){
12
                continue;
13
            }
14
            //优化细节1：如果前三个数加起来都大于0了，那么就不可能存在三个数加起来能等于0
15
            if (nums[i] + nums[i+1] + nums[i+2] > 0) {
16
                return res;
17
            }
18
            //优化细节1，如果最小的和最大的两个加起来小于0的话，那就没必要去遍历第二个数和第三个数了，因为这两个数比最大的两个数小
19
            //直接进入下一循环
20
            if (nums[i] + nums[n-2] + nums[n-1] < 0){
21
                continue;
22
            }
23
            int left = i + 1;
24
            int right = nums.length - 1;
25
            while (left < right){
26
                if (nums[i] + nums[left] + nums[right] == 0){
27
                    res.add(Arrays.asList(nums[i],nums[left],nums[right]));
28
                    //去重第二个数字
29
                    while (left < right && nums[right] == nums[right-1]){
30
                        right--;
31
                    }
32
                    //去重第三个数
33
                    while (left < right && nums[left] == nums[left+1]){
34
                        left++;
35
                    }
36
                    //移动指针
37
                    left++;
38
                    right--;
39
                }else if (nums[i] + nums[left] + nums[right] < 0){
40
                    left++;
41
                }else {
42
                    right--;
43
                }
44
            }
45
        }
46
        return res;
47
    }
48
}

9.电话号码的字母组合 Medium

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

xxxxxxxxxx
2
1
输入：digits = "23"
2
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

xxxxxxxxxx
2
1
输入：digits = ""
2
输出：[]

示例 3：

xxxxxxxxxx
2
1
输入：digits = "2"
2
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4

• digits[i] 是范围 ['2', '9'] 的一个数字。

Related Topics

• 哈希表

• 字符串

• 回溯

xxxxxxxxxx
44
1
class Solution {
2
    List<String> res = new LinkedList<>();
3
    StringBuffer sb = new StringBuffer();
4
    String[] numsStr = new String[]{
5
            "",
6
            "",
7
            "abc",
8
            "def",
9
            "ghi",
10
            "jkl",
11
            "mno",
12
            "pqrs",
13
            "tuv",
14
            "wxyz"
15
    };
16
    public List<String> letterCombinations(String digits) {
17
        if (digits.length() == 0) {
18
            return res;
19
        }
20
        dfs(digits,0);
21
        return res;
22
    }
23

24
    public void dfs(String digits, int index){
25
        //已经递归到这个数字对应的最后一个字母了，那就记录
26
        if (index == digits.length()) {
27
            res.add(sb.toString());
28
            return;
29
        }
30
        //获取这个数字对应的字母字符串
31
        String numChar = numsStr[digits.charAt(index)-'0'];
32
        //遍历字母字符
33
        for (int i = 0; i < numChar.length(); i++) {
34
            //记录该字母
35
            sb.append(numChar.charAt(i));
36
            //递归
37
            dfs(digits,index+1);
38
            //回溯
39
            sb.deleteCharAt(sb.length()-1);
40
        }
41

42
    }
43

44
}

xxxxxxxxxx
41
1
//回溯的另一种写法
2
class Solution {
3
    public static final String[] MAPPING = new String[]{
4
            "",
5
            "",
6
            "abc",
7
            "def",
8
            "ghi",
9
            "jkl",
10
            "mno",
11
            "qprs",
12
            "tuv",
13
            "wxyz"
14
    };
15

16
    List<String> res = new LinkedList<>();
17
    char[] path, digits;
18

19
    public List<String> letterCombinations(String digits) {
20
        int n = digits.length();
21
        if (n == 0) return res;
22
        this.digits = digits.toCharArray();
23
        path = new char[n];
24
        dfs(0);
25
        return res;
26
    }
27

28
    public void dfs(int i){
29
        if (i == digits.length) {
30
            res.add(new String(path));
31
            return;
32
        }
33
        //比如这里的是digits是[2,3]
34
        //那么MAPPING[2]对应的就是"abc"
35
        for (char c : MAPPING[digits[i] -'0'].toCharArray()){
36
            //这里path中的元素虽然没有被删掉，但在下一层循环中会被覆盖
37
            path[i] = c;
38
            dfs(i+1);
39
        }
40
    }
41
}

10.删除链表倒数第N个节点 Medium

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

xxxxxxxxxx
2
1
输入：head = [1,2,3,4,5], n = 2
2
输出：[1,2,3,5]

示例 2：

xxxxxxxxxx
2
1
输入：head = [1], n = 1
2
输出：[]

示例 3：

xxxxxxxxxx
2
1
输入：head = [1,2], n = 1
2
输出：[1]

提示：

• 链表中结点的数目为 sz

• 1 <= sz <= 30

• 0 <= Node.val <= 100

• 1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

Related Topics

• 链表

• 双指针

xxxxxxxxxx
27
1
class Solution {
2
    public ListNode removeNthFromEnd(ListNode head, int n) {
3
        //哑结点的好处在于可以不用讨论头结点被删除的情况
4
        ListNode dummy = new ListNode(-1,head);
5
        ListNode temp = dummy;
6
        //获取链表长度
7
        int len = getLength(head);
8
        int k = len - n ;
9
        for (int i = 0; i <= k; i++) {
10
            if (i == k){
11
                temp.next = temp.next.next;
12
                break;
13
            }
14
            temp = temp.next;
15
        }
16
        return dummy.next;
17
    }
18

19
    public int getLength(ListNode head){
20
        int len = 0;
21
        while (head != null){
22
            len++;
23
            head = head.next;
24
        }
25
        return len;
26
    }
27
}

xxxxxxxxxx
18
1
class Solution {
2
    public ListNode removeNthFromEnd(ListNode head, int n) {
3
        ListNode dummy = new ListNode(-1, head);
4
        ListNode left = dummy;
5
        ListNode right =dummy;
6
        //让right指针先走n步
7
        while (n-- > 0){
8
            right = right.next;
9
        }
10
        //然后left和right一起走，直到right到最后一个节点，这个时候left所指向的就是待删除节点的前一个节点
11
        while (right.next != null){
12
            left = left.next;
13
            right = right.next;
14
        }
15
        left.next = left.next.next;
16
        return dummy.next;
17
    }
18
}

11.有效的括号 Easy

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

xxxxxxxxxx
2
1
输入：s = "()"
2
输出：true

示例 2：

xxxxxxxxxx
2
1
输入：s = "()[]{}"
2
输出：true

示例 3：

xxxxxxxxxx
2
1
输入：s = "(]"
2
输出：false

提示：

• 1 <= s.length <= 104

• s 仅由括号 '()[]{}' 组成

Related Topics

• 栈

• 字符串

xxxxxxxxxx
24
1
class Solution {
2
    public boolean isValid(String s) {
3
        char[] chars = s.toCharArray();
4
        Deque<Character> deque = new LinkedList<>();
5
        for (int i = 0; i < chars.length; i++) {
6
            char c = chars[i];
7
            //遇到左括号，就把右括号放入队列中
8
            if (c == '(') {
9
                deque.push(')');
10
            }else if (c == '[') {
11
                deque.push(']');
12
            }else if (c == '{') {
13
                deque.push('}');
14
            }else if (deque.isEmpty() || deque.peek() != c){
15
                //因为当前已经遍历到字符并且这个字符不是左括号，但是队列已经为空了，说明右括号多了
16
                //如果头元素和当前字符不一样，要么是左括号多了，要么就是左右括号不能匹配
17
                return false;
18
            }else {//如果遇到队列头元素和当前字符相同，就把头元素删掉
19
                deque.pop();
20
            }
21
        }
22
        return deque.isEmpty();
23
    }
24
}

12.合并两个有序列表 Easy

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

xxxxxxxxxx
2
1
输入：l1 = [1,2,4], l2 = [1,3,4]
2
输出：[1,1,2,3,4,4]

示例 2：

xxxxxxxxxx
2
1
输入：l1 = [], l2 = []
2
输出：[]

示例 3：

xxxxxxxxxx
2
1
输入：l1 = [], l2 = [0]
2
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]

• -100 <= Node.val <= 100

• l1 和 l2 均按 非递减顺序 排列

Related Topics

• 递归

• 链表

xxxxxxxxxx
26
1
//最简单的办法是新造一个链表，遍历这两个链表，比较两个节点的大小，用小节点的值创建新的节点，连接在新链表之后
2
class Solution {
3
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
4
        if (list1 == null) return list2;
5
        if (list2 == null) return list1;
6
        ListNode dummy = new ListNode(-1);
7
        ListNode cur = dummy;
8
        while (list1 != null && list2 != null){
9
            if (list1.val <= list2.val) {
10
                cur.next = new ListNode(list1.val);
11
                list1 = list1.next;
12
            } else {
13
                cur.next = new ListNode(list2.val);
14
                list2 = list2.next;
15
            }
16
            cur = cur.next;
17
        }
18
        if (list1 != null) {
19
            cur.next = list1;
20
        }
21
        if (list2 != null){
22
            cur.next = list2;
23
        }
24
        return dummy.next;
25
    }
26
}

xxxxxxxxxx
26
1
//方法二，使用原来链表的节点去造新链表
2
class Solution {
3
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
4
        if (list1 == null) return list2;
5
        if (list2 == null) return list1;
6
        ListNode dummy = new ListNode(-1);
7
        ListNode cur = dummy;
8
        while (list1 != null && list2 != null){
9
            if (list1.val <= list2.val) {
10
                cur.next = list1;
11
                list1 = list1.next;
12
            } else {
13
                cur.next = list2;
14
                list2 = list2.next;
15
            }
16
            cur = cur.next;
17
        }
18
        if (list1 != null) {
19
            cur.next = list1;
20
        }
21
        if (list2 != null){
22
            cur.next = list2;
23
        }
24
        return dummy.next;
25
    }
26
}

xxxxxxxxxx
14
1
//使用递归
2
class Solution {
3
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
4
        if (list1 == null) return list2;
5
        if (list2 == null) return list1;
6
        if (list1.val <= list2.val) {
7
            list1.next = mergeTwoLists(list1.next,list2);
8
            return list1;
9
        }else {
10
            list2.next = mergeTwoLists(list1,list2.next);
11
            return list2;
12
        }
13
    }
14
}

13.括号生成 Medium

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

xxxxxxxxxx
2
1
输入：n = 3
2
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

xxxxxxxxxx
2
1
输入：n = 1
2
输出：["()"]

提示：

• 1 <= n <= 8

Related Topics

• 字符串

• 动态规划

• 回溯

xxxxxxxxxx
28
1
class Solution {
2
    List res = new LinkedList<>(); // 保存结果的集合
3
    char[] path; // 保存括号组合的数组
4
    int n; // 括号对数
5

6
    public List<String> generateParenthesis(int n) {
7
    path = new char[2 * n]; // 初始化括号组合数组的长度
8
    this.n = n; // 保存括号对数
9
    dfs(0,0); // 开始深度优先搜索，以0作为起始位置，初始括号数为0
10
    return res; // 返回结果集合
11
    }
12

13
    public void dfs(int i, int open) {
14
        if (i == 2 *n){ // 当组合的括号对数达到2n时，即所有位置都填满了括号
15
            res.add(new String(path)); // 将当前的括号组合转化为字符串，并添加进结果集合
16
            return; // 结束当前的深度优先搜索
17
        }
18

19
        if (open < n) { // 如果当前开放的左括号数小于n
20
            path[i] = '('; // 在当前位置添加一个左括号
21
            dfs(i+1,open+1); // 继续下一个位置的搜索，并更新左括号数
22
        }
23
        if (i - open < open) { // 如果当前位置之前的右括号数小于左括号数
24
            path[i] = ')'; // 在当前位置添加一个右括号
25
            dfs(i+1,open); // 继续下一个位置的搜索，并保持左括号数不变
26
        }
27
    }
28
}

14.合并K个升序链表 Hard

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

xxxxxxxxxx
10
1
输入：lists = [[1,4,5],[1,3,4],[2,6]]
2
输出：[1,1,2,3,4,4,5,6]
3
解释：链表数组如下：
4
[
5
  1->4->5,
6
  1->3->4,
7
  2->6
8
]
9
将它们合并到一个有序链表中得到。
10
1->1->2->3->4->4->5->6

示例 2：

xxxxxxxxxx
2
1
输入：lists = []
2
输出：[]

示例 3：

xxxxxxxxxx
2
1
输入：lists = [[]]
2
输出：[]

提示：

• k == lists.length

• 0 <= k <= 10^4

• 0 <= lists[i].length <= 500

• -10^4 <= lists[i][j] <= 10^4

• lists[i] 按 升序 排列

• lists[i].length 的总和不超过 10^4

Related Topics

• 链表

• 分治

• 堆（优先队列）

• 归并排序

xxxxxxxxxx
21
1
class Solution {
2
    public ListNode mergeKLists(ListNode[] lists) {
3
        //优先队列，默认情况下，最小的数排在队列头部
4
        PriorityQueue<Integer> queue = new PriorityQueue<>();
5
        for (ListNode listNode : lists) {//将所有节点值塞进优先队列中，这样就得到了从小到大的排序
6
            while (listNode != null) {
7
                queue.add(listNode.val);
8
                listNode = listNode.next;
9
            }
10
        }
11

12
        ListNode dummy = new ListNode(-1);
13
        ListNode cur = dummy;
14
        while (!queue.isEmpty()) {//通过遍历队列，创建节点
15
            cur.next = new ListNode(queue.poll());
16
            cur = cur.next;
17
        }
18
        return dummy.next;
19

20
    }
21
}

xxxxxxxxxx
46
1
class Solution {
2
    public ListNode mergeKLists(ListNode[] lists) {
3
        if (lists == null || lists.length == 0) {
4
            return null;
5
        }
6
        if (lists.length == 1) {
7
            return lists[0];
8
        }
9
        return mergeKListNodes(lists, 0, lists.length - 1);
10
    }
11

12
    // 合并 lists 数组中区间 [i, j] 的链表
13
    public ListNode mergeKListNodes(ListNode[] lists, int i, int j) {
14
        if (i == j) {
15
            return lists[i]; // 当 i 和 j 相等时，直接返回该链表
16
        }
17
        int mid = i + (j - i) / 2;
18
        ListNode left = mergeKListNodes(lists, i, mid); // 递归合并左侧区间 [i, mid]
19
        ListNode right = mergeKListNodes(lists, mid + 1, j); // 递归合并右侧区间 [mid + 1, j]
20
        return mergeTwoListNode(left, right); // 合并左右两个链表
21
    }
22

23
    // 合并两个有序链表
24
    public ListNode mergeTwoListNode(ListNode listNode1, ListNode listNode2) {
25
        if (listNode1 == null) {
26
            return listNode2;
27
        }
28
        if (listNode2 == null) {
29
            return listNode1;
30
        }
31
        ListNode dummy = new ListNode(-1);
32
        ListNode cur = dummy;
33
        while (listNode1 != null && listNode2 != null) {
34
            if (listNode1.val <= listNode2.val) {
35
                cur.next = listNode1; // 将当前节点连接到合并后的链表中
36
                listNode1 = listNode1.next; // 移动 listNode1 的指针
37
            } else {
38
                cur.next = listNode2; // 将当前节点连接到合并后的链表中
39
                listNode2 = listNode2.next; // 移动 listNode2 的指针
40
            }
41
            cur = cur.next; // 移动合并后的链表指针
42
        }
43
        cur.next = listNode1 == null ? listNode2 : listNode1; // 将剩余的节点连接到合并后的链表中
44
        return dummy.next; // 返回合并后的链表
45
    }
46
}

15.下一个排列 Medium

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

• 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。

• 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。

• 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

示例 1：

xxxxxxxxxx
2
1
输入：nums = [1,2,3]
2
输出：[1,3,2]

示例 2：

xxxxxxxxxx
2
1
输入：nums = [3,2,1]
2
输出：[1,2,3]

示例 3：