手撕相关 | cwp0

经典题型

链表

有序链表合并

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 虚拟头结点
    ListNode dummy = new ListNode(-1), p = dummy;
    ListNode p1 = l1, p2 = l2;
    while (p1 != null && p2 != null) {
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 指针
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // p 指针不断前进
        p = p.next;
    }
    if (p1 != null) {
        p.next = p1;
    }
    if (p2 != null) {
        p.next = p2;
    }
    return dummy.next;
}

拓展：有序数组合并

public int[] mergeTwoArrays(int[] arr1, int[] arr2) {
    // 创建一个结果数组，长度为两个数组之和
    int[] result = new int[arr1.length + arr2.length];
    int i = 0, j = 0, k = 0;

    // 当两个数组都没有遍历完时，依次比较两个数组的当前元素
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] <= arr2[j]) {
            result[k++] = arr1[i++];
        } else {
            result[k++] = arr2[j++];
        }
    }
    // 如果第一个数组还有剩余，直接加入结果数组
    while (i < arr1.length) {
        result[k++] = arr1[i++];
    }
    // 如果第二个数组还有剩余，直接加入结果数组
    while (j < arr2.length) {
        result[k++] = arr2[j++];
    }
    return result;
}

拓展：有序数组逆序合并

public int[] mergeTwoArraysInReverseOrder(int[] arr1, int[] arr2) {
    // 创建一个结果数组，长度为两个数组之和
    int[] result = new int[arr1.length + arr2.length];
    int i = arr1.length - 1, j = arr2.length - 1, k = 0;

    // 当两个数组都没有遍历完时，依次比较两个数组的当前元素（从末尾开始）
    while (i >= 0 && j >= 0) {
        if (arr1[i] >= arr2[j]) {
            result[k++] = arr1[i--];
        } else {
            result[k++] = arr2[j--];
        }
    }
    // 如果第一个数组还有剩余，从末尾加入结果数组
    while (i >= 0) {
        result[k++] = arr1[i--];
    }
    // 如果第二个数组还有剩余，从末尾加入结果数组
    while (j >= 0) {
        result[k++] = arr2[j--];
    }
    return result;
}

重排链表

class Solution {
    public void reorderList(ListNode head) {
        Stack<ListNode> stk = new Stack<>();
        // 先把所有节点装进栈里，得到倒序结果
        ListNode p = head;
        while (p != null) {
            stk.push(p);
            p = p.next;
        }

        p = head;
        while (p != null) {
            ListNode lastNode = stk.pop(); // 链表尾部的节点
            ListNode next = p.next; // 链表头部节点的下一个节点
            if (lastNode == next || lastNode.next == next) {
                // 结束条件，链表节点数为奇数或偶数时均适用
                lastNode.next = null;
                break;
            }
            // 将链表尾部的节点 加入 1 2 之间
            p.next = lastNode; // 链表头部节点的指针 指向 链表尾部节点
            lastNode.next = next; // 链表尾部节点 指向 链表头部节点的下一个节点
            p = next;
        }
    }
}

给定x分解单链表，使得小于x的数都在x之前

ListNode partition(ListNode head, int x) {
    // 存放小于 x 的链表的虚拟头结点
    ListNode dummy1 = new ListNode(-1);
    // 存放大于等于 x 的链表的虚拟头结点
    ListNode dummy2 = new ListNode(-1);
    // p1, p2 指针负责生成结果链表
    ListNode p1 = dummy1, p2 = dummy2;
    // p 负责遍历原链表，类似合并两个有序链表的逻辑
    // 这里是将一个链表分解成两个链表
    ListNode p = head;
    while (p != null) {
        if (p.val >= x) {
            p2.next = p;
            p2 = p2.next;
        } else {
            p1.next = p;
            p1 = p1.next;
        }
        // 不能直接让 p 指针前进，
        // p = p.next
        // 断开原链表中的每个节点的 next 指针
        ListNode temp = p.next;
        p.next = null;
        p = temp;
    }
    // 连接两个链表
    p1.next = dummy2.next;
    return dummy1.next;
}

返回链表的倒数第k个节点

快慢指针法

// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) {
        p1 = p1.next;
    }
    ListNode p2 = head;
    // p1 和 p2 同时走 n - k 步
    while (p1 != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
    // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
    return p2;
}

寻找链表的中间节点

快慢指针法

ListNode middleNode(ListNode head) {
    // 快慢指针初始化指向 head
    ListNode slow = head, fast = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
    }
    // 慢指针指向中点
    return slow;
}

判断链表是否包含环

快慢指针法

boolean hasCycle(ListNode head) {
    // 快慢指针初始化指向 head
    ListNode slow = head, fast = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指针相遇，说明含有环
        if (slow == fast) {
            return true;
        }
    }
    // 不包含环
    return false;
}

如果链表有环，找到环的入口

class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        // 上面的代码类似 hasCycle 函数
        if (fast == null || fast.next == null) {
            // fast 遇到空指针说明没有环
            return null;
        }
        // 重新指向头结点
        slow = head;
        // 快慢指针同步前进，相交点就是环起点
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

相交链表

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

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // p1 指向 A 链表头结点，p2 指向 B 链表头结点
    ListNode p1 = headA, p2 = headB;
    while (p1 != p2) {
        // p1 走一步，如果走到 A 链表末尾，转到 B 链表
        if (p1 == null) p1 = headB;
        else            p1 = p1.next;
        // p2 走一步，如果走到 B 链表末尾，转到 A 链表
        if (p2 == null) p2 = headA;
        else            p2 = p2.next;
    }
    return p1;
}

反转整个链表

递归法

public class ListNode {
    public int val;
    public ListNode next;

    public ListNode () {};
    public ListNode (int val) { this.val = val; }
    public ListNode (int val, ListNode next) { this.val = val; this.next = next; }
}
// 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode last = reverse(head.next); // 除了头结点外，反转其余结点，last 为新的头结点
    head.next.next = head; // 其余节点反转好了，将反转后的链表的尾结点指向头节点
    head.next = null; // 头结点原本指向第二个元素，现在指向空节点
    return last; // 返回新的头结点
}
// 打印链表的函数
public static void printList(ListNode head) {
    ListNode current = head;
    while (current != null) {
        System.out.print(current.val + " ");
        current = current.next;
    }
    System.out.println();
}
public static void main(String[] args) {
    // 创建链表 1 -> 2 -> 3 -> 4 -> 5
    ListNode head = new ListNode(1);
    head.next = new ListNode(2);
    head.next.next = new ListNode(3);
    head.next.next.next = new ListNode(4);
    head.next.next.next.next = new ListNode(5);

    System.out.println("原始链表:");
    printList(head);

    // 反转链表
    ListNode reversedHead = reverse(head);

    System.out.println("反转后的链表:");
    printList(reversedHead);
}

反转部分链表

递归法

ListNode successor = null; // 后驱节点
ListNode reverseBetween(ListNode head, int m, int n) {
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 reverseN
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}
// 反转以 head 为起点的前 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点，反转前 n - 1 个节点
    ListNode last = reverse(head.next, n - 1); // 除了头节点，反转地 2-n 个节点，last 为第 n 个节点，也是新的头节点
    head.next.next = head; // 其余节点反转好了，将反转后的链表的尾结点指向头节点
    head.next = successor; // 让反转之后的 head 节点和后面的节点successor连起来
    return last; // 返回新的头结点
}

k 个一组翻转链表

ListNode reverseKGroup(ListNode head, int k) {
    if (head == null) return null;
    // 区间 [a, b) 包含 k 个待反转元素
    ListNode a, b;
    a = b = head;
    for (int i = 0; i < k; i++) {
        // 不足 k 个，不需要反转，base case
        if (b == null) return head;
        b = b.next;
    }
    // 反转前 k 个元素
    ListNode newHead = reverse(a, b);
    // 递归反转后续链表并连接起来
    a.next = reverseKGroup(b, k);
    return newHead;
}
// 反转区间 [a, b) 的元素，注意是左闭右开
ListNode reverse(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    // while 终止的条件改一下就行了
    while (cur != b) {
        nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> originToClone = new HashMap<>();
        // 第一次遍历，先把所有节点克隆出来
        for (Node p = head; p != null; p = p.next) {
            if (!originToClone.containsKey(p)) {
                originToClone.put(p, new Node(p.val));
            }
        }
        // 第二次遍历，把克隆节点的结构连接好
        for (Node p = head; p != null; p = p.next) {
            if (p.next != null) {
                originToClone.get(p).next = originToClone.get(p.next);
            }
            if (p.random != null) {
                originToClone.get(p).random = originToClone.get(p.random);
            }
        }
        // 返回克隆之后的头结点
        return originToClone.get(head);
    }
}

有序链表删除重复元素(一个不留)

public class RemoveDuplicates {
    // Definition for singly-linked list.
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode current = head;

        while (current != null) {
            boolean isDuplicate = false;
            while (current.next != null && current.val == current.next.val) {
                isDuplicate = true;
                current = current.next;
            }
            if (isDuplicate) {
                prev.next = current.next;
            } else {
                prev = prev.next;
            }
            current = current.next;
        }
        return dummy.next;
    }
    // Utility function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // Read input
        int n = scanner.nextInt();
        if (n == 0) {
            System.out.println();
            return;
        }
        ListNode head = new ListNode(scanner.nextInt());
        ListNode current = head;
        for (int i = 1; i < n; i++) {
            current.next = new ListNode(scanner.nextInt());
            current = current.next;
        }
        // Process
        head = deleteDuplicates(head);
        // Output result
        printList(head);
    }
}

数组

动态规划

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution {
    // 备忘录
    int[] memo;

    public int climbStairs(int n) {
        memo = new int[n + 1];
        return dp(n);
    }

    // 定义：爬到第 n 级台阶的方法个数为 dp(n)
    int dp(int n) {
        // base case
        if (n <= 2) {
            return n;
        }
        if (memo[n] > 0) {
            return memo[n];
        }
        // 状态转移方程：
        // 爬到第 n 级台阶的方法个数等于爬到 n - 1 的方法个数和爬到 n - 2 的方法个数之和。
        memo[n] = dp(n - 1) + dp(n - 2);
        return memo[n];
    }
}

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组(子数组最少包含一个元素)，返回其最大和。

// 动态规划
public int maxSubArray(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    // 定义：dp[i] 记录以 nums[i] 为结尾的「最大子数组和」
    int[] dp = new int[n];
    // base case
    // 第一个元素前面没有子数组
    dp[0] = nums[0];
    // 状态转移方程
    // dp[i] 有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。
    for (int i = 1; i < n; i++) {
        dp[i] = Math.max(nums[i] + dp[i - 1], nums[i]);
    }
    // 得到 nums 的最大子数组
    int res = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
}

最长递增子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        // dp解题 dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
        int[] dp = new int[n + 1];
        // base case 最长递增子序列最短为其本身
        Arrays.fill(dp, 1);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

编辑距离

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。

class Solution {
    // 备忘录
    private int[][] memo;
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        memo = new int[m][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        return dp(word1, m - 1, word2, n - 1);
    }

    // 定义dp[s1, i, s2, j] 为s1[0..i]变为s2[0..j]的最小编辑距离
    private int dp(String s1, int i, String s2, int j) {
        // base case
        // 如果是s1从末尾走到了头，则需要将s2剩下的长度一个个插入s1，所以返回s2剩余长度
        if (i == -1) return j + 1;
        // 如果是s2从末尾走到了头，则需要将s1剩下的长度一个个删除，所以返回s2剩余长度
        if (j == -1) return i + 1;

        if (memo[i][j] != -1) {
            return memo[i][j];
        }

        // 状态转移函数
        if (s1.charAt(i) == s2.charAt(j)) {
            // 如果s1在i处的字符和s2在j处的字符相等，则不做操作，编辑距离不变。
            // dp[s1, i, s2, j] == dp[s1, i-1, s2, j-1]
            memo[i][j] = dp(s1, i - 1 , s2, j - 1);
        } else {
            // 如果不想等，则找出三种情况：插入、删除、替换操作的最小编辑距离的那个
            // 插入：在s1[i]后插入s2[j], s2前进，变为s2[j-1]继续与s1[i]比较，编辑次数+1
            // 替换：s1[i]替换为s2[j]，s1和s2都前进，变为s1[i-1]和s2[j-1]，编辑次数+1
            // 删除：删除s1[i]处的字符，s1前进，变为s1[i-1]继续与s2[j]比较，编辑次数+1
            memo[i][j] = min(
                dp(s1, i, s2, j - 1) + 1,
                dp(s1, i - 1, s2, j - 1) + 1,
                dp(s1, i - 1, s2, j) + 1
            );
        }
        return memo[i][j];

    }

    private int min(int a, int b, int c) {
        return Math.min(Math.min(a, b), c);
    }

}

最长回文子序列

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        // 定义dp[i][j]为 s[i..j]之间的最长回文子序列
        int[][] dp = new int[n][n];
        // base case
        // 每个字符处，最长回文子序列为其本身，长度1
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        // i > j处，不存在子序列，全部为0
        for (int i = n-2; i >= 0; i--) {
            for (int j = i+1; j < n; j++) {
                // 状态转移函数
                if (s.charAt(i) == s.charAt(j)) {
                    // 如果s在i处的字符和s在j处的字符相等，则两字符同时加入dp[i+1][j-1],长度+2
                    dp[i][j] = dp[i+1][j-1] + 2;
                } else {
                    // 如果不相等，则两字符不能同时出现在最长回文子序列中，把两个字符都加入，看看哪个更长
                    dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
                }

            }
        }
        return dp[0][n-1];
    }
}

最长公共子序列

class Solution {
    // 备忘录
    private int[][] memo;
    public int longestCommonSubsequence(String text1, String text2) {
        memo = new int[text1.length()][text2.length()];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dp(text1, 0, text2, 0);
    }
    // 定义dp[s1, i, s2, j]为s1[i..]和s2[j..]的最长公共子序列
    private int dp(String s1, int i, String s2, int j) {
        // base case
        // 相当于是s1 最右边的空串 和s2 最右边的空串的最长公共子序列，为0
        if (i == s1.length() || j == s2.length()) return 0;
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        // 状态转移函数
        if (s1.charAt(i) == s2.charAt(j)) {
            // 如果s1在i处的字符和s2在j处的字符相等，则该字符必定属于最长公共子序列，长度+1，s1、s2都前进向下一字符比较
            memo[i][j] = 1 + dp(s1, i+1, s2, j+1);
        } else {
            // 如果s1在i处的字符和s2在j处的字符不相等，三种情况:
            // 1. s1在i处的字符不属于最长公共子序列，但s2所在j处的字符属于最长公共子序列，则s1前进至下一字符
            // 2. s2在j处的字符不属于最长公共子序列，但s1所在i处的字符属于最长公共子序列，则s2前进至下一字符
            // 3. s1在i处的字符和s2在j处的字符都不属于最长公共子序列，但这种情况下最长公共子序列的长度肯定没有前两种长，忽略dp(s1, i+1, s2, j+1)
            memo[i][j] = Math.max(dp(s1, i+1, s2, j), dp(s1, i, s2, j+1));
        }
        return memo[i][j];
    }
}

最长有效括号

给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效(格式正确且连续)括号子串的长度。

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stk = new Stack<>();
        // dp[i] 的定义：记录以 s[i-1] 结尾的最长合法括号子串长度
        int[] dp = new int[s.length() + 1];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                // 遇到左括号，记录索引
                stk.push(i);
                // 左括号不可能是合法括号子串的结尾
                dp[i + 1] = 0;
            } else {
                // 遇到右括号
                if (!stk.isEmpty()) {
                    // 配对的左括号对应索引
                    int leftIndex = stk.pop();
                    // 以这个右括号结尾的最长子串长度
                    int len = 1 + i - leftIndex + dp[leftIndex];
                    dp[i + 1] = len;
                } else {
                    // 没有配对的左括号
                    dp[i + 1] = 0;
                }
            }
        }
        // 计算最长子串的长度
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

