1 - 链表

1.1 反转链表 - easy

迭代法：使用三个指针，分别指向当前节点、前一个节点和后一个节点，逐个翻转节点的指向。

public class Solution {
    public ListNode ReverseList (ListNode head) {
        ListNode a = null;
        ListNode b = head;

        while(b != null) {
            ListNode c = b.next;
            b.next = a;
            a = b;
            b = c;
        }
        return a;
    }
}

1.4 合并两个排序的链表 - easy

双指针法：创建一个哑节点作为头节点，使用两个指针分别指向当前节点，比较节点值，将较小的节点加到新链表中，并移动指针。

• 时间复杂度为 O(n+m)，空间复杂度为 O(1)

public class Solution {
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val < pHead2.val) {
                tail.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                tail.next = pHead2;
                pHead2 = pHead2.next;
            }
            tail = tail.next;
        }
        tail.next = (pHead1 != null) ? pHead1 : pHead2;

        return dummy.next;
    }
}

1.7 链表中环的入口结点

可以使用双指针法，fast 每次移动两个节点，slow 每次移动一个节点，如果它们在途中相遇 ，说明这个链表有环。

如图，slow 走了 x + y 步，则 fast 走了 (x + y) * 2 步，所以 (x + y) * 2 = x + y + n * (y + z)，令 n = 1解得 x = z。

public ListNode EntryNodeOfLoop(ListNode pHead) {
    if (pHead == null) return null;
    ListNode slow = pHead;
    ListNode fast = pHead;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            ListNode entry = pHead;
            while (entry != slow) {
                entry = entry.next;
                slow = slow.next;
            }
            return entry;
        }
    }
    return null;
}

1.8 链表中倒数最后k个结点 - easy

快慢指针法：先让快指针走k步，然后快慢指针一起走，直到快指针到达链表末尾，此时慢指针即为倒数第k个节点。

• 时间复杂度为 O(n)，空间复杂度为 O(1)

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode slow = pHead;
        ListNode fast = pHead;

        for (int i = 0; i < k; i++) {
            if (fast == null) return null;
            fast = fast.next;
        }

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

1.10 两个链表的第一个公共结点 - easy

双指针法：同时遍历这两个链表，每次移动一个节点。如果在 ptr1 到达了链表 A 的末尾，将其重新指向链表 B 的头节点。

同样，如果 ptr2 到达了链表 B 的末尾，将其重新指向链表 A 的头节点。直到两个指针相遇，相遇点就是第一个公共节点。

• 时间复杂度为 O(n)，空间复杂度为 O(1)

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode a = pHead1;
        ListNode b = pHead2;

        while (a != b) {
            a = (a == null) ? pHead2 : a.next;
            b = (b == null) ? pHead1 : b.next;
        }
        return a;
    }
}

1.11 链表相加（二） - medium

递归法：首先让指针指向相同位置的节点。然后递归地将相同位置的节点值相加，并考虑进位。最后处理进位和剩余的节点。

• 时间复杂度为 O(max(n, m))，空间复杂度为 O(max(n, m))

public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
        if (head1 == null) return head2;
        if (head2 == null) return head1;
        
        head1 = reverseList(head1);     // 1.1 反转链表，略
        head2 = reverseList(head2);

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        int carry = 0;

        while (head1 != null || head2 != null) {
            int x = (head1 != null) ? head1.val : 0;
            int y = (head2 != null) ? head2.val : 0;
            int sum = x + y + carry;
            carry = sum / 10;
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
            if (head1 != null) head1 = head1.next;
            if (head2 != null) head2 = head2.next;
        }
        return reverseList(dummy.next);
    }
}

1.12 单链表的排序 - medium

归并排序：将链表分成两半，递归地对每一半进行排序，然后合并两个已排序的链表。

• 时间复杂度为 O(nlogn)，空间复杂度为 O(1)

public class Solution {
    public ListNode sortInList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode left = head;
        ListNode mid = head.next;
        ListNode right = head.next.next;

        // right 指针指向右段的末尾节点，mid 指针指向中间节点
        while (right != null && right.next != null) {
            left = left.next;
            mid = mid.next;
            right = right.next.next;
        }   
        // left 指针指向左段的末尾节点，从这里断开
        left.next = null;

