Leetcode Top100题目和答案（面试必备）_leetcode题库

Leetcode Top100题目和答案（面试必备）

---

在面试准备过程中，LeetCode上的Top 100题目无疑是最受重视的资源之一。这些题目涵盖了算法、数据结构、动态规划、图论等多个领域，是检验编程能力和逻辑思维能力的绝佳工具。下面，我们将从LeetCode Top 100中精选几道题目，并给出相应的答案和解析。

1. 两数之和

---

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

答案：

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}
1
2
3
4
5
6
7
8
9
10
11

解题思路：
本题使用哈希表来存储数组中的元素及其索引。遍历数组，对于每个元素，计算其与目标值的差值，并检查哈希表中是否已存在该差值。若存在，则返回该差值对应的索引和当前元素的索引；若不存在，则将当前元素及其索引存入哈希表。

2. 两数相加

---

题目描述：
给定两个非空链表来表示两个非负整数。它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。将这两个数相加并返回一个新的链表。

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

示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8

答案：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0); // 虚拟头节点
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0; // 进位

    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;

        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;

        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }

    if (carry > 0) {
        curr.next = new ListNode(carry);
    }

    return dummyHead.next;
}

// ListNode类的定义
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
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

解题思路：
本题使用链表来模拟进位加法的过程。我们创建一个虚拟头节点，该节点不存储任何值，仅用于简化边界条件的处理。同时，我们定义两个指针p和q分别指向两个链表的头节点，以及一个指针curr指向虚拟头节点的下一个节点，即新链表的当前节点。我们还定义一个变量carry来保存进位。在遍历过程中，我们计算当前位的和sum，并将其对10取余得到当前位的值，然后更新进位carry为sum除以10的商。接着，我们创建一个新的节点，其值为sum的个位数，并将其连接到当前节点curr的下一个位置，然后更新curr指针。最后，如果遍历结束后仍有进位，我们需要将其添加到新链表的末尾。最后返回虚拟头节点的下一个节点，即新链表的头节点。

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

---

题目描述：
给定一个字符串，找出不含有重复字符的最长子串的长度。

示例：
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

答案：

public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    if (n == 0) return 0;

    int maxLength = 0, start = 0; // start表示当前子串的起始位置
    Set<Character> set = new HashSet<>(); // 使用集合来保存当前子串中的字符

    for (int i = 0; i < n; i++) {
        char curChar = s.charAt(i);
        if (set.contains(curChar)) { // 如果当前字符已经在集合中出现过
            set.remove(s.charAt(start)); // 移除起始位置的字符
            start++; // 起始位置后移
        }
        set.add(curChar); // 添加当前字符到集合中
        maxLength = Math.max(maxLength, i - start + 1); // 更新最长子串长度
    }
    return maxLength;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解题思路：
本题采用滑动窗口的思想，通过维护一个字符集合和一个滑动窗口来找到最长的不含重复字符的子串。我们遍历字符串中的每个字符，如果字符已经存在于集合中，说明出现了重复字符，此时需要移动窗口的起始位置，并更新集合中的字符。如果字符不存在于集合中，我们将其添加到集合中，并更新最长子串的长度。最终返回最长子串的长度即可。

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

---

题目描述：
给定两个按升序排列的有序数组nums1和nums2，请找出这两个有序数组的中位数。要求算法的时间复杂度为O(log(m+n))。

示例：
输入: nums1 = [1, 3], nums2 = [2]
输出: 2.00000
解释: 合并后的数组为 [1, 2, 3]，中位数为 2。

答案：

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int totalLength = nums1.length + nums2.length;
    if (totalLength % 2 == 1) {
        return (double) findKth(nums1, 0, nums2, 0, totalLength / 2 + 1);
    } else {
        int left = findKth(nums1, 0, nums2, 0, totalLength / 2);
        int right = findKth(nums1, 0, nums2, 0, totalLength / 2 + 1);
        return (left + right) / 2.0;
    }
}