小于k的最大数

用指定的几个个位数（可重复）表示出小于n的最大整数
样例：2、4、7表示27221 -> 24777

import java.util.Arrays;

public class MaxNumberLessThanN {
    
    // 从指定数字集合中找小于等于给定数的最大值
    public static int getLargest(int[] digits, int limit) {
        int result = -1;
        for (int digit : digits) {
            if (digit <= limit) {
                result = Math.max(result, digit);
            }
        }
        return result;
    }

    // 返回用 digits 中的数字构造的，不超过 n 的最大数字
    public static String findMax(int[] digits, String n) {
        char[] nArray = n.toCharArray();
        int length = nArray.length;
        char[] result = new char[length];
        boolean hasSmaller = false;
        
        // 排序 digits 方便后面处理
        Arrays.sort(digits);
        
        for (int i = 0; i < length; i++) {
            int limit = nArray[i] - '0';
            int largest = getLargest(digits, limit);
            
            if (largest == -1) {
                // 找不到合适的数字，回退
                int j = i - 1;
                while (j >= 0 && result[j] == (char)(digits[0] + '0')) {
                    j--;
                }
                
                if (j < 0) {
                    // 找不到合适的结果，只能用最大数字构造小一位的数字
                    char[] newResult = new char[length - 1];
                    Arrays.fill(newResult, (char)(digits[digits.length - 1] + '0'));
                    return new String(newResult);
                }
                
                result[j] = (char)(getLargest(digits, result[j] - '0' - 1) + '0');
                for (int k = j + 1; k < length; k++) {
                    result[k] = (char)(digits[digits.length - 1] + '0');
                }
                return new String(result);
            }
            
            result[i] = (char)(largest + '0');
            if (largest < limit) {
                // 如果找到比当前位小的数字，后续位可以用最大数字填充
                for (int j = i + 1; j < length; j++) {
                    result[j] = (char)(digits[digits.length - 1] + '0');
                }
                return new String(result);
            }
        }
        
        return new String(result);
    }

    public static void main(String[] args) {
        int[] digits = {2, 4, 7}; // 给定的数字
        String n = "27221";        // 给定的数字 n
        
        String result = findMax(digits, n);
        System.out.println(result); // 输出：24777
    }
}

最长回文子串

class Solution {

    public String palindrome(String s, int l, int r) {
        while (l >= 0 && r <= s.length() -1 && s.charAt(l) == s.charAt(r)) {
            l --;
            r ++;
        }
        // 注意这里的l+1，原因是前面的while循环在s.charAt(l) == s.charAt(r)执行之前会l--和r++，在不满足前面条件时，已经进行了l--和r++，所以需要加回来。
        return s.substring(l+1, r);
    }
    public String longestPalindrome(String s) {
        String res = "";
        for (int i = 0; i < s.length(); i ++) {
            // 以 s[i] 为中心的最长回文子串
            String s1 = palindrome(s, i, i);
            // 以 s[i] 和 s[i+1] 为中心的最长回文子串
            String s2 = palindrome(s, i, i + 1);
            // res = longest(res, s1, s2)
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }
        return res;
    }
}

滑动窗口

滑动窗口最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n-k+1];
        int resIndex = 0;
        // pq 存储元素值及索引
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return b[0] - a[0];
            }
        });
        for (int i = 0; i < n; i++) {
            // 将当前元素及其索引添加到 pq 中
            pq.offer(new int[]{nums[i], i});
            // 根据 index 移除掉超出的元素
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            // 当窗口大小达到 k 时，记录当前窗口的最大值
            if (i >= k - 1) {
                res[resIndex++] = pq.peek()[0];
            }
        }
        return res;
    }
}

无重复最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长连续子字符串的长度。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        // 滑动窗口
        HashMap<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            // 增大窗口
            right++;
            // 窗口变化后对数据进行处理
            window.put(c, window.getOrDefault(c, 0) + 1);
            // 是否需要缩小窗口
            while (window.get(c) > 1) {
                char d = s.charAt(left);
                // 缩小窗口
                left++;
                // 窗口变化后对数据进行处理
                window.put(d, window.get(d) - 1);
            }
            // 缩小窗口后保证window内没有重复元素
            res = Math.max(right - left, res);
        }
        return res;
    }
}

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int ans = Integer.MAX_VALUE;
        int left = 0, right = 0;
        int sum = 0;
        // 滑动窗口
        while (right < n) {
            sum += nums[right];
            // 滑动窗口缩小条件
            while (sum >= target) {
                ans = Math.min(ans, right - left + 1);
                sum -= nums[left];
                // 缩小窗口
                left++;
            }
            // 增大窗口
            right++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

缓存淘汰策略

LRU缓存

LRU(Least Recently Used)策略是一种常见的缓存淘汰策略，它的核心思想是：如果数据最近被访问过，那么将来被访问的几率也更高。LRU 算法的实现可以通过哈希表和双向链表来完成。

// 方法 1
class LRUCache {
    // 缓存的容量
    private int cap;
    // 用LinkedHashMap作为cache，尾部为新使用过的数据，头部为未使用过的数据。
    private LinkedHashMap<Integer, Integer> cache;
    public LRUCache(int capacity) {
        this.cap = capacity;
        cache = new LinkedHashMap<>();
    }
    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        makeNew(key);
        return cache.get(key);
    }
    public void put(int key, int value) {
        cache.put(key, value);
        makeNew(key);
        if (cache.size() > this.cap) {
            // 头部的元素是最老的
            int head = cache.keySet().iterator().next();
            cache.remove(head);
        }
    }
    // 让key变为新使用的数据
    private void makeNew(int key) {
        int value = cache.get(key);
        cache.remove(key);
        // 将key添加到LinkedHashMap尾部
        cache.put(key, value);
    }
}
// 方法 2
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    public LRUCache(int capacity) {
        super(capacity, 1f, true);
        this.capacity = capacity;
    }
    // 判断size超过容量时返回true，告知LinkedHashMap移除最老的缓存项(即链表的第一个元素)
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> lruCache = new LRUCache<>(5);
        lruCache.put(1, "apple");
        lruCache.put(2, "banana");
        lruCache.put(3, "pear");
        lruCache.put(4, "watermelon");
        lruCache.put(5, "peach");
        System.out.println(lruCache);
        lruCache.put(6, "orange");
        System.out.println(lruCache);
        lruCache.get(4);
        System.out.println(lruCache);
    }

}

LFU淘汰策略

LFU(Least Frequently Used)策略是根据数据使用的频率来决定淘汰哪一个数据的策略。使用频率最少的数据会被淘汰。

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;

class LFUCache {
    private final int capacity;  // 缓存的最大容量
    private int minFrequency;  // 当前缓存中最小的频率
    private final Map<Integer, Integer> valueMap;  // 存储键到值的映射
    private final Map<Integer, Integer> frequencyMap;  // 存储键到频率的映射
    private final Map<Integer, LinkedHashSet<Integer>> frequencyListMap;  // 存储频率到具有该频率的键集合的映射
    public LFUCache(int capacity) {
        this.capacity = capacity;  // 初始化缓存容量
        this.minFrequency = 0;  // 初始最小频率为0
        this.valueMap = new HashMap<>();  // 初始化键值映射表
        this.frequencyMap = new HashMap<>();  // 初始化键频率映射表
        this.frequencyListMap = new HashMap<>();  // 初始化频率到键集合的映射表
    }
    public int get(int key) {
        if (!valueMap.containsKey(key)) {  // 如果缓存中不包含该键，返回-1
            return -1;
        }
        int frequency = frequencyMap.get(key);  // 获取该键的当前频率
        frequencyMap.put(key, frequency + 1);  // 更新该键的频率
        frequencyListMap.get(frequency).remove(key);  // 从当前频率的键集合中移除该键

        // 如果当前频率的键集合为空且频率等于最小频率，移除该频率并增加最小频率
        if (frequencyListMap.get(frequency).isEmpty()) {
            frequencyListMap.remove(frequency);
            if (frequency == minFrequency) {
                minFrequency++;
            }
        }
        // 将该键添加到新的频率集合中
        frequencyListMap.computeIfAbsent(frequency + 1, k -> new LinkedHashSet<>()).add(key);
        return valueMap.get(key);  // 返回该键对应的值
    }
    public void put(int key, int value) {
        if (capacity <= 0) {  // 如果缓存容量为0或更小，直接返回
            return;
        }
        if (valueMap.containsKey(key)) {  // 如果键已存在，更新其值，并更新频率
            valueMap.put(key, value);
            get(key);  // 调用get方法来更新该键的频率
            return;
        }
        // 如果缓存已满，执行淘汰操作
        if (valueMap.size() >= capacity) {
            // 获取并移除最小频率集合中的第一个键
            int evictKey = frequencyListMap.get(minFrequency).iterator().next();
            frequencyListMap.get(minFrequency).remove(evictKey);
            if (frequencyListMap.get(minFrequency).isEmpty()) {  // 如果最小频率集合为空，移除该频率
                frequencyListMap.remove(minFrequency);
            }
            valueMap.remove(evictKey);  // 从键值映射表中移除被淘汰的键
            frequencyMap.remove(evictKey);  // 从键频率映射表中移除被淘汰的键
        }
        // 插入新键值对，初始频率为1
        valueMap.put(key, value);
        frequencyMap.put(key, 1);
        minFrequency = 1;  // 插入新键后，最小频率重置为1
        // 将新键添加到频率为1的集合中
        frequencyListMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
    }
}

FIFO淘汰策略

FIFO(First In First Out)策略是根据数据进入缓存的顺序来决定淘汰哪一个数据的策略。最早进入缓存的数据会被淘汰。

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
class FIFOCache {
    private final int capacity;
    private final Map<Integer, Integer> map;
    private final Queue<Integer> queue;
    public FIFOCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.queue = new LinkedList<>();
    }
    public int get(int key) {
        return map.getOrDefault(key, -1);
    }
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.put(key, value);
            return;
        }
        if (map.size() >= capacity) {
            int evictKey = queue.poll();
            map.remove(evictKey);
        }
        map.put(key, value);
        queue.add(key);
    }
}

排序算法

链接：https://learn.skyofit.com/archives/1291

复杂度
排序算法总结

概念：

稳定：如果a原本在b前面且a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面且a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
In-Place：占用常数内存，不占用额外内存。比如：程序里没有创建新数组来保存数据，只用了临时变量。
Out-Place：占用额外内存。比如：创建了新的数组来保存或者处理数据。

冒泡排序

基本思想
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为每趟比较将当前数列未排序部分的最大的元素“沉”到数列末端，而小的元素会经由交换慢慢“浮”到数列的顶端。

算法描述

比较相邻的元素。如果前一个比后一个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。为了优化算法，可以设立一个布尔标识，每趟排序开始前设为false，如果该趟排序发生了交换就置为true，如果一趟排序结束标识仍为false表示该趟排序没有发生交换，即数组已经有序，可以提前结束排序。

public static int[] bubbleSort(int[] array) {
    if (array.length == 0)
        return array;
    for (int i = 0; i < array.length; i++){  //外层循环一次为一趟排序
        /*设置标识，判断这趟排序是否发生了交换。
       如果未发生交换，则说明数组已经有序，不必再排序了*/
        boolean isSwap = false;
        //内层循环一次为一次相邻比较
        for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j + 1] < array[j]) {
                int temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
                isSwap = true;
            }
        }
        if (!isSwap)
            break;
    }
    return array;
}

时间复杂度：冒泡排序平均时间复杂度为O(n2)，最好时间复杂度为O(n)，最坏时间复杂度为O(n2)。
最好情况：如果待排序元素本来是正序的，那么一趟冒泡排序就可以完成排序工作，比较和移动元素的次数分别是 (n – 1) 和 0，因此最好情况的时间复杂度为O(n)。
最坏情况：如果待排序元素本来是逆序的，需要进行 (n – 1) 趟排序，所需比较和移动次数分别为 n * (n – 1) / 2和 3 * n * (n-1) / 2。因此最坏情况下的时间复杂度为O(n2)。
空间复杂度：冒泡排序使用了常数空间，空间复杂度为O(1)
稳定性：当 array[j] == array[j+1] 的时候，不交换 array[i] 和 array[j]，所以冒泡排序是稳定的。

拓展：鸡尾酒排序
又称定向冒泡排序、搅拌排序等，是对冒泡排序的改进。在把最大的数往后面冒泡的同时，把最小的数也往前面冒泡，同时收缩无序区的左右边界，有序区在序列左右逐渐累积。
1
2
3
4
5
6
7
8
9
10
11
12
13
public static void cocktailSort(int[] array) {
   int left = 0,right = array.length-1;
   while(left < right) {
       for(int i = left; i < right; i++)
         if(array[i] > array[i+1])
               swap(array,i,i + 1);
       right--;
       for(int i = right; i > left; i--)
         if(array[i] < array[i-1])
               swap(array,i,i-1);
       left++;
   }
}
鸡尾酒排序是稳定的。它的平均时间复杂度为O(n2)，最好情况是待排序列原先就是正序的，时间复杂度为O(n)，最坏情况是待排序列原先是逆序的，时间复杂度为O(n2)。空间复杂度为O(1)。

选择排序

基本思想
简单选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法描述
n个记录的简单选择排序可经过(n-1)趟简单选择排序得到有序结果。具体算法描述如下：

初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n]。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
(n-1)趟结束，数组有序化了。

public static int[] selectionSort(int[] array) {
    if (array.length == 0)
         return array;
    for (int i = 0; i < array.length; i++) {
        int minIndex = i;
        for (int j = i; j < array.length; j++) {
            if (array[j] < array[minIndex]) //找到最小的数
                minIndex = j; //将最小数的索引保存
        }
        int temp = array[minIndex]; //将最小数和无序区的第一个数交换
        array[minIndex] = array[i];
        array[i] = temp;
    }
    return array;
}

时间复杂度：简单选择排序平均时间复杂度为O(n2)，最好时间复杂度为O(n2)，最坏时间复杂度为O(n2)。
最好情况：如果待排序元素本来是正序的，则移动元素次数为 0，但需要进行 n * (n – 1) / 2 次比较。
最坏情况：如果待排序元素中第一个元素最大，其余元素从小到大排列，则仍然需要进行 n * (n – 1) / 2 次比较，且每趟排序都需要移动 3 次元素，即移动元素的次数为3 * (n – 1)次。
- 需要注意的是，简单选择排序过程中需要进行的比较次数与初始状态下待排序元素的排列情况无关。
空间复杂度：简单选择排序使用了常数空间，空间复杂度为O(1)
稳定性：简单选择排序不稳定，比如序列 2、4、2、1，知道第一趟排序第 1 个元素 2 会和 1 交换，那么原序列中 2 个 2 的相对前后顺序就被破坏了，所以简单选择排序不是一个稳定的排序算法。

直接插入排序

基本思想
直接插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法描述
一般来说，直接插入排序都采用in-place(原地算法)在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素(已排序)大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

public static int[] insertionSort(int[] array) {
    if (array.length == 0)
        return array;
    int current;
    for (int i = 1; i < array.length; i++) {
        current = array[i];
        int preIndex = i - 1;
        while (preIndex >= 0 && current < array[preIndex]) {
            array[preIndex + 1] = array[preIndex];
            preIndex--;
        }
        array[preIndex + 1] = current;
    }
    return array;
}

