手撕相关

Agent开发手撕

手写一个简单的ReAct Agent

核心就是一个 for 循环： 思考、行动、观察

package agent.react;

import java.util.*;
import java.util.function.Function;

public class ReActAgent {

    private final Map<String, Function<Map<String, String>, String>> tools = new HashMap<>();
    private final int maxRounds;

    public ReActAgent(int maxRounds) {
        this.maxRounds = maxRounds;
    }

    public void registerTool(String name, Function<Map<String, String>, String> func) {
        tools.put(name, func);
    }

    public String run(String query) {
        List<String> history = new ArrayList<>();
        history.add("Question: " + query);

        for (int i = 0; i < maxRounds; i++) {
            // 1. Thought — LLM 推理，决定下一步动作
            LLMResult result = callLLM(history);

            // 2. 如果 LLM 给出了最终答案，直接返回
            if (result.finalAnswer != null) {
                return result.finalAnswer;
            }

            // 3. Action — 调用工具
            String observation;
            Function<Map<String, String>, String> tool = tools.get(result.toolName);
            if (tool == null) {
                observation = "Error: 工具不存在 " + result.toolName;
            } else {
                try {
                    observation = tool.apply(result.toolParams);
                } catch (Exception e) {
                    observation = "Error: " + e.getMessage();
                }
            }

            // 4. Observation — 将结果反馈给下一轮推理
            history.add("Thought: " + result.thought);
            history.add("Action: " + result.toolName + " " + result.toolParams);
            history.add("Observation: " + observation);
        }

        return "超过最大轮数，未得出答案";
    }

    // 调用大模型，返回结构化结果（实际对接 OpenAI/Claude API）
    private LLMResult callLLM(List<String> history) {
        // TODO: 拼装 system prompt（含工具描述）+ history，调用 LLM，解析输出
        return new LLMResult();
    }

    static class LLMResult {
        String thought;
        String toolName;
        Map<String, String> toolParams;
        String finalAnswer; // 非null表示结束
    }
}

手写一个并行的双Agent系统

核心就是 CompletableFuture + 共享 ConcurrentHashMap

package agent.parallel;

import java.util.concurrent.*;

public class DualAgentSystem {

    // 线程安全的共享状态
    private final ConcurrentHashMap<String, Object> state = new ConcurrentHashMap<>();

    @FunctionalInterface
    interface Agent {
        String execute(ConcurrentHashMap<String, Object> state) throws Exception;
    }

    public String run(Agent syncAgent, Agent asyncAgent, long timeoutSeconds) {

        // 1. 异步启动 Agent B
        CompletableFuture<String> asyncFuture = CompletableFuture.supplyAsync(() -> {
            try {
                String result = asyncAgent.execute(state);
                state.put("async_result", result);
                return result;
            } catch (Exception e) {
                return "ASYNC_ERROR: " + e.getMessage();
            }
        });

        // 2. 同步执行 Agent A（主线程）
        String syncResult;
        try {
            syncResult = syncAgent.execute(state);
            state.put("sync_result", syncResult);
        } catch (Exception e) {
            syncResult = "SYNC_ERROR: " + e.getMessage();
        }

        // 3. 等待异步 Agent 完成（带超时）
        String asyncResult;
        try {
            asyncResult = asyncFuture.get(timeoutSeconds, TimeUnit.SECONDS);
        } catch (TimeoutException e) {
            asyncFuture.cancel(true);
            asyncResult = "ASYNC_TIMEOUT";
        } catch (Exception e) {
            asyncResult = "ASYNC_ERROR: " + e.getMessage();
        }

        // 4. 合并结果
        return "同步: " + syncResult + "\n异步: " + asyncResult;
    }
}

手写一个带重试和降级的Tool调用

package agent.retry;

import java.util.Map;
import java.util.function.Function;

public class ResilientToolInvoker {

    @FunctionalInterface
    interface ToolFunction {
        String call(Map<String, Object> params) throws Exception;
    }

    /**
     * 带重试和降级的工具调用
     * @param tool       要调用的工具
     * @param params     工具参数
     * @param maxRetries 最大重试次数
     * @param fallback   降级函数（全部失败后调用，可为null）
     */
    public static String invoke(ToolFunction tool, Map<String, Object> params,
                                int maxRetries, ToolFunction fallback) {

        Exception lastError = null;

        for (int attempt = 0; attempt <= maxRetries; attempt++) {
            // 指数退避（首次调用不等待）
            if (attempt > 0) {
                long delay = Math.min(1000L * (1L << (attempt - 1)), 10000); // 1s, 2s, 4s... 上限10s
                try { Thread.sleep(delay); } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                    break;
                }
            }

            try {
                String result = tool.call(params);
                validateJson(result); // JSON 格式校验
                return result;
            } catch (Exception e) {
                lastError = e;
            }
        }

        // 所有重试失败，尝试降级
        if (fallback != null) {
            try {
                String result = fallback.call(params);
                validateJson(result);
                return result;
            } catch (Exception ignored) {}
        }

        throw new RuntimeException("工具调用失败，已重试" + maxRetries + "次", lastError);
    }

    // 简易JSON校验：检查是否以{}或[]包裹，括号是否匹配
    private static void validateJson(String json) {
        if (json == null || json.isBlank()) {
            throw new IllegalArgumentException("返回结果为空");
        }
        String s = json.trim();
        if (s.startsWith("{") && s.endsWith("}")) return;
        if (s.startsWith("[") && s.endsWith("]")) return;
        if (s.startsWith("\"") && s.endsWith("\"")) return;
        try { Double.parseDouble(s); return; } catch (NumberFormatException ignored) {}
        if ("true".equals(s) || "false".equals(s) || "null".equals(s)) return;
        throw new IllegalArgumentException("非法JSON: " + s);
    }
}

链表

有序链表合并

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

