LeetCode

原记录于2023-10-21（创建），目前提前至此于调整布局用

力扣算法题记录

s: simple m:middle h:hard

除了算法题还有场景题

链表相关

单链表如下

1
2
3
4
5
6
7
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; }
}

尾插法

1
2
3
4
5
6
7
8
9
public void addLast(Object value) {
    ListNode newNode = new ListNode(value);
    while (current.next != null) {
        //获取尾结点
        current = current.next;
    }
    current.next = newNode;
    newNode.next = null;
}

头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void addHead(Object value) {
    ListNode newNode = new ListNode(value);
    //后一个结点
    current = head;
    if (current.next != null) {
        //获取尾结点
        current = current.next;
    }
    newNode.next = current;
    head.next = newNode;
}

public ListNode reverseList(ListNode head) {
    ListNode cur = head, pre = null;
    while(cur != null) {
        ListNode tmp = cur.next; // 暂存后继节点 cur.next
        cur.next = pre;          // 修改 next 引用指向
        pre = cur;               // pre 暂存 cur
        cur = tmp;               // cur 访问下一节点
    }
    return pre;
}

如果需要指定位置，那么则添加一个限制条件为计数即可

全排列🌈

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
/**
  * 全排列优化版本
  * res为全局结果集 List<List<Integer>> res = new ArrayList<>();
  *
  * @param arr   需要进行全排列的数组
  * @param track 参与递归存储每一种排列的数组
  * @param count 排列的数级（比如我需要排列三种结果的[1,2,3],[1,2,4]）
  * @param index 从哪一个下标开始进行（增加此项可以避免重复计算）
  */
public static void dfs(List<Integer> arr, List<Integer> track, int count, int index) {
    if (track.size() == count) {
        res.add(new ArrayList<>(track));
        return;
    }
    for (int i = index; i < arr.size(); i++) {
        // 前置条件 剪枝处
        if (track.contains(arr.get(i)) {
            continue;
        }
        // 1. 做选择
        track.add(arr.get(i));
        // 2. 递归
        dfs(arr, track, count++, index + 1);
        // 3. 撤销选择
        track.remove(track.size() - 1);
        count--;
    }
}

Hot100记录🌈

哈希

P1 两数之和 #哈希表

1. 两数之和

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

49 字母异位词 #局部排序

49. 字母异位词分组

1
2
3
4
5
6
7
8
9
public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        map.computeIfAbsent(new String(chars), value -> new ArrayList<>()).add(str);
    }
    return new ArrayList<>(map.values());
}

P128 最长连续序列 M #哈希表

128. 最长连续序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int longestConsecutive(int[] nums) {
    if (nums.length <= 1) return nums.length;
    HashSet<Integer> set = new HashSet<>();
    for (Integer num : nums) {
        set.add(num);
    }
    int ans = 0;
    for (Integer item : set) {
        int curAns = 1, curNum = item;
        if (!set.contains(item - 1)) {
            // 只需要往后遍历，就是一直往后面判断就可以了，直到找到一个（连续列中）最小的数
            while (set.contains(curNum + 1)) {
                curNum++; // 后移
                curAns++; // 计数
            }
        }
        ans = Math.max(ans, curAns);
    }
    return ans;
}

双指针

双指针（技巧）

对于双指针, 用的最多的无非就是左右指针, 那么左右指针一般都有类似的解法

1
2
3
4
5
6
7
8
9
10
11
public static void template(int []nums){
    int left=0, right=nums.length-1;
    while(left < right){
        // 逻辑
        if(){ // 指针移动条件
            left++;
        }else{
            right++;
        }
    }
}

例如题P11 盛水最多的容器 就是左右指针, 其中还有一种为中间发散指针(从中间到两边)5. 最长回文子串 - 力扣（LeetCode）

P283 移动零 #快慢指针

283. 移动零

1
2
3
4
5
6
7
8
9
10
11
12
13
public void moveZeroes(int[] nums) {
    int index = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) {

        } else { // 不是0
            nums[index] = nums[i];
            index++;
        }
    }
    for (int i = index;i<nums.length;i++)
        nums[i] = 0;
}

P11 盛水最多的容器 M 数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int ans = 0;
    while (left < right) {
        int area = (right - left) * Math.min(height[right], height[left]);// 当前面积
        ans = Math.max(ans, area); // 判断面积
        if (height[left] < height[right]) { // 左边是短的边
            left++; // 指针移动
        } else {
            right--;
        }
    }
    return ans;
}

模板都是类似固定的, 同样的模板模式还出现在二叉树

P15 三数之和

15. 三数之和

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
public List<List<Integer>> threeSum(int[] nums) {
    int length = nums.length;
    if (length < 3)
        return new ArrayList<>();
    Arrays.sort(nums);
    Set<List<Integer>> set = new HashSet<>();
    for (int i = 0; i < length; i++) {
        if (nums[i] > 0)
            break;
        int L = i + 1;
        int R = length - 1;
        while (L < R) {
            int sum = nums[i] + nums[L] + nums[R];
            if (sum == 0) {
                set.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 new ArrayList<>(set);
}

滑动窗口

P3 无重复字符的最长子串 M #滑动窗口

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int res = 0;
        int slow = -1;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char t = s.charAt(i);
            // 如果已经存在则更新慢索引(用原来的索引)
            if(map.containsKey(t)){
                slow = Math.max(slow, map.get(t));
            }
            map.put(t, i);
            res = Math.max(res, i - slow);
        }
        return res;
    }
}

具体图解见 leetcode Krahets题解

P438 找到字符串中所有字母异位词 M #区间排序

