本文收集了一些LeetCode的一些中等难度的题目。

基础数据类型定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class ListNode1 {
    int val;
    ListNode1 next;

    ListNode1(int x) {
        val = x;
    }
    
    public ListNode1(int val , ListNode1 next){
        this.val = val;
        this.next = next;
    }

    public ListNode1 reverseLink(ListNode1 head) {
        ListNode1 head1 = head, next1 = head.next, prev1 = null;
        while(head1 != null){
            head1.next = prev1;
            prev1 = head1;
            head1 = next1;
            next1 = head1.next;  // next1 = next1.next;
        }
        return prev1;
    }
}

Quick Start

给出两个非空链表来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)；输出：7 -> 0 -> 8。原因：342 + 465 = 807

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
public static ListNode1 problem(ListNode1 l1, ListNode1 l2) {
    ListNode1 head = new ListNode1(0);
    ListNode1 p1 = l1, p2 = l2, re = head;
    int temp = 0; // 进位
    while (p1 != null || p2 != null || temp != 0) {
        if (p1 != null && p2 != null) {
            re.val = (p1.val + p2.val + temp) % 10;
            temp = (p1.val + p2.val + temp) / 10;
            p1 = p1.next;
            p2 = p2.next;
        } else if (p1 == null && p2 != null) {     // p2 长
            re.val = (p2.val + temp) % 10;
            temp = (p2.val + temp) / 10;
            p2 = p2.next;
        } else if (p1 != null && p2 == null) {   // p1 长
            re.val = (p1.val + temp) % 10;
            temp = (p1.val + temp) / 10;
            p1 = p1.next;
        } else if (temp != 0) {
            re.val = temp;
            temp = 0;
        }
        if (p1 != null || p2 != null || temp != 0) {
            re.next = new ListNode1(0);
            re = re.next;
        } else {
            re.next = null;
        }
    }
    return head;
}
// 优化
public static ListNode1 problem_pre(ListNode1 l1, ListNode1 l2) {
    ListNode1 head = new ListNode1(0);
    ListNode1 p1 = l1, p2 = l2, re = head;
    int temp = 0; // 进位
    while (p1 != null || p2 != null || temp != 0) {
        int sum = (p1 != null ? p1.val : 0)  + (p2 != null ? p2.val : 0) + temp;
        temp = sum / 10;
        re.next = new ListNode1(sum % 10);
        p1 = p1 != null ?  p1.next : null;
        p2 = p2 != null ?  p2.next : null;
    }
    return head.next;
}

不含重复字符的最长子串长度

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。 请注意，你的答案必须是子串的长度。
示例 1: 输入: “abcabcbb”。输出: 3。解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2: 输入: “bbbbb”。输出: 1。解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3: 输入: “pwwkew”。输出: 3。解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 

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
55
56
57
58
59
60
61
public static int problem(String strSrc) {
    if (strSrc.equals("") || strSrc.length() == 0 || strSrc.length() == 1) {
        System.out.println("源字符串<" + strSrc + ">的最长子串<" + strSrc + ">长度为 >> " + strSrc.length());
        return strSrc.length();
    }
    String subStr = "" + strSrc.charAt(0);
    String maxStr = subStr;
    int maxLen = maxStr.length();
    int count = 0;
    boolean flag;
    for (int i = 1; i < strSrc.length(); ) {
        int j = 0;
        flag = true;
        for (; j < subStr.length(); j++) {  // 和子串的全部字符比较
            if (strSrc.charAt(i) == subStr.charAt(j)) { // 有重复字符 回退 子串长度-1 位 当前字符为新子串 指针下一位
                count++;
                i = i - subStr.length() + 1;
                subStr = "" + strSrc.charAt(i);
                i += 1;
                flag = false;
                break;
            }
        }
        if (j == subStr.length() && flag && i < strSrc.length()) { // 比完没有重复字符  当前字符串加入字符集
            subStr = subStr + strSrc.charAt(i);
            maxStr = maxStr.length() < subStr.length() ? subStr : maxStr;
            maxLen = maxStr.length();
            i += 1;
        }
    }
    System.out.println("源字符串<" + strSrc + ">的最长子串<" + maxStr + ">长度为 >> " + maxLen);
    return maxLen;
}