        // 1.4 合并两个排序的链表，略
        return merge(sortInList(head), sortInList(mid));
    }
}

2 - 二分查找、排序

2.1 二分查找 - easy

双指针法：通过比较数组中间元素与目标值，根据比较结果调整搜索范围，直到找到目标值或搜索范围为空。

public class Solution {
    public int search (int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;

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

2.3 寻找峰值 - median

二分查找：利用数组的特性，通过比较中间元素与相邻元素，确定峰值所在的区间，然后继续在该区间内查找。

public class Solution {
    public int findPeakElement (int[] nums) {
        if (nums.length == 1) return 0;

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

2.4 数组中的逆序对 - median

归并排序：提供了一种优雅且高效的方式来统计逆序对，在归并的过程中统计逆序对的数量。

• 时间复杂度为 O(nlogn)，空间复杂度为 O(n)

public class Solution {
    private long count = 0;

    public int InversePairs (int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return (int) (count % 1000000007);
    }

    private void mergeSort(int[] nums, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            merge(nums, left, mid, right);
        }
    }

    private void merge(int[] nums, int left, int mid, int right) {
        // temp 数组用于保存合并后的有序结果
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {
            if (nums[i] > nums[j]) {
                // nums[i] 右侧的所有元素与 nums[j] 形成逆序对
                count += (mid - i + 1);
                temp[k++] = nums[j++];
            } else {
                temp[k++] = nums[i++];
            }
        }
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= right) temp[k++] = nums[j++];

        for (int r = left; r <= right; r++) {
            nums[r] = temp[r - left];
        }
    }
}

2.5 旋转数组的最小数字 - easy

二分查找：通过比较中间元素与首尾元素，确定最小值所在的区间，然后继续在该区间内查找。

• 时间复杂度为 O(logn)，空间复杂度为 O(1)

public class Solution {
    public int minNumberInRotateArray (int[] nums) {
        if (nums.length == 1) return nums[0];

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

2.6 比较版本号 - median

逐个比较：逐个字符比较版本号，遇到 '.' 时分隔出一个修订号进行比较。

• 时间复杂度为 O(n + m)，其中 n 和 m 分别是两个版本号的长度

public class Solution {
    public int compare (String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        int maxLen = Math.max(v1.length, v2.length);

        for (int i = 0; i < maxLen; i++) {
            int x = (i < v1.length) ? Integer.parseInt(v1[i]) : 0;
            int y = (i < v2.length) ? Integer.parseInt(v2[i]) : 0;
            if (x < y) {
                return -1;
            } else if (x > y){
                return 1;
            }
        }
        return 0;
    }
}

3 - 二叉树

3.1 二叉树的前序遍历 - easy

递归法：前序遍历的顺序是 “根左右”。可以定义一个递归函数，首先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。

public class Solution {
    public int[] preorderTraversal (TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorder(root, result);
        
        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            res[i] = result.get(i);
        }
        return res;
    }

    private void preorder(TreeNode node, List<Integer> result) {
        if (node == null) return;
        result.add(node.val);
        preorder(node.left, result);
        preorder(node.right, result);
    }
}

3.2 二叉树的中序遍历 - easy

递归法：中序遍历的顺序是 “左根右”。可以定义一个递归函数，首先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。

public class Solution {
    public int[] inorderTraversal (TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        
        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            res[i] = result.get(i);
        }
        return res;
    }

    private void inorder(TreeNode node, List<Integer> result) {
        if (node == null) return;
        inorder(node.left, result);
        result.add(node.val);
        inorder(node.right, result);
    }
}

3.3 二叉树的后序遍历 - easy

递归法：后序遍历的顺序是 “左右根”。可以定义一个递归函数，首先递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。

public class Solution {
    public int[] postorderTraversal (TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorder(root, result);
        
        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            res[i] = result.get(i);
        }
        return res;
    }

    private void postorder(TreeNode node, List<Integer> result) {
        if (node == null) return;
        postorder(node.left, result);
        postorder(node.right, result);
        result.add(node.val);
    }
}

3.6 二叉树的最大深度 - easy

递归法：深度优先搜索（DFS），递归地计算左右子树的最大深度，然后取两者的最大值加 1（当前节点）。

public class Solution {
    public int maxDepth (TreeNode root) {
        if (root == null) return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

3.8 二叉搜索树与双向链表

3.10 合并二叉树 - easy

递归法：前序遍历两棵树，对于每个节点，如果两棵树都有对应的节点，则将它们的值相加并创建一个新的节点；

如果只有一棵树有节点，则直接使用那个节点；如果两棵树都没有节点，则返回空。

public class Solution {
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        
        TreeNode node = new TreeNode(t1.val + t2.val);
        node.left = mergeTrees(t1.left, t2.left);
        node.right = mergeTrees(t1.right, t2.right);
        return node;
    }
}

4 - 堆、栈、队列

4.1 用两个栈实现队列 - easy

一个栈用于入队操作，另一个栈用于出队操作。当出队时，如果出队栈为空，将入队栈的所有元素移动到出队栈中。

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

4.2 包含min函数的栈 - easy

使用两个栈，一个存储所有元素，另一个辅助栈存储当前的最小值。

每次push操作时，将新元素与辅助栈顶部元素比较，更新辅助栈。pop和min操作分别对应两个栈的相应操作。

public class Solution {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    public void push(int node) {
        if (minStack.isEmpty() || node <= minStack.peek()) {
            minStack.push(node);
        }
        stack.push(node);
    }