合并k个升序链表

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        // 虚拟头结点创建新的链表
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;

        // 优先级队列，默认从小到大排列，最前面就是最小的值。
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) { // 以结点的值来比较大小
                return o1.val - o2.val;
            }
        });

        // 将所有连标的头结点加入优先级队列
        for (ListNode head : lists) {
            if (head != null)
                pq.add(head);
        }

        while (!pq.isEmpty()) {
            // 取出优先级队列的头元素，该元素就是所有链表头节点中最小的。
            ListNode temp = pq.poll();
            // 取出的头节点加入到新的链表中
            p.next = temp;

            // 如果包含temp结点的链表的元素不为空，则该链表前进向下一个元素
            if (temp.next != null) {
                pq.add(temp.next);
            }
            // 新链表p前进
            p = p.next;
        }
        // 注意返回的是虚拟头结点的下一个元素
        return dummy.next;
    }
}

重排链表

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

删除链表倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

class Solution {
    // 返回链表的倒数第 k 个节点
    private 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 一起向前走， p1 走到结尾
        while (p1.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }

        // 此时 p2 所在就是倒数第 k 个结点
        return p2;
    }
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建虚拟头结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 删除倒数第 n 个结点，要先找到该结点前面的结点，即正数第 n-1 个结点，然而这时候使用dummy增加了一个结点，所以此时正数第 n-1 个结点变为正数第 n 个结点。
        ListNode tar = findFromEnd(dummy, n); // 注意这里使用dummy的技巧，巧妙利用dummy，不用分开讨论删除头结点的情况。
        // 找到要删除的结点的前面的结点，然后让其指向该结点所指向的结点，跳过该结点，就等于删除。
        tar.next = tar.next.next;

        // 注意返回 dummy.next
        return dummy.next;
    }
}

寻找链表的中间节点

快慢指针法

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; // 返回新的头结点
}

两两交换链表节点

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

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 结束条件
        if (head == null || head.next == null) return head;

        ListNode first = head;
        ListNode second = head.next;
        ListNode others = head.next.next;
        // 先反转前两个元素
        second.next = first;
        // 原来的头结点指向反转后的剩余元素
        first.next = swapPairs(others);
        // 第二个元素是现在的头结点
        return second;
    }
}

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 ，该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
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);
    }
}

回文链表

判断该链表是否为回文链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    private static final int MAX_N = 100001;
    private static int[] nums = new int[MAX_N];
    public boolean isPalindrome(ListNode head) {
        if(head == null) return false;
        ListNode p = head;
        int len = 0;
        for (int i = 1; i < MAX_N; i++) {
            nums[i] = p.val;
            if (p.next != null) {
                p = p.next;
            } else {
                len = i;
                break;
            }
        }

        return isPalindrome(1, len);
    }
    private boolean isPalindrome(int start_index, int end_index) {
        int left = start_index, right = end_index;
        while (left < right && nums[left] == nums[right]) {
            left++;
            right--;
        }
        if (left >= right) {
            return true;
        } else {
            return false;
        }
    }
}

两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return addTwo(l1, l2, 0);
    }

    // l1 和 l2 为当前遍历的节点，carry 为进位
    private ListNode addTwo(ListNode l1, ListNode l2, int carry) {
        // 递归边界
        if (l1 == null && l2 == null && carry == 0) {
            return null;
        }

        int s = carry;
        if (l1 != null) {
            s += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            s += l2.val;
            l2 = l2.next;
        }

        // s 除以 10 的余数为当前节点值，商为进位，注意使用的是第二个构造方法，直接就将当前节点与new的节点连接了
        return new ListNode(s % 10, addTwo(l1, l2, s / 10));
    }
}

排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

import java.util.*;

class Solution {
    public ListNode sortList(ListNode head) {
        List<Integer> nums = new ArrayList<>();
        for (ListNode p = head; p != null; p = p.next) {
            nums.add(p.val);
        }
        Collections.sort(nums);
        ListNode p = head;
        for (int num : nums) {
            p.val = num;
            p = p.next;
        }
        return head;
    }
}

二叉树

二叉树深度

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

二叉树最大深度

class Solution {
    public int res = 0;
    public int maxDepth(TreeNode root) {
        traverse(root, 0);
        return res;
    }
    public int traverse(TreeNode root, int depth) {
        if (root == null) {
            return 0;
        }
        int leftDep = traverse(root.left, depth + 1);
        int rightDep = traverse(root.right, depth + 1);

        res = Math.max(leftDep, rightDep) + 1;
        return res;
    }
}

翻转二叉树

class Solution {
    public TreeNode invertTree(TreeNode root) {
        traverse(root);
        return root;
    }

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

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

对称二叉树

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

class Solution {
    private int[] nums;
    public boolean isSymmetric(TreeNode root) {
        return traverse(root, root);
    }

    private boolean traverse(TreeNode root, TreeNode root1) {
        if (root == null && root1 == null) {
            return true;
        }
        if (root == null || root1 == null) {
            return false;
        }

        return root.val == root1.val && traverse(root.left, root1.right) && traverse(root.right, root1.left);
    }
}

二叉树前序遍历转链表

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

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 {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }

}

二叉搜索树种第K小元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。

class Solution {
    private List<Integer> nums = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        traverse(root);
        Collections.sort(nums);
        return nums.get(k-1);
    }

    private void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        nums.add(root.val);
        traverse(root.left);
        traverse(root.right);
    }

}

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

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);
    }
    
    // leetcode
    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); // 当前子树的最大链和
    }
}

路径总和3

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

class Solution {
    public int pathSum(TreeNode root, long targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = rootSum(root, targetSum);
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return ret;
    }

    public int rootSum(TreeNode root, long targetSum) {
        int ret = 0;

        if (root == null) {
            return 0;
        }
        int val = root.val;
        if (val == targetSum) {
            ret++;
        }

        ret += rootSum(root.left, targetSum - val);
        ret += rootSum(root.right, targetSum - val);
        return ret;
    }
}

二叉树最大宽度

// 层序遍历思路
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);
    }
}

二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。

class Solution {