此题和上面的异位词异曲同工之妙

438. 找到字符串中所有字母异位词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    if (s.length() < p.length() || p.length() == 0)
        return res;
    char[] p1 = p.toCharArray();
    Arrays.sort(p1);
    int pLength = p.length();
    for (int i = 0; i < s.length() - pLength + 1; i++) {
        String temp = s.substring(i, pLength + i);
        char[] p2 = temp.toCharArray();
        Arrays.sort(p2);
        if (Arrays.equals(p1, p2)) {
            res.add(i);
        }
    }
    return res;
}

字串

普通数组

矩阵

链表

当前栏有一些不是hot100的，但是都是很经典的

P160 相交链表 S 链表 #hash表(map)

160. 相交链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    Map<ListNode, Integer> ans = new HashMap<>();
    if (headA == null) return null;
    ListNode p = headA;
    while (p != null) {
        ans.put(p, p.val);
        p = p.next;
    }
    ListNode b = headB;
    while (b != null) {
        if (ans.containsKey(b))  // 如果相交则可以拿到相同的对象
            return b;
        b = b.next;
    }
    return null;
}

P206 反转链表 S 链表 🌈

正常解法

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode reverseList(ListNode head) {
    //申请节点，pre和 cur，pre指向null
    ListNode pre = null;
    ListNode cur = head;
    while(cur!=null) {
        ListNode tmp = cur.next;//记录当前节点的下一个节点
        cur.next = pre;         //然后将当前节点指向pre
        pre = cur;              //pre和cur节点都前进一位
        cur = tmp;
    }
    return pre;
}

常规法助理解：

1
2
3
4
ListNode tmp = cur.next; 	   cur右
cur.next = pre;   		 cur左 pre右
pre = cur;				 pre左 cur右
cur = tmp;				 cur左

cur：右左右左
pre：右左

递归解法

1
2
3
4
5
6
7
8
9
public ListNode reverseList(ListNode head) {
    if(head==null || head.next==null) return head;//递归终止条件是当前为空，或者下一个节点为空
    ListNode cur = reverseList(head.next);//这里的cur就是最后一个节点，因为一直在递归，然后走到了最后
    //如果链表是 1->2->3->4->5，那么此时的cur就是5,而head是4，head的下一个是5，下下一个是空
    //所以head.next.next 就是5->4
    head.next.next = head;
    head.next = null;//防止链表循环，需要将head.next设置为空
    return cur;//每层递归函数都返回cur，也就是最后一个节点
}

递归法助理解：就是从最后开始，走到最后然后从后面开始处理，依次连接，断开

1
2
3
head.next.next = head;
head.next = null;
return cur;

P234 回文链表 #栈

234. 回文链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isPalindrome(ListNode head) {
    ListNode tt = head;
    Stack<ListNode> sta = new Stack<>();
    while (tt != null) {
        sta.push(tt);
        tt = tt.next;
    }
    ListNode ans = head;
    while (!sta.empty()) {
        if(ans.val != sta.pop().val){
            return false;
        }
        ans = ans.next;
    }
    return true;
}

P141 环形链表 S 链表 #hash表(set)

141. 环形链表

使用Set集合判断

1
2
3
4
5
6
7
8
9
10
11
public boolean hasCycle(ListNode head) {
    HashSet<ListNode> set = new HashSet<>();
    ListNode current = head;
    while (current != null) {
        if (set.contains(current)) 
            return true; // 环
        set.add(current);
        current = current.next;
    }
    return false; // 无环
}

标准方法判断（当前方法参考环形链表Ⅱ衍生出）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (fast == slow)
            return true;
    }
    if (fast == null || fast.next == null)
        return false;
    return true;
    /** 
    // 找到相交的节点
    slow = head;
    while(slow != fast){
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
    */
}

P142 环形链表 II M 链表 #快慢指针(步进差)🌈

142. 环形链表 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while(fast != null && fast.next != null){
        slow = slow.next;	   // 慢指针 步进1
        fast = fast.next.next; // 快指针 步进2
        if(slow == fast) break; // 相等则退出循环
    }
    // 排除没有成环的情况，快指针后面没有节点代表没成环
    if(fast == null || fast.next == null) 
        return null; 
    slow = head; // 从头开始，此时快指针已经到了相交节点
    while(slow != fast){            
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

P21 合并两个有序链表 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
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    // 其中一个为空
    if (list1 == null) 
        return list2;
    if (list2 == null) 
        return list1;
    ListNode ans = new ListNode(-1);
    ListNode margin = ans;
    while (list1 != null && list2 != null) {
        // 除了尾部情况
        if (list1.val < list2.val) {
            margin.next = list1;
            list1 = list1.next;
        } else {
            margin.next = list2;
            list2 = list2.next;
        }
        margin = margin.next;
    }
    // 排尾阶段
    if(list1 == null)
        margin.next = list2;
    if(list2 == null)
        margin.next = list1;
    return ans.next;
}

对于上题，通过采用新链表+双指针，双指针判断两个链表，新链表用于构建答案

易踩坑：1. 在构建新链表时，不保存头节点而直接赋值，导致数据丢失（7-8行） 需要使用一个新的链表节点+另外一个指向新节点的节点变量，然后用于构建ans（错误案例：ListNode ans = new ListNode(-1); 只使用一个头节点进行操作，不进行头节点的保存引用）

  1. 对于循环内的赋值，需要使用赋值节点的下一个节点赋值，而不是他自己（错误案例：margin= list1；margin = margin.next；）
  2. 对于当前题：注意到还有一个收尾的操作，笔者在debug的时候发现最后一个节点被忽略了，因而才引入排尾阶段