public static int lengthOfLongestSubstring(String s) {
    if (s.equals("") || s.length() == 0 || s.length() == 1) {
        return s.length();
    }
    String subStr = "" + s.charAt(0);
    int maxLen = subStr.length();
    boolean flag;
    for (int i = 1; i < s.length(); i++) {
        int j = 0;
        flag = true;
        for (; j < subStr.length(); j++) {  // 和子串的全部字符比较
            if (s.charAt(i) == subStr.charAt(j)) { // 有重复字符 回退 子串长度-1个位置 取当前字符为新子串 指针下一位
                i = i - subStr.length() + 1;
                subStr = "" + s.charAt(i);
                i += 1;
                flag = false;
                break;
            }
        }
        if (j == subStr.length() && flag && i < s.length()) { // 比完没有重复字符  当前字符串加入字符集
            subStr = subStr + s.charAt(i);
            maxLen = maxLen > subStr.length() ? maxLen : subStr.length();
            i += 1;
        }
    }
    return maxLen;
}

找出字符串中最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：输入: “babad”。输出: “bab”。注意: “aba” 也是一个有效答案。
示例 2：输入: “cbbd”。输出: “bb”

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
public static String problem(String s) {
    String result = "";
    boolean dp[][] = new boolean[s.length()][s.length()];
    for(int i = 0; i < s.length(); i++){
        for(int j = 0; j < s.length(); j++){
            dp[i][j] = false;
        }
    }
    // 枚举所有子串长度
    for (int l = 0; l < s.length(); l++) {
        for (int i = 0; i < s.length(); i++) { // 枚举子串的起始位置 i
            int j = i + l; // 通过 j=i+l 得到子串的结束位置
            if (j >= s.length()) {
                break;
            }
            if (l == 0) {
                dp[i][j] = true;
            } else if (l == 1) {
                dp[i][j] = (s.charAt(i) == s.charAt(j));
            } else {
                dp[i][j] = (dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j));
            }
            // 判断回文串长度
            if(dp[i][j] && l + 1 > result.length()){
                result = s.substring(i, j + 1); // 取值为左闭右开区间 [ start, end )
            }
        }
    }
    return result;
}

将给定字符串按给定行数Z字排列

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。具体示例如下图所示。请你实现这个将字符串进行指定行数变换的函数： string convert(string s, int numRows);

image-20250622221010005

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
/*官方解答
按顺序遍历字符串 s；
res[i] += c： 把每个字符 c 填入对应行s_i；
i += flag： 更新当前字符 c 对应的行索引；
flag = - flag： 在达到 ZZ 字形转折点时，执行反向*/
public static String problem(String s, int numRows) {
    if(numRows < 2){
        return s;
    }
    List<StringBuilder> rows = new ArrayList<StringBuilder>();  // 每一行的字符数组
    for(int i = 0; i < numRows; i++) {
        rows.add(new StringBuilder());
    }
    int i = 0, flag = -1;
    for(char c : s.toCharArray()) { // 所有字符串
        rows.get(i).append(c); // 实际上 遍历了rows数组
        if(i == 0 || i == numRows - 1){ // 转折点 反向遍历
            flag = -flag;
        }
        i += flag;
    }
    StringBuilder res = new StringBuilder();
    for(StringBuilder row : rows) {
        res.append(row);
    }
    return res.toString();
}

字符串转整数的实现函数 atoi