时间复杂度：直接插入排序平均时间复杂度为O(n2)，最好时间复杂度为O(n)，最坏时间复杂度为O(n2)。
最好情况：如果待排序元素本来是正序的，比较和移动元素的次数分别是 (n – 1) 和 0，因此最好情况的时间复杂度为O(n)。
最坏情况：如果待排序元素本来是逆序的，需要进行 (n – 1) 趟排序，所需比较和移动次数分别为 n * (n – 1) / 2和 n * (n – 1) / 2。因此最坏情况下的时间复杂度为O(n2)。
空间复杂度：直接插入排序使用了常数空间，空间复杂度为O(1)
稳定性：直接插入排序是稳定的。

拓展：在直接插入排序中，待插入的元素总是在有序区线性查找合适的插入位置，没有利用有序的优势，考虑使用二分查找搜索插入位置进行优化，即二分插入排序。

public static int[] BinaryInsertionSort(int[] array) {
    if (array.length == 0)
        return array;
    for(int i = 1;i < array.length;i++) {
        int left = 0;
        int right = i - 1;  // left 和 right 分别为有序区的左右边界 
        int current = array[i];
        while (left <= right) {
            //搜索有序区中第一个大于 current 的位置，即为 current 要插入的位置
            int mid = left + ((right - left) >> 1);
            if(array[mid] > current){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        for(int j = i - 1;j >= left;j--) {
            array[j + 1] = array[j];
        }
        array[left] = current; // left 为第一个大于 current 的位置，插入 current
    }
    return array;
}

二分插入排序是稳定的。它的平均时间复杂度是O(n2)，最好时间复杂度为O(nlogn)，最坏时间复杂度为O(n2)。

希尔排序

基本思想
1959年Shell发明，第一个突破O(n2)的排序算法，是直接插入排序的改进版。它与直接插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

算法描述
先将整个待排元素序列分割成 gap 个增量为 gap 的子序列(每个子序列由位置相差为 gap 的元素组成，整个序列正好分割成 gap 个子序列，每个序列中有 n / gap 个元素)分别进行直接插入排序，然后缩减增量为之前的一半再进行排序，待 gap == 1时，希尔排序就变成了直接插入排序。因为此时序列已经基本有序，直接插入排序在元素基本有序的情况下(接近最好情况)，效率是很高的。gap初始值一般取 len / 2。

public static int[] ShellSort(int[] array) {
    int len = array.length;
    if(len == 0)
        return array;
    int current, gap = len / 2;
    while (gap > 0) {
        for (int i = gap; i < len; i++) {
            current = array[i];
            int preIndex = i - gap;
            while (preIndex >= 0 && array[preIndex] > current) {
                array[preIndex + gap] = array[preIndex];
                preIndex -= gap;
            }
            array[preIndex + gap] = current;
        }
        gap /= 2;
    }
    return array;
}

时间复杂度：希尔排序平均时间复杂度为O(nlogn)，最好时间复杂度为O(nlog2n)，最坏时间复杂度为O(nlog2n)。希尔排序的时间复杂度与增量序列的选取有关。
空间复杂度：希尔排序使用了常数空间，空间复杂度为O(1)
稳定性：由于相同的元素可能在各自的序列中插入排序，最后其稳定性就会被打乱，比如序列 2、4、1、2，所以希尔排序是不稳定的。

归并排序

基本思想
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述

把长度为 n 的输入序列分成两个长度为 n / 2 的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

// 归并排序
public static int[] MergeSort(int[] array) {
    if (array.length < 2) return array;
    int mid = array.length / 2;
    int[] left = Arrays.copyOfRange(array, 0, mid);
    int[] right = Arrays.copyOfRange(array, mid, array.length);
    return merge(MergeSort(left), MergeSort(right));
}
// 将两段有序数组结合成一个有序数组
public static int[] merge(int[] left, int[] right) {
   int[] result = new int[left.length + right.length];
   int i = 0,j = 0,k = 0;
   while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result[k++] = left[i++];
        } else {
            result[k++] = right[j++];
        }
    }
    while (i < left.length) {
        result[k++] = left[i++];
    }
    while (j < right.length) {
        result[k++] = right[j++];
    }
    return result;
}

时间复杂度：归并排序平均时间复杂度为O(nlogn)，最好时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)。归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它在任何情况下时间复杂度均是O(nlogn)。
空间复杂度：归并排序空间复杂度为O(n)
稳定性：归并排序是稳定的。

快速排序

基本思想
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述
快速排序使用分治法来把一个数列分为两个子数列。具体算法描述如下：

从数列中挑出一个元素，称为 “基准”(pivot)；
重新排序数列，所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面(相同的数可以到任一边)，该基准就处于数列的中间位置。这称为分区(partition)操作；
递归地(recursive)对小于基准值元素的子数列和大于基准值元素的子数列进行快速排序。

代码实现
快速排序最核心的步骤就是partition操作，即从待排序的数列中选出一个数作为基准，将所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面(相同的数可以到任一边)，该基准就处于数列的中间位置。partition函数返回基准的位置，然后就可以对基准位置的左右子序列递归地进行同样的快排操作，从而使整个序列有序。

两种方法：左右指针法、挖坑法
左右指针法：

将数组的最后一个数 right 作为基准数 key。
分区过程：从数组的首元素 begin 开始向后找比 key 大的数(begin 找大)；end 开始向前找比 key 小的数(end 找小)；找到后交换两者(swap)，直到 begin >= end 终止遍历。最后将 begin(此时begin == end)和最后一个数交换( 这个时候 end 不是最后一个位置)，即 key 作为中间数(左区间都是比key小的数，右区间都是比key大的数)

再对左右区间重复第二步，直到各区间只有一个数。
左右指针法

public class Demo {
    public static void main(String[] args) {
        int[] a = {3, 5, 8, 1, 2, 9, 4, 7, 6};
        sort(a, 0, a.length - 1);
        for(int i = 0; i < a.length; i++){
            System.out.print(a[i] + ",");
        }
    }
    // left 数列左边界 right 数列右边界
    public static void sort(int[] array,int left,int right) {
        int p = left;
        int q = right;
        int key = right;
        if(left >= right)
            return;
        while( p < q ) {
            //p找大
            while(p < q && array[p] <= array[key])
                p++;
            //q找小
            while(p < q && array[q] >= array[key])
                q--;
            if(p < q)
                swap(array, p, q);
        }
        swap(array, p, key);
        sort(array, left, p - 1);
        sort(array, q + 1, right);
    }
    // 交换数组内两个元素
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

挖坑法：

定义两个指针 left 指向起始位置，right 指向最后一个元素的位置，然后指定一个基准 key(right)，作为坑。

left 寻找比基准(key)大的数字，找到后将 left 的数据赋给 right，left 成为一个坑，然后 right 寻找比基数(key)小的数字，找到将 right 的数据赋给 left，right 成为一个新坑，循环这个过程，直到 begin 指针与 end指针相遇，然后将 key 填入那个坑(最终：key的左边都是比key小的数，key的右边都是比key大的数)，然后进行递归操作。
挖坑法

// 快速排序方法 left 数列左边界 right 数列右边界
public static void Quicksort(int array[], int left, int right) {
    if (left < right){
        int pos = partition(array, left, right);
        Quicksort(array, left, pos - 1);
        Quicksort(array, pos + 1, right);
    }
}
// partition操作
public static int partition(int[] array,int left,int right) {
    int key = array[right];//初始坑
    while(left < right) {
        //left找大
        while(left < right && array[left] <= key )
            left++;
        array[right] = array[left];//赋值，然后left作为新坑
        //right找小
        while(left <right && array[right] >= key)
            right--;
        array[left] = array[right];//right作为新坑
    }
    array[left] = key;
    /*将key赋值给left和right的相遇点，保持key的左边都是比key小的数，key的右边都是比key大的数*/
    return left;//最终返回基准
}

优化

之前选择基准的策略都是固定基准，即固定地选择序列的右边界值作为基准，但如果在待排序列几乎有序的情况下，选择的固定基准将是序列的最大(小)值，快排的性能不好(因为每趟排序后，左右两个子序列规模相差悬殊，大的那部分最后时间复杂度很可能会达到O(n2))。

优化一：随机基准
每次随机选取基准值，而不是固定选取左或右边界值。将随机选取的基准值和右边界值进行交换，然后就回到了之前的解法。
只需要在 partition 函数前增加如下操作即可：

//随机选择 left ~ right 之间的一个位置作为基准
int random = (int) (left + Math.random() * (right - left + 1));
//把基准值交换到右边界
swap(array, random, right);

优化二：三数取中法
取第一个数，最后一个数，第(N/2)个数即中间数，三个数中数值中间的那个数作为基准值。

举个例子，对于int[] array = { 2，5，4，9，3，6，8，7，1，0}，2、3、0分别是第一个数，第(N/2)个是数以及最后一个数，三个数中3最大，0最小，2在中间，所以取2为基准值。

实现getMid函数即可：

// 三数取中，返回array[left]、array[mid]、array[right]三者的中间者下标作为基准
public static int getMid(int[] array,int left,int right) {
    int mid = left + ((right - left) >> 1);
    int a = array[left];
    int b = array[mid];
    int c = array[right];
    if ((b <= a && a <= c) || (c <= a && a <= b)) { //a为中间值
        return left;
    }
    if ((a <= b && b <= c) || (c <= b && b <= a)) { //b为中间值
        return mid;
    }
    if ((a <= c && c <= b) || (b <= c && c <= a)) { //c为中间值
        return right;
    }
    return left;
}

优化三：当待排序序列的长度分割到一定大小后，使用插入排序
在子序列比较小的时候，直接插入排序性能较好，因为对于有序的序列，插排可以达到O(n)的复杂度，如果序列比较小，使用插排效率要比快排高。

实现方式也很简单，快排是在子序列元素个数为 1 时才停止递归，可以设置一个阈值n，假设为5，则大于5个元素，子序列继续递归，否则选用插排。

此时QuickSort()函数如下：

public static void Quicksort(int array[], int left, int right) {
    if(right - left > 5){
        int pos = partition(array, left, right);
        Quicksort(array, left, pos - 1);
        Quicksort(array, pos + 1, right);
    }else{
        insertionSort(array);
    }
}

优化四：三路划分
如果待排序列中重复元素过多，也会大大影响排序的性能，这是因为大量相同元素参与快排时，左右序列规模相差极大，快排将退化为冒泡排序，时间复杂度接近O(n2)。这时候，如果采用三路划分，则会很好的避免这个问题。

三路划分的思想是利用 partition 函数将待排序列划分为三部分：第一部分小于基准v，第二部分等于基准v，第三部分大于基准v。这样在递归排序区间的时候，就不必再对第二部分元素均相等的区间进行快排了，这在待排序列存在大量相同元素的情况下能大大提高快排效率。
三路划分示意图

红色部分为小于基准v的序列，绿色部分为等于基准v的序列，白色部分由于还未被 cur 指针遍历到，属于大小未知的部分，蓝色部分为大于基准v的序列。

left 指针为整个待排区间的左边界，right 指针为整个待排区间的右边界。less 指针指向红色部分的最后一个数(即小于v的最右位置)，more 指针指向蓝色部分的第一个数(即大于v的最左位置)。cur 指针指向白色部分(未知部分)的第一个数，即下一个要判断大小的位置。

算法思路：

由于最初红色和蓝色区域没有元素，初始化 less = left – 1，more = right + 1，cur = left。整个区间为未知部分(白色)。
如果当前 array[cur] < v，则 swap(array,++less,cur++)，即把红色区域向右扩大一格(less指针后移)，把 array[cur] 交换到该位置，cur 指针前移判断下一个数。
如果当前 array[cur] = v，则不必交换，直接 cur++
如果当前 array[cur] > v，则 swap(array,–more,cur)，即把蓝色区域向左扩大一格(more指针前移)，把 array[cur] 交换到该位置。特别注意！此时cur指针不能前移，这是因为交换到cur位置的元素来自未知区域，还需要进一步判断array[cur]。

public static int[] partition(int[] array,int left,int right){
    int v = array[right]; //选择右边界为基准
    int less = left - 1; // < v 部分的最后一个数
    int more = right + 1; // > v 部分的第一个数
    int cur = left;
    while(cur < more){
        if(array[cur] < v){
            swap(array,++less,cur++);
        }else if(array[cur] > v){
            swap(array,--more,cur);
        }else{
            cur++;
        }
    }
    return new int[]{less + 1,more - 1};  //返回的是 = v 区域的左右下标
}
// 交换数组内两个元素
public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
public static void Quicksort(int array[], int left, int right) {
    if (left < right) {
        int[] p = partition(array,left,right);
        Quicksort(array,left,p[0] - 1); //避开重复元素区间
        Quicksort(array,p[1] + 1,right);
    }
}

时间复杂度：快速排序平均时间复杂度为O(nlogn)，最好时间复杂度为O(nlogn)，最坏时间复杂度为O(n2)。
最好情况：基准选择得当，partition函数每次恰好能均分序列，其递归树的深度就为logn，时间复杂度为O(nlogn)。
最坏情况：选择了最大或者最小数字作为基准，每次划分只能将序列分为一个元素与其他元素两部分，此时快速排序退化为冒泡排序，如果用树画出来，得到的将会是一棵单斜树，即所有的结点只有左(右)结点的树，树的深度为 n，时间复杂度为O(n2)。
空间复杂度：快速排序的空间复杂度主要考虑递归时使用的栈空间。在最好情况下，即partition函数每次恰好能均分序列，空间复杂度为O(logn)；在最坏情况下，即退化为冒泡排序，空间复杂度为O(n)。平均空间复杂度为O(logn)。
稳定性：快速排序是不稳定的。

堆排序

基本思想
堆排序是一种树形选择排序方法，它利用了堆这种数据结构。在排序的过程中，将array[0，…，n-1]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的关系，在当前无序区中选择关键字最大(最小)的元素。

算法描述

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为(n-1)，则整个排序过程完成。

//声明全局变量，用于记录数组array的长度；
static int len;
// 堆排序算法
public static int[] HeapSort(int[] array) {
        len = array.length;
        if (len == 0) return array;
        //1.构建一个大根堆
        buildMaxHeap(array);
        //2.循环将堆顶(最大值)与堆尾交换，删除堆尾元素，然后重新调整大根堆
        while (len > 0) {
            swap(array, 0, len - 1);
            len--; //原先的堆尾进入有序区，删除堆尾元素
            adjustHeap(array, 0); //重新调整大根堆
        }
        return array;
 }
// 自顶向下调整以 i 为根的堆为大根堆
public static void adjustHeap(int[] array, int i) {
        int maxIndex = i;
        //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
        if (2 * i + 1 < len && array[2 * i + 1] > array[maxIndex])
            maxIndex = 2 * i + 1;
        //如果有右子树，且右子树大于父节点，则将最大指针指向右子树
        if (2 * i + 2 < len && array[2 * i + 2] > array[maxIndex])
            maxIndex = 2 * i + 2;
        //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
        if (maxIndex != i) {
            swap(array, maxIndex, i);
            adjustHeap(array, maxIndex);
        }
 }
 // 自底向上构建初始大根堆
 public static void buildMaxHeap(int[] array) {
        //从最后一个非叶子节点开始自底向上构造大根堆
        for (int i = (len - 2) / 2; i >= 0; i--) {
            adjustHeap(array, i);
        }
 }
 // 交换数组内两个元素
public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

拓展：
- 插入元素：只需要把待插入的元素放置在堆尾，然后 len++ 把其纳入堆，然后调用 adjustHeap 函数重新调整堆即可。
- 删除堆顶元素：只需要把堆顶元素交换到堆尾，然后 len– 把其移出堆，然后调用 adjustHeap 函数重新调整堆即可。
时间复杂度：堆排序平均时间复杂度为O(nlogn)，最好时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)。堆排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它在任何情况下时间复杂度均是O(nlogn)。
空间复杂度：堆排序使用了常数空间，空间复杂度为O(1)。
稳定性：堆排序是不稳定的。