P143 重排链表 M #合并链表+反转链表+链表中点🌈综合题

这道题可以说非常有意思了，结合了前面的三个知识点

143. 重排链表

题目描述
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为：L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例1:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
示例2：
给定链表 1->2->3->4, 重新排列为 1->4->2->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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
public static ListNode reorderList(ListNode head) {

    // 1、使用快慢指针寻找出链表的中点来
    ListNode mid = middleNode(head);

    // 2、基于 mid 这个中点，将链表划分为两个区域

    // 左边的区域开头节点是 head
    ListNode leftHead = head;

    // 右边的区域开头节点是 mid.next
    ListNode rightHead = mid.next;

    // 将链表断开，就形成了两个链表了
    mid.next = null;

    // 3、将右边的链表进行反转
    rightHead = reverseList(rightHead);

    // 4、将这两个链表进行合并操作，即进行【交错拼接】
    return mergeTwoListNode(leftHead, rightHead, true, false);

}

    /**
     * LeetCode 21 : 合并两个有序链表（升级）
     *
     * @param isAlternateMerge    是否为交替合并
     * @param isCompareValueMerge 是否为根据值大小合并合并
     */
public static ListNode mergeTwoListNode(ListNode l1, ListNode l2, boolean isAlternateMerge, boolean isCompareValueMerge) {
    ListNode dummy = new ListNode(-1);
    ListNode node = dummy;
    boolean flag1 = true;
    while (l1 != null && l2 != null) {
        if (isAlternateMerge) { // 交替合并
            if (flag1) {
                node.next = l1;
                l1 = l1.next;
            } else {
                node.next = l2;
                l2 = l2.next;
            }
            flag1 = !flag1;
        } else if (isCompareValueMerge) { // 根据值的大小合并
            if (l1.val < l2.val) {
                node.next = l1;
                l1 = l1.next;
            } else {
                node.next = l2;
                l2 = l2.next;
            }
        }
        node = node.next;
    }
    if (l1 == null) {
        node.next = l2;
    } else {
        node.next = l1;
    }
    return dummy.next;
}

    /**
     * LeetCode 876 : 链表的中间节点
     */
public static ListNode middleNode(ListNode head) {

    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

    /**
     * LeetCode 206 : 反转链表
     */
public static ListNode reverseList(ListNode head) {
    if (head == null || head.next == null)
        return head;
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode t = cur.next;
        cur.next = pre;
        pre = cur;
        cur = t;
    }
    return pre;
}

P83 删除排序链表中的重复元素 S 链表

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode deleteDuplicates(ListNode head) {
    if(head == null) return null;
    ListNode slow = head;
    ListNode fast = head.next;
    while(fast != null){
        if(slow.val != fast.val){
            slow.next = fast;// 慢指针执行快指针 连接
            slow = slow.next;// 慢指针往后移动
        }
        fast = fast.next;
    }
    // 收尾操作(对于最后一组是重复元素的情况,假如没有重复元素则不会有该情况)
    if(slow != null) 
        slow.next = null;
    return head;
}

对于上述的两题(链表), 都有收尾操作

Pxxx 返回倒数第 k 个节点 S 链表 #快慢

面试题 02.02. 返回倒数第 k 个节点

相同题：LCR 140. 训练计划 II - 力扣（LeetCode）