private int findKth(int[] nums1, int start1, int[] nums2, int start2, int k) {
    if (start1 == nums1.length) return nums2[start2 + k - 1];
    if (start2 == nums2.length) return nums1[start1 + k - 1];
    if (k == 1) return Math.min(nums1[start1], nums2[start2]);

    int mid1 = (start1 + k / 2 - 1) < nums1.length ? nums1[start1 + k / 2 - 1] : Integer.MAX_VALUE;
    int mid2 = (start2 + k / 2 - 1) < nums2.length ? nums2[start2 + k / 2 - 1] : Integer.MAX_VALUE;

    if (mid1 < mid2) {
        return findKth(nums1, start1 + k / 2, nums2, start2, k - k / 2);
    } else {
        return findKth(nums1, start1, nums2, start2 + k / 2, k - k / 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

解题思路：
本题采用二分查找的思想来寻找两个有序数组的中位数。由于两个数组都是有序的，我们可以利用这个性质来减少搜索范围。我们可以将问题转化为在两个有序数组中找到第k小的数，其中k为(m+n)/2（m和n分别为两个数组的长度）。

5. 最长回文子串

---

题目描述：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

答案：

为了找到最长的回文子串，我们可以使用动态规划的方法。我们定义一个二维数组 dp，其中 dp[i][j] 表示从索引 i 到索引 j 的子串是否是回文串。然后，我们可以使用两个指针 i 和 j 来遍历字符串，并更新 dp 数组。

public String longestPalindrome(String s) {
    int n = s.length();
    if (n < 2) return s;
    
    String longest = "";
    boolean[][] dp = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (j - i + 1 > longest.length()) {
                    longest = s.substring(i, j + 1);
                }
            }
        }
    }
    return longest;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解题思路：
在动态规划的方法中，我们首先初始化 dp 数组。然后，我们从字符串的末尾开始遍历，并更新 dp 数组。对于 dp[i][j]，如果 s[i] == s[j] 并且子串 s[i+1:j-1] 也是回文串（或者 i 和 j 相邻），那么 s[i:j] 就是回文串。我们同时跟踪找到的最长回文子串的长度和位置。

6. 整数反转

---

题目描述：
给出一个 32 位的有符号整数，你需要将这个整数中的每个数字进行反转。

示例：
输入: 123
输出: 321

答案：

我们可以使用一个变量来记录反转后的数字，并遍历输入数字的每一位。

public int reverse(int x) {
    int reversed = 0;
    while (x != 0) {
        int digit = x % 10;
        x /= 10;
        if (reversed > Integer.MAX_VALUE/10 || (reversed == Integer.MAX_VALUE / 10 && digit > 7)) return 0; // 防止溢出
        if (reversed < Integer.MIN_VALUE/10 || (reversed == Integer.MIN_VALUE / 10 && digit < -8)) return 0; // 防止溢出
        reversed = reversed * 10 + digit;
    }
    return reversed;
}
1
2
3
4
5
6
7
8
9
10
11

解题思路：
在反转整数的过程中，我们需要考虑溢出的问题。由于Java中的整数类型是有符号的，并且范围是 -2^31 到 2^31 - 1，我们在每次将新的数字添加到 reversed 变量之前，需要检查是否会发生溢出。我们通过比较 reversed 和 Integer.MAX_VALUE / 10 以及 Integer.MIN_VALUE / 10 来确定是否会发生溢出，并同时考虑最后一位数字的情况。如果即将发生溢出，我们返回0作为结果。

7. 合并两个有序链表

---

题目描述：
给定两个按升序排列的链表，合并这两个链表并使新链表也是按升序排列的。

示例：
输入: 1->2->4, 1->3->4
输出: 1->1->2->3->4->4

答案：

我们可以使用迭代或递归的方法来合并两个链表。以下是迭代方法的实现：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0); // 创建一个哑节点作为结果链表的头部
    ListNode current = dummy; // current用于遍历结果链表

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    // 如果l1还有剩余节点，将它们添加到结果链表的末尾
    if (l1 != null) {
        current.next = l1;
    }
    // 如果l2还有剩余节点，将它们添加到结果链表的末尾
    if (l2 != null) {
        current.next = l2;
    }

    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
25
26

解题思路：
我们创建一个哑节点作为结果链表的头部，然后使用两个指针l1和l2分别遍历两个输入链表。在每一步中，我们比较两个链表的当前节点的值，将较小的节点添加到结果链表中，并移动对应的指针。当其中一个链表遍历完后，我们将另一个链表的剩余部分直接添加到结果链表的末尾。

8. 字符串转换整数 (atoi)

---

题目描述：
将字符串转换成一个整数(32位有符号整数)。

要求：

• 字符串中的数字可能包含前导空格，但是必须忽略它们。
• 字符串可能包含正负号。
• 字符串中的非数字字符（除了前导空格和正负号）必须被忽略。
• 如果字符串无法表示成32位有符号整数，则返回 INT_MAX 或 INT_MIN。

示例：
输入: “42”
输出: 42

输入: " -42"
输出: -42

输入: “4193 with words”
输出: 4193

输入: “words and 987”
输出: 0

答案：

为了处理这个问题，我们可以按照以下步骤编写代码：

public int myAtoi(String str) {
    str = str.trim(); // 去除前导空格
    int sign = 1; // 符号位，默认为正
    int index = 0; // 当前处理字符的索引
    int result = 0; // 转换结果

    // 处理符号位
    if (index < str.length() && (str.charAt(index) == '-' || str.charAt(index) == '+')) {
        sign = (str.charAt(index++) == '-') ? -1 : 1;
    }

    // 转换数字
    while (index < str.length() && Character.isDigit(str.charAt(index))) {
        int digit = str.charAt(index++) - '0'; // 字符转数字
        // 检查是否溢出
        if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && digit > 7)) {
            return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        result = result * 10 + digit;
    }

    return result * sign;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

解题思路：
我们首先去除字符串的前导空格，然后检查第一个非空格字符是否为符号位。接着，我们遍历字符串中的每个字符，将其转换为数字并累加到结果中。在每一步中，我们都检查是否会发生溢出。如果发生溢出，我们返回相应的最大或最小值。最后，我们返回符号位与结果的乘积作为最终结果。

9. 盛最多水的容器

---

题目描述：
给定一个长度为 n 的整数数组 height。有 n 条垂直线段，第 i 条线段的两个端点是 (i, 0) 和 (i, height[i])。找出其中的两条线，使得它们与 x 轴构成的容器可以容纳最多的水。

返回容器可以容纳的最多水的量。

示例：
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
解释: 在图中，容器的高度由较短的线段决定。在这个例子中，容器的高度是 1（第 1 条线段的高度）和 5（第 5 条线段的高度），宽度是 5-1=4。因此，最多可以容纳 41=4 升水。但是，我们可以找到一个更大的容器：第 2 条线段和第 5 条线段，高度为 5，宽度为 5-2=3。因此，最多可以容纳 53=15 升水。最终答案是 15 和 34（第 2 条线段和第 8 条线段构成）中的较大值，即 49。

答案：

为了解决这个问题，我们可以使用双指针法。一个指针从数组的开始指向最小的线段，另一个指针从数组的末尾指向最大的线段。我们计算这两个指针所指向的线段构成的容器的容量，并更新最大容量。然后，我们移动指向较短线段的指针，因为移动指向较长线段的指针不会使容器的容量增加（容器的容量由较短的线段决定）。

public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int maxArea = 0;
    
    while (left < right) {
        int currentArea = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, currentArea);
        
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxArea;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解题思路：
我们使用双指针从数组的两端开始。在每一步中，我们计算当前指针所指向的线段构成的容器的容量，并更新最大容量。然后，我们移动指向较短线段的指针，因为容器的容量由较短的线段决定。我们重复这个过程，直到两个指针相遇。

10. 移除元素

---

题目描述：
给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例：
输入: nums = [3,2,2,3], val = 3
输出: 2, nums = [2,2]
解释: 函数应该返回新的长度 2, 并且 nums 的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。

