推荐网站

Hello 算法：学习数据结构与算法基础

代码随想录：按照顺序刷题

本文的序号是在力扣题库中的题号

注意事项

  1. 为了避免大数越界，取中值时采用 m = i + (j - i)/2 来计算中点，而不是 m = (i + j)/2 。
  2. 递归和和迭代是编程方法，往往递归更简洁，迭代更易于理解；分治、回溯、动态规划和贪心是算法。

数组

209长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

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

示例 3：

1
2
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int minSubArrayLen(int target, int[] nums) {
    // 头尾双指针，比较大小
    int result = nums.length + 1;
    int sum = 0;
    int i = 0;
    for (int j = 0; j < nums.length; j++) {
        sum += nums[j];
        while (sum >= target) {
            result = Math.min(result, j - i + 1);
            sum -= nums[i++];
        }
    }
    return result == nums.length + 1 ? 0 : result;
}

链表

注意

  1. 涉及到对链表节点中的的增删改操作，使用虚拟头节点，如果只是查询，则不需使用。同时，在增删改操作中，如果使用递归，则不需要虚拟头节点，如果使用迭代，则需要。
  2. 链表问题常考虑使用双指针法来解决，例如寻找距离尾部第 K 个节点、寻找环入口、寻找公共尾部入口等。

203移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

img

1
2
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

1
2
输入：head = [], val = 1
输出：[]

示例 3：

1
2
输入：head = [7,7,7,7], val = 7
输出：[]
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
// 方式一:递归
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }
}
// 方式二:迭代
// 使用虚拟头节点可以避免对头结点的单独判断
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null) {
            if (temp.next.val == val) {
                temp.next = temp.next.next;
            } else {
                temp = temp.next;
            }
        }
        return dummyHead.next;
    }
}
// 不使用虚拟头节点的情况
public ListNode removeElements(ListNode head, int val) {
    // 需要特殊处理头节点
    while (head != null && head.val == val) {
        head = head.next;  // 头节点需要单独处理
    }
    
    if (head == null) return null;
    
    ListNode temp = head;
    while (temp.next != null) {
        if (temp.next.val == val) {
            temp.next = temp.next.next;
        } else {
            temp = temp.next;
        }
    }
    return head;
}

206反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

img

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,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
// 方式一:递归
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}
// 方式二:迭代
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

步骤图解

递归

以反转 1->2->3 为例：

初始状态：

1
1 -> 2 -> 3 -> null

递归到底：

1
2
3
1 -> 2 -> 3 -> null
     ↑
    head (3的next是null，返回3)

回溯第一步（处理节点2）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1 -> 2 -> 3 -> null
     ↑    ↑
    head next

head.next.next = head  // 3.next = 2
1 -> 2 -> 3 -> 2 (形成环)
     ↑    ↑
    head next

head.next = null       // 2.next = null
1 -> 2 -> null  ← 3
     ↑         
    head

返回 newHead = 3

回溯第二步（处理节点1）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1 -> 2 -> null  ← 3
↑    ↑
head next

head.next.next = head  // 2.next = 1
1 -> 2 -> 1 (形成环)
↑    ↑
head next

head.next = null       // 1.next = null
null ← 1 ← 2 ← 3
       ↑
      head

返回 newHead = 3

最终结果

1
2
null ← 1 ← 2 ← 3
        (反转完成)
迭代

初始状态

1
2
3
4
5
6
7
prev = null
curr = 1
next = 2

[null]   [1] -> [2] -> [3] -> [4] -> [5] -> null
  ↑       ↑      ↑
 prev    curr   next

第一步操作

1
2
3
4
5
6
7
8
1. 保存next (2)
2. curr.next = prev (1指向null)
3. prev = curr (prev移动到1)
4. curr = next (curr移动到2)

[null] <- [1]   [2] -> [3] -> [4] -> [5] -> null
           ↑     ↑      ↑
          prev  curr   next

第二步操作

1
2
3
[null] <- [1] <- [2]   [3] -> [4] -> [5] -> null
                 ↑     ↑      ↑
                prev  curr   next

继续直到完成

1
2
3
[null] <- [1] <- [2] <- [3] <- [4] <- [5]
                                      ↑
                                     prev

24两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

img

1
2
输入：head = [1,2,3,4]
输出：[2,1,4,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
// 方式一:递归
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
}
// 方式二:迭代
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            // 因为是要交换两个节点，所以这里有两个
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            // temp每次向后移,选择node1是因为此时node1已在node2之后
            temp = node1;
        }
        return dummyHead.next;
    }
}