先让fast走n步，然后让 p1 和 p2 同时向前走，p1 走到链表末尾的空指针时前进了 n - k 步，p2 也从 head 开始前进了 n - k 步，停留在第 n - k + 1 个节点上，即恰好停链表的倒数第 k 个节点上

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode kthToLast(ListNode head, int cnt) {
    ListNode fast = head;
    // 先快指针走n步
    for (int i = 0; i < cnt; i++) {
        fast = fast.next;
    }
    ListNode slow = head;
    while (fast != null){
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

P19 删除链表的倒数第 N 个结点 M 链表 #快慢指针 #虚拟节点

19. 删除链表的倒数第 N 个结点

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
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(-1);// 建立虚拟节点
    dummy.next = head;               // 虚拟节点连接到头节点
    ListNode shoudDel = kthToLast(dummy, n + 1); // 拿到倒数第k个的前一个
    //get point index          ↓    (需要删除的倒数第n个节点)
    //origin   1 ->2 ->3 ->4 ->5 ->6->
    //ans      1 ->2 ->3 ->4 ->    6->
    shoudDel.next = shoudDel.next.next;// 跳过需要删除的那个
    return dummy.next;
}
// 拿到倒数第n个节点
public ListNode kthToLast(ListNode head, int cnt) {
    ListNode fast = head;
    // 先快指针走n步
    for (int i = 0; i < cnt; i++) {
        fast = fast.next;
    }
    ListNode slow = head;
    // 然后一起走到终点
    while (fast != null){
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

P61 旋转链表 M 链表 #环形链表解法 #快慢指针

61. 旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

这个题很妙好吧，与前面的那个获取倒数第k个结合起来了。

首先我们拿到长度，然后拿到需要旋转的节点

例如题：1 - > 2 - > 3 - > 4 - > 5，我们需要旋转两个长度单位，此时结果应该为 4 - > 5 - > 1 - > 2 - > 3

1
2
3
4
第一步：size = 5，K=2  =>我们只需要拿到倒数第 s-k=3个位置的节点作为newHead即可
第二步:           newT  newH  tail（指针位置）
样例： 1 - > 2 - > 3 - > 4 - > 5
第三步：tail连接头节点构成循环链表，然后newT的下一个指针断开

详细代码如下

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
class Solution {
    // 定义一个名为 Solution 的类
    public ListNode rotateRight(ListNode head, int k) {
        // 定义一个名为 rotateRight 的公共方法，接收一个头节点和一个整数 k 作为参数
        if (head == null || k == 0)
            return head;
        // 如果头节点为空或者 k 为 0，则直接返回头节点，不需要旋转
        // 计算链表的长度
        ListNode tail = head;
        int size = 1;
        // 计算链表的长度
        while (tail.next != null) {
            size++;
            tail = tail.next;// 此时结束 tail则已经到了末尾了
        }
        // 对 k 进行取模运算，确保 k 在链表长度范围内
        k %= size;
        if (k == 0) // 如果 k 等于 0，则不需要旋转，直接返回头节点
            return head;
        // 找到倒数第 k 个节点
        ListNode fast = getNode(head, size - k);
        // 调用 getNode 方法找到倒数第 k 个节点，作为新的尾节点
        // 新的头节点是新尾节点的下一个节点
        ListNode newHead = fast.next;
        // 新的头节点是新尾节点的下一个节点
        // 将新的尾节点与头节点连接起来
        tail.next = head;
        // 将原始尾节点的 next 指针指向原始头节点，形成环形链表
        // 断开链表，使得新的尾节点指向 null
        fast.next = null;
        // 将新的尾节点的 next 指针指向 null，断开环形链表
        return newHead;
        // 返回新的头节点
    }

    // 获取链表中第 k 个节点
    public ListNode getNode(ListNode head, int k) {
        ListNode p = head;
        for (int i = 1; i < k && p != null; i++)
            p = p.next;
        return p;
    }
}

P23 合并 K 个升序链表 H 优先队列

23. 合并 K 个升序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
    for (ListNode node : lists) {
        if (node != null)
            queue.offer(node);
    }
    // 合并
    ListNode head = new ListNode(-1);
    ListNode tail = head; 
    while (!queue.isEmpty()) {
        ListNode poll = queue.poll();
        tail.next = poll;
        tail = poll; 		// tail继续作为尾节点指针
        if (poll.next != null) {
            queue.offer(poll.next);
        }
    }
    return head.next;
}

如果优先队列的签名是这样的

1
2
PriorityQueue<Integer> queue = 
    new PriorityQueue<>((o1, o2) -> o1 - o2);
  • 优先队列内部结构:

优先队列内部通常使用最小堆或最大堆实现。

最小堆保证队首元素是最小的元素，最大堆保证队首元素是最大的元素。

  • 添加元素:

当向优先队列中添加元素时，这些元素会根据堆的规则进行插入。

插入操作保持堆的性质不变，但并不意味着整个队列是完全有序的。

  • poll操作:

每次调用poll方法时，都会返回队首元素，即当前队列中最小的元素。

调用poll后，队列会自动调整以保持堆的性质，确保新的队首元素仍然是最小的。

  • 输出队列内容:

输出的队列内容反映的是内部堆的结构，而不是完全排序的结果。

输出的结果可能看起来无序，但队首元素始终是最小的。

综上所述：优先队列仅仅保证在出队列的时候是最小的，即 poll( )的时候，但是你在过程中输出队列的内部结构，他不一定是保证内部也是顺序的

二叉树

图论

不重要

回溯

递归正向是遍历，递归回来是回溯

二分查找

栈

堆

贪心算法

动态规划

多维动态规划

技巧

日常区记录

待迁移

P88 合并两个有序数组 S 数组

思路一 先合并在排序
思路二 合并的时候就进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 合并两个有序数组
 *
 * @param nums1 主数组 nums1.length = m + n
 * @param m 后面需要替换的数量
 * @param nums2 替换数组
 * @param n nums2.length
 */
public static void merge(int[] nums1, int m, int[] nums2, int n) {
      int index = 0;
      for (int i = m; i < nums1.length; i++) {
          nums1[i] = nums2[index++];
      }
      Arrays.sort(nums1);
  }

P27 移除元素 S 数组

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

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

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

思路: 快慢差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 移除元素
*
* @param nums 给定数组
* @param val  移除value
* @return
*/
public static int removeElement(int[] nums, int val) {
    int count = 0;
    for (int num : nums) {
        if (num != val) {
            nums[count++] = num;
        }
    }
    return count;
}

P169 多数元素 S 数组

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素

思路一 排序取中间(题目 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题)

1
2
3
4
public static int majorityElement(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length >> 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
/**
 * 多数元素
 *
 * @param nums 目标数组
 * @return
 */
public static int majorityElement(int[] nums) {
  // 默认候选人就是第一个元素
  int candidate = nums[0];
  int count = 1;
  for (int i = 1; i < nums.length; i++) {
      // 得支持票
      if (nums[i] == candidate) {
          count++;
      } else { // 得反对票
          count--;
          if (count == 0) {
              // 更换候选人
              candidate = nums[i];
              count = 1;
          }
      }
  }
  return candidate;
  // 默认候选人就是第一个元素，然后给自己投一票（count=1），如果遇到相同的票则+1，否则-1。当count为0的时候换下一个人，并且重置票数为1（count=1）。
}

P125 验证回文串 S 字符串

对于该题的要点有:

  1. 需要跳过非字符的元素

  2. 通过Java的API Character.isLetterOrDigit判断是字符还是数字(is: true not: false)

    java.lang.Character.isLetterOrDigit(char ch) 这个方法确定指定的字符是否为字母或数字。字符被认为是字母或数字，如果字符是字母或数字则此方法返回true，否则为false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    if (s == "" || s == null) {
        return true;
    }
    while (left < right) {
        while(left < right && !Character.isLetterOrDigit(s.charAt(left))) {
            left++;//如果是不是字符则左指针向后移动。
        }
        while(left < right && !Character.isLetterOrDigit(s.charAt(right))) {
            right--;//如果不是字符则右指针向前移动。
        }
        if(Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
            return false;//判断是否为回文串。若不是退出。
        }
        // 指针一同移动 判断对称位置字符
        left++;
        right--;
    }
    return true;
}

可以看出来, 大体的模板是不动的, 唯一变化的就是中间, 当前案例由于需要俩头一起遍历并且跳过非字符, 那么需要一直判断(while)

然后学习新的API java.lang.Character.isLetterOrDigit(char ch)

1
2
3
4
5
6
7
8
9
10
11
public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        // 代码逻辑
        
        // 指针移动
        left++;
        right--;
    }
    return true;
}