计数排序

基本思想
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法描述

找出待排序的数组中最大和最小的元素；
统计数组中每个值为 i 的元素出现的次数，存入数组C的第i项；
对所有的计数累加(从C中的第一个元素开始，每一项和前一项相加)；
反向填充目标数组：将每个元素 i 放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

public static int[] CountingSort(int[] array) {
    if (array.length == 0) return array;
    int bias, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int i = 0; i < array.length; i++) {
        max = Math.max(max, array[i]);
        min = Math.min(min, array[i]);
    }
   //计算偏移量，将 min ~ max 映射到 bucket 数组的 0 ~ (max - min) 位置上
    bias = -min;
    int[] bucket = new int[max - min + 1];
    Arrays.fill(bucket, 0);
    for (int i = 0; i < array.length; i++) {
        bucket[array[i] + bias]++;
    }
    int index = 0, i = 0;
    while (index < array.length) {
        if (bucket[i] != 0) {
            array[index] = i - bias;
            bucket[i]--;
            index++;
        } else
            i++;
    }
    return array;
}

时间复杂度：计数排序平均时间复杂度为O(n + k)，最好时间复杂度为O(n + k)，最坏时间复杂度为O(n + k)。n 为遍历一趟数组计数过程的复杂度，k 为遍历一趟桶取出元素过程的复杂度。
空间复杂度：计数排序空间复杂度为O(k)，k为桶数组的长度。
稳定性：计数排序是稳定的。

桶排序

基本思想
桶排序与计数排序很相似，不过现在的桶不单计数，是实实在在地放入元素。按照映射函数将数据分配到不同的桶里，每个桶内元素再分别排序(可能使用别的排序算法)，最后拼接各个桶中排好序的数据。映射函数人为设计，但要保证桶 i 中的数均小于桶 j (i < j)中的数，即必须桶间必须有序，桶内可以无序，可以考虑按照数的区间范围划分桶。下面代码的桶映射函数为：(i – min) / arr.length。

算法描述

设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶的桶内元素进行排序(可以使用直接插入排序等)；
从不是空的桶里把排好序的数据拼接起来。

public static int[] bucketSort(int[] array){
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < array.length; i++){
        max = Math.max(max, array[i]);
        min = Math.min(min, array[i]);
    }
    /*桶映射函数：自己设计，要保证桶 i 的数均小于桶 j (i < j)的数，即必须桶间必须有序，桶内可以无序。这里桶映射函数为：(i - min) / arr.length*/
    int bucketNum = (max - min) / array.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList<Integer>());
    }
    //将每个元素放入桶
    for(int i = 0; i < array.length; i++){
        int num = (array[i] - min) / (array.length);
        bucketArr.get(num).add(array[i]);
    }
    //对每个桶进行排序
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
    }
   int k = 0;
   for(int i = 0; i < bucketArr.size(); i++){
      for(int j = 0;j < bucketArr.get(i).size();j++) {
           array[k++] = bucketArr.get(i).get(j);
      }
  }
  return array;
}

时间复杂度：桶排序平均时间复杂度为O(n + k)，最好时间复杂度为O(n + k)，最坏时间复杂度为O(n2)。
空间复杂度：桶排序空间复杂度为O(n + k)。
稳定性：桶排序是稳定的。

基数排序

基本思想
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

算法描述

取得数组中的最大数，并取得位数；
array 为原始数组，从最低位开始取每个位组成 radix 数组；
对 radix 进行计数排序(利用计数排序适用于小范围数的特点)；

public static int[] RadixSort(int[] array) {
     if (array == null || array.length < 2)
        return array;
        // 1.先算出最大数的位数；
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < array.length; i++) {
            max = Math.max(max, array[i]);
    }
    int maxDigit = 0;
    while (max != 0) {
            max /= 10;
            maxDigit++;
    }
    int div = 1;
    ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
    for (int i = 0; i < 10; i++)
        bucketList.add(new ArrayList<Integer>());
        //2.进行maxDigit趟分配
    for (int i = 0; i < maxDigit; i++,div *= 10) {
            for (int j = 0; j < array.length; j++) {
                int num = (array[j] / div) % 10;
                bucketList.get(num).add(array[j]);
            }
        //3.收集
            int index = 0;
            for (int j = 0; j < bucketList.size(); j++) {
                for (int k = 0; k < bucketList.get(j).size(); k++)
                    array[index++] = bucketList.get(j).get(k);
                bucketList.get(j).clear();
            }
   }
   return array;
}

时间复杂度：基数排序平均时间复杂度为O(n * k)，最好时间复杂度为O(n * k)，最坏时间复杂度为O(n * k)。
空间复杂度：基数排序空间复杂度为O(n + k)。
稳定性：基数排序是稳定的。

二分查找

public class BinarySearch {
    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止整形的(left + right)/2溢出
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // 未找到目标值
    }
    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;
        int result = binarySearch(array, target);
        System.out.println("目标值的索引: " + result);
    }
}

// 递归实现
public class BinarySearch {
    public static int binarySearch(int[] array, int target, int left, int right) {
        if (left > right) {
            return -1;
        }

        int mid = left + (right - left) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            return binarySearch(array, target, mid + 1, right);
        } else {
            return binarySearch(array, target, left, mid - 1);
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;
        int result = binarySearch(array, target, 0, array.length - 1);
        System.out.println("目标值的索引: " + result);
    }
}

寻找左右边界的二分查找

int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}
    // 寻找左侧边界的二分搜索，如果 target 不存在，搜索左侧边界的二分搜索返回的索引是大于 target 的最小索引。
    private int left_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                // 不返回，右边界一直收缩
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        // 判断 target 是否存在于 nums 中
        // 如果越界，target 肯定不存在，返回 -1
        if (left < 0 || left >= nums.length) {
            return -1;
        }
        // 判断一下 nums[left] 是不是 target
        return nums[left] == target ? left : -1;
    }
    // 寻找右侧边界的二分搜索，如果 target 不存在，搜索右侧边界的二分搜索返回的索引是小于 target 的最大索引。
    private int right_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                // 不返回，左侧边界一直收缩
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        // 判断 target 是否存在于 nums 中
        // 如果越界，target 肯定不存在，返回 -1
        if (right < 0 || right >= nums.length) {
            return -1;
        }
        // 判断一下 nums[left] 是不是 target
        return nums[right] == target ? right : -1;
    }

递归删除文件夹

import java.io.File;
public class FileDeleter {
    public static void main(String[] args) {
        // 示例：删除路径为"example"的文件或目录
        String path = "example";
        boolean result = deleteRecursively(new File(path));
        if (result) {
            System.out.println("删除成功: " + path);
        } else {
            System.out.println("删除失败: " + path);
        }
    }

    /**
     * 递归删除文件或目录
     * @param file 要删除的文件或目录
     * @return 如果成功删除，则返回true；否则返回false
     */
    public static boolean deleteRecursively(File file) {
        if (!file.exists()) {
            System.out.println("文件不存在: " + file.getAbsolutePath());
            return false;
        }
        // 如果是目录，则递归删除目录中的内容
        if (file.isDirectory()) {
            File[] files = file.listFiles();
            if (files != null) {
                for (File child : files) {
                    if (!deleteRecursively(child)) {
                        return false;
                    }
                }
            }
        }
        // 删除文件或空目录
        return file.delete();
    }
}

两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

三数之和

class Solution {
    // 从 nums[start] 开始，计算有序数组 nums 中所有和为 target 的二元组
    private List<List<Integer>> towSum(int[] nums, int start, int target) {
        int low = start, high = nums.length - 1;
        // Arrays.sort(nums); // 先排序
        List<List<Integer>> res = new ArrayList<>();
        while (low < high) {
            int sum = nums[low] + nums[high];
            int left = nums[low], right = nums[high]; // 用来标记左右元素，对比重复元素
            if (sum < target) {
                while (low < high && nums[low] == left) low++;
            } else if (sum > target) {
                while (low < high && nums[high] == right) high--;
            } else {
                res.add(new ArrayList<>(Arrays.asList(left, right)));
                while (low < high && nums[low] == left) low++;
                while (low < high && nums[high] == right) high--;
            }
        }
        return res;
    }
    public List<List<Integer>> threeSum(int[] nums, int target) {
        int n = nums.length;
        Arrays.sort(nums); // 先排序
        List<List<Integer>> res = new ArrayList<>();
        // 先穷举第一个数
        for (int i = 0; i < n; i++) {
            // 对 target - nums[i] 计算 twoSum
            List<List<Integer>> twoSumRes = towSum(nums, i+1, target -nums[i]);
            // 如果存在满足条件的二元组，再加上 nums[i] 就是结果三元组
            for (List<Integer> tuple : twoSumRes) {
                tuple.add(nums[i]);
                res.add(tuple);
            }
            // 跳过第一个数字重复的情况
            while (i < n-1 && nums[i] == nums[i+1]) i++;
        }
        return res;
    }
}

最接近的三数之和

import java.util.*;
public class Solution {
    public int ClosestSum (int[] nums, int target) {
        int n = nums.length;
        Arrays.sort(nums);
        int delta = Integer.MAX_VALUE;
        for (int i = 0; i < n - 2; i++) {
            // 固定nums[i],从i+1开始
            int sum = nums[i] + ClosestSum2(nums, i + 1, target - nums[i]);
            if (Math.abs(delta) > Math.abs(target - sum)) {
                delta = target - sum;
                if (delta == 0) {
                    break;
                }
            }
        }
        return target - delta;
    }
    // 最接近的两数之和
    private int ClosestSum2 (int[] nums, int start, int target) {
        int low = start;
        int high = nums.length - 1;
        int delta = Integer.MAX_VALUE;
        while (low < high) {
            int sum = nums[low] + nums[high];
            if (Math.abs(delta) > Math.abs(target - sum)) {
                delta = target - sum;
                if (delta == 0) {
                    break;
                }
            }
            if (sum < target) {
                low++;
            } else {
                high--;
            }
        }
        return target - delta;
    }
}

接雨水

// 暴力解法，备忘录优化
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;
        int res = 0;
        // 备忘录记录每个位置左右柱子高度的最大值
        int[] l_max = new int[n];
        int[] r_max = new int[n];
        l_max[0] = height[0];
        r_max[n-1] = height[n-1];
        // 从左到右计算l_max
        for (int i = 1; i < n; i++) {
            l_max[i] = Math.max(height[i], l_max[i-1]);
        }
        // 从右往左计算r_max
        for (int i = n-2; i >= 0; i--) {
            r_max[i] = Math.max(height[i], r_max[i+1]);
        }
        // 计算答案
        for (int i = 1; i < n-1; i++) {
            res += Math.min(l_max[i], r_max[i]) - height[i];
        }
        return res;
    }
}
// 双指针法
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;
        int res = 0;
        int left = 0, right = height.length - 1;
        int l_max = 0, r_max = 0;
        while (left < right) {
            l_max = Math.max(l_max, height[left]);
            r_max = Math.max(r_max, height[right]);
            if (l_max < r_max) {
                res += l_max - height[left];
                left++;
            } else {
                res += r_max - height[right];
                right--;
            }
        }
        return res;
    }
}

字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：
输入：s = “3[a]2[bc]”
输出：”aaabcbc”

import java.util.*;
class Solution {
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();

        Stack<Integer> multi_stack = new Stack<>(); // 用于倍数计算的栈
        Stack<String> res_stack = new Stack<>(); // 用于字符串拼接的栈

        int multi = 0; // 初始化乘数
        for (char c : s.toCharArray()) {
            if (c >= '0' && c<= '9') {
                multi = multi * 10 + Integer.parseInt(c + ""); // 乘数可能大于10
            } else if (c == '[') {
                multi_stack.push(multi); // 乘数入栈
                res_stack.push(res.toString()); // 子串入栈，如3[a2[c]]中的a
                multi = 0; // 重置乘数
                res = new StringBuilder(); // 重置res
            } else if (c == ']') {
                StringBuilder temp = new StringBuilder(); // 构造结果
                int cur_multi = multi_stack.peek(); // 乘数
                multi_stack.pop(); // 弹出
                String last_res = res_stack.peek(); // 子串
                res_stack.pop(); // 弹出
                for (int i = 0; i < cur_multi; i++) {
                    temp.append(res); // 根据乘数构造结果
                }
                // 中括号中的结果为前面的res + 当前够早的结果
                res = new StringBuilder(last_res + temp);
            } else {
                res.append(c);
            }
        }

        return res.toString();
    }
}

每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        // 单调栈解题
        int n = temperatures.length;
        int[] res = new int[n];
        Stack<Integer> stack = new Stack<>();
        // 倒着遍历
        for (int i = n-1; i >= 0; i--) {
            // 判定个子高矮，注意这里的while循环
            while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) {
                // 矮个起开，反正也被挡着了。。。
                stack.pop();
            }
            // nums[i] 身后的更大元素
            res[i] = stack.isEmpty() ? 0 : (stack.peek() - i);
            stack.push(i);
        }

        return res;
    }
}

下一个更大的元素1

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 记录 nums2 中每个元素的下一个更大元素
        int[] greater = calculateGreaterElement(nums2);
        // 转化成映射：元素 x -> x 的下一个最大元素
        HashMap<Integer, Integer> greaterMap = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            greaterMap.put(nums2[i], greater[i]);
        }
        // nums1 是 nums2 的子集，所以根据 greaterMap 可以得到结果
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = greaterMap.get(nums1[i]);
        }
        return res;
    }

    int[] calculateGreaterElement(int[] nums) {
        int n = nums.length;
        // 存放答案的数组
        int[] res = new int[n];
        Stack<Integer> s = new Stack<>();
        // 倒着往栈里放
        for (int i = n - 1; i >= 0; i--) {
            // 判定个子高矮
            while (!s.isEmpty() && s.peek() <= nums[i]) {
                // 矮个起开，反正也被挡着了。。。
                s.pop();
            }
            // nums[i] 身后的更大元素
            res[i] = s.isEmpty() ? -1 : s.peek();
            s.push(nums[i]);
        }
        return res;
    }
}

下一个更大的元素2

int[] calculateGreaterElement(int[] nums) {
    int n = nums.length;
    // 存放答案的数组
    int[] res = new int[n];
    Stack<Integer> s = new Stack<>(); 
    // 倒着往栈里放
    for (int i = n - 1; i >= 0; i--) {
        // 判定个子高矮
        while (!s.isEmpty() && s.peek() <= nums[i]) {
            // 矮个起开，反正也被挡着了。。。
            s.pop();
        }
        // nums[i] 身后的更大元素
        res[i] = s.isEmpty() ? -1 : s.peek();
        s.push(nums[i]);
    }
    return res;
}

判断是否是质数