    public void pop() {
        if (stack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        return minStack.peek();
    }
}

4.3 有效括号序列 - easy

使用一个栈存储右括号。遍历字符串，左括号时压栈，右括号时匹配栈顶元素。最后检查栈是否为空，空则有效，非空则无效。

public class Solution {
    public boolean isValid (String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');

        for (char c : s.toCharArray()) {
            if (map.containsKey(c)) {
                if (stack.isEmpty() || stack.pop() != map.get(c)) {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

4.4 滑动窗口的最大值 - hard

使用双指针定义窗口，结合双端队列存储窗口内的最大值。随着窗口的滑动，更新双端队列以保持最大值在队列头部。

public class Solution {
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        ArrayList<Integer> result = new ArrayList<>();
        if (size == 0 || size > num.length) return result;
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < num.length; i++) {
            // 移除比当前元素小的元素
            while (!deque.isEmpty() && num[i] > num[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offer(i);
            // 维护窗口大小 [i - size + 1, i]
            if (deque.peek() < i - size + 1) {
                deque.poll();
            }
            // 窗口大小到达要求时，添加最大值
            if (i >= size - 1) {
                result.add(num[deque.peek()]);
            }
        }
        return result;
    }
}

4.5 最小的 K 个数 - medium

使用最大堆，维护数组中最小的K个数。遍历数组，将元素与堆顶比较，必要时替换堆顶并调整堆。

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>((x, y) -> y - x);
        ArrayList<Integer> result = new ArrayList<>();
        if (k == 0) return result;

        for (int i = 0; i < input.length; i++) {
            q.offer(input[i]);
            if (q.size() > k) {
                q.poll();
            }
        }
        for (int i = 0; i < k; i++) {
            result.add(q.poll());
        }
        return result;
    }
}

4.7 数据流中的中位数 - medium

一个最大堆存储较小一半的元素，一个最小堆存储较大一半的元素。根据元素数量的奇偶性，调整两个堆的大小，并计算中位数。

import java.util.*;

public class Solution {
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    public void Insert(Integer num) {
        if (maxHeap.isEmpty() || num < maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }
        if (maxHeap.size() > minHeap.size() + 1) {      // 保持两个堆的平衡，确保最大堆的大小最多只比最小堆大1
            minHeap.offer(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public Double GetMedian() {
        if (maxHeap.size() > minHeap.size()) {          // 如果最大堆的元素个数多，中位数就是最大堆的堆顶
            return (double) maxHeap.peek();
        } else {                                        // 如果最小堆的元素个数多，中位数是两个堆顶的平均值
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }
}

5 - 哈希、贪心

5.2 数组中出现次数超过一半的数字 - easy

使用哈希表来记录每个数字出现的次数，然后遍历哈希表找到出现次数超过一半的数字。

public class Solution {
    public int MoreThanHalfNum_Solution (int[] numbers) {
        HashMap<Integer, Integer> map = new HashMap<>();
        
        for (int num : numbers) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        for (int num : numbers) {
            if (map.get(num) > numbers.length / 2) {
                return num;
            }
        }
        return 0;
    }
}

5.3 数组中只出现一次的两个数字 - medium

使用哈希表记录每个数字出现的次数，然后找到出现次数为1的两个数字。

public class Solution {
    public int[] FindNumsAppearOnce (int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        List<Integer> result = new ArrayList<>();

        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (int num : nums) {
            if (map.get(num) == 1) {
                result.add(num);
            }
        }
        if (result.get(0) < result.get(1)) {
            return new int[] {result.get(0), result.get(1)};
        } else {
            return new int[] {result.get(1), result.get(0)};
        }
    }
}

5.4 缺失的第一个正整数 - medium

使用哈希表记录数组中所有数字的出现，然后从1开始依次枚举正整数，并判断其是否在哈希表中。

public class Solution {
    public int minNumberDisappeared(int[] nums) {
        Set<Integer> set = new HashSet<>();

        // 将数组中的所有数字加入哈希表
        for (int num : nums) {
            set.add(num);
        }
        // 枚举正整数，查找缺失的第一个正整数
        for (int i = 1; i <= nums.length; i++) {
            if (!set.contains(i)) {
                return i;
            }
        }
        // 如果所有从1到n的正整数都存在，那么缺失的数就是n+1
        return nums.length + 1;
    }
}

6 - 递归、回溯

6.1 没有重复项的全排列 - medium

回溯法：使用一个数组来存储当前的排列，然后递归地尝试数字，如果该数字没有被使用过，就添加到排列中，并继续递归。

如果当前排列的长度等于数组的长度，则将其添加到结果中。然后回溯，移除最后一个添加的数字，尝试下一个数字。

public class Solution {
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        backtrack(new ArrayList<>(), num);
        return result;
    }

    private void backtrack(ArrayList<Integer> res, int[] num) {
        if (res.size() == num.length) {
            result.add(new ArrayList<>(res));
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (res.contains(num[i])) continue;
            res.add(num[i]);
            backtrack(res, num);
            res.remove(res.size() - 1);
        }
    }
}

6.2 有重复项的全排列 - medium

回溯法：这个问题与没有重复项的全排列类似。在递归之前，对数组进行排序，并且在递归中添加一个判断，

如果当前数字与前一个数字相同，并且前一个数字已经被使用过，则跳过当前数字，以避免重复的排列。

public class Solution {
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        Arrays.sort(num);
        backtrack(new ArrayList<>(), num, new boolean[num.length]);
        return result;
    }

    private void backtrack(ArrayList<Integer> res, int[] num, boolean[] used) {
        if (res.size() == num.length) {
            result.add(new ArrayList<>(res));
            return;
        }

        for (int i = 0; i < num.length; i++) {
            if (used[i]) continue;
            if (i > 0 && num[i] == num[i - 1] && !used[i - 1]) continue;
            res.add(num[i]);
            used[i] = true;
            backtrack(res, num, used);
            res.remove(res.size() - 1);
            used[i] = false;
        }
    }
}

6.3 岛屿数量 - medium

深度优先搜索（DFS）：遍历每一个单元格，如果是岛屿的一部分，则使用DFS来标记所有相连的岛屿单元格，同时计数器加一。

public class Solution {
    public int solve (char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(i, j, grid);
                    count++;
                }
            }
        }
        return count;
    }

    private void dfs(int x, int y, char[][] grid) {
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) return;
        if (grid[x][y] == '0') return;

        grid[x][y] = '0';
        dfs(x + 1, y, grid);
        dfs(x - 1, y, grid);
        dfs(x, y + 1, grid);
        dfs(x, y - 1, grid);
    }
}

6.4 字符串的排列 - medium

回溯法：使用一个字符串来存储当前的排列，然后递归地尝试字符，如果该字符没有被使用过，就添加到当前排列中，并继续递归。

如果当前排列的长度等于原始字符串的长度，则将其添加到结果中。然后回溯，移除最后一个添加的字符，尝试下一个字符。

public class Solution {
    ArrayList<String> result = new ArrayList<>();