    int maxDiameter = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return maxDiameter;
    }

    // 计算二叉树的最大深度
    private int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 前序遍历
        int leftMax = maxDepth(root.left);
        
        // 中序遍历
        
        int rightMax = maxDepth(root.right);
        
        // 后序遍历
        // 后序遍历能获取左右子树的最大深度，所以在这里计算。
        int myDiameter = leftMax + rightMax;
        maxDiameter = Math.max(maxDiameter, myDiameter);

        // 注意返回的是树的最大深度，不是最大直径。
        return 1 + Math.max(leftMax, rightMax);
    }
}

二叉树的右视图

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size-1) {
                    res.add(node.val);
                }

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return res;
    }
}

二叉树展开为链表

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;

        flatten(root.left);
        flatten(root.right);

        TreeNode left = root.left;
        TreeNode right = root.right;

        root.left = null;
        root.right = left;

        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }
        p.right = right;
    }
}

多叉树查找某个值

// 定义多叉树的节点类
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);
    }
}

动态规划

爬楼梯

假设你正在爬楼梯。需要 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;
    }
}


/*
    保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标：
- 对于遇到的每个 ‘(’ ，将它的下标放入栈中
- 对于遇到的每个 ‘)’ ，先弹出栈顶元素表示匹配了当前右括号：
    - 如果栈为空，说明当前的右括号为没有被匹配的右括号，将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
    - 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
 */
class Solution2 {
    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;
    }
}

最长回文子串

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 {
    private int[] memo;
    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return dp(nums, 0);
    }

    // 定义dp(nums, index)为抢夺nums[index..]所能够盗窃到的最高金额
    private int dp(int[] nums, int index) {
        // base case
        if (index >= nums.length) return 0;
        
        if (memo[index] != -1) return memo[index];

        // 状态转移函数
        // 第一种选择，如果在当前index盗窃，则不能在index+1盗窃
        int first = nums[index] + dp(nums, index + 2);
        // 第二种选择，如果不在当前index盗窃，则可以在index+1盗窃
        int second = dp(nums, index+1);
        
        int res = Math.max(first, second);
        memo[index] = res;
        
        return res;

    }

}

完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

class Solution {
    public int numSquares(int n) {
        // 定义：和为 i 的平方数的最小数量是 dp[i]
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        // base case
        dp[0] = 0;
        // 状态转移方程
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                // i - j * j 只要再加一个平方数 j * j 即可凑出 i
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }

}

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

class Solution {
    int[] memo;
    public int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        Arrays.fill(memo, -100);
        return dp(coins, amount);
    }

    private int dp(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;

        if (memo[amount] != -100) {
            return memo[amount];
        }

        int res = Integer.MAX_VALUE;

        for (int coin : coins) {
            int subProblem = dp(coins, amount - coin);
            if (subProblem == -1) continue;

            res = Math.min(res, subProblem + 1);
        }

        memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;

        return memo[amount];
    }
}

单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

import java.util.*;
class Solution {
    HashSet<String> set;
    int[] memo;
    public boolean wordBreak(String s, List<String> wordDict) {
        set = new HashSet<>(wordDict);

        memo = new int[s.length()];
        // -1未计算，0不能被拼出，1可以被拼出
        Arrays.fill(memo, -1);

        return dp(s, 0);
    }

    // 定义dp(s, i)为s[i..]是否可以被拼接出。
    private boolean dp(String s, int i) {
        if (i == s.length()) return true;

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

        for (int len = 1; i + len <= s.length(); len++) {
            // 如果prefix包含在wordDict里面
            String prefix = s.substring(i, i + len);
            if (set.contains(prefix)) {
                // 如果s[i+len..]可以被拼出，则s[i..]也可以被拼出
                if (dp(s, i + len)) {
                    memo[i] = 1;
                    return true;
                }
            }
        }
        memo[i] = 0;
        return false;
    }
}

分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        // 如果和为奇数，则不能平分
        if (sum % 2 != 0) {
            return false;
        }
        sum = sum/2;
        // 定义dp[i][j]为nums中前i个数是否可以拼凑出sum
        boolean[][] dp = new boolean[n+1][sum+1];

        // base case
        // 前0个的话，没有数字可以拼凑出num，dp[0][..] = false
        // 如果背包为0，不管任何数字，不使用就可以填满
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }

        // 状态转移函数
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                // 如果容量不足，不能装入第i个物品
                if (j < nums[i-1]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    // 不装入 || 装入第i个物品
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }


        return dp[n][sum]; // sum已经除以2了。
    }
}

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

class Solution {
    int[][] memo;
    public int uniquePaths(int m, int n) {
        memo = new int[m][n];
        return dp(m-1, n-1);
    }

    private int dp(int x, int y) {
        // base case
        if (x == 0 && y == 0) {
            return 1;
        }
        if (x < 0 || y < 0) {
            return 0;
        }

        if (memo[x][y] > 0) return memo[x][y];
        memo[x][y] = dp(x-1, y) + dp(x, y-1);
        return memo[x][y];
    }
}

最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // 定义dp[i][j]为grid[0..i][0..j]的最小路径和
        int[][] dp = new int[m][n];

        // base case
        dp[0][0] = grid[0][0];
        // 处理一些边界情况
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }


        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 状态转移函数
                dp[i][j] = Math.min(dp[i-1][j] + grid[i][j], dp[i][j-1] + grid[i][j]);
            }
        }
        return dp[m-1][n-1];
    }
}

乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

class Solution {
    public int maxProduct(int[] nums) {
        int res = Integer.MIN_VALUE;
        int max = 1;
        int min = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) {
                // 如果nums[i] 小于0，则交换max和min
                int temp = max;
                max = min;
                min = temp;
            }

            // 维护当前最大值和当前最小值
            max = Math.max(max*nums[i], nums[i]);
            min = Math.min(min*nums[i], nums[i]);
            