答案：

为了解决这个问题，我们可以使用双指针法。一个指针 i 用于遍历数组，另一个指针 j 用于记录不等于 val 的元素应该放置的位置。

public int removeElement(int[] nums, int val) {
    int j = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != val) {
            nums[j++] = nums[i];
        }
    }
    return j;
}
1
2
3
4
5
6
7
8
9

解题思路：
我们初始化两个指针 i 和 j 都指向数组的起始位置。然后，我们遍历数组 nums，对于每个元素 nums[i]，如果它不等于 val，则将其复制到 nums[j] 的位置，并将 j 增加 1。最后，j 的值就是移除所有等于 val 的元素后数组的新长度。注意，我们不需要将 j 之后的元素置为任何特定的值，因为题目没有要求考虑这些元素。

11. 盛最多水的容器（扩展版）

---

题目描述：
给定一个高度数组 height，表示一个容器中不同宽度下对应位置的高度。宽度从 0 到 n-1（其中 n 是数组 height 的长度）。找出这个容器能装下的最大水量，且容器左右两侧可以向外扩展（即容器的宽度可以大于 n-1）。但扩展的部分高度默认为 0。

示例：
输入: height = [1,8,6,2,5,4,8,3,7]
输出: 49
解释: 当容器的左右边界分别为索引 1 和 6 时（对应的高度分别为 8 和 8），此时容器能装下的水量最大，为 (6-1) * min(8, 8) = 5 * 8 = 40。同时，容器的左右两侧可以向外扩展，再增加 9 的容量（左侧扩展 1 格，右侧扩展 2 格，高度均为 0）。因此，总容量为 40 + 9 = 49。

解题思路：
我们可以首先处理基础的容器（即宽度为 n-1 的情况），使用双指针法来找到最大的容量。然后，考虑容器的扩展部分。由于扩展部分的高度默认为 0，我们只需要计算扩展的宽度即可。对于左侧扩展，我们可以从索引 0 开始，依次累加宽度直到遇到第一个非零的高度；对于右侧扩展，我们可以从索引 n-1 开始，做相同的处理。

答案：
（基础容器的答案部分略去，因为与标准版本类似）

public int maxAreaWithExpansion(int[] height) {
    int maxArea = maxAreaWithoutExpansion(height); // 调用基本版本的双指针法
    int leftExpansion = 0; // 左侧扩展的容量
    int rightExpansion = 0; // 右侧扩展的容量
    
    // 计算左侧扩展的容量
    for (int i = 0; i < height.length && height[i] == 0; i++) {
        leftExpansion += i + 1; // 累加宽度，因为高度为 0
    }
    
    // 计算右侧扩展的容量（与左侧类似，但方向相反）
    for (int i = height.length - 1; i >= 0 && height[i] == 0; i--) {
        rightExpansion += height.length - i; // 累加宽度
    }
    
    // 返回总容量
    return maxArea + leftExpansion + rightExpansion;
}

// ... （maxAreaWithoutExpansion 方法的实现与标准版本相同）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

12. 三数之和
    题目描述：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

示例：

输入: nums = [-1,0,1,2,-1,-4]
输出: [[-1,-1,2],[-1,0,1]]

解题思路：

为了解决这个问题，我们可以使用双指针法，但在这之前，我们需要先对数组进行排序。排序的目的是为了处理重复元素。

首先，固定一个数 nums[i]，然后使用两个指针 left 和 right 分别指向 i+1 和 n-1 的位置。接着，我们计算三个数的和 sum = nums[i] + nums[left] + nums[right]。

• 如果 sum == 0，那么找到了一个有效的三元组，我们将其添加到结果集中，并将 left 和 right 分别向中间移动一位，同时跳过所有重复的元素，以避免结果集中出现重复的三元组。
• 如果 sum < 0，说明当前的和太小了，需要增加和的值，因此将 left 向右移动一位。
• 如果 sum > 0，说明当前的和太大了，需要减少和的值，因此将 right 向左移动一位。

当 left 大于等于 right 时，说明对于当前固定的 nums[i]，已经不可能再找到满足条件的三元组了，此时将 i 向右移动一位，继续寻找。

答案：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); // 先对数组进行排序
        List<List<Integer>> result = new ArrayList<>();
        
        for (int i = 0; i < nums.length - 2; i++) {
            // 跳过重复元素
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            int left = i + 1;
            int right = nums.length - 1;
            
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    
                    // 跳过重复元素
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return result;
    }
}
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

13. 罗马数字转整数

---

题目描述：
罗马数字包含以下七种字符: I，V，X，L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
1
2
3
4
5
6
7
8

这些字符可以组合起来，表示罗马数字。例如，罗马数字 III 表示 3，IV 表示 4。罗马数字的一个规则是，较小的数字在较大的数字的右边则表示相加，如 IV = 5 + 1 = 6，但较小的数字在较大的数字的左边则表示相减，如 IV = 5 - 1 = 4。给定一个罗马数字字符串，将其转换为整数。

答案：