P20 有效的括号 S 字符串 #栈

20. 有效的括号

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
public boolean isValid(String s) {
    if (s.length() % 2 == 1) // 如果不是偶数 那么直接返回了
        return false;
    Stack<Character> stack = new Stack<Character>(); // 栈
    char[] chars = s.toCharArray();
    for (char item : chars) {
        // 左括号们
        if (item == '(' || item == '[' || item == '{') {
            stack.push(item);
        } else {
            // 这两个必须一起(一个是判断栈有没有值,一个是拿栈顶值) 不然会爆空指针
            if (stack.empty())
                return false;
            char top = stack.peek();
            // 判断栈顶的值与右边的括号们是不是一对 是则出栈
            if ((top == '(' && item == ')')
                || (top == '[' && item == ']')
                || (top == '{' && item == '}')) {
                stack.pop();
            } else {
                return false; // 没有匹配的参数
            }
        }
    }
    return stack.empty();
}

P26-80 删除有序数组中的重复项(I and II) S-M 数组

同类的两道题目, 这两个题目的快慢指针都是同类解法

26. 删除有序数组中的重复项(简单)

1
2
3
4
5
6
7
8
9
10
11
12
13
public int removeDuplicates(int[] nums) {
    int slow = 1, fast = 1;
    while (fast < nums.length) {
        if (nums[slow - 1] == nums[fast]) {
            // 其实这一步就是移动快指针(但是由于哪种情况都需要移动快指针 故直接写外层了)
        } else {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
}

80. 删除有序数组中的重复项 II (中等)

1
2
3
4
5
6
7
8
9
10
11
12
13
public int removeDuplicates(int[] nums) {
    int slow = 2, fast = 2;
    while (fast < nums.length) {
        if (nums[slow - 2] == nums[fast]) {
            fast++;
        } else {
            nums[slow] = nums[fast];
            fast++;
            slow++;
        }
    }
    return slow;
}

可以看出来, 差距只有在指针判断的间隔上(对于判断不需要重复的情况那么指针间隔为1, 至多两个重复的情况则间隔为2)可参考 B站 两题的详细视频讲解

P392 判断子序列 S 字符串

P392 判断子序列

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isSubsequence(String s, String t) {
    int left = 0, right = 0;
    if (s.length() == 0)
        return true;
    if (t.length() == 0)
        return false;
    while (right < t.length() && left < s.length()) {
        // 相等两个指针都移动
        if (s.charAt(left) == t.charAt(right)) {
            left++;
        }
        right++;
    }
    return left >= s.length();
}

P189 轮转数组 M

189. 轮转数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void rotate(int[] nums, int k) {
    int len = nums.length;
    k %= len;
    // 整体旋转
    reverse(nums, 0, len - 1);
    // 旋转从0到k的位置
    reverse(nums, 0, k - 1);
    // 旋转从k到末尾的位置
    reverse(nums, k, len - 1);
}

private void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

例如 [1,2,3,4,5,6,7,8]，k=3

第一次全部翻转

[8,7,6,5,4,3,2,1]

第二次翻转从 0 到 k-1 位置

[6,7,8,5,4,3,2,1]

第三次翻转剩下的 k 到末尾位置

[6,7,8,1,2,3,4,5]

这个方法挺好的

如果你用空间换时间也是可以的

1
2
3
4
5
6
7
8
9
public void rotate(int[] nums, int k) {
    int len = nums.length;
    int arr[] = new int[len];
    for (int i = 0; i < len; i++) 
        arr[(i + k) % len] = nums[i];
    
    for (int i = 0; i < len; i++) 
        nums[i] = arr[i];
}

对于当前题，还有一个是链表的翻转，也是指定 k

这个笔者也有写，笔者是采用类似的方法，三个指针位置断开/连接 处理的

1
2
               p1   p2       tail
a -> b -> c -> d -> e -> f -> g

假如现在的 k=3，那么就是上面这个图形

p1 的位置是不是就是等于链表长度 减去 k

然后我们拿到当前 p1 的下一个指针

把 p1 给断开，再把 tail 连接到头结点

返回 p2 指针正是结果

1
2
p2       tail                 p1    
e -> f -> g -> a -> b -> c -> d

相对链表题来说，数组的解法更容易想到，而链表的这个可能复杂些

P2 两数相加 M 链表 #模拟进位

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
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode p1 = l1, p2 = l2;
    ListNode dummyHead = new ListNode(-1);
    // 创建一个指针current用于遍历结果链表
    ListNode current = dummyHead;
    // （1）初始化进位carry为0
    int carry = 0;
    while (p1 != null || p2 != null || carry != 0) {
        // （2）初始化当前和sum为进位carry
        int sum = carry;
        // 如果链表l1还有节点，则加上l1当前节点的值，并移动p1指针到下一个节点
        if (p1 != null) {
            sum += p1.val;
            p1 = p1.next;
        }
        // 如果链表l2还有节点，则加上l2当前节点的值，并移动p2指针到下一个节点
        if (p2 != null) {
            sum += p2.val;
            p2 = p2.next;
        }
        // （3）计算当前位运算的进位值（0-1）即是否影响下一位
        carry = sum / 10;
        // 计算当前节点的值
        sum %= 10;
        // 创建一个新节点存储当前节点的值，并连接到结果链表的尾部
        current.next = new ListNode(sum);
        current = current.next;
    }
    // 返回结果链表的头节点，即虚拟头节点的下一个节点
    return dummyHead.next;
}

对于题目中的（1）（2）（3）出进行答疑：

（1）进位初始化全局变量

（2）对于上一次运算的进位在本次（即 本次是上一次的前一位：如目前是百位，那么上一次就是十位，那么此时进位是在百位操作的）

（3）每一次对于当前进位运算后，需要计算当前位进行运算后的进位值（结果0-1，）即是否影响下一位

P144 二叉树的前序遍历 S 二叉树

144. 二叉树的前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    middle(root, ans);
    return ans;
}

