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

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

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

字串

普通数组

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

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

P56 合并区间 M #排序

56. 合并区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> ans = new ArrayList<>();
    // 添加第1个元素（初始化第一个对照标准）
    ans.add(intervals[0]);

    for (int[] interval : intervals) {
        int curLeft = interval[0];
        int curRight = interval[1];
        int curIndex = ans.size() - 1;
        // 如果当前元素左侧点 大于 结果数组的右侧节点 => 新的区间则添加
        if (curLeft > ans.get(curIndex)[1]) {
            ans.add(new int[]{curLeft, curRight});
        } else { // 否则就是有交集 => 则更新右侧边界
            ans.get(curIndex)[1] = Math.max(ans.get(curIndex)[1], curRight);
        }
    }
    return ans.toArray(new int[ans.size()][]);
}

矩阵

链表

当前栏有一些不是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;
}

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

P25 翻转 K 个一组链表 H

25. K 个一组翻转链表

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
public ListNode reverseKGroup(ListNode head, int k) {
    // 定义哑节点，用于返回整个链表
    // 定义 pre 节点，记录前驱节点位置
    // 定义 end 节点，记录末端
    ListNode dummy = new ListNode(-1, head);
    ListNode pre = dummy;
    ListNode end = dummy;

    // 一直将 end 遍历到尾部
    while (end != null) {
        // 让节点 end 位移到 right 位置
        // 如果当前是最后一段，还要判断不能出界
        for (int i = 0; i < k && end != null; i++) {
            end = end.next;
        }
        if (end == null) {// 如果 end 为 null，则表示已经到达链表末尾
            break;
        }
        // 记录
        ListNode start = pre.next;
        ListNode endNext = end.next;
        // 断链
        end.next = null;
        // 反转 + 指向
        ListNode reversedHead = reverse(start); // 反转后的头节点

        // 头节点连接反转后的子链表
        pre.next = reversedHead;
        start.next = endNext;

        // 还原（让pre和end从start开始重新计算，就像最开始的dummy一样）
        pre = start;
        end = start;
    }
    return dummy.next;
}