class Solution {
    public boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

ArrayList实现最大堆

import java.util.ArrayList;

public class MaxHeap {
    private ArrayList<Integer> heap;
    public MaxHeap() {
        heap = new ArrayList<>();
    }
    public void insert(int value) {
        heap.add(value);
        heapifyUp(heap.size() - 1);
    }
    public int extractMax() {
        if (heap.isEmpty()) {
            throw new IllegalStateException("Heap is empty");
        }
        int max = heap.get(0);
        int last = heap.remove(heap.size() - 1);
        if (!heap.isEmpty()) {
            heap.set(0, last);
            heapifyDown(0);
        }
        return max;
    }
    private void heapifyUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap.get(index) > heap.get(parentIndex)) {
                swap(index, parentIndex);
                index = parentIndex;
            } else {
                break;
            }
        }
    }
    private void heapifyDown(int index) {
        int size = heap.size();
        while (index < size) {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
            int largestIndex = index;

            if (leftChildIndex < size && heap.get(leftChildIndex) > heap.get(largestIndex)) {
                largestIndex = leftChildIndex;
            }
            if (rightChildIndex < size && heap.get(rightChildIndex) > heap.get(largestIndex)) {
                largestIndex = rightChildIndex;
            }

            if (largestIndex != index) {
                swap(index, largestIndex);
                index = largestIndex;
            } else {
                break;
            }
        }
    }
    private void swap(int index1, int index2) {
        int temp = heap.get(index1);
        heap.set(index1, heap.get(index2));
        heap.set(index2, temp);
    }
    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap();
        maxHeap.insert(10);
        maxHeap.insert(20);
        maxHeap.insert(5);
        System.out.println("Max element: " + maxHeap.extractMax()); // 输出 20
        System.out.println("Max element: " + maxHeap.extractMax()); // 输出 10
        System.out.println("Max element: " + maxHeap.extractMax()); // 输出 5
    }
}

最长有效括号

保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标：

对于遇到的每个 ‘(’ ，将它的下标放入栈中

对于遇到的每个 ‘)’ ，先弹出栈顶元素表示匹配了当前右括号：

如果栈为空，说明当前的右括号为没有被匹配的右括号，将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」

如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」

class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        // 使用栈来存储括号的位置，保持栈底元素是最后一个没有被匹配的右括号的下标
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1); // 先在栈中加入-1，作为基准位置，用于计算有效长度
        for (int i = 0; i < s.length(); i++) {
            // 如果当前字符是 '('，将它的位置压入栈中
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                // 如果当前字符是 ')'，从栈中弹出一个位置
                stack.pop();
                // 如果栈为空，说明当前的 ')' 没有匹配的 '('，将当前位置压入栈中
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    // 否则，计算当前有效括号的长度，并更新最大长度
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        // 返回最长有效括号的长度
        return maxans;
    }
}

判断是否是回文串

private static boolean isPalindrome(String s) {
    for (int i = 0; i < s.length()/2; i++) {
        if (s.charAt(i) != s.charAt(s.length()-1-i)) {
            return false;
        }
    }
    return true;
}

最大公约数

public class GCD {
    // 方法 1：递归实现
    public static int gcdRecursive(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcdRecursive(b, a % b);
    }

    // 方法 2：非递归实现（迭代）
    public static int gcdIterative(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

创建三个线程有序打印1-100

public class ConcurrentDemo {
    private static final int MAX_NUMBER = 100;  // 定义最大数字为100
    private static int number = 1;  // 当前要打印的数字，初始值为1
    private static final Object lock = new Object();  // 锁对象，用于线程间的通信
    public static void main(String[] args) {
        // 创建三个线程，每个线程使用不同的threadId(0, 1, 2)
        Thread t1 = new Thread(new PrintTask(1));
        Thread t2 = new Thread(new PrintTask(2));
        Thread t3 = new Thread(new PrintTask(0));
        // 启动线程
        t1.start();
        t2.start();
        t3.start();
    }
    static class PrintTask implements Runnable {
        private int threadId;  // 线程的标识符，用于控制打印顺序
        public PrintTask(int threadId) {
            this.threadId = threadId;
        }
        @Override
        public void run() {
            while (true) {
                synchronized (lock) {  // 锁定lock对象，保证同一时刻只有一个线程可以访问
                    // 如果当前数字不能被对应线程处理，则等待
                    while (number % 3 != threadId) {
                        try {
                            lock.wait();  // 当前线程等待，释放锁
                        } catch (InterruptedException e) {
                            Thread.currentThread().interrupt();  // 处理线程中断
                        }
                    }
                    // 如果当前数字超过最大值，通知其他线程并结束循环
                    if (number > MAX_NUMBER) {
                        lock.notifyAll();  // 通知其他所有线程
                        break;  // 退出循环，结束线程
                    }
                    // 打印当前数字并自增
                    System.out.println("Thread-" + threadId + " prints: " + number++);
                    // 唤醒其他等待的线程
                    lock.notifyAll();
                }
            }
        }
    }
}

SQL模拟死锁

为了展示如何在事务中引发死锁，可以创建一个简单的数据库表，然后编写两个事务，在特定的情况下导致死锁。下面以MySQL为例，假设有一张users表，事务1和事务2分别对不同的记录进行锁定，但由于它们相互等待对方释放锁而产生了死锁。

创建表结构

CREATE TABLE users (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    balance DECIMAL(10, 2)
);

插入一些初始数据

1 2	INSERT INTO users (id, name, balance) VALUES (1, 'Alice', 100.00); INSERT INTO users (id, name, balance) VALUES (2, 'Bob', 200.00);

模拟死锁的两个事务

-- 事务1：
-- 开启事务
START TRANSACTION;

-- 锁定用户1的记录
UPDATE users SET balance = balance - 50 WHERE id = 1;

-- 模拟某些操作的延迟
-- 在实际场景中，这可能是业务逻辑处理时间
DO SLEEP(5);

-- 尝试更新用户2的记录
UPDATE users SET balance = balance + 50 WHERE id = 2;

-- 提交事务
COMMIT;



-- 事务2：
-- 开启事务
START TRANSACTION;

-- 锁定用户2的记录
UPDATE users SET balance = balance + 50 WHERE id = 2;

-- 模拟某些操作的延迟
DO SLEEP(5);

-- 尝试更新用户1的记录
UPDATE users SET balance = balance - 50 WHERE id = 1;

-- 提交事务
COMMIT;

死锁的过程：

事务1 先更新用户1的记录，此时用户1的记录被事务1锁定。
事务2 先更新用户2的记录，此时用户2的记录被事务2锁定。
事务1 尝试更新用户2的记录，但用户2的记录已被事务2锁定，所以事务1进入等待状态。
事务2 尝试更新用户1的记录，但用户1的记录已被事务1锁定，所以事务2也进入等待状态。

由于两个事务互相等待对方释放锁，导致了死锁。最终数据库检测到死锁后，会主动回滚其中一个事务，以解除死锁。

模拟死锁

public class DeadLockSample {
    private final Object lock1 = new Object();
    private final Object lock2 = new Object();
    public void createDeadLock() {
        Thread thread1 = new Thread(() -> {
            synchronized (lock1) {
                System.out.println("Thread1 get lock1");
                // 让线程1休眠，确保线程2可以获取到lock2
                try {
                    Thread.sleep(50);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
                synchronized (lock2) {
                    System.out.println("Thread1 try get lock2.");
                }
            }
        });
        Thread thread2 = new Thread(() -> {
            synchronized (lock2) {
                System.out.println("Thread2 get lock2");
                // 让线程2休眠，确保线程1可以获取到lock2
                try {
                    Thread.sleep(50);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
                synchronized (lock1) {
                    System.out.println("Thread2 try get lock1.");
                }
            }
        });
        thread1.start();
        thread2.start();
    }
    public static void main(String[] args) {
        DeadLockSample deadLockSample = new DeadLockSample();
        deadLockSample.createDeadLock();
    }
}

手写线程池

线程池的基本组成部分
- 任务队列：存储提交的任务。
- 工作线程：从任务队列中取出任务并执行。
- 线程池管理类：负责管理线程和任务的调度。

设计关键点

使用BlockingQueue存储任务。
使用Thread或Executor实现工作线程。
提供execute()方法提交任务。

管理线程的生命周期（如启动和停止线程池）。

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class MyThreadPool {
    // 任务队列
    private final BlockingQueue<Runnable> taskQueue;
    // 工作线程数组
    private final WorkerThread[] workers;
    // 线程池是否正在运行
    private volatile boolean isRunning = true;

    // 构造函数
    public MyThreadPool(int poolSize, int queueSize) {
        taskQueue = new LinkedBlockingQueue<>(queueSize);
        workers = new WorkerThread[poolSize];
        // 初始化工作线程
        for (int i = 0; i < poolSize; i++) {
            workers[i] = new WorkerThread();
            workers[i].start();
        }
    }

    // 提交任务到线程池
    public void execute(Runnable task) throws InterruptedException {
        if (isRunning) {
            taskQueue.put(task); // 阻塞式添加任务
        } else {
            throw new IllegalStateException("ThreadPool is not running!");
        }
    }

    // 关闭线程池
    public void shutdown() {
        isRunning = false;
        // 中断所有工作线程
        for (WorkerThread worker : workers) {
            worker.interrupt();
        }
    }

    // 工作线程类
    private class WorkerThread extends Thread {
        public void run() {
            while (isRunning || !taskQueue.isEmpty()) {
                try {
                    Runnable task = taskQueue.poll(); // 非阻塞取任务
                    if (task != null) {
                        task.run();
                    }
                } catch (Exception e) {
                    // 捕获并处理线程执行中的异常
                    System.out.println("WorkerThread interrupted: " + e.getMessage());
                }
            }
        }
    }

    // 测试代码
    public static void main(String[] args) throws InterruptedException {
        MyThreadPool pool = new MyThreadPool(3, 10);

        // 提交任务
        for (int i = 0; i < 15; i++) {
            final int taskId = i;
            pool.execute(() -> {
                System.out.println("Task " + taskId + " is running on " + Thread.currentThread().getName());
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            });
        }

        // 等待所有任务完成
        Thread.sleep(5000);
        pool.shutdown();
    }
}

实现生产者消费者模型

使用BlockingQueue

public class ProducerConsumerExample {
    // 定义缓冲区的容量
    private static final int BUFFER_CAPACITY = 10;
    // 创建一个共享缓冲区
    private final BlockingQueue<Integer> buffer = new LinkedBlockingQueue<>(BUFFER_CAPACITY);
    public static void main(String[] args) {
        ProducerConsumerExample example = new ProducerConsumerExample();
        // 启动生产者线程
        new Thread(example.new Producer()).start();
        // 启动消费者线程
        new Thread(example.new Consumer()).start();
    }
    // 生产者类
    class Producer implements Runnable {
        @Override
        public void run() {
            int value = 0;
            while (true) {
                try {
                    produce(value++);
                    Thread.sleep(1000); // 模拟生产过程
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        }
        private void produce(int value) throws InterruptedException {
            // 将产品放入缓冲区，若缓冲区满则等待
            buffer.put(value);
            System.out.println("Produced: " + value);
        }
    }
    // 消费者类
    class Consumer implements Runnable {
        @Override
        public void run() {
            while (true) {
                try {
                    consume();
                    Thread.sleep(1500); // 模拟消费过程
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        }
        private void consume() throws InterruptedException {
            // 从缓冲区中取出产品，若缓冲区空则等待
            int value = buffer.take();
            System.out.println("Consumed: " + value);
        }
    }
}

使用wait()和notify()

public class ProducerConsumerExample {
    // 定义缓冲区的容量
    private static final int BUFFER_CAPACITY = 10;
    // 创建一个共享缓冲区
    private final Queue<Integer> buffer = new LinkedList<>();
    private final Object lock = new Object();
    public static void main(String[] args) {
        ProducerConsumerExample example = new ProducerConsumerExample();

        // 启动生产者线程
        new Thread(example.new Producer()).start();

        // 启动消费者线程
        new Thread(example.new Consumer()).start();
    }
    // 生产者类
    class Producer implements Runnable {
        @Override
        public void run() {
            int value = 0;
            while (true) {
                try {
                    produce(value++);
                    Thread.sleep(1000); // 模拟生产过程
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        }
        private void produce(int value) throws InterruptedException {
            synchronized (lock) {
                // 如果缓冲区已满，等待消费者消费
                while (buffer.size() == BUFFER_CAPACITY) {
                    System.out.println("Buffer is full, producer is waiting...");
                    lock.wait();
                }
                // 将产品放入缓冲区
                buffer.add(value);
                System.out.println("Produced: " + value);
                // 通知消费者有新的产品
                lock.notifyAll();
            }
        }
    }
    // 消费者类
    class Consumer implements Runnable {
        @Override
        public void run() {
            while (true) {
                try {
                    consume();
                    Thread.sleep(1500); // 模拟消费过程
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        }
        private void consume() throws InterruptedException {
            synchronized (lock) {
                // 如果缓冲区为空，等待生产者生产
                while (buffer.isEmpty()) {
                    System.out.println("Buffer is empty, consumer is waiting...");
                    lock.wait();
                }
                // 从缓冲区中取出产品
                int value = buffer.poll();
                System.out.println("Consumed: " + value);
                // 通知生产者有空位
                lock.notifyAll();
            }
        }
    }
}

CompletableFuture实现异步调用

import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutionException;
public class AsyncExample {
    public static void main(String[] args) {
        // 创建一个CompletableFuture来执行异步任务
        CompletableFuture<String> future = CompletableFuture.supplyAsync(() -> {
            // 模拟一个长时间运行的任务
            try {
                Thread.sleep(2000); // 休眠2秒
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            return "任务完成";
        });
        // 注册一个回调函数，当任务完成时获取结果
        future.thenAccept(result -> {
            System.out.println("异步任务结果: " + result);
        });
        // 主线程继续执行其他操作
        System.out.println("主线程继续执行...");
        // 阻塞主线程，直到异步任务完成(可选)
        try {
            // 这一步会阻塞主线程，直到异步任务完成
            String result = future.get();
            System.out.println("异步任务完成后获取的结果: " + result);
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
    }
}

遍历HashMap

七种

HashMap<Integer, String> map = new HashMap<>();
// ForEach EntrySet
for (Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ":" + entry.getValue());
}
// ForEach KeySet
for (Integer key : map.keySet()) {
    System.out.println(key + ":" + map.get(key));
}
// 迭代器EntrySet
Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<Integer, String> entry = iterator.next();
    System.out.println(entry.getKey() + ":" + entry.getValue());
}
// 迭代器KeySet
Iterator<Integer> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
    Integer key = iterator.next();
    System.out.println(key + ":" + map.get(key));
}
// Lambda
map.forEach((key, value) -> {
    System.out.println(key);
    System.out.println(value);
});
// Streams API 单线程
map.entrySet().stream().forEach(entry -> {
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
});
// Streams API 多线程
map.entrySet().parallelStream().forEach(entry -> {
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
});

遍历Set

Set<Integer> row = new HashSet<>();
row.add(1);
row.add(2);
row.add(3);
// 增强for循环
for (Integer number : row) {
    System.out.println(number);
}
// 迭代起
Iterator<Integer> iterator = row.iterator();
while (iterator.hasNext()) {
    Integer number = iterator.next();
    System.out.println(number);
}
// forEach+Lambda表达式
row.forEach(number -> System.out.println(number));
// Streams API 单线程
row.stream().forEach(System.out::println);

二叉树

二叉树深度

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
        left = null;
        right = null;
    }
}

public class BinaryTree {
    TreeNode root;

    // 计算二叉树的深度
    public int maxDepth(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            int leftDepth = maxDepth(node.left);
            int rightDepth = maxDepth(node.right);
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(5);

        System.out.println("二叉树的深度: " + tree.maxDepth(tree.root));
    }
}

二叉树前序遍历转链表

二叉树的先序遍历，然后按照前序顺序将其转化为一个链表

public class Solution {
    private static Node trans(TreeNode root) {
        Node dummy = new Node(-1), p = dummy;
        traverse(root, p);
        return dummy.next;
    }
    private static void traverse(TreeNode root, Node p) {
        if (root == null)
            return ;
        Node node = new Node(root.val, null);
        p.next = node;
        p = p.next;
        traverse(root.left, p);
        traverse(root.right, p);
    }
}

有序数组转二叉平衡搜索树

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // 递归构造平衡二叉搜索树
        return dfs(nums, 0, nums.length - 1);
    }
    private TreeNode dfs(int[] nums, int low, int high) {
        if (low > high) {
            return null;
        }
        int mid = low + (high - low)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(nums, low, mid-1);
        root.right = dfs(nums, mid+1, high);
        return root;
    }
}

根据前序和中序遍历构造二叉树

class Solution {
    // 存储 inorder 中值到索引的映射
    HashMap<Integer, Integer> valToIndex = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    private TreeNode build(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd) {
        if (preStart > preEnd) {
            return null;
        }
        // root 节点对应的值就是前序遍历数组的第一个元素
        int rootVal = preOrder[preStart];
        // rootVal 在中序遍历数组中的索引
        int index = valToIndex.get(rootVal);
        // 左子树的节点数量
        int leftSize = index - inStart;
        // 先构造出当前根节点
        TreeNode root = new TreeNode(rootVal);
        // 递归构造左右子树
        root.left = build(preOrder, preStart + 1, preStart + leftSize, inOrder, inStart, index - 1);
        root.right = build(preOrder, preStart + leftSize + 1, preEnd, inOrder, index + 1, inEnd);
        return root;
    }
}

根据中序和后序遍历构造二叉树

class Solution {
    // 存储 inorder 中值到索引的映射
    HashMap<Integer, Integer> valToIndex = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length - 1,
                    postorder, 0, postorder.length - 1);
    }
    // build 函数的定义：
    // 后序遍历数组为 postorder[postStart..postEnd]，
    // 中序遍历数组为 inorder[inStart..inEnd]，
    // 构造二叉树，返回该二叉树的根节点 
    TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart > inEnd) {
            return null;
        }
        // root 节点对应的值就是后序遍历数组的最后一个元素
        int rootVal = postorder[postEnd];
        // rootVal 在中序遍历数组中的索引
        int index = valToIndex.get(rootVal);
        // 左子树的节点个数
        int leftSize = index - inStart;
        TreeNode root = new TreeNode(rootVal);
        // 递归构造左右子树
        root.left = build(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1);
        root.right = build(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);
        return root;
    }
}

根据前序和后序遍历构造二叉树

class Solution {
    // 存储 postorder 中值到索引的映射
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        for (int i = 0; i < postorder.length; i++) {
            valToIndex.put(postorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1,
                    postorder, 0, postorder.length - 1);
    }
    // 定义：根据 preorder[preStart..preEnd] 和 postorder[postStart..postEnd]
    // 构建二叉树，并返回根节点。
    TreeNode build(int[] preorder, int preStart, int preEnd,
                   int[] postorder, int postStart, int postEnd) {
        if (preStart > preEnd) {
            return null;
        }
        if (preStart == preEnd) {
            return new TreeNode(preorder[preStart]);
        }
        // root 节点对应的值就是前序遍历数组的第一个元素
        int rootVal = preorder[preStart];
        // root.left 的值是前序遍历第二个元素
        // 通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点
        // 确定 preorder 和 postorder 中左右子树的元素区间
        int leftRootVal = preorder[preStart + 1];
        // leftRootVal 在后序遍历数组中的索引
        int index = valToIndex.get(leftRootVal);
        // 左子树的元素个数
        int leftSize = index - postStart + 1;
        // 先构造出当前根节点
        TreeNode root = new TreeNode(rootVal);
        // 递归构造左右子树
        // 根据左子树的根节点索引和元素个数推导左右子树的索引边界
        root.left = build(preorder, preStart + 1, preStart + leftSize, postorder, postStart, index);
        root.right = build(preorder, preStart + leftSize + 1, preEnd, postorder, index + 1, postEnd - 1);
        return root;
    }
}

迭代实现二叉树前序遍历

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            result.add(current.val); // 前序遍历的操作
            // 将右子树和左子树添加到栈中，注意顺序(栈是后进先出)
            if (current.right != null) {
                stack.push(current.right);
            }
            if (current.left != null) {
                stack.push(current.left);
            }
        }
        return result;
    }
}