步骤图解

递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
第1层：swapPairs(1)
  第2层：swapPairs(3)
    第3层：swapPairs(null)  // 3.next = 4，4.next = null，所以传入的是null
    第3层返回：null
    
  第2层执行：
    head = 3, newHead = 4
    head.next = swapPairs(4.next) = swapPairs(null) = null  // 3.next = null
    newHead.next = head  // 4.next = 3
    return newHead  // 返回 4 -> 3 -> null
    
  第2层返回：4 -> 3 -> null

第1层执行：
  head = 1, newHead = 2
  head.next = swapPairs(2.next) = swapPairs(3) 得到的 4->3->null  // 1.next = 4
  newHead.next = head  // 2.next = 1
  return newHead  // 返回 2 -> 1 -> 4 -> 3 -> null

面试题 02.07. 链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

示例 1：

img

1
2
3
4
5
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
1
2
3
4
5
6
7
8
9
10
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }
}

142环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

示例 1：

img

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    // 两次相遇，追击问题，具体解析见LeetCode的解析
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}
// 解析：
// 采用快慢双节点的方法
// 第一次追击:fast = 2 * slow;两节点相遇时:fast = slow + n * b;可得slow = n * b;
// 第二次追击:此时fast从head开始,slow仍停留在第一次两节点相遇处,两节点同时走,当再次相遇时,slow = a + n * b,快慢节点此时都在环起始处

哈希表

242有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。

示例 1:

1
2
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

1
2
输入: s = "rat", t = "car"
输出: false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isAnagram(String s, String t) {
        int len1 = s.length(), len2 = t.length();
        if (len1 != len2)
            return false;
        HashMap<Character, Integer> dic = new HashMap<>();
        for (int i = 0; i < len1; i++) {
            dic.put(s.charAt(i) , dic.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (int i = 0; i < len2; i++) {
            dic.put(t.charAt(i) , dic.getOrDefault(t.charAt(i), 0) - 1);
        }
        for (int val : dic.values()) {
            if (val != 0)
                return false;
        }
        return true;
    }
}

349两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

1
2
3
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
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 {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 使用HashSet来存储结果（自动去重）
        Set<Integer> resultSet = new HashSet<>();
        // 将nums2转换为HashSet，便于快速查找
        Set<Integer> set2 = new HashSet<>();
        for (int num : nums2) {
            set2.add(num);
        }
        // 遍历nums1，检查元素是否在set2中
        for (int num : nums1) {
            // 只有在set中才有contains方法
            if (set2.contains(num)) {
                resultSet.add(num);
            }
        }
        // 将Set转换为数组
        int[] result = new int[resultSet.size()];
        int index = 0;
        for (int num : resultSet) {
            // 如果是ArrayList的话,可以直接add;但此时要求的返回值是Java自带的数组,没有add方法!
            result[index++] = num;
        }
        return result;
    }
}

202快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

1
2
3
4
5
6
7
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
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 boolean isHappy(int n) {
        // 数学上可以证明只要结果不等于1结果一定是遇到了环
        if(n == 0){
            return false;
        }
        Set<Integer> res = new HashSet<>();
        while(n != 1 && !res.contains(n)){
            res.add(n);
            n = sumOfSquare(n);
        }
        return n == 1;
    }
    private int sumOfSquare(int n){
        int temp = 0;
        while(n > 0){
            int num = n%10;
            temp += num * num;
            n = n/10;
        }
        return temp;
    }
}

454四数相加 II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

1
2
3
4
5
6
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> countAB = new HashMap<Integer, Integer>();
        for (int u : A) {
            for (int v : B) {
                countAB.put(u + v, countAB.getOrDefault(u + v, 0) + 1);
            }
        }
        int ans = 0;
        for (int u : C) {
            for (int v : D) {
                if (countAB.containsKey(-u - v)) {
                    ans += countAB.get(-u - v);
                }
            }
        }
        return ans;
    }
}

步骤图解

假设：

1
2
3
4
A = [1, 2]
B = [-2, -1]
C = [-1, 2]
D = [0, 2]

第一步结果（A+B）：

  • 1 + (-2) = -1
  • 1 + (-1) = 0
  • 2 + (-2) = 0
  • 2 + (-1) = 1

countAB = {-1:1, 0:2, 1:1}