private ListNode reverse(ListNode node) {
    ListNode pre = null;
    ListNode cur = node;
    while (cur != null) {
        ListNode temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

画图帮助理解：

最开始的时候

1
2
3
4
5
6
dummy   pre
        end
             1     2     3     4     5     6
// ListNode dummy = new ListNode(-1, head);
// ListNode pre = dummy;
// ListNode end = dummy;

第一次遍历（k=3）

1
2
3
4
5
dummy  pre
           start        end  endNext
             1     2     3     4     5     6
// ListNode start = pre.next
// ListNode endNext = end.next

然后翻转后

1
2
3
4
5
dummy  pre 	(reversedHead)
                end        start  endNext
                 3     2     1      4     5     6
// ListNode reversedHead = reverse(start);// reversedHead其实就是现在的end节点
// pre.next = reversedHead; 			  // 连接翻转前的最后一个节点位置（现在是第一个节点）

然后进行连接后

1
2
3
4
5
6
7
dummy  				   pre
                       end    endNext
                       start
             3     2     1      4     5     6
// 还原（让pre和end从start开始重新计算，就像最开始的dummy一样）
// pre = start;
// end = start;

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( )的时候，但是你在过程中输出队列的内部结构，他不一定是保证内部也是顺序的

P146 LRU缓存 M🧣

146. LRU 缓存

此题，没什么可说的

摘抄自牛客评论：2024.09.26腾讯一面 / 深信服成都线下(A4纸上手写) / 华为笔试题 / 字节面试题(在此基础上加入过期时间)

字节面试题拓展解析：给每个节点增加一个expiryTime属性，这个时间戳表示节点的过期时间。当创建或更新节点时，基于当前时间加上设定的生存时间（ttl）计算这个时间戳。当尝试获取一个节点时，首先检查该节点是否存在，然后判断它的expiryTime是否小于当前时间（即节点是否已经过期）。这样，每次访问节点时只会检查该节点。

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
94
95
96
97
98
99
100
101
/**
 * @Author: CALYEE
 * @CreateTime: 2024-09-29
 * @Description: 最少使用的缓存
 * @Version: 1.0
 */
public class LRUCache {

    private Entry head, tail;
    private int capacity;
    private int size;
    private Map<Integer, Entry> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>(capacity + 2);
        head = new Entry();
        tail = new Entry();
        this.size = 0;
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        Entry entry = cache.get(key);
        if (entry != null) {
            // 需要把当前节点移动到顶部
            moveToHead(entry);
            return entry.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        Entry entry = cache.get(key);
        if (entry != null) {
            entry.value = value;
            moveToHead(entry);
            return;
        }
        // 如果容量满了，删除尾节点
        if (size == capacity) {
            Entry del = tail.pre;
            delCurrentNode(del);
            cache.remove(del.key);
            size--;
        }
        Entry e = new Entry(key, value);
        cache.put(key, e);
        moveToHead(e);
        size++;
    }

    /**
     * 把当前节点置顶
     *
     * @param entry 当前节点
     */
    private void moveToHead(Entry entry) {
        // 1. 移除旧关系：先移除node2，然后连接node3和node1
        delCurrentNode(entry);
        // 2. 然后处理移动头结点关系
        head.next.pre = entry;       // head结点的后面的节点的前指针指向当前节点
        entry.next = head.next;      // 当前节点连接head结点的下一个节点（原始节点）
        entry.pre = head;            // 当前节点的前指针为head
        head.next = entry;           // head节点的下一个指针为当前节点
    }

    /**
     * 删除当前节点
     *
     * @param entry 当前节点
     */
    private void delCurrentNode(Entry entry) {
        // 1. 移除旧关系：先移除node2，然后连接node3和node1
        if (entry.pre != null) {
            entry.pre.next = entry.next;
        }
        if (entry.next != null) {
            entry.next.pre = entry.pre;
        }
    }

    /**
     * 双向链表
     */
    class Entry {
        int key;
        int value;
        Entry next;
        Entry pre;

        public Entry() {
        }

        public Entry(int _key, int _value) {
            this.key = _key;
            this.value = _value;
        }
    }
}

二叉树

P94 二叉树中序遍历 S

94. 二叉树的中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
List<Integer> ans = new ArrayList<>();

public List<Integer> inorderTraversal(TreeNode root) {
    dfs(root);
    return ans;
}

public void dfs(TreeNode root) {
    if (root == null)
        return ;
    dfs(root.left);
    ans.add(root.val);
    dfs(root.right);
}

P104 二叉树的最大深度 S

104. 二叉树的最大深度

深度没别的 直接计算最大值即可

1
2
3
4
5
6
7
8
9
10
11
public int maxDepth(TreeNode root) {
    return dfs(root);
}

public int dfs(TreeNode root) {
    if (root == null)
        return 0;
    int left = dfs(root.left);
    int right = dfs(root.right);
    return Math.max(left, right) + 1;
}

P226 翻转二叉树 S

226. 翻转二叉树

直接交换左右节点位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public TreeNode invertTree(TreeNode root) {
    reserve(root);
    return root;
}

public void reserve(TreeNode root) {
    if (root == null)
        return ;
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    reserve(root.left);
    reserve(root.right);
}

P101 对称二叉树 S

101. 对称二叉树

理解对称是什么样子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isSymmetric(TreeNode root) {
    if (root == null)
        return true;
    return compare(root.left, root.right);
}

public boolean compare(TreeNode l, TreeNode r) {
    if (l == null && r == null)
        return true;
    if (l == null || r == null)
        return false;
    return l.val == r.val           // 比较当前节点
        && compare(l.left, r.right) // 比较当前节点的左左 与 右右
        && compare(l.right, r.left);// 比较当前节点的左右 与 右左
}

P543 二叉树的直径 S

543. 二叉树的直径

直径是说 从左边数到右边数的最长路径（平铺）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int ans = 0;
public int diameterOfBinaryTree(TreeNode root) {
    dfs(root);
    return ans;
}

public int dfs(TreeNode root) {
    if (root == null)
        return 0;
    int left = dfs(root.left);
    int right = dfs(root.right);
    ans = Math.max(ans, left + right); // 此处细节处 
    return Math.max(left, right) + 1;
}

对于为什么需要一个ans来表示最后的结果：可以参考大佬解答

P102 二叉树的层序遍历 M 🧣

102. 二叉树的层序遍历

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
List<List<Integer>> ans = new ArrayList<>();

public List<List<Integer>> levelOrder(TreeNode root) {
    dfs(root);
    return ans;
}

public void dfs(TreeNode root) {
    if (root == null)
        return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        List<Integer> temp = new ArrayList<>(); // 渲染层级
        int size = queue.size(); // 层序遍历的关键
        while (size-- > 0) {
            TreeNode node = queue.poll();
            temp.add(node.val);
            if (node.left != null)
                queue.offer(node.left);
            if (node.right != null)
                queue.offer(node.right);
        }
        ans.add(temp);
    }
}

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] =>[[1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

1
2
3
4
5
6
7
8
public static void dfs(List<Integer> arr, List<Integer> track, int start) {
    res.add(new ArrayList<>(track)); // 添加当前组合
    for (int i = start; i < arr.size(); i++) {
        track.add(arr.get(i));
        dfs(arr, track, i + 1);
        track.remove(track.size() - 1);
    }
}
全排列之指定排列长度

排列的长度永远是指定的长度：[1,2,3],[1,2,4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
  * 全排列优化版本
  * 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, i + 1);
        // 3. 撤销选择
        track.remove(track.size() - 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
42
43
44
45
46
47
48
49
50
51
52
53
public int search(int[] nums, int target) {
        int i = lowerBound(nums, target); // 选择其中一种写法即可
        return nums[i] == target ? i : -1;
    }

    // 闭区间写法
    private int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length - 2; // 闭区间 [left, right]
        while (left <= right) { // 区间不为空
            // 循环不变量：
            // nums[left-1] < target
            // nums[right+1] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1; // 范围缩小到 [mid+1, right]
            else
                right = mid - 1; // 范围缩小到 [left, mid-1]
        }
        return left; // 或者 right+1
    }

    // 左闭右开区间写法
    private int lowerBound2(int[] nums, int target) {
        int left = 0, right = nums.length - 1; // 左闭右开区间 [left, right)
        while (left < right) { // 区间不为空
            // 循环不变量：
            // nums[left-1] < target
            // nums[right] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1; // 范围缩小到 [mid+1, right)
            else
                right = mid; // 范围缩小到 [left, mid)
        }
        return left; // 或者 right
    }

    // 开区间写法
    private int lowerBound3(int[] nums, int target) {
        int left = -1, right = nums.length - 1; // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] < target
            // nums[right] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid; // 范围缩小到 (mid, right)
            else
                right = mid; // 范围缩小到 (left, mid)
        }
        return right; // 或者 left+1
    }
}