            res = Math.max(res, max);
            
        }
        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 int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n-k+1];
        int resIndex = 0;

        // pq存储元素值及其索引，自定义Comparator，让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.offer(new int[]{nums[i], i});
            // 根据 index 堆顶元素是否不在窗口，不在的话poll出来
            while (pq.peek()[1] < i-k+1) {
                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;
    }
}

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

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        // 滑动窗口
        HashMap<Character, Integer> window = new HashMap<>();
        HashMap<Character, Integer> need = new HashMap<>();
        // 将p存入need
        for (char c : p.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0, valid = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            // 增大窗口
            right++;
            // 增大窗口后对数据处理
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if ((int)need.get(c) == (int)window.get(c)) {
                    valid++;
                }
            }
            // 缩小窗口条件: 窗口长度达到p的长度
            while (right - left == p.length()) {
                // 更新结果
                if (valid == need.size()) {
                    res.add(left);
                }
                char d = s.charAt(left);
                // 缩小窗口
                left++;
                // 缩小窗口后对数据处理
                if (need.containsKey(d)) {
                    if ((int)need.get(d) == (int)window.get(d)) {
                        valid--;
                    }
                    window.put(d, window.get(d) -1);
                }
            }
        }
        return res;
    }
}

最小覆盖子串

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 “”。

class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> window = new HashMap<>();
        HashMap<Character, Integer> need = new HashMap<>();

        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0, valid = 0;
        int start = 0, len = Integer.MAX_VALUE;
        while (right < s.length()) {
            char c = s.charAt(right);
            // 增大窗口
            right++;
            // 增大窗口后对数据处理
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            // 缩小窗口条件
            while(need.size() == valid){
                // 更新res相关逻辑，这里本应该是right - left + 1，但是在while 中前面的right++已经加过1了。
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }

                char d = s.charAt(left);
                // 缩小窗口
                left++;
                // 缩小窗口后对数据处理
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

数组

轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int newK = k % n;
        int[] newNums = new int[2*n];
        for (int i = 0; i < n; i++) {
            newNums[i] = nums[i];
            newNums[i+n] = nums[i];
        }
        for (int i = 0; i < n; i++) {
            nums[i] = newNums[n-newK+i];
        }
    }
}

除了自身以外数组的乘积

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] l_nums = new int[n];
        int[] r_nums = new int[n];
        l_nums[0] = 1;
        r_nums[n-1] = 1;
        for (int i = 1; i < n; i++) {
            l_nums[i] = l_nums[i-1] * nums[i-1];
        }
        for (int i = n-2; i >= 0; i--) {
            r_nums[i] = r_nums[i+1] * nums[i+1];
        }
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = l_nums[i] * r_nums[i];
        }
        return res;
    }
}

缺失的第一个整数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0 && nums[i] <= n) {
                map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            }
        }

        for (int i = 1; i <= n; i++) {
            if (map.containsKey(i)) {
                continue;
            } else {
                return i;
            }
        }
        return n+1;
    }
}

矩阵

矩阵置0

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        Set<Integer> rols = new HashSet<>();
        Set<Integer> cols = new HashSet<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rols.add(i);
                    cols.add(j);
                }
            }
        }
        if (cols.size() == 0 || rols.size() == 0) {
            return;
        }
        for (int x : rols) {
            for (int i = 0; i < n; i++) {
                matrix[x][i] = 0;
            }
        }
        for (int y : cols) {
            for (int i = 0; i < m; i++) {
                matrix[i][y] = 0;
            }
        }
    }
}

螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;
        if (m == 0 || n == 0) return res;
        // 防止重复访问，触发向内收缩
        boolean[][] isVisited = new boolean[m][n];
        //                                 右  →     下  ↓     左  ←      上  ↑
        int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int total = m*n;
        int dIdx = 0;
        int row = 0, col = 0;
        for (int i = 0; i < total; i++) {
            res.add(matrix[row][col]);
            isVisited[row][col] = true;
            // 先计算下一步位置
            int nextRow = row + directions[dIdx][0];
            int nextCol = col + directions[dIdx][1];
            // 如果下一步越界或已访问，则顺时针转向（切换到下一个方向）
            if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || isVisited[nextRow][nextCol]) {
                dIdx = (dIdx + 1) % 4;
            }
            row += directions[dIdx][0];
            col += directions[dIdx][1];
        }
        return res;
    }
}

旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 首先转置矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 遍历对角线下方的元素
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // 再关于垂直中轴翻转
        for (int[] row : matrix) {
            for (int j = 0; j < n/2; j++) {
                //遍历左半边元素
                int temp = row[j];
                row[j] = row[n-1-j];
                row[n-1-j] = temp;
            }
        }
    }
}

搜索二维矩阵2

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        // 初始化搜索位置在右上角
        int i = 0, j = n-1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] > target) {
                j--;
            } else {
                i++;
            }
        }
        return false;
    }
}

图

岛屿数量

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 {
    // 每个橘子的上下左右四个方向
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int ans = -1;

        // 新鲜橘子个数
        int fresh = 0;
        // 存放坏橘子的位置
        List<int[]> list = new ArrayList<>();
        // 统计坏橘子的位置和好橘子的个数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    fresh++;
                }
                if (grid[i][j] == 2) {
                    list.add(new int[]{i, j});
                }
            }
        }

        while (!list.isEmpty()) {
            ans++;
            List<int[]> tmp = new ArrayList<>();
            tmp = list;
            list = new ArrayList<>();
            for (int[] pos : tmp) {
                for (int[] d : DIRECTIONS) {
                    int i = pos[0] + d[0];
                    int j = pos[1] + d[1];
                    if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1) {
                        grid[i][j] = 2;
                        fresh--;
                        list.add(new int[]{i, j});
                    }
                }
            }
        }
        if (fresh > 0) return -1;
        return Math.max(0, ans);
    }
}

回溯

全排列

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); // 撤销选择
        }
    }
}

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