第二步查找（C+D = -x）：

  • (-1,0): -( -1+0 ) = 1 → countAB[1] = 1
  • (-1,2): -( -1+2 ) = -1 → countAB[-1] = 1
  • (2,0): -( 2+0 ) = -2 → 不存在
  • (2,2): -( 2+2 ) = -4 → 不存在
    结果 ans = 2

15三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-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
class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 3) return ans;
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len ; i++) {
            if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
            int L = i+1;
            int R = len-1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L<R && nums[L] == nums[L+1]) L++; // 去重
                    while (L<R && nums[R] == nums[R-1]) R--; // 去重
                    L++;
                    R--;
                }
                else if (sum < 0) L++;
                else if (sum > 0) R--;
            }
        }        
        return ans;
    }
}

18四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

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

示例 1：

1
2
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,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
33
34
35
36
37
38
39
40
41
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 4) return ans;
        Arrays.sort(nums); // 排序
        
        for (int i = 0; i < len - 3; i++) {
            if(i > 0 && nums[i] == nums[i-1]) continue; 	// 去重
            
            for (int j = i + 1; j < len - 2; j++) {
                if(j > i + 1 && nums[j] == nums[j-1]) continue; 	// 去重
                
                int L = j + 1;
                int R = len - 1;
                
                while (L < R) {
                    // 使用long防止溢出
                    long sum = (long)nums[i] + (long)nums[j] + (long)nums[L] + (long)nums[R];
                    
                    if (sum == target) {
                        ans.add(Arrays.asList(nums[i], nums[j], nums[L], nums[R]));
                        
                        while (L < R && nums[L] == nums[L+1]) L++; 	// 去重
                        while (L < R && nums[R] == nums[R-1]) R--;
                        
                        L++;
                        R--;
                    }
                    else if (sum < target) {
                        L++;
                    }
                    else {
                        R--;
                    }
                }
            }
        }
        return ans;
    }
}

字符串

541反转字符串II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

1
2
输入：s = "abcdefg", k = 2
输出："bacdfeg"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public String reverseStr(String S, int k) {
        char[] s = S.toCharArray();
        int n = s.length;
        for (int i = 0; i < n; i += k * 2) {
            reverse(s, i, Math.min(i + k, n) - 1);
        }
        return new String(s);
    }

    private void reverse(char[] s, int left, int right) {
        while (left < right) {
            char tmp = s[left];
            s[left++] = s[right];
            s[right--] = tmp;
        }
    }
}

151翻转字符串里的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

1
2
输入：s = "the sky is blue"
输出："blue is sky the"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String reverseWords(String s) {
        s = s.trim();                                    // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while (i >= 0) {
            while (i >= 0 && s.charAt(i) != ' ') i--;     // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
            while (i >= 0 && s.charAt(i) == ' ') i--;     // 跳过单词间空格
            j = i;                                       // j 指向下个单词的尾字符
        }
        return res.toString().trim();                    // 转化为字符串并返回
    }
}

步骤图解

输入：" hello world "

  1. trim()后："hello world"
  2. 第一次循环：
    • i从末尾向前移动，找到空格前："world"
    • 添加："world "
  3. 第二次循环：
    • i继续向前，找到下一个单词："hello"
    • 添加："world hello "
  4. 返回："world hello"

28找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

1
2
3
4
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

1
2
3
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 可以直接用java中的indexOf方法，return ss.indexOf(pp);
// 朴素解法
class Solution {
    public int strStr(String ss, String pp) {
        int n = ss.length(), m = pp.length();
        char[] s = ss.toCharArray(), p = pp.toCharArray();
        // 枚举原串的「发起点」
        for (int i = 0; i <= n - m; i++) {
            // 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
            int a = i, b = 0;
            while (b < m && s[a] == p[b]) {
                a++;
                b++;
            }
            // 如果能够完全匹配，返回原串的「发起点」下标
            if (b == m) return i;
        }
        return -1;
    }
}

步骤图解

示例1： ss = "hello", pp = "ll"

1
2
3
i=0: h vs l ❌
i=1: e vs l ❌
i=2: l vs l ✓, l vs l ✓ → b=2 == m=2 → 返回 2

KMP方法(待补充)

栈与队列

注意

  1. Hello 算法 中的栈和队列讲解是用链表和数组实现栈和队列的功能，以下的算法题是让栈和队列互相实现彼此。

常用方法