public int romanToInt(String s) {
    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    int sum = 0;
    for (int i = 0; i < symbols.length; i++) {
        while (s.startsWith(symbols[i])) {
            sum += values[i];
            s = s.substring(symbols[i].length());
        }
    }
    return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12

解题思路：
本题使用两个数组，一个存储罗马数字对应的整数值，另一个存储罗马数字的字符表示（按从大到小排列，并考虑相减的情况）。从大到小遍历这些字符表示，如果字符串以当前字符表示开始，则将对应的整数值加到结果中，并从字符串中去掉这部分。重复这个过程直到字符串为空。

14. 验证回文字符串

---

题目描述：
给定一个字符串，判断它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

答案：

public boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
        char leftChar = Character.toLowerCase(s.charAt(left));
        char rightChar = Character.toLowerCase(s.charAt(right));
        if (!Character.isLetterOrDigit(leftChar)) {
            left++;
        } else if (!Character.isLetterOrDigit(rightChar)) {
            right--;
        } else if (leftChar != rightChar) {
            return false;
        } else {
            left++;
            right--;
        }
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

解题思路：
本题使用双指针法，一个指针从字符串开头开始，另一个指针从字符串末尾开始。在每次迭代中，都跳过非字母和数字的字符，然后比较两个指针所指向的字符（忽略大小写）。如果两个字符不相等，则返回 false；如果两个字符相等，则继续向中间移动两个指针。当两个指针相遇或交叉时，说明已经检查完整个字符串，返回 true。

15. 合并两个有序数组

---

题目描述：

给你两个按非递减顺序排列的整数数组nums1和nums2，另有一个整数m和n，分别表示nums1和nums2中的元素个数。请你将nums2合并到nums1中，使合并后的数组同样按非递减顺序排列。

注意：你可以假设nums1有足够的空间（大小为m + n）来保存nums2中的元素。

答案：

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int p = m - 1; // nums1的尾部索引
    int q = n - 1; // nums2的尾部索引
    int k = m + n - 1; // 合并后数组的尾部索引

    while (p >= 0 && q >= 0) {
        if (nums1[p] > nums2[q]) {
            nums1[k] = nums1[p];
            p--;
        } else {
            nums1[k] = nums2[q];
            q--;
        }
        k--;
    }

    // 如果nums2还有剩余元素，则将它们复制到nums1的剩余位置
    while (q >= 0) {
        nums1[k] = nums2[q];
        q--;
        k--;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

解题思路：

本题可以使用双指针法。由于两个数组都是有序的，我们可以从两个数组的尾部开始比较，将较大的元素放入合并后数组的尾部，然后移动对应数组的指针。这样，当我们遍历完两个数组时，合并后的数组也就排好序了。

16. 最接近的三数之和

---

题目描述：

给定一个包含n个整数的数组nums 和 一个目标值target。找出nums中的三个整数，使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。

答案：

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums); // 先对数组进行排序
    int closestSum = nums[0] + nums[1] + nums[2]; // 初始化最接近的和为前三个数的和

    for (int i = 0; i < nums.length - 2; i++) {
        int left = i + 1;
        int right = nums.length - 1;

        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];

            // 更新最接近的和
            if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
                closestSum = sum;
            }

            // 根据当前和与目标值的差，移动指针
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                // 如果找到和等于target的三个数，则直接返回target（题目假设每组输入只存在唯一答案）
                return target;
            }
        }
    }

    return closestSum;
}
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

解题思路：

本题可以使用双指针法，在排序后的数组上进行遍历。对于固定的第一个数，使用双指针指向剩余部分的左右两端，通过计算三数之和与目标值的差来移动指针，同时更新最接近的和。当遍历完所有可能的组合后，返回最接近的和即可。

17. 电话号码的字母组合

---

题目描述：

给定一个数字字符串，按照如下映射关系，将字符串中的每个数字映射到一组英文小写字母：

• ‘2’ -> “abc”
• ‘3’ -> “def”
• ‘4’ -> “ghi”
• ‘5’ -> “jkl”
• ‘6’ -> “mno”
• ‘7’ -> “pqrs”
• ‘8’ -> “tuv”
• ‘9’ -> “wxyz”

现在，请你编写一个函数，将给定数字字符串中的所有可能字母组合按照字典序排列，并返回它们。

答案：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    private Map<Character, String> phoneMap;

    public Solution() {
        phoneMap = new HashMap<>();
        phoneMap.put('2', "abc");
        phoneMap.put('3', "def");
        // ... 其他映射关系
        phoneMap.put('9', "wxyz");
    }

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }
        backtrack(digits, 0, "", result);
        return result;
    }

    private void backtrack(String digits, int index, String current, List<String> result) {
        if (index == digits.length()) {
            result.add(current);
            return;
        }
        char digit = digits.charAt(index);
        String letters = phoneMap.get(digit);
        for (char letter : letters.toCharArray()) {
            backtrack(digits, index + 1, current + letter, result);
        }
    }
}
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

解题思路：

本题可以使用回溯算法来解决。首先，我们创建一个映射表来存储数字到字母的映射关系。然后，我们定义一个回溯函数，该函数接收当前的数字字符串、当前遍历到的索引、当前组合的字符串以及结果列表作为参数。在回溯函数中，如果索引等于数字字符串的长度，说明已经遍历完整个字符串，此时将当前组合添加到结果列表中。否则，我们取出当前索引对应的数字，并获取其对应的字母集合，然后遍历该集合，对于每个字母，将其添加到当前组合中，并递归调用回溯函数处理下一个索引。回溯完成后，我们需要将刚刚添加的字母从当前组合中移除，以便进行下一轮尝试。

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

---

题目描述：
给定一个链表，删除链表的倒数第 N 个节点，并且返回链表的头结点。

示例：
给定一个链表: 1->2->3->4->5, 和 N = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

解题思路：
要删除链表的倒数第N个节点，我们需要先找到这个节点的前一个节点。我们可以使用两个指针，一个快指针和一个慢指针。开始时，两个指针都指向链表的头结点。然后，快指针先向前走N步，之后快慢指针同时移动，当快指针到达链表末尾时，慢指针就指向了倒数第N个节点的前一个节点。

答案：

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 创建一个虚拟头结点，简化边界情况处理
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    // 初始化快慢指针都指向虚拟头结点
    ListNode fast = dummy;
    ListNode slow = dummy;
    
    // 快指针先向前走N步
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }
    
    // 快慢指针同时移动，直到快指针到达链表末尾
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // 删除倒数第N个节点
    slow.next = slow.next.next;
    
    // 返回链表的头结点（虚拟头结点的下一个节点）
    return dummy.next;
}

// 链表的定义
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
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

注意：在上面的答案中，我们创建了一个虚拟头结点dummy，这样做的目的是简化边界情况的处理。特别是当需要删除的是头结点时，如果不使用虚拟头结点，我们就需要特殊处理这种情况。使用虚拟头结点后，我们只需要统一处理慢指针slow的next指针即可。