栈

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();
}

堆

贪心算法

动态规划

动态规划思路养成：（爬楼梯思路）

1.70. 爬楼梯 - 力扣（LeetCode）

2.746. 使用最小花费爬楼梯 - 力扣（LeetCode）

P70 爬楼梯 S

70. 爬楼梯 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
public int climbStairs(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

多维动态规划

技巧

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）。
}

技巧型

并查集

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
public class 并查集 {
    /*
    测试用例
11 10
1 2
3 4
5 2
4 6
2 6
7 11
8 7
9 7
9 11
1 6
运行结果是：
3
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String oneLine = sc.nextLine();
        n = Integer.parseInt(oneLine.split(" ")[0]);
        m = Integer.parseInt(oneLine.split(" ")[1]);
        init();  //初始化是必须的

        StringBuilder sb = new StringBuilder();
        sb.append("Origin Arrays\n").append(Arrays.toString(arrays));

        for (int i = 1; i <= m; i++) {
            String line = sc.nextLine();
            int x = Integer.parseInt(line.split(" ")[0]);
            int y = Integer.parseInt(line.split(" ")[1]);
            //开始合并犯罪团伙
            merge(x, y);
        }

        //最后扫描有多少个独立的犯罪团伙
        for (int i = 1; i <= n; i++) {
            if (arrays[i] == i)
                sum++;
        }

        sb.append("\nThere are ").append(sum).append(" criminal groups.\n")
                .append("Processed Arrays\n")
                .append(Arrays.toString(arrays));
        System.out.println(sb.toString());

    }
    
    private static int[] arrays;
    /**
     * 可以输入以下数据进行验证。第一行n m，n表示强盗的人数，m表示警方搜集到的m条线索。接下来的m行每一行有两个数a和b，表示强盗a和强盗b是同伙。
     */
    private static int n, m, sum = 0;
    
    //这里是初始化，非常地重要，数组里面存的是自己数组下标的编号就好了。
    private static void init() {
        // 我们初始化是从1开始的，0用不上
        arrays = new int[n + 1];
        for (int i = 1; i <= n; i++)
            arrays[i] = i;
    }

    //这是找爹的递归函数，不停地去找爹，直到找到祖宗为止，其实就是去找犯罪团伙的最高领导人，
    //“擒贼先擒王”原则。
    private static int getParent(int v) {
        // 如果是自己的话 直接返回了
        if (arrays[v] == v)
            return v;
        else {
            //这里是路径压缩，每次在函数返回的时候，顺带把路上遇到的人的“BOSS”改为最后找
            //到的祖宗编号，也就是犯罪团伙的最高领导人编号。这样可以提高今后找到犯罪团伙的
            //最高领导人（其实就是树的祖先）的速度。
            arrays[v] = getParent(arrays[v]); //这里进行了路径压缩
            return arrays[v];
        }
    }