迭代实现二叉树中序遍历

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.add(current.val); // 中序遍历的操作
        current = current.right;
    }
    return result;
}

迭代实现二叉树后续遍历

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode current = stack.pop();
        // result.addFirst(node.val);
        result.add(0, current.val); // 后序遍历的操作，在结果列表的开头插入节点值
        // 先左后右的顺序入栈，保证出栈顺序为根右左，即后序遍历的顺序
        if (current.left != null) {
            stack.push(current.left);
        }
        if (current.right != null) {
            stack.push(current.right);
        }
    }
    return result;
}

二叉树的广度优先遍历

深度优先遍历有三种，前中后序遍历。如上。
广度优先遍历是层序遍历，即按照层级从上到下、从左到右逐层访问节点的遍历方式。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
public class BinaryTree {
    public void breadthFirstTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root); // 将根节点入队
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll(); // 出队
            System.out.print(node.val + " "); // 访问节点
            // 左右子节点依次入队
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    public static void main(String[] args) {
        // 构造二叉树示例
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        
        BinaryTree bt = new BinaryTree();
        System.out.println("Breadth-First Traversal:");
        bt.breadthFirstTraversal(root);
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                // 左右子树进队
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add(level);
        }
        return res;
    }
}

二叉树的最近公共祖先(LCA)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return find(root, p.val, q.val);
    }
    // 在二叉树中寻找 val1 和 val2 的最近公共祖先节点
    TreeNode find(TreeNode root, int val1, int val2) {
        if (root == null) {
            return null;
        }
        // 前序位置
        if (root.val == val1 || root.val == val2) {
            // 如果遇到目标值，直接返回
            return root;
        }
        TreeNode left = find(root.left, val1, val2);
        TreeNode right = find(root.right, val1, val2);
        // 后序位置，已经知道左右子树是否存在目标值
        if (left != null && right != null) {
            // 当前节点是 LCA 节点
            return root;
        }
        return left != null ? left : right;
    }
}

二叉树的最大路径和

class Solution {
    private int ans = Integer.MIN_VALUE; // 不能定义为static
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }
    private int dfs(TreeNode node) {
        // 没有节点，和为0
        if (node == null) return 0;
        int leftVal = dfs(node.left); // 左子树最大链和
        int rightVal = dfs(node.right); // 右子树最大链和
        ans = Math.max(ans, leftVal + rightVal + node.val); // 两条链拼接
        return Math.max(Math.max(leftVal, rightVal) + node.val, 0); // 当前子树的最大链和
    }
}

二叉树最大宽度

// 层序遍历思路
class Solution {
    // 记录节点和对应编号
    class Pair {
        TreeNode node;
        int id;
        public Pair( TreeNode node, int id) {
            this.node = node;
            this.id = id;
        }
    }
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 记录最大的宽度
        int maxWidth = 0;
        // 标准 BFS 层序遍历算法
        Queue<Pair> q = new LinkedList<>();
        q.offer(new Pair(root, 1));
        // 从上到下遍历整棵树
        while (!q.isEmpty()) {
            int sz = q.size();
            int start = 0, end = 0;
            // 从左到右遍历每一行
            for (int i = 0; i < sz; i++) {
                Pair cur = q.poll();
                TreeNode curNode = cur.node;
                int curId = cur.id;
                // 记录当前行第一个和最后一个节点的编号
                if (i == 0) {
                    start = curId;
                }
                if (i == sz - 1) {
                    end = curId;
                }
                // 左右子节点入队，同时记录对应节点的编号
                if (curNode.left != null) {
                    q.offer(new Pair(curNode.left, curId * 2));
                }
                if (curNode.right != null) {
                    q.offer(new Pair(curNode.right, curId * 2 + 1));
                }
            }
            // 用当前行的宽度更新最大宽度
            maxWidth = Math.max(maxWidth, end - start + 1);
        }
        return maxWidth;
    }
}
// 递归遍历思路
class Solution2 {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        traverse(root, 1, 1);
        return maxWidth;
    }
    // 记录最左侧节点的编号
    ArrayList<Integer> firstId = new ArrayList<>();
    int maxWidth = 1;
    // 二叉树遍历函数
    void traverse(TreeNode root, int id, int depth) {
        if (root == null) {
            return;
        }
        if (firstId.size() == depth - 1) {
            // 因为代码是先 traverse(root.left) 后 traverse(root.right)，
            // 所以第一次到达这个深度一定是最左侧的节点，记录其编号
            firstId.add(id);
        } else {
            // 这个深度的其他节点，负责计算更新当前深度的最大宽度
            maxWidth = Math.max(maxWidth, id - firstId.get(depth - 1) + 1);
        }
        traverse(root.left, id * 2, depth + 1);
        traverse(root.right, id * 2 + 1, depth + 1);
    }
}

多叉树查找某个值

// 定义多叉树的节点类
class TreeNode {
    int value;
    List<TreeNode> children;

    public TreeNode(int value) {
        this.value = value;
        this.children = new ArrayList<>();
    }

    // 添加子节点的方法
    public void addChild(TreeNode child) {
        this.children.add(child);
    }
}

public class MultiWayTree {
    // 在多叉树中查找值的方法
    public static boolean search(TreeNode root, int target) {
        // 如果根节点为空，返回false
        if (root == null) {
            return false;
        }

        // 如果找到目标值，返回true
        if (root.value == target) {
            return true;
        }

        // 遍历子节点，递归查找
        for (TreeNode child : root.children) {
            if (search(child, target)) {
                return true;
            }
        }

        // 如果没有找到，返回false
        return false;
    }

    public static void main(String[] args) {
        // 创建多叉树
        TreeNode root = new TreeNode(1);
        TreeNode child1 = new TreeNode(2);
        TreeNode child2 = new TreeNode(3);
        TreeNode child3 = new TreeNode(4);
        root.addChild(child1);
        root.addChild(child2);
        root.addChild(child3);
        child1.addChild(new TreeNode(5));
        child1.addChild(new TreeNode(6));
        child2.addChild(new TreeNode(7));
        child3.addChild(new TreeNode(8));

        // 查找某个值
        int target = 7;
        boolean found = search(root, target);
        System.out.println("Found target " + target + ": " + found);
    }
}

前缀树(Trie)

class Trie {
    private Trie[] children; // 指向子节点的指针数组
    private boolean isEnd; // 记录当前Trie节点是否为叶子节点
    public Trie() {
        children = new Trie[26]; // 仅包含26个小写英文字母
        isEnd = false;
    }
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }
    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

图

岛屿数量

class Solution {
    int[][] dirs = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};  // 方向数组，分别代表上、下、左、右
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    // 新发现一个岛屿，结果+1
                    res++;
                    // 使用dfs将这个岛屿淹没
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }
    // boolean[][] visited; 如果需要是否访问的话
    private void dfs(char[][] grid, int i, int j) { // 从 (i, j) 开始，将与之相邻的陆地都变成海水
        int m = grid.length, n = grid[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n) return; // 超出索引边界
        if (grid[i][j] == '0') return; // 已经是水了
        // if (visited[i][j]) return;
        grid[i][j] = '0'; // 将(i, j)变成海水
        for (int[] dir : dirs) {
            dfs(grid, i + dir[0], j + dir[1]);
        }
    }
}

二维数组搜索字符串

public class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 从每个位置开始搜索
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int x, int y, int index) {
        // 如果匹配到了整个字符串
        if (index == word.length()) {
            return true;
        }

        // 检查边界条件和当前字符是否匹配
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != word.charAt(index)) {
            return false;
        }

        // 临时保存当前字符，避免重复访问
        char temp = board[x][y];
        board[x][y] = '#';  // 标记为访问过

        // 在四个方向上进行 DFS 搜索
        boolean found = dfs(board, word, x + 1, y, index + 1) ||
                        dfs(board, word, x - 1, y, index + 1) ||
                        dfs(board, word, x, y + 1, index + 1) ||
                        dfs(board, word, x, y - 1, index + 1);

        // 回溯：恢复当前字符，以便继续搜索其他路径
        board[x][y] = temp;

        return found;
    }
}

回溯

全排列

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> permute(int[] nums) {
        res = new LinkedList<>();
        LinkedList<Integer> track = new LinkedList<>(); // 记录「路径」
        boolean[] used = new boolean[nums.length]; //「路径」中的元素会被标记为 true，避免重复使用
        backtrack(nums, track, used);
        return res;
    }
    private void backtrack(int[] nums, LinkedList<Integer> track, boolean[] used) {
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) { // 排除不合法的选择
                // nums[i] 已经在 track 中，跳过
                continue;
            }
            // 做选择
            track.add(nums[i]);
            used[i] = true;
            // 进入下一层决策树
            backtrack(nums, track, used);
            // 取消选择
            track.removeLast();
            used[i] = false;
        }
    }
}

N皇后

public class Solution {
    private List<List<String>> res = new ArrayList<>();

    // 输入棋盘边长 n，返回所有合法的放置
    public List<List<String>> solveNQueens(int n) {
        // 每个字符串代表一行，字符串列表代表一个棋盘
        // '.' 表示空，'Q' 表示皇后，初始化空棋盘
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            board.add(".".repeat(n));
        }
        backtrack(board, 0);
        return res;
    }

    // 路径：board 中小于 row 的那些行都已经成功放置了皇后
    // 选择列表：第 row 行的所有列都是放置皇后的选择
    // 结束条件：row 超过 board 的最后一行
    private void backtrack(List<String> board, int row) {
        // 触发结束条件
        if (row == board.size()) {
            res.add(new ArrayList<>(board));
            return;
        }
        
        int n = board.get(row).length();
        for (int col = 0; col < n; col++) {
            // 排除不合法选择
            if (!isValid(board, row, col)) {
                continue;
            }
            // 做选择
            char[] rowChars = board.get(row).toCharArray();
            rowChars[col] = 'Q';
            board.set(row, new String(rowChars));
            // 进入下一行决策
            backtrack(board, row + 1);
            // 撤销选择
            rowChars[col] = '.';
            board.set(row, new String(rowChars));
        }
    }

    // 是否可以在 board[row][col] 放置皇后？
    private boolean isValid(List<String> board, int row, int col) {
        int n = board.size();
        // 检查列是否有皇后互相冲突
        for (int i = 0; i <= row; i++) {
            if (board.get(i).charAt(col) == 'Q') {
                return false;
            }
        }
        // 检查右上方是否有皇后互相冲突
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board.get(i).charAt(j) == 'Q') {
                return false;
            }
        }
        // 检查左上方是否有皇后互相冲突
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board.get(i).charAt(j) == 'Q') {
                return false;
            }
        }
        return true;
    }
}

数组的子集

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集(幂集)。解集不能包含重复的子集。你可以按任意顺序返回解集。

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> subsets(int[] nums) {
        res = new ArrayList<>();
        List<Integer> track = new ArrayList<>();
        backtrack(nums, 0, track);
        return res;
    }
    private void backtrack(int[] nums, int start, List<Integer> track) {
        res.add(new ArrayList<>(track));
        for (int i = start; i < nums.length; i++) {
            track.add(nums[i]); // 做选择
            backtrack(nums, i+1, track); // 回溯
            track.remove(track.size() - 1); // 撤销选择
        }
    }
}

设计模式

单例模式

单例模式确保一个类只有一个实例，并提供一个全局访问点。

饿汉式：饿汉式单例模式在类加载时就完成实例化，线程安全，简单但可能会造成资源浪费。
懒汉式：懒汉式单例模式在第一次调用 getInstance 方法时创建实例，线程不安全，需要额外处理同步。
线程安全的懒汉式
- 同步方法：在 getInstance 方法上加 synchronized 关键字，保证线程安全，但是效率低。
- 双重检查锁定：在 getInstance 方法内部进行双重检查，保证只有第一次调用时才会加锁，提高效率。
静态内部类：利用静态内部类来实现懒加载和线程安全。
枚举：枚举实现单例模式是最简洁、安全的实现方式，可以防止反射和序列化攻击。