class Solution {
    String[] mapping = new String[] {
            "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) {
            return res;
        }
        // 从digits[0]开始回溯
        backtrack(digits, 0);
        return res;
    }

    void backtrack(String digits, int start) {
        // 到达回溯树的底部
        if (sb.length() == digits.length()) {
            res.add(sb.toString());
            return;
        }

        // 回溯算法框架
        int digit = digits.charAt(start) - '0';
        for (char c : mapping[digit].toCharArray()) {
            // 做选择
            sb.append(c);
            // 递归下一次回溯树
            backtrack(digits, start + 1);
            // 撤销选择
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

class Solution {

    List<List<Integer>> res = new LinkedList<>();
    // 记录回溯的路径
    LinkedList<Integer> track = new LinkedList<>();
    // 记录 track 中的路径和
    int trackSum = 0;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates.length == 0) {
            return res;
        }
        backtrack(candidates, 0, target);
        return res;
    }

    // 回溯算法主函数
    void backtrack(int[] nums, int start, int target) {
        // base case，找到目标和，记录结果
        if (trackSum == target) {
            res.add(new LinkedList<>(track));
            return;
        }
        // base case，超过目标和，停止向下遍历
        if (trackSum > target) {
            return;
        }

        // 回溯算法标准框架
        for (int i = start; i < nums.length; i++) {
            // 选择 nums[i]
            trackSum += nums[i];
            track.add(nums[i]);
            // 递归遍历下一层回溯树
            // 同一元素可重复使用，注意参数
            backtrack(nums, i, target);
            // 撤销选择 nums[i]
            trackSum -= nums[i];
            track.removeLast();
        }
    }
}

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        if (n == 0) return new ArrayList<>();
        // 记录所有的合法括号组合
        List<String> res = new ArrayList<>();
        // 回溯过程中的路径
        StringBuilder track = new StringBuilder();
        // 可用的左括号和右括号初始化为n
        backtrack(n, n, track, res);
        return res;
    }

    // 可用的左括号数量为 left 个，可用的右括号数量为 right 个
    private void backtrack(int left, int right, StringBuilder track, List<String> res) {
        // 若左括号剩下的多，说明不合法
        if (right < left) return;
        // 数量小于 0 肯定是不合法的
        if (left < 0 || right < 0) return;
        // 当所有括号都恰好用完时，得到一个合法的括号组合
        if (left == 0 && right == 0) {
            res.add(track.toString());
            return;
        }

        // 尝试放一个左括号
        // 选择
        track.append('(');
        backtrack(left - 1, right, track, res);
        // 撤消选择
        track.deleteCharAt(track.length() - 1);

        // 尝试放一个右括号
        // 选择
        track.append(')');
        backtrack(left, right - 1, track, res);
        // 撤消选择
        track.deleteCharAt(track.length() - 1);
    }
}

分隔回文串

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

import java.util.*;
class Solution {
    List<List<String>> res = new LinkedList<>();
    LinkedList<String> track = new LinkedList<>();
    public List<List<String>> partition(String s) {
        backtrack(s, 0);
        return res;
    }

    // 回溯算法框架
    private void backtrack(String s, int start) {
        if (start == s.length()) {
            // 走到了叶子节点，这是一种情况。
            res.add(new ArrayList<>(track));
        }
        // 多种选择
        for (int i = start; i < s.length(); i++) {
            if (!isPalindrome(s, start, i)) {
                // s[start..i] 不是回文串
                continue;
            }
            // s[start..i]是回文串，可以进行分隔
            // 做选择，把s[start..i]放入track
            track.addLast(s.substring(start, i+1));
            // 进入回溯树的下一层，继续切分s[i+1..]
            backtrack(s, i+1);
            // 撤销选择
            track.removeLast();

        }
    }

    // 判断是否是回文串
    private boolean isPalindrome(String s, int low, int high) {
        while (low < high) {
            if (s.charAt(low) != s.charAt(high)) {
                return false;
            }
            low++;
            high--;
        }
        return true;
    }
}

栈

有效的括号

class Solution {
    public boolean isValid(String s) {
        Stack<Character>stack = new Stack<Character>();
        for(char c: s.toCharArray()){
            if(c=='(')stack.push(')');
            else if(c=='[')stack.push(']');
            else if(c=='{')stack.push('}');
            else if(stack.isEmpty()||c!=stack.pop())return false;
        }
        return stack.isEmpty();
    }
}

最小栈

import java.util.*;
class MinStack {
    Stack<Integer> stack;
    // 记录每次插入后的最小元素
    Stack<Integer> minStack;
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val < minStack.peek()) {
            // 存最小元素的栈是空的或者当前插入的值小于最小栈的栈顶元素
            minStack.push(val);
        } else {
            // 当前插入的val大于最小栈的栈顶元素
            minStack.push(minStack.peek());
        }
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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;
    }
}

柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];

        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        mono_stack.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
}

堆

数组中的第K个最大元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 最小堆，堆顶是最小元素
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int num : nums) {
            // 遍历，入堆
            pq.offer(num);
            if (pq.size() > k) {
                // 堆中元素多于k个时候，删除堆顶元素
                pq.poll();
            }
        }
        // pq中剩下的是nums中k个最大元素，堆顶那个最小，即答案。
        return pq.peek();
    }
}

前k个高频元素

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

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // key 元素 value 元素出现频率
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((entry1, entry2) -> {
            // pq 按照键值对中的值从小到大排序
            return entry1.getValue().compareTo(entry2.getValue());
        });

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            // 过一遍元素
            pq.offer(entry);
            // 如果pq尺寸超过k，则弹出堆顶的小元素
            if (pq.size() > k) {
                pq.poll();
            }
        }
        // 现在pq中剩下的就是答案的集合。
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = pq.poll().getKey();
        }
        return res;
    }
}

数据流的中位数

class MedianFinder {
    // 最小堆，存储数组中较大的那部分
    private PriorityQueue<Integer> min_heap;
    // 最大堆，存储数组中较小的那部分
    private PriorityQueue<Integer> max_heap;

    public MedianFinder() {
        min_heap = new PriorityQueue<>();
        max_heap = new PriorityQueue<>((a, b) -> {
            return b - a;
        });
    }

    public void addNum(int num) {
        if (max_heap.size() >= min_heap.size()) {
            max_heap.offer(num);
            min_heap.offer(max_heap.poll());
        } else {
            min_heap.offer(num);
            max_heap.offer(min_heap.poll());
        }
    }

    public double findMedian() {
        // 如果元素不一样多，多的那个堆的堆顶元素就是中位数。
        if (max_heap.size() > min_heap.size()) {
            return max_heap.peek();
        } else if (max_heap.size() < min_heap.size()) {
            return min_heap.peek();
        }
        // 如果元素一样多，中位数是两个堆的堆顶元素的平均数。
        return (max_heap.peek() + min_heap.peek()) / 2.0;
    }
}