    //这里是合并两子集合的函数
    private static void merge(int v, int u) {
        //t1、t2分别为v和u的大BOSS（首领），每次双方的会谈都必须是各自最高领导人才行
        int t1 = getParent(v);
        int t2 = getParent(u);
        //判断两个结点是否在同一个集合中，即是否为同一个祖先。
        if (t1 != t2) {
            arrays[t2] = t1;//“靠左”原则，左边变成右边的BOSS。即把右边的集合，作为左边集合的子集合。
        }
    }
}

日常区记录

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

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

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();
}

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，）即是否影响下一位

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();
}

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

遇到的一些题

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

[数字马力 面试] 秋招 初试

多线程实现循环打印ABC（ReentrantLock + Condition）

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
/**
 * @Author: CALYEE
 * @CreateTime: 2024-10-09
 * @Description: 多线程轮流打印ABC
 * @Version: 1.0
 */
public class CirThreadPrint {
    private char[] charsToPrint;
    private int currentCharIndex = 0;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition condition = lock.newCondition();

    public CirThreadPrint(String chars) {
        this.charsToPrint = chars.toCharArray();
    }

    public void print() {
        for (int i = 0; i < charsToPrint.length; i++) {
            lock.lock(); // 获取锁
            try {
                // 当前线程应该打印的字符索引是(i)，循环直到当前索引等于currentCharIndex % charsToPrint.length
                while (currentCharIndex % charsToPrint.length != i) {
                    condition.await(); // 如果不是当前线程的轮次，则等待
                }
                // 当前线程的轮次，打印对应的字符
                System.out.print(charsToPrint[i]);
                // 更新currentCharIndex，以便下一个字符可以被打印
                currentCharIndex++;
                // 唤醒所有等待的线程，以便它们可以检查是否轮到它们执行
                condition.signalAll();
            } catch (InterruptedException e) {
                // 如果线程在等待过程中被中断，打印堆栈跟踪信息
                e.printStackTrace();
            } finally {
                // 在try块之后执行，确保锁被释放
                lock.unlock();
            }
        }
    }

    public static void main(String[] args) {
        String charsToPrint = "123";
        CirThreadPrint alternatePrint = new CirThreadPrint(charsToPrint);
        for (int i = 0; i < charsToPrint.length(); i++) {
            new Thread(() -> alternatePrint.print()).start();
        }
    }
}

[去哪儿旅行 笔试]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 2024

传染病防控

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);
    }
}

[58同城 笔试] 9.20 2024

合并时间区间

AC 0.1538

输入 [[0,3],[5,9],[11,13]],[[2,6],[8,10]]

输出 [[2,3],[5,6],[8,9]]

输入 [[1,2],[3,4]],[[2,3]]