push-入 pop-出 peek-查找
栈 Stack stack = new Stack<>(); push() pop() peek()
队列 Queue queue = new LinkedList<>(); offer() poll() peek()
双向队列 Deque deque = new LinkedList<>(); offerLast()/offerFirst() pollLast()/pollFirst() peekLast()/peekFirst()

232用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false
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 MyQueue {
    private Stack<Integer> A;
    private Stack<Integer> B;

    public MyQueue() {
        A = new Stack<>();
        B = new Stack<>();
    }

    public void push(int x) {
        A.push(x);
    }

    public int pop() {
        int peek = peek();
        B.pop();
        return peek;
    }

	public int peek() {
		// 如果输出栈B不为空，队首就是B的栈顶
		if (!B.isEmpty()) return B.peek();
		// 如果B为空且A也为空，队列为空，按题目假设此情况不会发生peek操作
		if (A.isEmpty()) return -1;
		// 核心：当B为空时，将A中所有元素转移到B中
		while (!A.isEmpty()){
			B.push(A.pop());
		}
		// 此时B的栈顶就是原A的栈底，即最先入队的元素
		return B.peek();
	}

    public boolean empty() {
        return A.isEmpty() && B.isEmpty();
    }
}

225用队列实现栈

你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
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 MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue2.offer(x);
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue1.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue1.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty();
    }
}

步骤图解

我们模拟执行 push(1)、push(2)、pop() 的过程：

操作 queue1 的内容 (队首 -> 队尾) queue2 的内容 (队首 -> 队尾) 步骤解释
初始 [] [] 两个队列都为空。
push(1) [1] [] 1. queue2 加入 1 → [1]。 2. queue1 为空，不转移。 3. 交换引用后，queue1 变为 [1]，queue2 变为 []。
push(2) 关键步骤：
[] [2] 1. 先将新元素 2 放入 queue2。
[] [2, 1] 2. 将 queue1 中的 [1] 转移到 queue2，queue2 变为 [2, 1]。
[2, 1] [] 3. 交换引用。现在 queue1 为 [2, 1] (队首 2 是栈顶)，queue2 为空。
pop() [1] [] 直接从 queue1 的队首取出元素 2 并返回。queue1 变为 [1]。

20有效的括号

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

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

1
2
输入：s = "([)]"
输出：false
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
class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                // 情况一：遇到的是右括号
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                // 情况二：遇到的是左括号
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

1047删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 s 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

1
2
3
4
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String removeDuplicates(String s) {
        StringBuffer stack = new StringBuffer();
        int top = -1;
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (top >= 0 && stack.charAt(top) == ch) {
                // 情况一：当前字符与栈顶字符相同
                stack.deleteCharAt(top);
                --top;
            } else {
                // 情况二：栈为空，或当前字符与栈顶字符不同
                stack.append(ch);
                // 此处使用 ++top 更多是一种习惯和逻辑上的自然选择。
                ++top;
            }
        }
        return stack.toString();
    }
}

步骤图解

s = "abbaca"

当前字符 ch 栈 stack (左侧是栈底，右侧是栈顶) top 索引 操作与说明
初始 "" (空) -1
‘a’ "a" 0 栈空，直接入栈。
‘b’ "ab" 1 栈顶 ‘a’ ≠ ‘b’，入栈。
‘b’ "a" 0 发现重复：栈顶 ‘b’ == 当前 ‘b’。 删除栈顶 ‘b’，top 变为 0。
‘a’ "" (空) -1 发现重复：栈顶 ‘a’ == 当前 ‘a’。 删除栈顶 ‘a’，top 变为 -1，栈空。
‘c’ "c" 0 栈空，直接入栈。
‘a’ "ca" 1 栈顶 ‘c’ ≠ ‘a’，入栈。

遍历结束，栈中字符为 "ca"，即为最终结果。

为什么不用 Stack 类？

Java 的 Stack 类继承自 Vector，是线程安全的，但在单线程环境下会有不必要的性能开销（如加锁）。它的 push 和 pop 操作也是基于数组的。官方题解中使用 StringBuffer 和整型指针 top 手动模拟，直接操作底层数组，避免了方法调用的开销，是更高效的做法。

150逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/' 。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

1
2
3
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

1
2
3
4
5
6
7
8
9
10
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
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
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = tokens.length;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                    default:
                }
            }
        }
        return stack.pop();
    }

    public boolean isNumber(String token) {
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }
}

步骤图解