贪心算法

买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        // 定义dp[i][k][0] 表示今天是第i天，剩余交易次数为k，没有持有股票所能获得的最大利润
        // dp[i][k][1]表示持有股票，且本题中交易次数k = 1

        // base case
        // dp[-1][..][0] = 0 交易未开始，不能持有股票，利润为0
        // dp[-1][..][1] = Integer.MIN_VALUE 不合法值，交易未开始，肯定不能持有股票，所以取一个取不到的最小值，便于取最大值
        // dp[..][0][0] = 0 交易开始，允许交易次数为0，利润为0
        // dp[..][0][1] = Integer.MIN_VALUE 不合法值，允许交易次数为0，不可能持有股票

        // 状态转移
        // 今天未持有股票，有两种情况，求最大值
        // 1 昨天就没有持有股票
        // 2 昨天持有股票，但是今天卖了
        // dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])

        // 今天持有股票，分两种情况，求最大值
        // 1 昨天就持有股票
        // 2 昨天没有，今天买入股票
        // dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

        // 定义dp[i][0]、dp[i][1]分别为第i天持有和未持有股票所能获得的最大利润
        // 这里省去k，因为k只为0或者1，k为0还是base case 所以k只剩1了。
        int[][] dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i-1 == -1) {
                dp[i][0] = 0;
                // dp[0][0] = Math.max(dp[-1][0], dp[-1][1] + prices[i];
                //          = Math.max(0, Integer.MIN_VALUE + prices[i]);
                //          = 0
                dp[i][1] = -prices[i];
                // dp[0][1] = Math.max(dp[-1][1], -prices[i]);
                //          = Math.max(Integer.MIN_VALUE, -price[i]);
                //          = -price[i]
                continue;
            }

            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], - prices[i]);

        }
        // 最后一天不持有股票所能获得的最大利润就是答案
        return dp[n-1][0];
    }

}

跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int farthest = 0;
        for (int i = 0; i < n-1; i++) {
            // 不断计算能跳到的最远距离
            farthest = Math.max(farthest, i + nums[i]);
            // 可能碰到了 0， 跳不动了
            if (farthest <= i) {
                return false;
            }
        }

        return farthest >= n-1;
    }
}

跳跃游戏2

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

0 <= j <= nums[i] 且 i + j < n
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int end = 0; // 当前跳跃的终点范围
        int farthest = 0; // 能够跳到的最远位置
        int res = 0; // 跳跃次数
        for (int i = 0; i < n-1; i++) {
            farthest = Math.max(nums[i] + i, farthest);
            if (end == i) { // 已经跳跃到当前要跳到的右端点
                res++;
                end = farthest; // 更新要跳跃到的右端点
            }
        }
        return res;
    }
}

划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 “ababcc” 能够被分为 [“abab”, “cc”]，但类似 [“aba”, “bcc”] 或 [“ab”, “ab”, “cc”] 的划分是非法的。

返回一个表示每个字符串片段的长度的列表。

class Solution {
    public List<Integer> partitionLabels(String s) {
        // 本质上是区间合并
        char[] chars = s.toCharArray();
        int n = chars.length;
        int[] last = new int[26]; // 记录每个字母最后一次出现的下标
        for (int i = 0; i < n; i++) {
            last[chars[i] - 'a'] = i;
        }

        List<Integer> res = new ArrayList<>();
        int start = 0; // 区间的起点
        int end = 0; // 区间的终点
        for (int i = 0; i < n; i++) {
            end = Math.max(end, last[chars[i] - 'a']); // 更新当前区间右端点的最大值
            if (end == i) { // 当前区间合并完毕
                res.add(end - start + 1); // 区间的长度
                start = end + 1; // 更新下一个区间的起点为当前区间终点+1
            }
        }

        return res;

    }
}

二分查找

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

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

class Solution {
    public int searchInsert(int[] nums, int target) {
        return lowerBound(nums, target); // 选择其中一种写法即可
    }

    // lowerBound 返回最小的满足 nums[i] >= target 的 i
    // 如果数组为空，或者所有数都 < target，则返回 nums.length
    // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]

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

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

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

搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。
• 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

你必须编写一个时间复杂度为 O(log(m * n)) 的解决方案。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (get(matrix, mid) == target) {
                return true;
            } else if (get(matrix, mid) < target) {
                left = mid + 1;
            } else if (get(matrix, mid) > target) {
                right = mid - 1;
            }
        }
        return false;
    }

    private int get(int[][] matrix, int index) {
        int m = matrix.length, n = matrix[0].length;
        int i = index / n;
        int j = index % n;
        return matrix[i][j];
    }

}

在排序数组中查找元素的第一个和最后一个位置

class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{left_bound(nums, target), right_bound(nums, target)};
    }
    // 寻找左侧边界的二分搜索，如果 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;
    }
}

搜索旋转排序数组

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

class Solution {
    public int 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) {
                return mid;
            }
            if (nums[mid] >= nums[left]) {
                // mid 落在断崖左边，此时 nums[left..mid] 有序
                if (target >= nums[left] && target < nums[mid]) {
                    // target落在[left..mid-1]中，缩小右边届
                    right = mid - 1;
                } else {
                    // target落在[mid+1..right]，缩小左边界
                    left = mid + 1;
                }
            } else {
                // mid 落在断崖右边，此时 nums[mid..right] 有序
                if (target > nums[mid] && target <= nums[right]) {
                    // target落在[mid+1..right]中，缩小左边届
                    left = mid + 1;
                } else {
                    // target落在[left..mid-1]中，做小右边界
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

寻找旋转排序数组中的最小值

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                left = mid+1;
            }
        }
        return nums[left];
    }
}