19. 删除链表中重复的节点

---

题目描述：
给定一个已排序的链表的头节点 head，删除所有重复出现的节点，只保留每个元素出现一次的节点。

示例：
假设给定链表 1->1->2->3->3，则删除重复节点后返回链表 1->2->3。

答案：

首先，我们需要定义一个链表节点的数据结构，如下所示：

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
1
2
3
4
5

接下来是删除重复节点的函数：

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
        // 如果链表为空或只有一个节点，则无需删除
        return head;
    }
    
    ListNode dummy = new ListNode(0); // 创建一个哑节点作为结果链表的头
    dummy.next = head;
    ListNode current = dummy; // current指针用于遍历结果链表
    
    while (current.next != null && current.next.next != null) {
        if (current.next.val == current.next.next.val) {
            // 发现重复节点，找到重复节点的最后一个
            int valToDelete = current.next.val;
            while (current.next != null && current.next.val == valToDelete) {
                current.next = current.next.next;
            }
        } else {
            // 当前节点和下一个节点不重复，继续向后遍历
            current = current.next;
        }
    }
    
    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
25

解题思路：
由于链表是已排序的，所以重复的节点一定相邻。我们可以使用两个指针遍历链表，一个指针current用于维护结果链表的当前节点，另一个隐式的指针（通过current.next和current.next.next）用于检查当前节点和下一个节点是否重复。当发现重复节点时，将current.next指针移动到重复节点序列的最后一个节点的下一个节点，从而跳过所有重复节点。如果当前节点和下一个节点不重复，则current指针向后移动一位。最终，current指针会停在结果链表的最后一个节点，我们返回dummy.next作为结果链表的头节点。

20. 有效的括号

---

题目描述：

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

示例：

• 输入: s = "()[]{}"

• 输出: true

• 输入: s = "(][)"

• 输出: false

答案：

为了判断一个括号字符串是否有效，我们可以使用栈这种数据结构。遍历输入的字符串，当我们遇到左括号时，我们将其对应的右括号压入栈中；当我们遇到右括号时，我们检查栈顶的元素是否与之匹配。如果匹配，则将栈顶元素弹出；如果不匹配或者栈为空，则说明字符串无效。

以下是Java实现的代码：

import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else if (stack.isEmpty() || stack.pop() != c) {
                // 如果遇到右括号但栈为空，或者栈顶元素与当前右括号不匹配，则返回false
                return false;
            }
        }
        // 如果遍历完字符串后栈为空，则说明所有括号都匹配成功
        return stack.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

解题思路：

首先，我们遍历输入的字符串。对于每个字符，我们检查它是左括号还是右括号。

• 如果是左括号，我们将其对应的右括号压入栈中。
• 如果是右括号，我们检查栈顶的元素是否与之匹配。如果匹配，我们将栈顶元素弹出；如果不匹配，则说明字符串无效，直接返回false。

遍历结束后，如果栈为空，则说明所有括号都找到了匹配的另一半，字符串是有效的；否则，字符串无效。

21. 反转链表

---

题目描述：

给定一个单链表的头节点 head，请编写一个函数来反转这个链表，并返回反转后链表的头节点。

示例：

• 输入: head = 1->2->3->4->5
• 输出: 5->4->3->2->1

答案：

为了反转链表，我们需要使用迭代或递归的方法。这里我们使用迭代方法，通过三个指针 prev、curr 和 next 来追踪链表中的节点。

以下是Java实现的代码：

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next; // 保存下一个节点
            curr.next = prev; // 反转当前节点
            prev = curr; // 移动prev
            curr = nextTemp; // 移动curr
        }
        return prev; // prev将变为新的头节点
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

解题思路：

首先，我们定义三个指针：prev 初始化为 null（反转链表的头节点），curr 初始化为原始链表的头节点 head，以及 nextTemp 用于临时存储 curr 的下一个节点。

然后，我们进入一个循环，直到 curr 为 null（即遍历完整个链表）。在每次循环中，我们执行以下步骤：

1. 保存 curr 的下一个节点到 nextTemp，因为下一步我们将改变 curr.next 的指向。
2. 将 curr.next 指向 prev，实现反转。
3. 将 prev 移动到 curr。
4. 将 curr 移动到 nextTemp，继续处理链表中的下一个节点。

循环结束后，prev 将指向新的头节点（原始链表的尾节点），我们返回 prev 即可。

22. 有效的数独

---

题目描述：

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个 3x3 的子数独（共 9 个）里只能出现一次。

示例：

有效的数独：

[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
1
2
3
4
5
6
7
8
9
10
11

无效的数独：

[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","5","9",".",".","."],
  [".",".",".",".","8",".",".","7","9"]
]
1
2
3
4
5
6
7
8
9
10
11

（注意：在这个示例中，同一行中存在两个数字 8，因此它是无效的。）

答案：

我们可以使用三个 9x1 的数组来分别记录每一行、每一列以及每一个 3x3 的子数独中出现的数字。

以下是Java实现的代码：

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        // 初始化三个 9x1 的数组来记录行、列和 3x3 子数独的状态
        boolean[][] row = new boolean[9][9];
        boolean[][] col = new boolean[9][9];
        boolean[][][] box = new boolean[3][3][9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char num = board[i][j];
                if (num == '.') continue; // 跳过空格

                int n = num - '1'; // 转换为 0-8 的索引
                int boxIndexRow = i / 3; // 计算 3x3 子数独的行索引
                int boxIndexCol = j / 3; // 计算 3x3 子数独的列索引

                // 检查当前数字在行、列和 3x3 子数独中是否已经出现过
                if (row[i][n] || col[j][n] || box[boxIndexRow][boxIndexCol][n]) {
                    return false;
                }

                // 标记当前数字在行、列和 3x3 子数独中出现过
                row[i][n] = true;
                col[j][n] = true;
                box[boxIndexRow][boxIndexCol][n] = true;
            }
        }

        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
25
26
27
28
29
30
31

解题思路：

