Java刷题计划

工作原因需要过可信考试，题型为算法题，所以重新捡起秋招准备机考的题目。只不过本次准备的是Java语言，秋招时准备的都是Python，语言的切换在一开始是存在阵痛期的，各种api的不熟悉，以及书写方式的不同，带来一定的不适应，但总要面对这样的过程，因此写下本篇。

数组

搜索插入位置

本题利用的是二分查找的思路，但是在最后一次查找的时候需要记录位置

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
package 数组;

/**
 * @program: SoftExam
 * @description:
 * @author: 郭寅之(Clay_Guo)
 * @create: 2025/7/30 22:23
 **/
public class 搜索插入位置 {
    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6};
        int target = 0;
        System.out.println(searchInsert(nums, target));
    }

    public static int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        int res = nums.length;
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else { // 记录最后一次查找的位置
                right = mid - 1;
                res = mid;
            }
        }
        return res;
    }
}

长度最小的子数组

滑动窗口的思路，虽然是模板题，但是需要注意窗口的条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package 数组;

/**
 * @program: SoftExam
 * @description:
 * @author: 郭寅之(Clay_Guo)
 * @create: 2025/8/3 21:27
 **/
public class 长度最小的子数组 {
    public static void main(String[] args) {

    }

    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int res = Integer.MAX_VALUE;
        int sum = 0;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                res = Math.min(res, right - left + 1);
                sum -= nums[left++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

最小覆盖子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package 数组;

import java.util.*;

/**
 * @program: SoftExam
 * @description:
 * @author: 郭寅之(Clay_Guo)
 * @create: 2025/8/2 9:19
 **/
public class 最小覆盖子串 {
    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
    }

    public static String minWindow(String s, String t) {
        int len = Integer.MAX_VALUE;
        Map<Character, Integer> map = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        int start = 0;
        int left = 0;
        int valid = 0;

        for (int i = 0; i < t.length(); i++) {
            map.merge(t.charAt(i), 1, Integer::sum);
        }
        for (int right = 0; right < s.length(); right++) {
            char key = s.charAt(right);
            if (map.containsKey(key)) {
                window.merge(key, 1, Integer::sum);
                if (window.get(key).equals(map.get(key))) {
                    valid += 1;
                }
            }
            while (valid == map.size()) {
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    start = left;
                }
                char out = s.charAt(left);
                left++;
                if (window.containsKey(out)) {
                    // 这里不能写== 因为Integer是对象的比较，而不是值的比较
                    // if (window.get(out) == map.get(out)) {
                    if (window.get(out).equals(map.get(out))) {
                        valid--;
                    }
                    window.put(out, window.get(out) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE || start + len > s.length() ? "" : s.substring(start, start + len);
    }
}

链表

203. 移除链表元素

经过调试发现，如果cur.next.val==val时，需要一直将下一个节点进行删除，否则需要将指针向后移动一位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        while (cur != null && cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}