寻找两个正序数组的中位数

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        if (totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            double median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            return median;
        }
    }

    public int getKthElement(int[] nums1, int[] nums2, int k) {
        /* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
         * 这里的 "/" 表示整除
         * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
         * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
         * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
         * 这样 pivot 本身最大也只能是第 k-1 小的元素
         * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
         * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
         * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
         */

        int length1 = nums1.length, length2 = nums2.length;
        int index1 = 0, index2 = 0;
        int kthElement = 0;

        while (true) {
            // 边界情况
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }

            // 正常情况
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}

缓存淘汰策略

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<>();
    }
    // 线程安全可加synchronized
    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        makeNew(key);
        return cache.get(key);
    }
    // 线程安全可加synchronized
    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. 比较相邻的元素。如果前一个比后一个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤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]，所以冒泡排序是稳定的。

拓展：鸡尾酒排序
又称定向冒泡排序、搅拌排序等，是对冒泡排序的改进。在把最大的数往后面冒泡的同时，把最小的数也往前面冒泡，同时收缩无序区的左右边界，有序区在序列左右逐渐累积。

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)趟简单选择排序得到有序结果。具体算法描述如下：

1. 初始状态：无序区为R[1..n]，有序区为空；
2. 第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个的新无序区；
3. (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(原地算法)在数组上实现。具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素(已排序)大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤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-路归并。

算法描述

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

// 归并排序
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)
• 稳定性：归并排序是稳定的。

快速排序

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

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

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

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

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

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

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

   挖坑法：
4. 定义两个指针 left 指向起始位置，right 指向最后一个元素的位置，然后指定一个基准 key(right)，作为坑。
5. 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 指针指向白色部分(未知部分)的第一个数，即下一个要判断大小的位置。

算法思路：

1. 由于最初红色和蓝色区域没有元素，初始化 less = left – 1，more = right + 1，cur = left。整个区间为未知部分(白色)。
2. 如果当前 array[cur] < v，则 swap(array,++less,cur++)，即把红色区域向右扩大一格(less指针后移)，把 array[cur] 交换到该位置，cur 指针前移判断下一个数。
3. 如果当前 array[cur] = v，则不必交换，直接 cur++
4. 如果当前 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]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的关系，在当前无序区中选择关键字最大(最小)的元素。

算法描述

1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
3. 由于交换后新的堆顶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)。
• 稳定性：堆排序是不稳定的。

计数排序

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

算法描述

1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中每个值为 i 的元素出现的次数，存入数组C的第i项；
3. 对所有的计数累加(从C中的第一个元素开始，每一项和前一项相加)；
4. 反向填充目标数组：将每个元素 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。

算法描述

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

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)。
• 稳定性：桶排序是稳定的。

基数排序

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

算法描述

1. 取得数组中的最大数，并取得位数；
2. array 为原始数组，从最低位开始取每个位组成 radix 数组；
3. 对 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)。
• 稳定性：基数排序是稳定的。

两数之和

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

字母异位词

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 用一个map存储每组字母异位词，key为排序后的异位词，value为异位词结果列表
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String key = new String(charArray);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }

        return new ArrayList<List<String>>(map.values());
    }
}

最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

class Solution {
    public int longestConsecutive(int[] nums) {
        // 先把nums转换为set
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int res = 0;
        for (int x : set) {
            // 如果不是序列起点，则跳过
            if (set.contains(x-1)) {
                continue;
            }
            // 如果是序列起点，则计算连续序列终点
            int y = x + 1;
            while (set.contains(y)) {
                y++;
            }
            // 更新结果，由于while循环缘故，序列终点为y-1，序列长度为 (y-1) - x + 1 = y - x
            res = Math.max(res, y - x);
        }

        return res;
    }
}

和为K的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int res = 0;
        // 前缀和数组
        int[] pre = new int[n+1];
        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i-1] + nums[i-1];
            for (int j = 1; j <= i; j++) {
                if (pre[i] - pre[j-1] == k) {
                    res++;
                }
            }
        }
        return res;
    }
}

颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        if (n == 1) return ;
        int current = 0;
        for (int i = 1; i < n; i++) {
            current = nums[i];
            int pre = i - 1;
            while (pre >= 0 && current <= nums[pre]) { // 注意，这里的 pre 必须在前面，要不会报错
                nums[pre + 1] = nums[pre];
                pre--;
            }
            nums[pre + 1] = current;
        }
        return ;
    }
}

下一个排列

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        // 从后向前找到i，满足nums[i] < nums[i+1]
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        if (i >= 0) {
            int j = nums.length - 1;
            // 从后向前找到j，满足nums[j] > nums[i];
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            // 交换nums[i]和nums[j]
            swap(nums, i, j);
        }
        
        reverse(nums, i + 1);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        slow = nums[slow];
        fast = nums[nums[fast]];
        while(slow != fast){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        int pre1 = 0;
        int pre2 = slow;
        while(pre1 != pre2){
            pre1 = nums[pre1];
            pre2 = nums[pre2];
        }
        return pre1;
    }
}

单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

class Solution {
    boolean found = false;
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, word, 0);
                if (found) {
                    return true;
                }
            }
        }
        return false;
    }

    // 从(i, j)开始向四周匹配，视图匹配word[p..]
    private void dfs(char[][] board, int i, int j, String word, int p) {
        // 整个word已经被匹配完，找到一个答案
        if (p == word.length()) {
            found = true;
            return ;
        }
        if (found) {
            return ;
        }
        int m = board.length;
        int n = board[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n) {
            return ;
        }
        if (board[i][j] != word.charAt(p)) {
            return ;
        }
        // 已经匹配过的字符串，添加一个负号作为标记，避免走回头路
        board[i][j] = (char)(-board[i][j]);
        // word[p]被board[i][j]，开始搜索word[p+1..]
        dfs(board, i, j+1, word, p+1);
        dfs(board, i+1, j, word, p+1);
        dfs(board, i-1, j, word, p+1);
        dfs(board, i, j-1, word, p+1);
        // 将该单元格恢复成其原来的值。因为DFS的搜索路径是回溯的，在探索完一个路径之后，必须将路径上“被标记过的”单元格恢复成初始状态，以便继续探索其他可能的路径。
        board[i][j] = (char)(-board[i][j]);

    }
}

杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        if (numRows == 0) return res;

        List<Integer> row1 = new ArrayList<>();
        row1.add(1);
        List<Integer> row2 = new ArrayList<>();
        row2.add(1);
        row2.add(1);
        for (int i = 1; i <= numRows; i++) {
            if (i == 1) {
                res.add(row1);
            } else if (i == 2) {
                res.add(row2);
            } else {
                List<Integer> prevRow = res.get(res.size() - 1);
                List<Integer> curRow = new ArrayList<>();
                curRow.add(1);
                for (int j = 0; j < prevRow.size() - 1; j++) {
                    curRow.add(prevRow.get(j) + prevRow.get(j+1));
                }
                curRow.add(1);
                res.add(curRow);
            }
        }
        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;
}

前缀树(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 {
    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都是正整数。
解题思路：

1. 定义状态：dp[j] 表示在总价值上限为 j 的情况下，能够选取的金币的最大总和。
2. 状态转移方程：
   • 选第 i 枚金币：dp[j] = dp[j]
   • 如果选第 i 枚金币（且 j >= value[i]）：dp[j] = max(dp[j], dp[j - value[i]] + value[i])
3. 初始化：
   • dp[0] = 0 表示价值上限为 0 时，选取的总价值为 0。
   • 其余 dp[j] 初始为 0（未选任何金币时）。
4. 目标：有金币和价值上限，计算出 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]);
    }
}

课程表

你这个学期必须选修 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()][]);
    }
}

分组使每组恰好有k个相同元素

输入为一个数组与一个数字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;
    }
}

组合最大的时间

给6个数字，组合最大的24进制的时间。比如201456组合就是21:56:40

public class Solution {
    static String maxTime = ""; // 用于存储最大时间

    public static void main(String[] args) {
        int[] digits = {2, 0, 1, 4, 5, 6}; // 输入数字
        boolean[] used = new boolean[digits.length]; // 标记是否使用
        dfs(digits, used, "", 0); // 开始DFS
        System.out.println(maxTime.isEmpty() ? "No valid time" : maxTime);
    }
    public static void dfs(int[] digits, boolean[] used, String current, int depth) {
        if (depth == 6) { // 时间完整
            String hh = current.substring(0, 2);
            String mm = current.substring(2, 4);
            String ss = current.substring(4, 6);
            if (isValidTime(hh, mm, ss)) {
                String time = hh + ":" + mm + ":" + ss;
                if (maxTime.isEmpty() || time.compareTo(maxTime) > 0) {
                    maxTime = time; // 更新最大时间
                }
            }
            return;
        }
        for (int i = 0; i < digits.length; i++) {
            if (used[i])
                continue; // 跳过已使用的数字
            used[i] = true; // 标记为已使用
            dfs(digits, used, current + digits[i], depth + 1); // 递归构建
            used[i] = false; // 回溯
        }
    }
    private static boolean isValidTime(String hh, String mm, String ss) {
        int hours = Integer.parseInt(hh);
        int minutes = Integer.parseInt(mm);
        int seconds = Integer.parseInt(ss);
        return hours < 24 && minutes < 60 && seconds < 60;
    }
}

递归删除文件夹

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

判断是否是回文串

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

• 插入一些初始数据

  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的记录被事务1锁定。
2. 事务2 先更新用户2的记录，此时用户2的记录被事务2锁定。
3. 事务1 尝试更新用户2的记录，但用户2的记录已被事务2锁定，所以事务1进入等待状态。
4. 事务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();
    }
}

手写线程池

1. 线程池的基本组成部分
   • 任务队列：存储提交的任务。
   • 工作线程：从任务队列中取出任务并执行。
   • 线程池管理类：负责管理线程和任务的调度。
2. 设计关键点
   • 使用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);

设计模式

单例模式

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

• 饿汉式：饿汉式单例模式在类加载时就完成实例化，线程安全，简单但可能会造成资源浪费。
• 懒汉式：懒汉式单例模式在第一次调用 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();
    }
}

策略模式

定义一系列算法，将每个算法封装起来，并使它们可以互相替换。策略模式让算法的变化独立于使用算法的客户端。消除条件分支

// ===================== 1. 策略接口 =====================
public interface SignTaskStrategy {
    String getType();
    String createSignTask(String params);
}

// ===================== 2. 具体策略实现 =====================
@Component
public class AliSignTaskStrategy implements SignTaskStrategy {
    @Override
    public String getType() { return "ALI"; }

    @Override
    public String createSignTask(String params) {
        return "阿里签署任务: " + params;
    }
}

@Component
public class OverseaSignTaskStrategy implements SignTaskStrategy {
    @Override
    public String getType() { return "OVERSEA"; }

    @Override
    public String createSignTask(String params) {
        return "海外签署任务: " + params;
    }
}

// ===================== 3. 策略工厂（核心） =====================
@Component
public class SignTaskStrategyFactory {

    // Spring 自动注入所有实现类，key = Bean 名称
    // 也可以用 List<SignTaskStrategy> 注入后手动构建 Map
    private final Map<String, SignTaskStrategy> strategyMap;

    @PostConstruct
    public SignTaskStrategyFactory(List<SignTaskStrategy> strategies) {
        this.strategyMap = strategies.stream()
            .collect(Collectors.toMap(SignTaskStrategy::getType, s -> s));
    }

    public SignTaskStrategy getStrategy(String type) {
        SignTaskStrategy strategy = strategyMap.get(type);
        if (strategy == null) {
            throw new IllegalArgumentException("未知策略类型: " + type);
        }
        return strategy;
    }
}

// ===================== 4. 调用方 =====================
@Service
public class SignTaskService {

    @Autowired
    private SignTaskStrategyFactory factory;

    public String execute(String type, String params) {
        return factory.getStrategy(type).createSignTask(params);
    }
}

观察者模式

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

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

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

空间复杂度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
    }
}

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

1. 判断符号位：补码表示中，最高位是符号位。0 表示正数，1 表示负数。
2. 处理正数：如果符号位是 0，直接将剩余位的二进制部分转为十进制。
3. 处理负数：如果符号位是 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;
       }
   }