private TreeNode middle(TreeNode node, List<Integer> res) {
    if (node == null) {
        return null;
    } else {
        res.add(node.val); // 前序
        middle(node.left, res); // 如果是中序则出现在这个位置
        middle(node.right,res);
    }
    return null;
}

P145 二叉树的后序遍历 S 二叉树

145. 二叉树的后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    func(root, ans);
    return ans;
}
private TreeNode func(TreeNode node, List<Integer> ans){
    if(node==null) return null;
    else{
        func(node.left,ans);
        func(node.right,ans);
        ans.add(node.val); // 后序
    }
    return null;
}

P230 二叉搜索树中第K小的元素 M 二叉树 #中序遍历 #二叉搜索树

230. 二叉搜索树中第K小的元素

二叉搜索树的特点：左边节点比右边节点小，右边比中间大，那么对应该类型的题，我们只需要处理一边，然后一个一个判断就行

1
2
3
4
5
6
7
8
9
10
11
12
13
public int kthSmallest(TreeNode root, int k) {
	Stack<TreeNode> stack = new Stack<>();
    while(true){
        while(root != null){
            stack.push(root.left);// 处理左边
            root = root.left;
        }
        TreeNode peek = stack.peek(); // 出栈
        if(k-- == 0) // 已经找到了第k个
            return peek.val;
        root = root.right;
    }
}

那么 如果是第k大的是不是也可以用这个去解决，那么我们只需要加一个计数器 遍历拿到长度反向去拿第k小的就行了

二叉树（技巧）

对于二叉树来说，无非就是有两种拆分问题的方案，一个是遍历，一个是分解

二叉树解题的思维模式分两类：

1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。

2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。

无论使用哪种思维模式，你都需要思考：

如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

这是一个链接

那么我们以226. 翻转二叉树 - 力扣（LeetCode）为例

遍历

常规写法

1
2
3
4
5
6
7
8
9
10
11
12
public TreeNode invertTree(TreeNode root) {
    if(root == null) return null;
    // 让每个节点的左右子节点颠倒过来就行了（前序位置）
    TreeNode t = root.left;
    root.left = root.right;
    root.right = t;
    
    // 遍历框架
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 定义：将以 root 为根的这棵二叉树翻转，返回翻转后的二叉树的根节点
public TreeNode invertTree(TreeNode root) {
    if(root == null) return null;
    // 利用函数定义，先翻转左右子树
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);

    // 然后交换左右子节点
    root.left = right;
    root.right = left;
    
    
    // 和定义逻辑自恰：以 root 为根的这棵二叉树已经被翻转，返回 root
    return root;
}

这种「分解问题」的思路，核心在于你要给递归函数一个合适的定义，然后用函数的定义来解释你的代码；

小结

二叉树解题的思维模式分两类：

1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。

2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。

无论使用哪种思维模式，你都需要思考：

如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

二叉树的层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public List<List<Integer>> levelOrder(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // Java 的 pop 写作 poll()
        // 如果需要拿到层序遍历的结果，在此进行操作，例如 ans.add(node.val)
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

P71 简化路径 M 栈

71. 简化路径

1
2
3
Linux下的路径
输入：path = "/a/./b/../../c/"
输出："/c"
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 static String simplifyPath(String path) {
    Stack<String> stack = new Stack<>();
    String[] split = path.split("/");
    // 遍历路径中的每个部分
    for (String part : split) {
        // 如果部分为空或为当前目录符号 "."
        if (part.isEmpty() || part.equals(".")) 
            continue;
        // 如果部分为父目录符号 ".."，则弹出栈顶元素
        else if (part.equals("..")) {
            if (!stack.empty())
                stack.pop();
        }
        // 否则，将部分压入栈中
        else 
            stack.push(part);
    }
    StringBuilder sb = new StringBuilder();
    for (String s : stack) 
        sb.append("/").append(s);
    if (sb.length() == 0) 
        return "/";
    return sb.toString();
}

其实很好理解，如果遇到.则什么都不做处理，如果遇到..那么则需要出栈

当然此题还可以使用队列去实现，笔者最开始就是使用的队列，如果遇到上述的相同情况则出入队列，原理一致（Queue）

P150 逆波兰表达式求值 M 栈

150. 逆波兰表达式求值

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 int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    for (String token : tokens) {
        // 如果是遇到符号 则需要进行运算
        if ("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token)) {
            // 因为需要得到两个操作数 需要出栈两次
            Integer left = stack.pop();
            Integer right = stack.pop();
            switch (token) {
                case "+":
                    stack.push(left + right);
                    break;
                case "*":
                    stack.push(left * right);
                    break;
                case "-":
                    // 易错：left是第一个出栈的，那么他是做除数/减数
                    stack.push(right - left);
                    break;
                case "/":
                    stack.push(right / left);
                    break;
            }
        } else { // 不是符号情况 则是数字 直接push即可
            stack.push(Integer.parseInt(token));
        }
    }
    return stack.peek();
}