在这个Java实现中，我们使用了三个二维数组（row, col, box）来跟踪数独中每个位置（行、列、3x3子数独）的数字是否已经出现过。我们遍历数独中的每个位置，并跳过空格（‘.’）。对于每个非空格字符，我们将其转换为0-8的索引（因为数字是1-9），并计算它所在的3x3子数独的行和列索引。

然后，我们检查这个数字在其所在的行、列和3x3子数独中是否已经出现过。如果它已经出现过，则数独无效，我们返回false。否则，我们在三个数组中标记这个数字已经出现过，并继续检查下一个位置。

如果遍历完整个数独后都没有发现重复的数字，则数独有效，我们返回true。

这个解决方案的时间复杂度是O(1)，因为它只遍历了数独中的固定数量的位置（9x9=81个）。空间复杂度也是O(1)，因为我们只使用了固定大小的数组来存储状态。这里的“O(1)”意味着算法的性能不随输入规模的增长而增长，而是保持不变。在这个问题中，输入规模始终是9x9的数独，所以这种描述是合适的。

23. 合并K个升序链表

---

题目描述：

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

请你将所有链表合并成一个升序链表并返回。

答案：

首先，我们需要定义一个链表节点的数据结构。在Java中，链表节点可以定义如下：

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
1
2
3
4
5

接下来，我们可以使用最小堆（优先队列）来解决这个问题。我们将每个链表的头节点放入最小堆中，并根据节点的值进行排序。然后，我们不断地从堆中取出最小的节点，并将其添加到结果链表中，同时将该节点的下一个节点（如果存在）添加到堆中。这个过程会一直持续到堆为空为止。

import java.util.PriorityQueue;

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }

    // 使用最小堆（优先队列）来存储链表节点
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);

    // 将每个链表的头节点添加到最小堆中
    for (ListNode node : lists) {
        if (node != null) {
            pq.offer(node);
        }
    }

    ListNode dummy = new ListNode(0); // 虚拟头节点
    ListNode curr = dummy;

    // 从最小堆中取出节点，并构建结果链表
    while (!pq.isEmpty()) {
        ListNode minNode = pq.poll();
        curr.next = minNode;
        curr = curr.next;

        // 如果当前节点的下一个节点不为空，则将其添加到最小堆中
        if (minNode.next != null) {
            pq.offer(minNode.next);
        }
    }

    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
25
26
27
28
29
30
31
32
33
34

解题思路：

本题的关键在于如何有效地合并多个有序链表。由于每个链表都是有序的，我们可以利用最小堆（优先队列）来始终选择当前所有链表中的最小节点，从而确保合并后的链表也是有序的。

我们首先将每个链表的头节点添加到最小堆中。然后，我们不断地从堆中取出最小的节点，并将其添加到结果链表中。同时，我们还需要将该节点的下一个节点（如果存在）添加到堆中，以便后续选择。这个过程会一直持续到堆为空为止，此时我们已经合并了所有的链表。

最后，我们返回结果链表的头节点即可。需要注意的是，由于我们使用了虚拟头节点，所以返回的是虚拟头节点的下一个节点。

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

---

题目描述：

在一个未排序的整数数组 nums 中，找到第 k 个最大的元素。请注意，你可以假设 k 总是有效的，即 1 ≤ k ≤ 数组的长度。

答案：

为了找到数组中第K个最大的元素，我们可以使用最小堆（优先队列）来解决这个问题。我们将数组中的前K个元素放入最小堆中，并维护堆的大小为K。接下来，我们遍历数组的剩余元素，对于每个元素，如果它大于堆顶元素（即当前K个最大元素中的最小者），我们就弹出堆顶元素，并将当前元素加入堆中。

在遍历完整个数组后，堆顶元素就是第K个最大的元素。

以下是相应的Java代码实现：

import java.util.PriorityQueue;

public int findKthLargest(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k < 1 || k > nums.length) {
        throw new IllegalArgumentException("Invalid input for nums or k");
    }

    // 使用最小堆（优先队列）来存储元素
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); // 注意这里是比较器是降序排列

    // 将前K个元素加入最小堆
    for (int i = 0; i < k && i < nums.length; i++) {
        pq.offer(nums[i]);
    }

    // 遍历数组的剩余元素
    for (int i = k; i < nums.length; i++) {
        // 如果当前元素大于堆顶元素，则弹出堆顶元素，并将当前元素加入堆中
        if (nums[i] > pq.peek()) {
            pq.poll();
            pq.offer(nums[i]);
        }
    }

    // 堆顶元素即为第K个最大的元素
    return pq.peek();
}
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

解题思路：

本题要求找到数组中第K个最大的元素。由于数组未排序，我们需要一种高效的方法来确定第K大的元素。由于我们只关心前K大的元素，因此可以使用最小堆来维护这些元素。

首先，我们将数组的前K个元素加入最小堆中。由于堆的性质，堆顶元素总是最小的。然后，我们遍历数组的剩余元素，对于每个元素，如果它大于堆顶元素，说明它是前K大的元素之一，因此我们可以弹出堆顶元素，并将当前元素加入堆中。

遍历完整个数组后，堆中剩下的元素就是前K大的元素，堆顶元素即为第K个最大的元素。

这种方法的时间复杂度为O(NlogK)，其中N是数组的长度。在最坏的情况下，我们可能需要遍历整个数组，并将每个元素与堆顶元素进行比较和可能的替换操作，而堆的插入和删除操作的时间复杂度为O(logK)。因此，总的时间复杂度为O(NlogK)。

25. 排序链表

---

题目描述：

给定一个单链表，将其按升序排序。

答案：

为了对链表进行排序，我们可以使用多种算法，但在这里我们将使用一种基于归并排序的变体，因为归并排序在处理链表时非常有效，其空间复杂度可以通过迭代的方式降低到O(1)。