以 tokens = ["2", "1", "+", "3", "*"] 为例（对应中缀表达式 (2 + 1) * 3）：

当前 token 栈的操作 栈的内容 (栈底 -> 栈顶) 说明
"2" push(2) 2 数字，直接入栈
"1" push(1) 2, 1 数字，直接入栈
"+" 弹出 1 和 2，计算 2 + 1 = 3，push(3) 3 运算符，进行计算
"3" push(3) 3, 3 数字，直接入栈
"*" 弹出 3 和 3，计算 3 * 3 = 9，push(9) 9 运算符，进行计算

最终栈顶弹出结果 9。

239滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for(int j = 0, i = 1 - k; j < nums.length; i++, j++) {
            // 删除 deque 中对应的 nums[i-1]
            if(i > 0 && deque.peekFirst() == nums[i - 1])
                deque.pollFirst();
            // 保持 deque 递减
            while(!deque.isEmpty() && deque.peekLast() < nums[j])
                deque.pollLast();
            deque.offerLast(nums[j]);
            // 记录窗口最大值
            if(i >= 0)
                res[i] = deque.peekFirst();
        }
        return res;
    }
}

总结

  1. 每次遍历到一个新值时，要做一个事情：删除队列中所有比这个值小的值。因为这个值入队之后，所以比这个值小的，并且在这个值之前的，都不可能是答案。
  2. 另外，不管最新遍历到的这个值，大小如何，都要加入队列。因为这个值有可能是后面的答案。

347前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1：

输入：nums = [1,1,1,2,2,3], k = 2

输出：[1,2]

示例 2：

输入：nums = [1], k = 1

输出：[1]

示例 3：

输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 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
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 统计元素出现频率
        Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }
        // 2.使用小顶堆找出前K个高频元素
        // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });
        // 3.遍历频率Map，维护大小为K的堆
        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            } else {
                queue.offer(new int[]{num, count});
            }
        }
        // 4.构建结果数组
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }
}

步骤图解

输入：nums = [1,1,1,2,2,3], k = 2

  1. 统计频率：{1:3, 2:2, 3:1}
  2. 小顶堆维护过程：
    • 加入[1,3] → 堆：[1,3]
    • 加入[2,2] → 堆：[2,2], [1,3]
    • 遇到[3,1]，堆已满，1<2，不加入
  3. 结果：[2,1] ，因为是小顶堆

二叉树

二叉树的遍历方式

层序遍历

广度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 层序遍历 */
List<Integer> levelOrder(TreeNode root) {
    // 初始化队列，加入根节点
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    // 初始化一个列表，用于保存遍历序列
    List<Integer> list = new ArrayList<>();
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // 队列出队
        list.add(node.val);           // 保存节点值
        if (node.left != null)
            queue.offer(node.left);   // 左子节点入队
        if (node.right != null)
            queue.offer(node.right);  // 右子节点入队
    }
    return list;
}

前/中/后序遍历

深度优先

二叉搜索树的前序、中序、后序遍历

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
/* 前序遍历 */
void preOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：根节点 -> 左子树 -> 右子树
    list.add(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

/* 中序遍历 */
void inOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：左子树 -> 根节点 -> 右子树
    inOrder(root.left);
    list.add(root.val);
    inOrder(root.right);
}

/* 后序遍历 */
void postOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：左子树 -> 右子树 -> 根节点
    postOrder(root.left);
    postOrder(root.right);
    list.add(root.val);
}

226翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

img

1
2
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public TreeNode invertTree(TreeNode root) {
        //翻转这棵二叉树，并返回其根节点。
        invert(root);
        return root;
    }

    public void invert(TreeNode root){
        if(root == null){
            return;
        }

        //交换左右子树
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        invert(root.left);
        invert(root.right);
    }
}

101对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

img

1
2
输入：root = [1,2,2,3,4,4,3]
输出：true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root.left, root.right);
    }

    public boolean check(TreeNode L, TreeNode R) {
        if (L == null && R == null) {
            return true;
        }
        if (L == null || R == null) {
            return false;
        }
        return L.val == R.val && check(L.left, R.right) && check(L.right, R.left);
    }
}

104二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

img

1
2
输入：root = [3,9,20,null,null,15,7]
输出：3
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

111二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

img

1
2
输入：root = [3,9,20,null,null,15,7]
输出：2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }

        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }

        return min_depth + 1;
    }
}

为什么最大深度和最小深度的解法有较大不同？