其实这个题和上面那个题很像

遇到的一些笔试题

此处用于记录遇到的一些笔试题（不完整记录）

[去哪儿旅行]2025届秋季校园招聘笔试

第一题

输入 n 代表数组长度，然后你需要排列最小的序列例如

n = 3

arr = [ 2 , -1 , 1 ]

输出

-1 2 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());
        String[] as = reader.readLine().split(" ");
		// 这一个用法很妙
        Arrays.sort(as, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));

        for (String str : as) {
            System.out.printf("%s ", str);
        }
    }
}

第二题

什么签到积分 可以使用翻倍积分卡

  1. 给定两个整数 ( n ) 和 ( m )，其中 ( n ) 代表任务奖励的成长值数量，( m ) 代表需要积累的成长值总量。
  2. 接着给出 ( n ) 个任务奖励的成长值数组 ( a_1, a_2, …, a_n )，每个任务的成长值不超过 1000。
  3. 然后给出 ( n ) 个整数数组 ( b_1, b_2, …, b_n )，表示每个任务可以翻倍 ( b_i ) 次，翻倍会增加对应任务的成长值。

任务是通过选择任务并合理翻倍，使得能积累至少 ( m ) 成长值，计算最少需要的翻倍次数。

输出描述：

  • 输出一个整数，表示为了达到目标 ( m )，最少需要的翻倍次数。如果无法达到目标，则输出 -1。

Java 实现代码：

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
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class TaskGrowth {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 输入任务数和所需的总成长值
        int n = sc.nextInt();
        long m = sc.nextLong();
        
        int[] a = new int[n]; // 任务的基础成长值
        int[] b = new int[n]; // 每个任务的翻倍次数
        
        // 输入任务奖励的成长值和翻倍次数
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextInt();
        }
        
        // 创建优先队列，按照翻倍后的值降序排列
        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
        long totalGrowth = 0;
        int doublesUsed = 0;
        
        // 先不翻倍的情况下累积成长值
        for (int i = 0; i < n; i++) {
            totalGrowth += a[i];
            pq.add(a[i]); // 先将当前成长值加入优先队列
        }
        
        // 如果初始值已经超过目标
        if (totalGrowth >= m) {
            System.out.println(0);
            return;
        }
        
        // 开始尝试翻倍
        while (totalGrowth < m && !pq.isEmpty()) {
            int maxGrowth = pq.poll(); // 取出当前成长值最大的任务
            if (maxGrowth == 0) break; // 如果已经无法再翻倍，退出
            
            totalGrowth += maxGrowth; // 每次翻倍
            doublesUsed++; // 记录使用的翻倍次数
            
            if (totalGrowth >= m) {
                System.out.println(doublesUsed);
                return;
            }
        }
        
        // 如果无法达到目标，输出 -1
        System.out.println(-1);
    }
}

第三题

伪周期字符串

是关于找到字符串的伪周期串的最大值 ( k )，题目大致内容如下：

题目描述：

  1. 给定一个字符串 ( T )，长度为 ( n )（1 ≤ ( n ) ≤ 2000），字符串仅包含数字字符（0-9）。
  2. 如果一个字符串可以被重复某个子串 ( S ) ( k ) 次得到，则称该字符串为 ( S ) 的伪周期串。
  3. 目标是找到一个最大的整数 ( k )，使得字符串可以表示为 ( S_1+S_2+\dots+S_k ) 的伪周期串。

输入描述：

  1. 第一行输入整数 ( n )，表示字符串的长度。
  2. 第二行输入长度为 ( n ) 的字符串 ( T )，仅包含数字字符。

输出描述：

在一行输出最大的整数 ( k )，代表 ( k ) 种伪周期。

例如

n = 8

string = 00123123

输出：2

n = 6

123123

输出：1

Java 实现代码：

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
import java.util.Scanner;

public class PseudoPeriodicString {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 输入字符串长度 n 和字符串 T
        int n = sc.nextInt();
        String t = sc.next();
        
        // 最大的伪周期 k 初始化为 1，因为最小也可以是 1（整个字符串本身）
        int maxK = 1;
        
        // 尝试不同的子串长度 i (1 到 n)
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) { // 只有当 n 能整除 i 时，才可能构成伪周期
                String sub = t.substring(0, i); // 提取可能的伪周期子串
                StringBuilder sb = new StringBuilder();
                
                // 构建长度为 n 的字符串，尝试用 sub 重复 k 次
                for (int j = 0; j < n / i; j++) {
                    sb.append(sub);
                }
                
                // 如果构造出的字符串和原字符串相同，则更新最大 k
                if (sb.toString().equals(t)) {
                    maxK = n / i;
                }
            }
        }
        
        // 输出最大伪周期 k
        System.out.println(maxK);
    }
}

说明：

  1. 首先读取字符串 ( T ) 及其长度 ( n )。
  2. 通过遍历所有可能的子串长度 ( i )，检查如果字符串 ( T ) 能被长度为 ( i ) 的子串重复 ( k ) 次构成，则更新最大 ( k )。
  3. 如果构造出的字符串与原始字符串相等，则当前子串为有效的伪周期子串。
  4. 输出最大的伪周期数 ( k )。