    public ArrayList<String> Permutation(String str) {
        char[] charStr = str.toCharArray();
        Arrays.sort(charStr);
        backtrack(new StringBuffer(), charStr, new boolean[charStr.length]);
        return result;
    }

    private void backtrack(StringBuffer res, char[] str, boolean[] used) {
        if (res.length() == str.length) {
            result.add(res.toString());
            return;
        }
        for (int i = 0; i < str.length; i++) {
            if (used[i]) continue;
            if (i > 0 && str[i] == str[i - 1] && !used[i - 1]) continue;
            
            res.append(str[i]);
            used[i] = true;
            backtrack(res, str, used);
            res.deleteCharAt(res.length() - 1);
            used[i] = false;
        }
    }
}

6.6 括号生成 - medium

回溯法：使用一个字符串来存储当前的括号组合，然后递归地尝试添加左括号或右括号。

如果左括号的数量大于右括号，就添加一个左括号；反正亦然。如果相等，说明找到了一个有效的括号组合，则添加到结果中。

public class Solution {
    ArrayList<String> result = new ArrayList<>();

    public ArrayList<String> generateParenthesis (int n) {
        backtrack("", n, 0, 0);
        return result;
    }

    private void backtrack(String res, int n, int x, int y) {
        if (res.length() == n * 2) {
            result.add(res);
            return;
        }
        if (x < n) backtrack(res + '(', n, x + 1, y);
        if (y < x) backtrack(res + ')', n, x, y + 1);
    }
}

7 - 动态规划

7.1 斐波那契数列

题目已经把递推公式直接给我们了，即状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]

public int Fibonacci (int n) {
    // write code here
    if(n == 1 || n == 2) return 1;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

7.2 跳台阶

① 确定含义：爬到第 i 层楼梯，有 dp[i] 种方法；② 递推公式： dp[i] = dp[i - 1] + dp[i - 2]；

③ 初始化：dp[1] = 1，dp[2] = 2；④ 遍历顺序：从前往后

public int jumpFloor (int n) {
    if(n == 1) return 1;
    
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for(int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

7.3 最小花费爬楼梯 - easy

状态转移方程：将问题分解为子问题，即到达第 i 个台阶的最小花费，可以通过第 i-1 个台阶或第 i-2 个台阶到达。

public class Solution {
    public int minCostClimbingStairs (int[] cost) {
        int[] dp = new int[cost.length + 1];

        for (int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }
}

7.4 最长公共子序列（二）- medium

状态转移方程：构建一个二维数组，dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的最长公共子序列长度。

public class Solution {
    public String LCS (String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                sb.insert(0, s1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        return sb.toString().isEmpty() ? "-1" : sb.toString();
    }
}

7.5 最长公共子串 - medium

状态转移方程：与最长公共子序列类似，但是要求子串必须是连续的。

public class Solution {
    public String LCS (String str1, String str2) {
        int m = str1.length(), n = str2.length();
        int len = 0, end = 0;
        int[][] dp = new int[m + 1][n + 1];
        
        // 1. 遍历两个字符串，填充 dp 数组
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > len) {
                        len = dp[i][j];
                        end = i;
                    }
                }
            }
        }
        // 2. 根据结束索引和最长长度，截取最长公共子串
        return str1.substring(end - len, end);
    }
}

7.7 矩阵的最小路径和 - medium

最优问题：使用一个与原矩阵同样大小的 dp 数组，dp[i][j] 表示到达矩阵 (i,j) 位置的最小路径和。

public class Solution {
    public int minPathSum (int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = matrix[0][0];

        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + matrix[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], dp[i][j - 1]) + matrix[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
}

7.10 最长上升子序列（一）- medium

优化问题：使用二分查找来优化查找下一个更大元素的过程，从而减少时间复杂度。

public class Solution {
    public int LIS (int[] arr) {
        if (arr.length == 0) return 0;
        int[] dp = new int[arr.length];
        Arrays.fill(dp, 1);

        int maxLen = 1;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}

7.17 打家劫舍（一）- medium

边界问题：构建状态转移方程，dp[i] 表示到第 i 家时的最大抢劫金额，需要考虑是否抢劫当前家，以及是否抢劫前一家。

public class Solution {
    public int rob (int[] nums) {
        int[] dp = new int[nums.length + 1];
        dp[1] = nums[0];

        // 前 i - 1 个房子最多能偷到的金额 dp[i - 1]
        // 前 i - 2 个房子最多能偷到的金额 dp[i - 2]
        // 第 i 个房子的金额 nums[i - 1]
        
        for (int i = 2; i <= nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[nums.length];
    }
}

8 - 字符串、双指针

8.1 字符串变形 - medium

StringBuilder：首先对每个字符进行大小写转换，然后翻转整个字符串，接着以空格为界，对每个单词进行二次翻转，最终返回。

public class Solution {
    public String trans (String s, int n) {
        if (n == 1) return s;
        StringBuilder sb = new StringBuilder();

        for (char c : s.toCharArray()) {
            if (c <= 'Z' && c >= 'A') {
                sb.append((char)(c - 'A' + 'a'));
            } else if (c >= 'a' && c <= 'z') {
                sb.append((char)(c - 'a' + 'A'));
            } else {
                sb.append(c);
            }
        }
        sb.reverse();
        for (int i = 0; i < n; i++) {
            int j = i;
            while (j < n && sb.charAt(j) != ' ') j++;
            StringBuilder str = new StringBuilder(sb.substring(i, j));
            sb.replace(i, j, str.reverse().toString());
            i = j;
        } 
        return sb.toString();
    }
}

8.2 最长公共前缀 - easy

纵向扫描：将字符串数组看作一个二维空间。每一次从第一列开始确定字符，逐层扫描后面每一列，遇到不同字符停止扫描。

public class Solution {
    public String longestCommonPrefix (String[] strs) {
        if (strs.length == 0) return "";
        int m = strs.length, n = strs[0].length();

        for (int i = 0; i < n; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < m; j++) {
                if (i >= strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

8.9 反转字符串 - easy

双指针法：通过双指针从两端向中间遍历，交换字符来实现。

public class Solution {
    public String solve (String str) {
        char[] chars = str.toCharArray();
        int left = 0, right = chars.length - 1;

        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
        return new String(chars);
    }
}

8.10 最长无重复子数组 - medium

滑动窗口：通过维护一个窗口来不断更新最长无重复子数组的长度。

public class Solution {
    public int maxLength (int[] arr) {
        int n = arr.length;
        if (n == 0 || n == 1) return n;
        Map<Integer, Integer> map = new HashMap<>();

        int maxLen = 0, left = 0;
        for (int right = 0; right < n; right++) {
            int num = arr[right];
            if (map.containsKey(num)) {
                left = Math.max(left, map.get(num) + 1);
            }
            map.put(num, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

8.11 盛水最多的容器 - medium

双指针法：通过维护两个指针来遍历数组，计算在不同位置的 “雨水” 量。

public class Solution {
    public int maxArea (int[] height) {
        int maxArea = 0, left = 0, right = height.length - 1;
        
        while (left < right) {
            int h1 = height[left], h2 = height[right];
            int area = Math.min(h1, h2) * (right - left);
            maxArea = Math.max(maxArea, area);
            
            if (h1 < h2) left++;
            else right--;
        }
        return maxArea;
    }
}

9 - 模拟

9.3 顺时针旋转矩阵 - medium

通过交换矩阵的上三角和下三角元素，将矩阵转置。然后对每一行的元素进行左右翻转。

public class Solution {
    public int[][] rotateMatrix (int[][] mat, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int temp = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = mat[i][j];
                mat[i][j] = mat[i][n - j - 1];
                mat[i][n - j - 1] = temp;
            }
        }
        return mat;
    }
}

9.4 设计 LRU 缓存结构 - hard

使用 HashMap 来存储缓存的键值对，它会按照访问顺序排序，方便快速定位最近访问的元素。

使用 LinkedHashSet 来存储缓存的键，它的元素有序，且不重复，可以快速定位最老的元素。

public class Solution {
    private int capacity;
    Map<Integer, Integer> map = new HashMap<>();
    Set<Integer> set = new LinkedHashSet<>();

    public Solution(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            set.remove(key);                // 更新 Set，保证最近使用的元素在末尾
            set.add(key);
            return map.get(key);
        }
        return -1;
    }
    public void set(int key, int value) {
        if (!map.containsKey(key) && map.size() == capacity) {  // 如果缓存已满，则移除最老的元素
            int oldestKey = set.iterator().next();
            map.remove(oldestKey);
            set.remove(oldestKey);
        }
        map.put(key, value);                // 新增或更新 Map
        set.add(key);                       // 新增 Set
    }
}