// 饿汉式
public class Singleton {
    private static final Singleton instance = new Singleton();
    private Singleton() {}
    public static Singleton getInstance() {
        return instance;
    }
}

// 懒汉式
public class Singleton {
    private static Singleton instance;
    private Singleton() {}
    public static Singleton getInstance() {
        if (instance == null) {
            instance = new Singleton();
        }
        return instance;
    }
}

// 线程安全的懒汉式-同步方法
public class Singleton {
    private static Singleton instance;
    private Singleton() {}
    public static synchronized Singleton getInstance() {
        if (instance == null) {
            instance = new Singleton();
        }
        return instance;
    }
}

// 线程安全的懒汉式-双重检查锁定
public class Singleton {
    // 单例模式中用于保存实例的字段，被声明为volatile，确保对该变量的写入操作会立即反映到所有线程中，这样可以防止可能发生的指令重排序问题。
    private volatile static Singleton uniqueInstance;
    // 私有的构造方法确保该类不能在外部被初始化，只能通过getUniqueInstance()方法获取实例
    private Singleton() {
    }
    // 双重检查锁定的机制，实现对外提供的获取单例实例的方法。
    public static Singleton getInstance() {
        // 第一层检查：首先检查 uniqueInstance 是否为 null。如果不是 null，意味着实例已经被创建，则直接返回这个实例。
        if (uniqueInstance == null) {
            // 类对象加锁，表示进入同步代码前要获得 Singleton类 的锁
            synchronized (Singleton.class) {
                // 第二层检查：在同步代码块内再次检查 uniqueInstance 是否为 null。
                // 这种双重检查是为了在等待锁的线程获取到锁后再次确认实例是否已经被创建，因为在等待锁的过程中可能有其他线程已经创建了实例。
                if (uniqueInstance == null) {
                    uniqueInstance = new Singleton();
                }
            }
        }
        return uniqueInstance;
    }
    public static void main(String[] args) {
        System.out.println(getInstance());
    }

}

// 静态内部类
public class Singleton {
    private Singleton() {}
    private static class SingletonHolder {
        private static final Singleton INSTANCE = new Singleton();
    }
    public static Singleton getInstance() {
        return SingletonHolder.INSTANCE;
    }
}

// 枚举
public enum Singleton {
    // 注意 上面不是 class 是 enum
    INSTANCE;
    public void someMethod() {
        // do something
    }
    public static void main(String[] args) {
        Singelton singleton = Singleton.INSTANCE;
        singleton.someMethod();
    }
}

工厂模式

工厂模式定义了一个用于创建对象的接口，但由子类决定实例化哪个类。它使得类的实例化延迟到子类。

// 产品接口
interface Product {
    void use();
}
// 具体产品A
class ProductA implements Product {
    @Override
    public void use() {
        System.out.println("Using Product A");
    }
}
// 具体产品B
class ProductB implements Product {
    @Override
    public void use() {
        System.out.println("Using Product B");
    }
}
// 工厂类
class ProductFactory {
    public static Product createProduct(String type) {
        if (type.equals("A")) {
            return new ProductA();
        } else if (type.equals("B")) {
            return new ProductB();
        }
        throw new IllegalArgumentException("Unknown product type");
    }
}
// 使用
public class FactoryPatternDemo {
    public static void main(String[] args) {
        Product product = ProductFactory.createProduct("A");
        product.use();
    }
}

适配器模式

适配器模式将一个类的接口转换成客户希望的另一个接口，使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。

// 目标接口
interface Target {
    void request();
}
// 需要适配的类
class Adaptee {
    public void specificRequest() {
        System.out.println("Specific request");
    }
}
// 适配器
class Adapter implements Target {
    private Adaptee adaptee;
    public Adapter(Adaptee adaptee) {
        this.adaptee = adaptee;
    }
    @Override
    public void request() {
        adaptee.specificRequest();
    }
}
// 使用
public class AdapterPatternDemo {
    public static void main(String[] args) {
        Adaptee adaptee = new Adaptee();
        Target target = new Adapter(adaptee);
        target.request();
    }
}

装饰者模式

装饰者模式允许向一个现有的对象添加新的功能，同时又不改变其结构。

// 组件接口
interface Component {
    void operation();
}
// 具体组件
class ConcreteComponent implements Component {
    @Override
    public void operation() {
        System.out.println("ConcreteComponent operation");
    }
}
// 抽象装饰者
abstract class Decorator implements Component {
    protected Component component;
    public Decorator(Component component) {
        this.component = component;
    }
    @Override
    public void operation() {
        component.operation();
    }
}
// 具体装饰者A
class ConcreteDecoratorA extends Decorator {
    public ConcreteDecoratorA(Component component) {
        super(component);
    }
    @Override
    public void operation() {
        super.operation();
        System.out.println("ConcreteDecoratorA additional operation");
    }
}
// 具体装饰者B
class ConcreteDecoratorB extends Decorator {
    public ConcreteDecoratorB(Component component) {
        super(component);
    }
    @Override
    public void operation() {
        super.operation();
        System.out.println("ConcreteDecoratorB additional operation");
    }
}
// 使用
public class DecoratorPatternDemo {
    public static void main(String[] args) {
        Component component = new ConcreteComponent();
        Component decoratedComponentA = new ConcreteDecoratorA(component);
        Component decoratedComponentB = new ConcreteDecoratorB(decoratedComponentA);
        decoratedComponentB.operation();
    }
}

策略模式

策略模式定义了一系列算法，并将每一个算法封装起来，使它们可以相互替换。策略模式使得算法可独立于使用它的客户而变化。

// 策略接口
interface Strategy {
    int doOperation(int num1, int num2);
}
// 具体策略A
class OperationAdd implements Strategy {
    @Override
    public int doOperation(int num1, int num2) {
        return num1 + num2;
    }
}
// 具体策略B
class OperationSubtract implements Strategy {
    @Override
    public int doOperation(int num1, int num2) {
        return num1 - num2;
    }
}
// 具体策略C
class OperationMultiply implements Strategy {
    @Override
    public int doOperation(int num1, int num2) {
        return num1 * num2;
    }
}
// 上下文
class Context {
    private Strategy strategy;
    public Context(Strategy strategy) {
        this.strategy = strategy;
    }
    public int executeStrategy(int num1, int num2) {
        return strategy.doOperation(num1, num2);
    }
}
// 使用
public class StrategyPatternDemo {
    public static void main(String[] args) {
        Context context = new Context(new OperationAdd());
        System.out.println("10 + 5 = " + context.executeStrategy(10, 5));
        context = new Context(new OperationSubtract());
        System.out.println("10 - 5 = " + context.executeStrategy(10, 5));
        context = new Context(new OperationMultiply());
        System.out.println("10 * 5 = " + context.executeStrategy(10, 5));
    }
}

观察者模式

观察者模式定义对象间的一种一对多的依赖关系，使得每当一个对象改变状态，则所有依赖于它的对象都会得到通知并被自动更新。

import java.util.ArrayList;
import java.util.List;
// 观察者接口
interface Observer {
    void update(String message);
}
// 具体观察者
class ConcreteObserver implements Observer {
    private String name;
    public ConcreteObserver(String name) {
        this.name = name;
    }
    @Override
    public void update(String message) {
        System.out.println(name + " received: " + message);
    }
}
// 被观察者接口
interface Subject {
    void registerObserver(Observer observer);
    void removeObserver(Observer observer);
    void notifyObservers();
}
// 具体被观察者
class ConcreteSubject implements Subject {
    private List<Observer> observers = new ArrayList<>();
    private String message;
    @Override
    public void registerObserver(Observer observer) {
        observers.add(observer);
    }
    @Override
    public void removeObserver(Observer observer) {
        observers.remove(observer);
    }
    @Override
    public void notifyObservers() {
        for (Observer observer : observers) {
            observer.update(message);
        }
    }
    public void setMessage(String message) {
        this.message = message;
        notifyObservers();
    }
}
// 使用
public class ObserverPatternDemo {
    public static void main(String[] args) {
        ConcreteSubject subject = new ConcreteSubject();
        Observer observer1 = new ConcreteObserver("Observer 1");
        Observer observer2 = new ConcreteObserver("Observer 2");
        subject.registerObserver(observer1);
        subject.registerObserver(observer2);
        subject.setMessage("Hello Observers!");
    }
}

最长重复子串(不会)

class Solution {
    public String longestDupSubstring(String s) {
        Random random = new Random();
        // 生成两个进制
        int a1 = random.nextInt(75) + 26;
        int a2 = random.nextInt(75) + 26;
        // 生成两个模
        int mod1 = random.nextInt(Integer.MAX_VALUE - 1000000007 + 1) + 1000000007;
        int mod2 = random.nextInt(Integer.MAX_VALUE - 1000000007 + 1) + 1000000007;
        int n = s.length();
        // 先对所有字符进行编码
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = s.charAt(i) - 'a';
        }
        // 二分查找的范围是[1, n-1]
        int l = 1, r = n - 1;
        int length = 0, start = -1;
        while (l <= r) {
            int m = l + (r - l + 1) / 2;
            int idx = check(arr, m, a1, a2, mod1, mod2);
            if (idx != -1) {
                // 有重复子串，移动左边界
                l = m + 1;
                length = m;
                start = idx;
            } else {
                // 无重复子串，移动右边界
                r = m - 1;
            }
        }
        return start != -1 ? s.substring(start, start + length) : "";
    }
    public int check(int[] arr, int m, int a1, int a2, int mod1, int mod2) {
        int n = arr.length;
        long aL1 = pow(a1, m, mod1);
        long aL2 = pow(a2, m, mod2);
        long h1 = 0, h2 = 0;
        for (int i = 0; i < m; ++i) {
            h1 = (h1 * a1 % mod1 + arr[i]) % mod1;
            h2 = (h2 * a2 % mod2 + arr[i]) % mod2;
            if (h1 < 0) {
                h1 += mod1;
            }
            if (h2 < 0) {
                h2 += mod2;
            }
        }
        // 存储一个编码组合是否出现过
        Set<Long> seen = new HashSet<Long>();
        seen.add(h1 * mod2 + h2);
        for (int start = 1; start <= n - m; ++start) {
            h1 = (h1 * a1 % mod1 - arr[start - 1] * aL1 % mod1 + arr[start + m - 1]) % mod1;
            h2 = (h2 * a2 % mod2 - arr[start - 1] * aL2 % mod2 + arr[start + m - 1]) % mod2;
            if (h1 < 0) {
                h1 += mod1;
            }
            if (h2 < 0) {
                h2 += mod2;
            }
            long num = h1 * mod2 + h2;
            // 如果重复，则返回重复串的起点
            if (!seen.add(num)) {
                return start;
            }
        }
        // 没有重复，则返回-1
        return -1;
    }
    public long pow(int a, int m, int mod) {
        long ans = 1;
        long contribute = a;
        while (m > 0) {
            if (m % 2 == 1) {
                ans = ans * contribute % mod;
                if (ans < 0) {
                    ans += mod;
                }
            }
            contribute = contribute * contribute % mod;
            if (contribute < 0) {
                contribute += mod;
            }
            m /= 2;
        }
        return ans;
    }
}

A*算法

A*(A-star)算法是一种启发式搜索算法，常用于图搜索和路径规划问题。它结合了广度优先搜索和贪心最佳优先搜索的优点，使用启发式估计函数来指导搜索路径。

下面是一个简单的A*算法的Java实现，用于在二维网格上寻找从起点到终点的最短路径。假设网格中的每个节点是一个单元格，可以是可通行或不可通行的。

import java.util.*;
// 表示网格中的一个节点，包含节点的坐标、g 值(从起点到该节点的代价)、h 值(启发式估计值)和指向父节点的引用。
class Node implements Comparable<Node> {
    public int x, y;
    public int g, h;
    public Node parent; // 指向父节点的引用
    public Node(int x, int y, int g, int h, Node parent) {
        this.x = x;
        this.y = y;
        this.g = g;
        this.h = h;
        this.parent = parent;
    }
    public int getF() {
        return g + h;
    }
    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.getF(), other.getF());
    }
}
public class AStarAlgorithm {
    private static final int[] DIR_X = {-1, 1, 0, 0};
    private static final int[] DIR_Y = {0, 0, -1, 1};
    // aStar 方法执行 A* 搜索。它使用优先队列(基于节点的 F 值排序)来选择当前节点，并检查四个可能的移动方向(上下左右)。
    public List<Node> aStar(int[][] grid, Node start, Node goal) {
        PriorityQueue<Node> openList = new PriorityQueue<>();
        Set<Node> closedList = new HashSet<>();
        openList.add(start);
        while (!openList.isEmpty()) {
            Node current = openList.poll();
            if (current.x == goal.x && current.y == goal.y) {
                return constructPath(current);
            }
            closedList.add(current);
            for (int i = 0; i < 4; i++) {
                int newX = current.x + DIR_X[i];
                int newY = current.y + DIR_Y[i];
                if (isValid(grid, newX, newY) && !isInClosedList(closedList, newX, newY)) {
                    int newG = current.g + 1;
                    int newH = heuristic(newX, newY, goal.x, goal.y);
                    Node neighbor = new Node(newX, newY, newG, newH, current);
                    if (!isInOpenList(openList, neighbor)) {
                        openList.add(neighbor);
                    }
                }
            }
        }
        return Collections.emptyList(); // No path found
    }
    // isValid 方法检查移动是否在网格范围内且该位置可通行。
    private boolean isValid(int[][] grid, int x, int y) {
        return x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] == 0;
    }
    // isInClosedList 方法检查节点是否在 closedList 中。
    private boolean isInClosedList(Set<Node> closedList, int x, int y) {
        return closedList.stream().anyMatch(node -> node.x == x && node.y == y);
    }
    // isInOpenList 方法检查节点是否在 openList 中。
    private boolean isInOpenList(PriorityQueue<Node> openList, Node node) {
        return openList.stream().anyMatch(n -> n.x == node.x && n.y == node.y);
    }
    // heuristic 方法计算节点到目标节点的启发式估计值。这里使用的是曼哈顿距离。
    private int heuristic(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2); // Manhattan distance
    }
    // constructPath 方法从目标节点回溯构建路径。
    private List<Node> constructPath(Node node) {
        List<Node> path = new ArrayList<>();
        while (node != null) {
            path.add(node);
            node = node.parent;
        }
        Collections.reverse(path);
        return path;
    }
    // Main 方法：定义网格、起点和终点，运行 A* 算法并打印路径。
    public static void main(String[] args) {
        int[][] grid = {
            {0, 1, 0, 0, 0},
            {0, 1, 0, 1, 0},
            {0, 0, 0, 1, 0},
            {0, 1, 0, 0, 0},
            {0, 0, 0, 1, 0}
        };
        Node start = new Node(0, 0, 0, 0, null);
        Node goal = new Node(4, 4, 0, 0, null);
        AStarAlgorithm aStar = new AStarAlgorithm();
        List<Node> path = aStar.aStar(grid, start, goal);
        for (Node node : path) {
            System.out.println("Node: (" + node.x + ", " + node.y + ")");
        }
    }
}

漏桶算法

漏桶算法是一种流量整形(Traffic Shaping)和速率限制算法，用于控制数据传输速率。它通过固定容量的桶来限制数据的传输速率，当数据到达时，将数据放入桶中，然后以固定速率从桶中取出数据进行传输。

import java.util.concurrent.atomic.AtomicInteger;

public class LeakyBucket {
    private final int capacity;
    private final int rate;
    private AtomicInteger water;