请你来实现一个 atoi 函数，使其能将字符串转换成整数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：本题中的空白字符只包括空格字符 ‘ ‘ 。假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1: 输入: “42”。输出: 42。
示例 2: 输入: “ -42”。输出: -42
解释: 第一个非空白字符为 ‘-‘是一个负号。尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3: 输入: “4193 with words” 输出: 4193。解释: 转换截止于数字 ‘3’ ，因为它的下一个字符不为数字。
示例 4: 输入: “words and 987”。输出: 0。解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。因此无法执行有效的转换。
示例 5: 输入: “-91283472332”。输出: -2147483648。解释: 数字”-91283472332”超过32位有符号整数范围。返回 INT_MIN (−231) 。

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
public static int problem(String str) {
    if (str.length() == 0 || str.equals("")) {
        return 0;
    }
    int i = 0, flag = 0; // flag 表示有没有数字
    double target = 0;
    String numStr = "";
    for (; i < str.length(); i++) {
        if (str.charAt(i) == ' ' && numStr.length() == 0) { // 忽略有效字符前面的空格
            continue;
        }
        if (flag == 0 && (str.charAt(i) < '0' || str.charAt(i) > '9') 
            && (str.charAt(i) != '-' && str.charAt(i) != '+')) { // 排除第一个有效字符不是 + - 0到9的情况
                return 0;
        }
        if (flag == 0 && numStr.length() == 1 && (str.charAt(i) > '9' || str.charAt(i) < '0')) { 
            // + - 后面不是0-9的数字
            return 0;
        }
        if (flag == 1 && (str.charAt(i) > '9' || str.charAt(i) < '0')) { // 一串有效值后遇到了非数字字符
            break;
        }
        if (flag == 0 && (str.charAt(i) == '-' || str.charAt(i) == '+')) { // 第一个字符是 + -
            numStr = numStr + str.charAt(i);
        }
        if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
            flag = 1;
            numStr = numStr + str.charAt(i);
            target = target 10 + (str.charAt(i) - '0');
        }
    }
    if (!numStr.equals("") && numStr.charAt(0) == '-') {
        target = 0 - target;
    }
    if (target > Math.pow(2, 31) - 1 || target < Math.pow(-2, 31)) {
        return numStr.charAt(0) == '-' ? (int) Math.pow(-2, 31) : (int) Math.pow(2, 31);
    }
    return (int) target;
}

最大容量的容器

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。说明：你不能倾斜容器，且 n 的值至少为 2。
示例：输入：[1,8,6,2,5,4,8,3,7]。输出：49

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int problem(int[] height) {
    if (height == null || height.length <= 1) {
        return 0;
    }
    int bottomLen, target = 0;
    for (int i = 0; i < height.length - 1; i++) {
        for (int j = i + 1; j < height.length; j++) {
            bottomLen = j - i;
            int temp = bottomLen * Math.min(height[i], height[j]);
            target = Math.max(target, temp);
        }
    }
    return target;
}

罗马数字转整数