归并排序的基本思路是将链表不断拆分为更小的部分，直到每个部分只包含一个节点，然后合并这些部分，并在合并时对它们进行排序。但是，由于链表只能从头到尾遍历，我们不能直接在原地进行拆分。因此，我们需要一个辅助函数来递归地将链表拆分为两个大致相等的部分，并对它们进行排序和合并。

以下是相应的Java代码实现：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    // 使用快慢指针找到链表的中点
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 拆分链表为两个子链表
    ListNode secondHalf = slow.next;
    slow.next = null; // 断开链表
    
    // 递归地对两个子链表进行排序
    ListNode left = sortList(head);
    ListNode right = sortList(secondHalf);
    
    // 合并两个已排序的子链表
    return mergeLists(left, right);
}

private ListNode mergeLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0); // 创建一个哑节点作为结果链表的头部
    ListNode tail = dummy; // tail用于跟踪结果链表的尾部
    
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    
    // 如果l1或l2中还有剩余元素，将它们连接到结果链表的末尾
    if (l1 != null) {
        tail.next = l1;
    }
    if (l2 != null) {
        tail.next = l2;
    }
    
    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
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

解题思路：

本题要求我们对一个单链表进行排序。由于链表不支持像数组那样的随机访问，我们不能直接使用像快速排序或归并排序这样的比较排序算法的直接版本。但是，我们可以利用归并排序的“分而治之”策略，通过递归地将链表拆分为更小的部分，并对这些部分进行排序和合并，来实现链表的排序。

首先，我们使用快慢指针技巧来找到链表的中点，并将链表拆分为两个子链表。然后，我们递归地对这两个子链表进行排序。最后，我们合并这两个已排序的子链表，得到最终的排序结果。

在合并两个已排序的子链表时，我们维护一个哑节点作为结果链表的头部，并使用一个尾指针来跟踪结果链表的尾部。我们比较两个子链表的头节点，将较小的节点添加到结果链表的末尾，并移动相应的指针。当其中一个子链表遍历完时，我们将另一个子链表的剩余部分直接连接到结果链表的末尾。最后，我们返回去掉哑节点后的结果链表。

这种方法的时间复杂度为O(NlogN)，其中N是链表的长度。这是因为我们每次都将链表拆分为两个大致相等的部分，所以递归的深度为O(logN)。在合并两个已排序的子链表时，我们最多需要遍历N个节点。因此，总的时间复杂度为O(NlogN)。空间复杂度为O(logN)，这是由递归调用栈的最大深度决定的。但是，如果我们使用迭代的方式来实现归并排序，可以将空间复杂度降低到O(1)。

26. 删除排序数组中的重复项

---

题目描述：
给定一个排序数组nums，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。

答案：

public int removeDuplicates(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    int index = 0; // 当前不重复元素应该存放的索引
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] != nums[index]) {
            index++;
            nums[index] = nums[i];
        }
    }
    return index + 1; // 返回新数组的长度
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

解题思路：
由于数组已经排序，重复的元素一定相邻。因此，我们可以使用双指针法来解决这个问题：一个指针指向当前不重复元素应该存放的位置（index），另一个指针用于遍历整个数组。当我们遇到一个新元素（即与前一个元素不同）时，我们将它放到index指向的位置，并将index加一。最后，返回index + 1即为新数组的长度。

27. 移除元素（扩展版，原地操作）

---

题目描述：
给定一个数组nums和一个值val，你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。元素的顺序可以改变。

答案：

public int removeElement(int[] nums, int val) {
    int index = 0; // 当前不等于val的元素应该存放的索引
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != val) {
            nums[index] = nums[i];
            index++;
        }
    }
    return index; // 返回新数组的长度
}
1
2
3
4
5
6
7
8
9
10

解题思路：
这个问题与删除排序数组中的重复项类似，但我们需要移除的是所有等于特定值val的元素。我们仍然可以使用双指针法，但这次不需要数组是排序的。一个指针index指向当前不等于val的元素应该存放的位置，另一个指针i用于遍历整个数组。当我们遇到一个不等于val的元素时，我们将其放到index指向的位置，并将index加一。由于我们不需要保持元素的顺序，所以这种方法是可行的。最后，返回index即为新数组的长度。

28. 实现 strStr() 函数

---

题目描述：

实现 strStr() 函数。

给定一个字符串 haystack 和一个字符串 needle，在 haystack 字符串中查找 needle 字符串出现的第一个位置 (索引)。如果不存在，则返回 -1。

答案：

public int strStr(String haystack, String needle) {
    if (needle.isEmpty()) {
        return 0; // 空字符串在任何字符串中都从索引0开始
    }
    
    int hLen = haystack.length();
    int nLen = needle.length();
    
    // haystack长度小于needle长度时，needle不可能在haystack中出现
    if (hLen < nLen) {
        return -1;
    }
    
    // 使用双指针法遍历haystack字符串
    for (int i = 0; i <= hLen - nLen; i++) {
        int j;
        for (j = 0; j < nLen; j++) {
            if (haystack.charAt(i + j) != needle.charAt(j)) {
                break; // 当前字符不匹配，跳出内层循环
            }
        }
        if (j == nLen) {
            return i; // 找到了完整的needle字符串，返回起始索引
        }
    }
    
    return -1; // 没有找到needle字符串
}
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

解题思路：

为了解决这个问题，我们可以使用双指针法。一个指针i用于遍历haystack字符串，另一个指针j用于遍历needle字符串。在遍历过程中，我们比较两个指针所指向的字符是否相等。如果相等，则继续比较下一个字符；如果不相等，则停止内层循环，并将外层循环的指针i向后移动一位，重新开始比较。当内层循环结束时，我们检查j是否等于needle的长度nLen，如果是，则说明我们找到了完整的needle字符串，返回当前的i作为起始索引；否则，继续外层循环的遍历。如果遍历完整个haystack字符串都没有找到needle，则返回-1。

29. 两数相除

---

题目描述：

给定两个整数 dividend 和 divisor，将两数相除并返回商。

注意：

• 被除数 dividend 可能是负数，除数 divisor 不能为 0。
• 要求结果保留整数部分，对结果向零取整。