示例输入：

1
2
6
123123

示例输出：

1
2

这个代码会计算并输出字符串的最大伪周期数 ( k )。

[360]笔试 9.14

传染病防控

R市正在进行传染病防控。R市总共有n个人。具体的，每个人有一个位置(x;y;)，现在已知有一个是高风险人员，但还未追踪到具体是谁。同时我们定义一个安全距离k，如果某个人和这个高风险人员的距离不超过k，那么这个人也将被列为高风险人员。为了减少防控对市民生活的影响，工作人员希望知道所有可能情况下最多的高风险人员数量。两个人(x,y,),(x2,y2)的距离定义为 |x1 - x2| + |y1 - y2|

一行两个整数n,k。

接下来一行n个整数分别表示xX2….

接下来一行n个整数分别表示y1-V2.n

1<=n<=1000, 1<=k,x,y<=1000.

样例输入

5 2

8 6 1 5 1

4 4 3 4 6

样例输出

​ 3

提示：如果一开始一号人员高风险，则二号人员也会变成高风险，然后四号人员变成高风险，此时高风险人员数量最多为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
public static void 传染病防控() {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    sc.nextLine(); // Consume the newline character after reading k

    int[][] arr = new int[2][n];
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < n; j++) {
            arr[i][j] = sc.nextInt();
        }
        sc.nextLine(); // Consume the newline character after each line
    }

    int maxHighRisk = 0;
    for (int i = 0; i < n; i++) {
        int highRiskCount = 1; // Start with the initial high-risk person
        for (int j = 0; j < n; j++) {
            if (i != j && isWithinDistance(arr[0][i], arr[1][i], arr[0][j], arr[1][j], k)) {
                highRiskCount++;
            }
        }
        maxHighRisk = Math.max(maxHighRisk, highRiskCount);
    }

    System.out.println(maxHighRisk);
}

private static boolean isWithinDistance(int x1, int y1, int x2, int y2, int k) {
    return Math.abs(x1 - x2) + Math.abs(y1 - y2) <= k; // 这个不就是题目定义吗，他们的距离小于K
}

奇妙的约分

1
2
3
4
5
6
7
8
9
10
11
输入
4
114514/1919810 1454/91980
114514/1919810 454/9980
114514/1919810 114514/1919810
21/42 1/2
输出
Yes
Yes
Yes
No

其实就是可以理解为：对于一组数据114514/1919810 1454/91980

我可以先区分为左 114514 和 1454，他们中间就是去掉了 11

那么对于右边：1919810 -> 91980，他们也要去掉 11 然后相等才是符合题目的

比如第四组数据就对不上21/42 1/2，我删除 2 => 1/4 != 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public static void 奇妙的约分() {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    sc.nextLine(); // Consume the newline character after reading n
    String[] st = new String[n];
    for (int i = 0; i < n; i++) {
        st[i] = sc.nextLine();
    }

    for (int i = 0; i < n; i++) {
        String[] split = st[i].split(" ");

        String[] left = split[0].split("/");
        String[] right = split[1].split("/");
        	/*
             * left = [114514, 1919810] right = [1454, 91980]      YES  删除11
             * left = [114514, 1919810] right = [454, 9980]        YES
             * left = [114514, 1919810] right = [114514, 1919810]  YES
             * left = [21, 42] right = [1, 2]                      NO
             */
        boolean flag = judgeEqual(left[0], right[0], left[1], right[1]);
        System.out.println(flag ? "Yes" : "No");
    }
}

/**
* 简单粗暴 直接替换
* @param left1  左边1对比
* @param right1 右边1对比
* @param left2  右边2对比
* @param right2 右边2对比
* @return boolean
*/
private static boolean judgeEqual(String left1, String right1, String left2, String right2) {
    // 先让left1与right1比较，比较出差值
    // Character字符数组取差集（操作left1和right1）
    char[] chars = right1.toCharArray();
    for (char c : chars) {
        // 取出left1中与right1中相同的字符
        left1 = left1.replaceFirst(String.valueOf(c), "");
    }
    for (int i = 0; i < left1.length(); i++) {
        // 删除left2中与left1中相同的字符
        left2 = left2.replaceFirst(String.valueOf(left1.charAt(i)),"");
    }
    char[] chars1 = left2.toCharArray();
    for (char c : chars1) {
        // 取出right2中与left2中相同的字符 并且全部移除，如果刚刚好为空，那么就是匹配成功
            right2 = right2.replaceFirst(String.valueOf(c), "");
        }
        return "".equals(right2);
    }
}

场景题

分金条问题

问题描述：雇1个人工作7天，你有1根金条可以分成7份，只能切2刀，如何保证每天都得到1份金条

我们首先，把金条看出七份，然后我们我们切两刀（1/7，2/7，4/7）那么可以看成一个线段从1/7处和3/7处切了(切金条CSDN)

然后七天的话: 第一天给工人 1/7，那么我们还有（剩2/7 + 4/7 = 6/7）

第二天：我们给他2/7，然后他返回第一天我们给他的1/7（剩1/7 + 4/7 = 5/7）

第三天：我们给他第二天要回的1/7，此时我们（剩4/7）

第四天：要回所有的金条（3/7），我们给他我们剩的4/7. (剩1/7 + 2/7 = 3/7)

第五天：给他1/7。我们（剩2/7）

第六天：要回1/7，然后给剩下的2/7。（剩1/7）

第七天：给他1/7。我们（剩0）