1 - 鏈表

1.1 反轉(zhuǎn)鏈表 - easy

迭代法：使用三個指針，分別指向當前節(jié)點、前一個節(jié)點和后一個節(jié)點月劈，逐個翻轉(zhuǎn)節(jié)點的指向越除。

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

雙指針法：創(chuàng)建一個啞節(jié)點作為頭節(jié)點，使用兩個指針分別指向當前節(jié)點态辛，比較節(jié)點值麸澜，將較小的節(jié)點加到新鏈表中，并移動指針奏黑。

• 時間復雜度為 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 鏈表中環(huán)的入口結(jié)點

可以使用雙指針法编矾，fast 每次移動兩個節(jié)點，slow 每次移動一個節(jié)點馁害，如果它們在途中相遇 窄俏，說明這個鏈表有環(huán)。

如圖碘菜，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 鏈表中倒數(shù)最后k個結(jié)點 - easy

快慢指針法：先讓快指針走k步，然后快慢指針一起走计雌，直到快指針到達鏈表末尾缎岗，此時慢指針即為倒數(shù)第k個節(jié)點。

• 時間復雜度為 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 兩個鏈表的第一個公共結(jié)點 - easy

雙指針法：同時遍歷這兩個鏈表传泊，每次移動一個節(jié)點。如果在 ptr1 到達了鏈表 A 的末尾鸭巴，將其重新指向鏈表 B 的頭節(jié)點眷细。

同樣，如果 ptr2 到達了鏈表 B 的末尾鹃祖，將其重新指向鏈表 A 的頭節(jié)點溪椎。直到兩個指針相遇，相遇點就是第一個公共節(jié)點恬口。

• 時間復雜度為 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

遞歸法：首先讓指針指向相同位置的節(jié)點。然后遞歸地將相同位置的節(jié)點值相加祖能，并考慮進位歉秫。最后處理進位和剩余的節(jié)點。

• 時間復雜度為 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 反轉(zhuǎn)鏈表雁芙，略
        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 指針指向右段的末尾節(jié)點鳞滨，mid 指針指向中間節(jié)點
        while (right != null && right.next != null) {
            left = left.next;
            mid = mid.next;
            right = right.next.next;
        }   
        // left 指針指向左段的末尾節(jié)點洞焙，從這里斷開
        left.next = null;

        // 1.4 合并兩個排序的鏈表，略
        return merge(sortInList(head), sortInList(mid));
    }
}

2 - 二分查找、排序

2.1 二分查找 - easy

雙指針法：通過比較數(shù)組中間元素與目標值澡匪，根據(jù)比較結(jié)果調(diào)整搜索范圍熔任，直到找到目標值或搜索范圍為空。

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

二分查找：利用數(shù)組的特性仙蛉，通過比較中間元素與相鄰元素笋敞，確定峰值所在的區(qū)間碱蒙，然后繼續(xù)在該區(qū)間內(nèi)查找荠瘪。

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 數(shù)組中的逆序?qū)?- median

歸并排序：提供了一種優(yōu)雅且高效的方式來統(tǒng)計逆序?qū)Γ跉w并的過程中統(tǒng)計逆序?qū)Φ臄?shù)量赛惩。

• 時間復雜度為 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 數(shù)組用于保存合并后的有序結(jié)果
        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] 右側(cè)的所有元素與 nums[j] 形成逆序?qū)?                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 旋轉(zhuǎn)數(shù)組的最小數(shù)字 - easy

二分查找：通過比較中間元素與首尾元素，確定最小值所在的區(qū)間喷兼，然后繼續(xù)在該區(qū)間內(nèi)查找篮绰。

• 時間復雜度為 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

遞歸法：前序遍歷的順序是 “根左右”勉抓〖致可以定義一個遞歸函數(shù)，首先訪問根節(jié)點藕筋，然后遞歸地遍歷左子樹纵散，最后遞歸地遍歷右子樹。

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