罗马数字包含以下七种字符:I，V，X，L，C，D和M。
字符（数值）对应关系：I（1）、V（5）、X（10）、L（50）、C（100）、D（500）、M（1000）
例如， 罗马数字 2 写做II，即为两个并列的 1。12 写做XII，即为X+II。 27 写做XXVII, 即为XX+V+II。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做IIII，而是IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为IX。这个特殊的规则只适用于以下六种情况：
I可以放在V(5) 和X(10) 的左边，来表示 4 和9。
X可以放在L(50) 和C(100) 的左边，来表示 40 和90。
C可以放在D(500) 和M(1000) 的左边，来表示 400 和900。
给定一个罗马数字，将其转换成整数。输入确保在 1到 3999 的范围内
示例 1: 输入:”III” 输出: 3
示例 2: 输入:”IV” 输出: 4
示例 3: 输入:”IX” 输出: 9
示例 4: 输入:”LVIII” 输出: 58 解释: L = 50, V= 5, III = 3。
示例 5: 输入:”MCMXCIV” 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static String problem(int num) {
    if (num <= 0) {
        return "";
    }
    String sub[] = {"I", "II", "III", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
    int cons[] = {1, 2, 3, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
    String target = "";
    for (int i = cons.length - 1; i >= 0; ) {
        if (num == 0) {
            break;
        }
        if (num / cons[i] == 0) { // 不能匹配当前了 则匹配较小的
            i--;
        }
        if (num / cons[i] != 0) { // 减去已经匹配的
            target = target + sub[i];
            num -= cons[i];
        }
    }
    return target;
}

数组中三数之和为0的三元组

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。
示例：给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[ [-1, 0, 1], [-1, -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
25
26
27
28
29
30
31
32
public static List<List<Integer>> problem8(int[] nums) {
    List<List<Integer>> re = new ArrayList<>();
    // 找出所有的三元组 [a, b, c] 对应的指针分别为 i j k
    int n = nums.length;
    Arrays.sort(nums);  // 从小到大排序
    for (int i = 0; i < nums.length; ++i) {
        if (i > 0 && nums[i] == nums[i - 1]) {//  跳过数组中的重复元素
            continue;
        }
        int k = n - 1; // c对应的指针初始指向数组的最右端
        for (int j = i + 1; j < nums.length; ++j) {
            if (j > i + 1 && nums[j] == nums[j - 1]) {//  跳过数组中的重复元素
                continue;
            }
            while (k > j && nums[i] + nums[j] + nums[k] > 0) {  // 保证 b 的指针在 c 的指针的左侧
                --k;
            }
            // 如果指针重合，随着 b增大 不再存在满足 a+b+c=0 并且 b < c 的 c
            if (j == k) {
                break;
            }
            if (nums[i] + nums[j] + nums[k] == 0) {
                List<Integer> list = new ArrayList<Integer>();
                list.add(nums[i]);
                list.add(nums[j]);
                list.add(nums[k]);
                re.add(list);
            }
        }
    }
    return re;
}

数组中与给定值最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：输入：nums = [-1,2,1,-4], target = 1 输出：2。解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：3 <= nums.length <= 10^3；-10^3 <= nums[i] <= 10^3；-10^4 <= target <= 10^4

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
public static int problem(int[] nums, int target) {
    // 每个三元组 [a, b, c] 对应的指针分别为 i j k
    Arrays.sort(nums);  // 从小到大排序
    int res = nums[0] + nums[1] + nums[2];
    if (nums.length == 3) { // 只有三位数
        return res;
    }
    if (res - target == 0) { // 前三位之和为target
        return target;
    }
    for (int i = 0; i < nums.length; ++i) {
        if (i > 0 && nums[i] == nums[i - 1]) { // 跳过数组中的重复元素
            continue;
        }
        int k = nums.length - 1; // c对应的指针初始指向数组的最右端
        int j = i + 1;
        while (k > j) { // 保证 b 的指针在 c 的指针的左侧
            int temp = nums[i] + nums[j] + nums[k];
            if (temp == target) {
                return target;
            }
            if (Math.abs(res - target) >= Math.abs(temp - target)) {
                res = temp;
            }
            
            if (temp > target) { // 当前和比目标值较大 第三个数减小 右往左
                k = k - 1;
                while (j < k && nums[k] == nums[k + 1]) { // 跳过数组中的重复元素
                    k = k - 1;
                }
            } else if (temp < target) { // 当前和比目标值较小 第二个数增大 左往右
                j = j + 1;
                while (j < k && nums[j] == nums[j - 1]) { // 跳过数组中的重复元素
                    j = j + 1;
                }
            }
        }
    }
    return res;
}

字母异位词分组

49. 字母异位词分组

问题描述：给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]

输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

解释：

  • 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
  • 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
  • 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:

输入: strs = [“”]

输出: [[“”]]

示例 3:

输入: strs = [“a”]

输出: [[“a”]]

提示：

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写字母
1
2
3
4
5
6
7
8
9
10
11
public List<List<String>> groupAnagrams(String[] strs) {
    HashMap<String, List<String>> map = new HashMap<>();
    for (int i = 0; i < strs.length; i++) {
        char[] temp = strs[i].toCharArray();
        Arrays.sort(temp); // 字符串排序
        List<String> list = map.getOrDefault(new String(temp), new ArrayList<>());
        list.add(strs[i]);
        map.put(new String(temp), list);
    }
    return new ArrayList<>(map.values());
}

反转每对括号间的子串

给出一个字符串 s（仅含有小写英文字母和括号）。请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。注意，结果中不应包含任何括号。
示例 1：输入：s = “(abcd)”。输出：”dcba”
示例 2：输入：s = “(u(love)i)”。输出：”iloveu”。解释：先反转子字符串 “love” ，然后反转整个字符串。
示例 3：输入：s = “(ed(et(oc))el)”。输出：”leetcode”。解释：先反转子字符串 “oc” ，接着反转 “etco” ，然后反转整个字符串。
提示：1 <= s.length <= 2000；s 中只有小写英文字母和括号

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
public static String reverseParentheses(String s) {
    StringBuilder sb = new StringBuilder();
    char[] arr = s.toCharArray();
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == '(') {
            stack.push(i);
        }
        if (arr[i] == ')') {
            reverse(arr, stack.pop() + 1, i - 1);
        }
    }
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] != ')' && arr[i] != '(') {
            sb.append(arr[i]);
        }
    }
    return sb.toString();
}

public static void reverse(char[] arr, int left, int right) {
    while (right > left) {
        char tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        right--;
        left++;
    }
}