    public LeakyBucket(int capacity, int rate) {
        this.capacity = capacity;
        this.rate = rate;
        this.water = new AtomicInteger(0);

        // 定期漏水
        new Thread(() -> {
            while (true) {
                try {
                    Thread.sleep(1000 / rate);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
                water.decrementAndGet();
            }
        }).start();
    }

    public boolean grant() {
        int currentWater = water.get();
        if (currentWater < capacity) {
            water.incrementAndGet();
            return true;
        }
        return false;
    }
}

令牌桶算法

令牌桶算法是一种流量整形(Traffic Shaping)和速率限制算法，用于控制数据传输速率。它通过固定容量的桶来限制数据的传输速率，当数据到达时，需要获取令牌才能进行传输。

import java.util.concurrent.atomic.AtomicInteger;

public class TokenBucket {
    private final int capacity;
    private final int refillRate;
    private AtomicInteger tokens;
    private final long refillInterval;

    public TokenBucket(int capacity, int refillRate) {
        this.capacity = capacity;
        this.refillRate = refillRate;
        this.tokens = new AtomicInteger(capacity);
        this.refillInterval = 1000 / refillRate;

        // 定期添加令牌
        new Thread(() -> {
            while (true) {
                try {
                    Thread.sleep(refillInterval);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
                tokens.updateAndGet(current -> Math.min(capacity, current + 1));
            }
        }).start();
    }

    public boolean grant() {
        int currentTokens = tokens.get();
        if (currentTokens > 0) {
            tokens.decrementAndGet();
            return true;
        }
        return false;
    }
}

限流队列

结合漏桶算法和消息队列，实现一个限流队列，用于控制任务的执行速率。

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class RateLimiterQueue {
    private final LeakyBucket rateLimiter;
    private final BlockingQueue<Runnable> taskQueue;

    public RateLimiterQueue(int capacity, int rate, int queueSize) {
        this.rateLimiter = new LeakyBucket(capacity, rate);
        this.taskQueue = new LinkedBlockingQueue<>(queueSize);
        
        new Thread(() -> {
            while (true) {
                try {
                    Runnable task = taskQueue.take();
                    if (rateLimiter.grant()) {
                        new Thread(task).start();
                    } else {
                        // 限流，重新加入队列
                        taskQueue.offer(task);
                    }
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        }).start();
    }
    public void submitTask(Runnable task) {
        if (!taskQueue.offer(task)) {
            System.out.println("任务队列已满，拒绝任务");
        }
    }
    public static void main(String[] args) {
        RateLimiterQueue rateLimiterQueue = new RateLimiterQueue(100, 10, 1000);

        for (int i = 0; i < 10000; i++) {
            final int taskId = i;
            rateLimiterQueue.submitTask(() -> {
                System.out.println("处理任务：" + taskId);
                // 模拟任务处理时间
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            });
        }
    }
}

华为相关

课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 初始化入度数组和邻接表
        int[] inDegree = new int[numCourses];
        List<List<Integer>> adjList = new ArrayList<>();

        // 初始化邻接表
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }

        // 构建图并计算每个节点的入度
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int pre = prerequisite[1];
            adjList.get(pre).add(course);
            inDegree[course]++;
        }

        // 创建队列，加入所有入度为 0 的节点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 用于保存拓扑排序的结果
        int[] order = new int[numCourses];
        int index = 0;

        // Kahn 拓扑排序
        while (!queue.isEmpty()) {
            int course = queue.poll();
            order[index++] = course;

            // 遍历当前课程的邻接节点
            for (int neighbor : adjList.get(course)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // 如果结果中的课程数等于总课程数，说明没有环
        return index == numCourses ? true : false;
    }
}

课程表2

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前必须先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回任意一种就可以了。如果不可能完成所有课程，返回一个空数组。

import java.util.*;

public class CourseSchedule {
    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        // 初始化入度数组和邻接表
        int[] inDegree = new int[numCourses];
        List<List<Integer>> adjList = new ArrayList<>();
        
        // 初始化邻接表
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }
        
        // 构建图并计算每个节点的入度
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int pre = prerequisite[1];
            adjList.get(pre).add(course);
            inDegree[course]++;
        }
        
        // 创建队列，加入所有入度为 0 的节点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        // 用于保存拓扑排序的结果
        int[] order = new int[numCourses];
        int index = 0;
        
        // Kahn 拓扑排序
        while (!queue.isEmpty()) {
            int course = queue.poll();
            order[index++] = course;
            
            // 遍历当前课程的邻接节点
            for (int neighbor : adjList.get(course)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        // 如果结果中的课程数等于总课程数，说明没有环
        return index == numCourses ? order : new int[0];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numCourses = sc.nextInt();
        int m = sc.nextInt();
        int[][] prerequisites = new int[m][2];
        for (int i = 0; i < m; i++) {
            prerequisites[i][0] = sc.nextInt();
            prerequisites[i][1] = sc.nextInt();
        }
        int[] result = findOrder(numCourses, prerequisites);
        if (result.length == 0) {
            System.out.println("Impossible to complete all courses.");
        } else {
            for (int course : result) {
                System.out.print(course + " ");
            }
        }
    }
}

汇总区间

JavaACM模式解题
给定一个无重复元素的有序整数数组nums，返回恰好覆盖数组中所有数字的最小有序区间范围列表。
示例1：
输入：nums=[0,1,2,4,5,7]
输出：[(0,2), (4,5), (7)]
示例2：
输入：nums=[0,2,3,4,6,8,9]
输出：[(0), (2,4), (6), (8,9)]

import java.util.*;

public class Solution {
    public List<List<Integer>> summaryRanges(int[] nums) {
        // 创建一个列表用于存储结果
        List<List<Integer>> result = new ArrayList<>();
        
        // 如果输入数组为空，直接返回空列表
        if (nums.length == 0) return result;
        
        // 初始化起始点，起始点为数组的第一个数字
        int start = nums[0];
        
        // 遍历数组中的每一个元素
        for (int i = 1; i <= nums.length; i++) {
            // 判断当前数字是否与前一个数字连续（即 nums[i] == nums[i-1] + 1）
            // 或者当前已经是数组的最后一个元素
            if (i == nums.length || nums[i] != nums[i - 1] + 1) {
                // 创建一个区间的列表来记录当前的区间
                List<Integer> range = new ArrayList<>();
                // 将起始点添加到区间中
                range.add(start);
                
                // 如果区间的起始点和结束点不同，表示这是一个包含多个数字的区间
                if (i - 1 > 0 && nums[i - 1] != start) {
                    // 添加区间的结束点
                    range.add(nums[i - 1]);
                }
                
                // 将当前区间添加到结果列表中
                result.add(range);
                
                // 如果当前不是数组的最后一个元素，更新起始点为当前的数字
                if (i < nums.length) start = nums[i];
            }
        }
        
        // 返回最终的结果列表
        return result;
    }
}

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

class Solution {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        // 按区间起点升序排列，终点降序排列
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });
        List<int[]> res = new ArrayList<>();
        res.add(intervals[0]);
        int start = intervals[0][0];
        int end = intervals[0][1];

        for (int i = 1; i < n; i++) {
            int[] intv = intervals[i];
            int[] last = res.get(res.size() - 1);
            // 重叠了
            if (intv[0] <= last[1]) {
                // 找到两个区间中最大的 end
                last[1] = Math.max(last[1], intv[1]);
            } else {
                res.add(intv);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

ab=cd元组个数

一个数组没有重复数字，求ab=cd的元组的个数

import java.util.HashMap;

public class TupleCount {
    public static int countTuples(int[] nums) {
        int n = nums.length;
        HashMap<Integer, Integer> productMap = new HashMap<>();
        int count = 0;

        // 遍历所有的 (a, b) 对，计算乘积并存入哈希表
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int product = nums[i] * nums[j];
                productMap.put(product, productMap.getOrDefault(product, 0) + 1);
            }
        }

        // 遍历哈希表，计算每个乘积的组合数
        for (int k : productMap.values()) {
            if (k > 1) {
                count += k * (k - 1) / 2;  // C(k, 2) = k * (k - 1) / 2
            }
        }

        return count;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 4, 6};
        System.out.println(countTuples(nums));  // 输出符合条件的元组个数
    }
}

轮船最小载重

给定一个货物数组int[]weight，使用轮船运往对岸，不可更改顺序,天数d，要求在d天恰好能够将货物运送完毕，请求出能在d天将货物运送完毕的轮船最小载重量。

思路：
二分查找：通过二分查找来找到最小的最大载重。

左边界：最小载重应该是货物中最大的一项，因为一天至少需要能承载最大的货物。

右边界：最大载重应该是所有货物的总和，假如一天能运送所有货物。
判断是否可行：给定一个载重 x，我们可以计算出需要多少天才能完成运输。每次尽量多装一些货物，如果当前船的载重不够，就新的一天继续运输，直到所有货物都运送完或者天数超过 d。

public class Solution {
    public int shipWithinDays(int[] weights, int d) {
        int left = 0, right = 0;
        
        // 计算左边界和右边界
        for (int weight : weights) {
            left = Math.max(left, weight); // 左边界为最大单个货物重量
            right += weight; // 右边界为所有货物总重
        }
        
        // 使用二分查找来查找最小的船只最大载重
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // 判断在最大载重为 mid 的情况下，是否可以在 d 天内运送完所有货物
            if (canShip(weights, d, mid)) {
                right = mid; // 如果可以运送完，尝试更小的载重
            } else {
                left = mid + 1; // 如果不能运送完，载重太小，增大载重
            }
        }
        
        return left;
    }
    
    // 判断在最大载重为 cap 的情况下，是否能在 d 天内运送所有货物
    private boolean canShip(int[] weights, int d, int cap) {
        int daysRequired = 1, currentWeight = 0;
        
        for (int weight : weights) {
            // 如果当前货物加上已装载货物超过最大载重，则需要新的一天
            if (currentWeight + weight > cap) {
                daysRequired++;  // 新的一天
                currentWeight = 0; // 重置当前船的负重
            }
            currentWeight += weight; // 装载货物
        }
        
        return daysRequired <= d; // 如果需要的天数小于等于 d 天，则可以运送完
    }
}

将数组变锯齿数组的最小操作次数。

给一个数组int[] num，每次操作可以将数组任一元素减一，求将数组改变为锯齿状数组的最小操作数量。

public class ZigzagArray {
    public static int minOperationsToZigzag(int[] nums) {
        int n = nums.length;
        // 两种模式的操作次数
        int cost1 = 0; // 波峰模式
        int cost2 = 0; // 波谷模式

        for (int i = 0; i < n; i++) {
            // 获取左右相邻的值，如果越界，设为Integer.MAX_VALUE
            int left = (i > 0) ? nums[i - 1] : Integer.MAX_VALUE;
            int right = (i < n - 1) ? nums[i + 1] : Integer.MAX_VALUE;

            // 如果在波峰模式中，当前值需要大于左右相邻值
            if (i % 2 == 0) {
                int reduce = Math.max(0, nums[i] - Math.min(left, right) + 1);
                cost1 += reduce;
            } else { // 波谷模式
                int reduce = Math.max(0, nums[i] - Math.min(left, right) + 1);
                cost2 += reduce;
            }
        }

        // 返回两种模式的较小操作数
        return Math.min(cost1, cost2);
    }

    public static void main(String[] args) {
        int[] nums = {9, 6, 1, 6, 2};
        System.out.println("Minimum operations: " + minOperationsToZigzag(nums));
    }
}

盛水最多的容器

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int res = 0;
        while (left < right) {
            // [left, right] 之间的矩形面积
            int cur_area = Math.min(height[left], height[right]) * (right - left);
            res = Math.max(res, cur_area);
            // 双指针技巧，移动较低的一边
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return res;
    }
}

装金币

有num枚金币，每枚金币的价值分别是valuei，设置一个价值上限limitvalue，从中选一些金币出来，使金币总价值不超过limitvalue，求能选出的金币最大总和。其中value[i]和 limitvalue都是正整数。
解题思路：

定义状态：dp[j] 表示在总价值上限为 j 的情况下，能够选取的金币的最大总和。
状态转移方程：
- 选第 i 枚金币：dp[j] = dp[j]
- 如果选第 i 枚金币（且 j >= value[i]）：dp[j] = max(dp[j], dp[j - value[i]] + value[i])
初始化：
- dp[0] = 0 表示价值上限为 0 时，选取的总价值为 0。
- 其余 dp[j] 初始为 0（未选任何金币时）。
目标：有金币和价值上限，计算出 dp[limitValue] 即为答案。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 输入金币数量和价值上限
        int num = sc.nextInt();
        int limitValue = sc.nextInt();
        
        // 输入每枚金币的价值
        int[] value = new int[num];
        for (int i = 0; i < num; i++) {
            value[i] = sc.nextInt();
        }
        
        // 定义 dp 数组
        int[] dp = new int[limitValue + 1];
        
        // 动态规划求解
        for (int i = 0; i < num; i++) {
            for (int j = limitValue; j >= value[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - value[i]] + value[i]);
            }
        }
        // 输出结果
        System.out.println(dp[limitValue]);
    }
}

输入为一个数组与一个数字k，能否分组,使得每一组都刚好有k个相同的元素。思路为哈希表+取模判断
统计频率：
使用哈希表（HashMap）统计每个元素的出现次数。
取模判断：
遍历哈希表中的频率值，检查每个频率是否能被 k 整除。如果有某个频率不能被 k 整除，直接返回 false。
输出结果：
如果所有频率都能被 k 整除，返回 true。

import java.util.HashMap;

public class Solution {
    public static boolean canDivideIntoGroups(int[] nums, int k) {
        // 边界条件
        if (nums == null || nums.length == 0 || k <= 0) {
            return false;
        }
        
        // 统计每个元素的频率
        HashMap<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        
        // 检查每个频率是否能被 k 整除
        for (int freq : frequencyMap.values()) {
            if (freq % k != 0) {
                return false;
            }
        }
        
        // 所有频率都能被 k 整除
        return true;
    }
}

空间复杂度O(1)判断数组是否有重复元素

public class DuplicateChecker {
    public static boolean hasDuplicate(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        System.out.println(hasDuplicate(nums)); // 输出 false
    }
}

给一个二进制补码数组，求十进制数字

判断符号位：补码表示中，最高位是符号位。0 表示正数，1 表示负数。
处理正数：如果符号位是 0，直接将剩余位的二进制部分转为十进制。

处理负数：如果符号位是 1，将整个补码取反（0->1，1->0）后加 1 得到对应的绝对值，然后将其转为负数。

public class Main {
    public static void main(String[] args) {
        // 示例补码数组：-6 的补码表示
        int[] binary = {1, 1, 1, 1, 1, 0}; 
        
        // 计算十进制值
        int decimalValue = convertToDecimal(binary);
        System.out.println(decimalValue); // 输出 -6
    }

    public static int convertToDecimal(int[] binary) {
        int n = binary.length;
        boolean isNegative = binary[0] == 1; // 判断符号位
        int result = 0;
        
        if (!isNegative) {
            // 处理正数
            for (int i = 0; i < n; i++) {
                result = result * 2 + binary[i];
            }
        } else {
            // 处理负数
            // 1. 取反
            int[] inverted = new int[n];
            for (int i = 0; i < n; i++) {
                inverted[i] = binary[i] == 0 ? 1 : 0;
            }
            // 2. 加 1
            int carry = 1; // 表示进位
            for (int i = n - 1; i >= 0; i--) {
                int sum = inverted[i] + carry;
                inverted[i] = sum % 2;
                carry = sum / 2;
            }
            // 3. 计算绝对值
            for (int i = 0; i < n; i++) {
                result = result * 2 + inverted[i];
            }
            result = -result; // 转为负数
        }
        return result;
    }
}