遞歸法：中序遍歷的順序是 “左根右”隐圾∥橄疲可以定義一個遞歸函數(shù)，首先遞歸地遍歷左子樹暇藏，然后訪問根節(jié)點蜜笤，最后遞歸地遍歷右子樹。

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

遞歸法：后序遍歷的順序是 “左右根”盐碱〈窭可以定義一個遞歸函數(shù)，首先遞歸地遍歷左子樹甸各，然后遞歸地遍歷右子樹垛贤，最后訪問根節(jié)點。

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

遞歸法：深度優(yōu)先搜索（DFS）趣倾，遞歸地計算左右子樹的最大深度聘惦，然后取兩者的最大值加 1（當前節(jié)點）。

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

遞歸法：前序遍歷兩棵樹，對于每個節(jié)點善绎，如果兩棵樹都有對應的節(jié)點黔漂，則將它們的值相加并創(chuàng)建一個新的節(jié)點；

如果只有一棵樹有節(jié)點禀酱，則直接使用那個節(jié)點炬守；如果兩棵樹都沒有節(jié)點，則返回空剂跟。

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 用兩個棧實現(xiàn)隊列 - 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函數(shù)的棧 - 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

使用雙指針定義窗口颜骤，結(jié)合雙端隊列存儲窗口內(nèi)的最大值。隨著窗口的滑動捣卤，更新雙端隊列以保持最大值在隊列頭部忍抽。

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 個數(shù) - medium

使用最大堆董朝，維護數(shù)組中最小的K個數(shù)鸠项。遍歷數(shù)組，將元素與堆頂比較子姜，必要時替換堆頂并調(diào)整堆祟绊。

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 數(shù)據(jù)流中的中位數(shù) - medium

一個最大堆存儲較小一半的元素，一個最小堆存儲較大一半的元素。根據(jù)元素數(shù)量的奇偶性牧抽，調(diào)整兩個堆的大小嘉熊，并計算中位數(shù)。

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()) {          // 如果最大堆的元素個數(shù)多阐肤，中位數(shù)就是最大堆的堆頂
            return (double) maxHeap.peek();
        } else {                                        // 如果最小堆的元素個數(shù)多，中位數(shù)是兩個堆頂?shù)钠骄?            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }
}

5 - 哈希讲坎、貪心

5.2 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字 - easy

使用哈希表來記錄每個數(shù)字出現(xiàn)的次數(shù)孕惜，然后遍歷哈希表找到出現(xiàn)次數(shù)超過一半的數(shù)字。

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 數(shù)組中只出現(xiàn)一次的兩個數(shù)字 - medium

使用哈希表記錄每個數(shù)字出現(xiàn)的次數(shù)衣赶，然后找到出現(xiàn)次數(shù)為1的兩個數(shù)字诊赊。

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 缺失的第一個正整數(shù) - medium

使用哈希表記錄數(shù)組中所有數(shù)字的出現(xiàn)厚满，然后從1開始依次枚舉正整數(shù)府瞄，并判斷其是否在哈希表中。

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

        // 將數(shù)組中的所有數(shù)字加入哈希表
        for (int num : nums) {
            set.add(num);
        }
        // 枚舉正整數(shù)碘箍，查找缺失的第一個正整數(shù)
        for (int i = 1; i <= nums.length; i++) {
            if (!set.contains(i)) {
                return i;
            }
        }
        // 如果所有從1到n的正整數(shù)都存在遵馆，那么缺失的數(shù)就是n+1
        return nums.length + 1;
    }
}

6 - 遞歸、回溯

6.1 沒有重復項的全排列 - medium

回溯法：使用一個數(shù)組來存儲當前的排列丰榴，然后遞歸地嘗試數(shù)字货邓，如果該數(shù)字沒有被使用過，就添加到排列中四濒，并繼續(xù)遞歸换况。