输出 [[2,2],[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
32
33
34
35
36
37
38
39
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param firstList  int整型二维数组
 * @param secondList int整型二维数组
 * @return int整型二维数组
 */
public static int[][] findIntersection(int[][] firstList, int[][] secondList) {
    // write code here
    if (firstList.length == 0 || secondList.length == 0) {
        return firstList.length == 0 ? firstList : secondList;
    }
    int[][] ans = new int[1000][];
    // 遍历两个数组，判断是否有交集，有则加入结果数组中，没有则跳过
    for (int i = 0; i < firstList.length; i++) {// f[i] []
        int left = 0, right = 0;
        for (int j = 0; j < secondList.length; j++) {
            // 1，2    2，3
            if (left <= right) {
                left = Math.max(firstList[i][0], secondList[i][0]);
                right = Math.min(firstList[i][1], secondList[i][1]);
                ans[i] = new int[]{left, right};
            }
        }
    }
    return ans;
    // 上面的有问题
    //List<int[]> ans = new ArrayList<>();
    //        for (int[] interval1 : firstList) {
    //            for (int[] interval2 : secondList) {
    //                int left = Math.max(interval1[0], interval2[0]);
    //                int right = Math.min(interval1[1], interval2[1]);
    //                if (left <= right) {
    //                    ans.add(new int[]{left, right});
    //                }
    //            }
    //        }
    //        return ans.toArray(new int[0][]);
}

字符串得分

AC 0.6

输入：abbbab

输出： 5

将字符串 s 划分为两个非空子字符串的可行方案有：

左子字符串 = “a” 且 右子字符串 = “bbbab”，得分 = 1 + 4 = 5

左子字符串 = “ab” 且 右子字符串 = “bbab”，得分 = 1 + 3 = 4

左子字符串 = “abb” 且 右子字符串 = “bab”，得分 = 1 + 2 = 3

左子字符串 = “abbb” 且 右子字符串 = “ab”，得分 = 1 + 1 = 2

左子字符串 = “abbba” 且 右子字符串 = “b”，得分 = 2 + 1 = 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
/**
* 给你一个由若干 a和b 组成的字符串 s，请你计算并返回将该字符串分割
* 成两个非空子字符串（即左子字符串和右子字符串）所能获得的最大
* 得分。
* 「分割字符串的得分」为左子字符串中a的数量加上右子字符串中b的数
* 量。
*
* @param str string字符串
* @return int整型
*/
public static int StringSplit(String str) {
    // write code here
    int ans = 0;
    if ("".equals(str)) return 0;
    for (int i = 1; i < str.length(); i++) {
        String left = str.substring(0, i + 1);
        String right = str.substring(i + 1);
        int leftC = 0, rightC = 0;
        // 左边
        for (int j = 0; j < left.length(); j++) {
            if (left.charAt(j) == 'a') {
                leftC++;
            }
        }
        // 右边
        for (int k = 0; k < right.length(); k++) {
            if (right.charAt(k) == 'b') {
                rightC++;
            }
        }
        ans = Math.max(ans, leftC + rightC);
    }
    return ans;
}

忘记叫什么名的题

​ AC 50

​ 输入 1,2,3

​ 输出 3

​ 存在 3 种从 1 到 2 且恰好移动 3 步的方法：

​ - 1 -> 2 -> 3 -> 2.

​ - 1 -> 2 -> 1 -> 2.

​ - 1 -> 0 -> 1 -> 2.

​ 可以证明不存在其他方法，所以返回 3

​ ===

​ 输入 2,5,10

​ 输出 0

​ 不存在从 2 到 5 且恰好移动 10 步的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 最初，你站在无限数轴上位置 startPos 处。
 * 给你两个正整数startPos和endPos。
 * 在一次移动中，你可以向左或者向右移动一个位置。
 * 给你一个正整数k，返回从 startPos 出发、恰好移动k 步并到达 endPos
 * 的不同方法数目。
 * 由于答案可能会很大，返回对10^9+7取余的结果。
 * 如果所执行移动的顺序不完全相同，则认为两种方法不同。
 * 注意：数轴包含负整数。
 *
 * @param startPos int整型
 * @param endPos   int整型
 * @param k        int整型 < 1000
 * @return int整型
 */
public int numberOfWays(int startPos, int endPos, int k) {
    // write code here
    return 0; // AC 50
}

[深信服 笔试] 9.22 2024

气死了 菜就多练，本来能A三个的，现在这么久都忘记了

全排列

（全部情况：包括一个的 不是指定长度）

1
2
3
4
5
6
7
8
public static void dfs(List<Integer> arr, List<Integer> track, int start) {
    res.add(new ArrayList<>(track));
    for(int i = 0;i < arr.length; i++){
        track.add(arr.get(i));
        dfs(arr, track, start+1);
        track.remove(track.size() - 1);
    }
}

滑动窗口（最长连续序列）

不是力扣那个，这个是有重复元素的比如 [1,1,2,3,3,3,4,5,6,7,8,8,8,9]

linux path 模拟栈

[数字马力 笔试]AC 最简单的一次 9.24 2024

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
public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // abcaaXY12ab12
        String aaa = sc.nextLine();
        findRepeatWord(aaa);
    }

    // 给定字符串，找出有重复的字符，并输出其位置
    public static void findRepeatWord(String str) {
        Map<Character, List<Integer>> map = new HashMap<>();
        List<Character> set = new ArrayList<>(); // 用来排序的，其实可以直接拼接（此代码不优化）
        for (int i = 0; i < str.length(); i++) {
            if (!set.contains(str.charAt(i)))
                set.add(str.charAt(i));
            if (map.containsKey(str.charAt(i))) {
                map.get(str.charAt(i)).add(i + 1);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(i + 1);
                map.put(str.charAt(i), list);
            }
        }
        Map<Character, List<Integer>> ans = new HashMap<>();
        map.forEach((k, v) -> {
                    if (v.size() != 1) {
                        ans.put(k, v);
                    }
                }
        );
        StringBuilder sb = new StringBuilder();
        set.forEach(item -> {
            if (ans.containsKey(item)) {
                ans.get(item).forEach(i -> {
                    sb.append(item)
                            .append(", ")
                            .append(i)
                            .append("; ");
                });
            }
        });
        System.out.println(sb.toString());
    }
}

场景题

分金条问题

问题描述：雇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）