答案：

public int divide(int dividend, int divisor) {
    // 处理被除数为最小负整数，除数为-1的情况，此时结果会溢出
    if (dividend == Integer.MIN_VALUE && divisor == -1) {
        return Integer.MAX_VALUE;
    }
    
    // 定义结果的符号
    int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
    
    // 取绝对值进行运算，避免溢出
    long absDividend = Math.abs((long)dividend);
    long absDivisor = Math.abs((long)divisor);
    
    int result = 0;
    while (absDividend >= absDivisor) {
        long temp = absDivisor;
        long multiple = 1;
        
        // 使用左移操作找到不大于absDividend的最大倍数
        while (absDividend >= (temp << 1)) {
            temp <<= 1;
            multiple <<= 1;
        }
        
        // 更新被除数和结果
        absDividend -= temp;
        result += multiple;
    }
    
    // 返回带有符号的结果
    return result * sign;
}
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

解题思路：

这个问题主要需要考虑两个点：除法的符号和溢出问题。

1. 符号处理：结果的符号取决于被除数和除数的符号是否相同。如果相同，则结果为正；如果不同，则结果为负。
2. 溢出处理：由于Java中int类型的范围是-2^31到231-1，当被除数为Integer.MIN_VALUE（-2^31）且除数为-1时，结果会溢出。因此，我们需要特判这种情况，直接返回Integer.MAX_VALUE。

接下来，为了避免溢出，我们将被除数和除数都转换为long类型，并取它们的绝对值进行运算。

我们使用了一个循环来模拟手动的长除法。在循环中，我们使用一个临时变量temp来保存当前的除数，并使用一个multiple变量来记录倍数。我们通过不断将temp左移（即乘以2）来找到不大于absDividend的最大倍数，并更新multiple。然后，我们从absDividend中减去这个最大的倍数，并将result加上multiple。这个过程一直持续到absDividend小于absDivisor为止。

最后，我们将result乘以符号，并返回结果。

30. 搜索旋转排序数组

---

题目描述：

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

例如，数组 [0,0,1,2,2,5,6] 在点 3 处旋转，变为 [0,0,1,2,5,6,2]。

搜索一个给定的目标值 target，如果数组中存在这个目标值，则返回它的索引，否则返回 -1。

你可以假设数组中不存在重复的元素。

答案：

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        }

        // 判断左半部分是否有序
        if (nums[left] <= nums[mid]) {
            // 如果目标值在左半部分范围内
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // 如果目标值在右半部分范围内
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    // 没有找到目标值
    return -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

解题思路：

这个问题是一个变种的二分查找问题。由于数组是旋转排序的，我们可以利用这个性质来缩小搜索范围。

首先，我们定义两个指针left和right，分别指向数组的起始和末尾。然后，我们进入循环，直到left大于right为止。

在每次循环中，我们首先计算中间索引mid。然后，我们检查nums[mid]是否等于目标值target，如果是，则直接返回mid。

接下来，我们检查左半部分（从left到mid）是否有序。如果有序，我们检查目标值是否在这个范围内。如果是，我们将right更新为mid - 1，继续在左半部分搜索；否则，我们将left更新为mid + 1，在右半部分搜索。

如果左半部分不是有序的（即右半部分是有序的），我们执行类似的操作，但是方向相反。

通过这种方式，我们可以不断缩小搜索范围，直到找到目标值或者确定目标值不存在于数组中。

这个算法的时间复杂度是O(log n)，其中n是数组的长度，因为每次循环我们都将搜索范围减半。

先写30道题目吧，如需后续哪道题目的答案和解题思路，可以在评论区跟博主互动。

31. 搜索插入位置

32. 搜索旋转排序数组 II

33. 验证二叉搜索树

34. 二叉树中序遍历

35. 二叉搜索树的最小绝对差

36. 二叉搜索树的最近公共祖先

37. 序列化和反序列化二叉树

38. 路径总和

39. 路径总和 II

40. 平衡二叉树

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

42. 接雨水

43. 字符串相乘

44. 通配符匹配

45. 跳跃游戏

46. 跳跃游戏 II

47. 旋转图像

48. 矩阵置零

49. 矩阵中的最长递增路径

50. 字符串的排列

51. N皇后

52. 最小路径和

53. 单词接龙

54. 螺旋矩阵

55. 螺旋矩阵 II

56. 插入区间

57. 区间和的个数

58. 单调递增的数字

59. 滑动窗口的最大值

60. 不同的二叉搜索树

61. 不同的子序列

62. 不同的子序列 II

63. 乘积最大子数组

64. 股票的最大利润

65. 股票的最大利润（含冷冻期）

66. 加一

67. 二进制求和

68. 文本左右对齐

69. K 个非重叠子数组的最大和

70. 爬楼梯

71. 剪绳子

72. 编辑距离

73. 矩阵中的最短路径

74. 搜索二维矩阵

75. 颜色分类

76. 最小覆盖子串

77. 组合总和

78. 组合总和 II

79. 单词搜索

80. 单词搜索 II

81. 路径总和 III

82. 复制带随机指针的链表

83. 删除排序链表中的重复元素 II

84. 柱状图中最大的矩形

85. 链表中的节点每 k 个一组翻转

86. 分隔链表

87. 复原 IP 地址

88. 合并两个有序链表（扩展版，含重复元素）

89. 格雷编码

90. 子集 II

91. 解码方法

92. 反转链表 II

93. 复原 IP 地址（扩展版）

94. 二叉树的中序遍历（扩展版，使用栈）

95. 独特的电子邮件地址

96. 不同的二叉搜索树 II

97. 交错字符串

98. 验证二叉树的前序遍历序列

99. 滑动窗口的最大值（扩展版，使用双端队列）

100. 最小路径和（扩展版，含障碍物）

以上列出的题目涵盖了从基础数据结构（如数组、链表、二叉树）到动态规划、回溯、滑动窗口等多种算法和技巧的考察。通过练习这些题目，可以有效地提升编程能力和算法思维。