如果當前排列的長度等于數(shù)組的長度，則將其添加到結(jié)果中盗蟆。然后回溯戈二，移除最后一個添加的數(shù)字，嘗試下一個數(shù)字喳资。

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

回溯法：這個問題與沒有重復項的全排列類似觉吭。在遞歸之前，對數(shù)組進行排序仆邓，并且在遞歸中添加一個判斷鲜滩，

如果當前數(shù)字與前一個數(shù)字相同，并且前一個數(shù)字已經(jīng)被使用過节值，則跳過當前數(shù)字徙硅，以避免重復的排列。

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 島嶼數(shù)量 - medium

深度優(yōu)先搜索（DFS）：遍歷每一個單元格搞疗，如果是島嶼的一部分嗓蘑，則使用DFS來標記所有相連的島嶼單元格，同時計數(shù)器加一。

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

回溯法：使用一個字符串來存儲當前的排列脐往，然后遞歸地嘗試字符休吠，如果該字符沒有被使用過，就添加到當前排列中业簿，并繼續(xù)遞歸瘤礁。

如果當前排列的長度等于原始字符串的長度，則將其添加到結(jié)果中梅尤。然后回溯柜思，移除最后一個添加的字符，嘗試下一個字符巷燥。

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

回溯法：使用一個字符串來存儲當前的括號組合赡盘，然后遞歸地嘗試添加左括號或右括號。

如果左括號的數(shù)量大于右括號缰揪，就添加一個左括號陨享；反正亦然。如果相等钝腺，說明找到了一個有效的括號組合抛姑，則添加到結(jié)果中。

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 - 動態(tài)規(guī)劃

7.1 斐波那契數(shù)列

題目已經(jīng)把遞推公式直接給我們了艳狐，即狀態(tài)轉(zhuǎn)移方程 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

狀態(tài)轉(zhuǎn)移方程：將問題分解為子問題镀虐，即到達第 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

狀態(tài)轉(zhuǎn)移方程：構(gòu)建一個二維數(shù)組粉私，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

狀態(tài)轉(zhuǎn)移方程：與最長公共子序列類似，但是要求子串必須是連續(xù)的诺核。

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 數(shù)組
        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. 根據(jù)結(jié)束索引和最長長度，截取最長公共子串
        return str1.substring(end - len, end);
    }
}

7.7 矩陣的最小路徑和 - medium

最優(yōu)問題：使用一個與原矩陣同樣大小的 dp 數(shù)組窖杀，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

優(yōu)化問題：使用二分查找來優(yōu)化查找下一個更大元素的過程，從而減少時間復雜度入客。

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

邊界問題：構(gòu)建狀態(tài)轉(zhuǎn)移方程管毙，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：首先對每個字符進行大小寫轉(zhuǎn)換，然后翻轉(zhuǎn)整個字符串卓舵，接著以空格為界南用，對每個單詞進行二次翻轉(zhuǎn)，最終返回掏湾。

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

縱向掃描：將字符串數(shù)組看作一個二維空間裹虫。每一次從第一列開始確定字符，逐層掃描后面每一列融击，遇到不同字符停止掃描筑公。

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 反轉(zhuǎn)字符串 - easy

雙指針法：通過雙指針從兩端向中間遍歷，交換字符來實現(xiàn)尊浪。

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 最長無重復子數(shù)組 - medium

滑動窗口：通過維護一個窗口來不斷更新最長無重復子數(shù)組的長度匣屡。

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

雙指針法：通過維護兩個指針來遍歷數(shù)組，計算在不同位置的 “雨水” 量际长。

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 順時針旋轉(zhuǎn)矩陣 - medium

通過交換矩陣的上三角和下三角元素耸采，將矩陣轉(zhuǎn)置兴泥。然后對每一行的元素進行左右翻轉(zhuǎn)工育。

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 設(shè)計 LRU 緩存結(jié)構(gòu) - 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
    }
}