main - a920604a/leetcode GitHub Wiki

• *303 Range Sum Query - Immutable (Easy)
• *304 Range Sum Query 2D - Immutable (Medium)
• *560 Subarray Sum Equals K (Medium)
• *370 Range Addition (Medium, Premium)
• *1094 Car Pooling (Medium)
• *1109 Corporate Flight Bookings (Medium)

• *76 Minimum Window Substring (Hard)
• *567 Permutation in String (Medium)
• *438 Find All Anagrams in a String (Medium)
• *3 Longest Substring Without Repeating Characters (Medium)
• *239 Sliding Window Maximum (Hard)

• 704 Binary Search (Easy)

• 34 Find First and Last Position of Element in Sorted Array (Medium)

• 875 Koko Eating Bananas (Medium)

• 1011 Capacity To Ship Packages Within D Days (Medium)

• 35 Search Insert Position (Easy)

• *354 Russian Doll Envelopes (Hard)

• *392 Is Subsequence (Easy)

• *793 Preimage Size of Factorial Zeroes Function (Hard)

• 19 Remove Nth Node From End of List (Medium)

• 21 Merge Two Sorted Lists

• 23 Merge k Sorted Lists

• 141 Linked List Cycle (Easy)

• 142 Linked List Cycle II (Medium)

• 160 Intersection of Two Linked Lists

• 876 Middle of the Linked List (Easy)

• 2 Add Two Numbers (Medium)

• 25 Reverse Nodes in k-Group (Hard)

• 83 Remove Duplicates from Sorted List (Easy)

• 206 Reverse Linked List(Easy)

• 92 Reverse Linked List II (Medium)

• 234 Palindrome Linked List (Easy)

• 203 Remove Linked List Elements (Easy)

• 232 Implement Queue using Stacks (Easy)
• 225 Implement Stack using Queues (Easy)

• 20 Valid Parentheses (Easy)
• *921 Minimum Add to Make Parentheses Valid (Medium)
• *1541 Minimum Insertions to Balance a Parentheses String (Medium)
• *32 Longest Valid Parentheses (Hard)
• 1249 Minimum Remove to Make Valid Parentheses (Medium)

• 496 Next Greater Element I (Easy)
• 503 Next Greater Element II (Medium)
• 739 Daily Temperatures (Medium)
• *316 Remove Duplicate Letters (Medium)
• *1081 Smallest Subsequence of Distinct Characters (Medium)
• 42 Trapping Rain Water (Hard)
• *239 Sliding Window Maximum (Hard)
• *316 Remove Duplicate Letters (Medium)
• *1081 Smallest Subsequence of Distinct Characters (Medium)

• *146 LRU Cache (Medium)
• *460 LFU Cache (Hard)
• *380 Insert Delete GetRandom O(1) (Medium)

*381 Insert Delete GetRandom O(1) - Duplicates allowed

• *710 Random Pick with Blacklist (Hard)

• 295 Find Median from Data Stream (Hard)

• *355 Design Twitter (Medium)

• *341 Flatten Nested List Iterator (Medium)

• *895 Maximum Frequency Stack (Hard)

[補充]

• *1206 Design Skiplist (Hard)
• 705 Design HashSet (Easy)
• 706 Design HashMap (Easy)
• 707 Design Linked List (Medium)
• 641 Design Circular Deque (Medium)
• 622 Design Circular Queue (Medium)
• 225 Implement Stack using Queues (Easy)
• 232 Implement Queue using Stacks (Easy)
• 2241 Design an ATM Machine
• *535 Encode and Decode TinyURL (Medium)
• 1396 Design Underground System

• 215 Kth Largest Element in an Array (Medium)
• 23 Merge k Sorted Lists (Hard)
• 295 Find Median from Data Stream (Hard)
• 703 Kth Largest Element in a Stream (Easy)

• 226 Invert Binary Tree (Easy)

• 114 Flatten Binary Tree to Linked List (Medium)

• 116 Populating Next Right Pointers in Each Node (Medium)

• 654 Maximum Binary Tree (Medium)

Construct Binary Tree from

• 105 Construct Binary Tree from Preorder and Inorder Traversal (Medium)

• 106 Construct Binary Tree from Inorder and Postorder Traversal (Medium)

• 889 Construct Binary Tree from Preorder and Postorder Traversal (Medium)

• 652 Find Duplicate Subtrees (Medium)

• *297 Serialize and Deserialize Binary Tree (Hard)

• 236 Lowest Common Ancestor of a Binary Tree (Medium)

• *1373 Maximum Sum BST in Binary Tree (Hard)

• 104 Maximum Depth of Binary Tree (Easy)

• 111 Minimum Depth of Binary Tree (Easy)

• *669 Trim a Binary Search Tree (Medium)

• 543 Diameter of Binary Tree (Easy)

• 366 Find Leaves of Binary Tree (Medium, Premium)

• *124 Binary Tree Maximum Path Sum (Hard)

• 515 Find Largest Value in Each Tree Row (Medium)

• 100 Same Tree (Easy)

• 222 Count Complete Tree Nodes (Medium)

traverse

• 94 Binary Tree Inorder Traversal (Easy)
• 102 Binary Tree Level Order Traversal (Medium)
• 107 Binary Tree Level Order Traversal II (Medium)
• 103 Binary Tree Zigzag Level Order Traversal (Medium)
• 144 Binary Tree Preorder Traversal (Easy)
• 145 Binary Tree Postorder Traversal (Easy)
• 965 Univalued Binary Tree (Easy)

N-ary Tree

• 559 Maximum Depth of N-ary Tree (Easy)

• 589 N-ary Tree Preorder Traversal (Easy)

• 590 N-ary Tree Postorder Traversal (Easy)

• 429 N-ary Tree Level Order Traversal

• *341 Flatten Nested List Iterator (Medium)

• 230 Kth Smallest Element in a BST (Medium)
• 538 Convert BST to Greater Tree (Medium)
• 1038 Binary Search Tree to Greater Sum Tree (Medium)

operation

• 450 Delete Node in a BST (Medium)

• 701 Insert into a Binary Search Tree (Medium)

• 700 Search in a Binary Search Tree (Easy)

• 98 Validate Binary Search Tree (Medium)

• *96 Unique Binary Search Trees (Medium)

• *95 Unique Binary Search Trees II (Medium)

• *1373 Maximum Sum BST in Binary Tree (Hard)

• 501 Find Mode in Binary Search Tree (Easy)

• 530 Minimum Absolute Difference in BST (Easy)

• 783 Minimum Distance Between BST Nodes (Easy)

• 235 Lowest Common Ancestor of a Binary Search Tree (Easy)

• 208 Implement Trie (Prefix Tree) (Medium)
• 1804 Implement Trie II (Prefix Tree) (Medium, Premium)
• 648 Replace Words (Medium)
• 211 Design Add and Search Words Data Structure (Medium)
• 677 Map Sum Pairs (Medium)

• 46 Permutations (Medium)
• 47 Permutations II (Medium)
• 51 N-Queens (Hard)
• 52 N-Queens (Hard)
• *698 Partition to K Equal Sum Subsets (Medium)
• 78 Subsets (Medium)
• 77 Combinations (Medium)
• 37 Sudoku Solver (Hard)
• 22 Generate Parentheses (Medium)
• 17 Letter Combinations of a Phone Number (Medium)
• 401 Binary Watch (Easy)

islands

• 200 Number of Islands (Medium)
• 1254 Number of Closed Islands (Medium)
• 1020 Number of Enclaves (Medium)
• 695 Max Area of Island (Medium)
• *1905 Count Sub Islands (Medium)
• 694 Number of Distinct Islands (Medium, Premium)

BFS

• 111 Minimum Depth of Binary Tree (Easy)
• 752 Open the Lock (Medium)
• *773 Sliding Puzzle (Hard)
• *542 01 Matrix (Medium)
• *994 Rotting Oranges (Medium)

• 797 All Paths From Source to Target (Medium)

• 133 Clone Graph (Medium)

• *207 Course Schedule (Medium)

• 210 Course Schedule II (Medium)

• 785 Is Graph Bipartite? (Medium)

• 886 Possible Bipartition (Medium)

• 277 Find the Celebrity (Medium, Premium)

Union-Find

• 323 Number of Connected Components in an Undirected Graph (Medium, Premium)
• 547 Number of Provinces (Medium)
• 130 Surrounded Regions (Medium)
• 990 Satisfiability of Equality Equations (Medium)

Kruskal

• 261 Graph Valid Tree (Medium, Premium)
• 1135 Connecting Cities With Minimum Cost (Medium, Premium)
• 1584 Min Cost to Connect All Points (Medium)

Dijkstra

• 743 Network Delay Time (Medium)
• 1514 Path with Maximum Probability (Medium)
• 1631 Path With Minimum Effort (Medium)

• 509 Fibonacci Number (Easy)
• 322 Coin Change (Medium)
• *983 Minimum Cost For Tickets (Medium)
• 931 Minimum Falling Path Sum (Medium)

120 Triangle (Medium)

• 64 Minimum Path Sum (Medium)
• 70 Climbing Stairs (Easy)
• 62 Unique Paths (Easy)

• 53 Maximum Subarray (Easy)

• 300 Longest Increasing Subsequence (Medium)

• 354 Russian Doll Envelopes

• 1143 Longest Common Subsequence (Medium)

• 583 Delete Operation for Two Strings (Medium)

• 712 Minimum ASCII Delete Sum for Two Strings (Medium)

• *72 Edit Distance (Hard)

• 1312 Minimum Insertion Steps to Make a String Palindrome

• 516 Longest Palindromic Subsequence (Medium)

• *5 Longest Palindromic Substring (Medium)

• *647 Palindromic Substrings

• *10 Regular Expression Matching (Hard)

• *518 Coin Change 2 (Medium)
• *416 Partition Equal Subset Sum (Medium)

698 Partition to K Equal Sum Subsets

• *494 Target Sum (Medium)

• 121 Best Time to Buy and Sell Stock (Easy)
• 122 Best Time to Buy and Sell Stock II (Easy)
• 123 Best Time to Buy and Sell Stock III (Hard)
• 188 Best Time to Buy and Sell Stock IV (Hard)
• 309 Best Time to Buy and Sell Stock with Cooldown (Medium)
• 714 Best Time to Buy and Sell Stock with Cooldown (Medium)

• 198 House Robber (Medium)
• 213 House Robber II (Medium)
• 337 House Robber III (Medium)

• 134 Gas Station (Medium)

• 1024 Video Stitching (Medium)

• 453 Minimum Moves to Equal Array Elements (Easy)

• 435 Non-overlapping Intervals (Medium)

• 452 Minimum Number of Arrows to Burst Balloons (Medium)

• 55 Jump Game (Medium)

• 45 Jump Game II (Medium)

• 870 Advantage Shuffle (Medium)

• 2592 Maximize Greatness of an Array (Medium)

881. Boats to Save People
882. Broken Calculator
883. Smallest String With A Given Numeric Value
884. Minimum Domino Rotations For Equal Row
885. Candy
886. Two City Scheduling

• 174 Dungeon Game (Hard)

• 514 Freedom Trail (Hard)

• 787 Cheapest Flights Within K Stops (Medium)

• 887 Super Egg Drop (Hard)

• 312 Burst Balloons (Hard)

• 877 Stone Game (Medium)

• 651 4 Keys Keyboard (Medium)

• 292 Nim Game (Easy)

• 877 Stone Game (Medium)

• 319 Bulb Switcher (Medium)

• 204 Count Primes (Easy)

• 172 Factorial Trailing Zeroes (Easy)

• 793 Preimage Size of Factorial Zeroes Function (Hard)

• 382 Linked List Random Node (Medium)

• 398 Random Pick Index (Medium)

• 372 Super Pow (Medium)

• 453 Minimum Moves to Equal Array Elements (Easy)

263 Ugly Number (Easy) *264 Ugly Number II (Medium) 202 Happy Number (Easy) 204 Count Primes (Medium) *279 Perfect Squares (Medium)

• 15 3Sum (Medium)
• 16 3Sum Closest
• 18 4Sum (Medium)
• 454 4Sum (Medium)
• 923 3Sum With Multiplicity (Medium)

• 56 Merge Intervals (Medium)

57 Insert Interval (Medium)

• 986 Interval List Intersections (Medium)

• 1288 Remove Covered Intervals (Medium)

• 435 Non-overlapping Intervals (Medium)

• 452 Minimum Number of Arrows to Burst Balloons (Medium)

• 1024 Video Stitching (Medium)

763. Partition Labels

• 224 Basic Calculator (Hard)
• 227 Basic Calculator II (Medium)
• 772 Basic Calculator III (Hard)

• 659 Split Array into Consecutive Subsequences (Medium)

• 391 Perfect Rectangle (Hard)

• 969 Pancake Sorting (Medium)

• 43 Multiply Strings (Medium)

• 855 Exam Room (Medium)

• 241 Different Ways to Add Parentheses (Medium)
• 253 Meeting Rooms II (Medium, Premium)
• 134 Gas Station (Medium)
• 28 Implement strStr() (Easy)

• 136 Single Number (Easy)
• 137 Single Number II (Medium)
• 260 Single Number III (Medium)
• 268 Missing Number (Easy)
• 389 Find the Difference (Easy)
• 190 Reverse Bits (Easy)
• 191 Number of 1 Bits (Easy)
• 231 Power of Two (Easy)
• 405 Convert a Number to Hexadecimal (Easy)

• 448 Find All Numbers Disappeared in an Array (Easy)
• 26 Remove Duplicates from Sorted Array (Easy)

80. Remove Duplicates from Sorted Array II

• 83 Remove Duplicates from Sorted List (Easy)

82. Remove Duplicates from Sorted List II (Medium)

• 27 Remove Element (Easy)

• 283 Move Zeroes (Easy)

• 287 Find the Duplicate Number (Medium)

• 645 Set Mismatch

• 167 Two Sum II - Input array is sorted (Easy)

• 344 Reverse String (Easy)

• 541 Reverse String II (Easy)

• 345 Reverse Vowels of a String (Easy)

• 1 Two Sum (Easy)

• 350 Intersection of Two Arrays II (Easy)

• 349 Intersection of Two Arrays (Easy)

• 1002 Find Common Characters (Easy)

• 170 Two Sum III (Easy, Premium)

• 318 Maximum Product of Word Lengths (Medium)

• 912 Sort an Array (Medium)

• 315 Count of Smaller Numbers After Self (Hard)

[補充]

• *1089 Duplicate Zeros (Easy)
• 941 Valid Mountain Array (Easy)
• 1299 Replace Elements with Greatest Element on Right Side (Easy)

• 48 Rotate Image (Medium)
• 54 Spiral Matrix (Medium)
• 59 Spiral Matrix II (Medium)

• array
• linked list 資料遍歷
• 線性訪問 for/while
• 非線性訪問 遞迴

基本操作就是增刪查改，訪問方式迭代/遞迴 迭代與遞迴雖然時間複雜度都是O(N)，但是遞迴空間複雜度為O(N)，迭代則是O(1)

quick sort = preorder，這也說明了worse case 為什麼比merge sort差的原因 merge sort = postorder

void sort(int[] nums, int lo, int hi) {
    /****** 前序遍历位置 ******/
    // 通过交换元素构建分界点 p
    int p = partition(nums, lo, hi);
    /************************/

    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    sort(nums, lo, mid);
    sort(nums, mid + 1, hi);

    /****** 后序遍历位置 ******/
    // 合并两个排好序的子数组
    merge(nums, lo, mid, hi);
    /************************/
}

小知識

• 涉及到recursive，都可以視為樹的問題
• 很多動態規劃問題也是在拜訪一個樹
• 遞迴 其實就是stack概念

小訣竅

• 鏈接串列、子字串、數組題，用雙指針
• 快慢指針用於鏈接串列操作
• 左右指針用於數組操作，二元搜尋低一檔次
• 滑動窗口用於子字串

two pointer 雙指標問題 - slow fast 鏈接串列
- 環狀問題：第一次相遇後重置slow = head ，fast = 相遇點，再一起跑，這時快慢一致相遇點就是環狀起點。 - left right pointer 數組 ： - Binary Search、變形的Binary Search - 數組 sum、數組 reverse、in-place 修改數組 - Sliding window

• 刪除/搜尋 數組任意元素只要O(1)
  • 結合hash table 和 數組。hash插入搜尋刪除O(logn) 數組插入O(1)搜尋O(n)刪除O(n)
  • 關鍵在於刪除元素時，先把該元素交換到數組尾部，在pop掉

• 變形的Binary Search 找出自定義的函數，必須是單調遞減(遞增)函數、初始化left、right

字串的子序列或是匹配問題直接就上動態規劃 遇到需要求出所有可能況狀首先考慮用遞迴。 x^0 = 0, x^x = 0, xor滿足交換率 雙指針分為 快慢指針和左右指針，快慢指針主要解決linked list問題，比如linked list是否有環，左右指針主要解決數組或字串問題，例如二元搜尋 快慢指針 判斷linked list是否有環、鏈表的環的起點、鏈表中點、鏈表中特定位置元素 左右指針 二元搜尋、兩數之和、反轉數組、移動窗口、子字串問題

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

// 回溯算法關注的不是節點，而是樹枝

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路

    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

/* 二叉树遍历框架 */
void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

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

int left = 0, right = 0;

while (right < s.size()) {`
    // 增大窗口
    window.add(s[right]);
    right++;

    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

/* 多叉树遍历框架 */
void traverse(TreeNode root) {
    if (root == null) return;

    for (TreeNode child : root.children)
        traverse(child);
}

// 有環的圖
Graph graph;
boolean[] visited;

/* 图遍历框架 */
void traverse(Graph graph, int s) {
    if (visited[s]) return;
    // 经过节点 s
    visited[s] = true;
    for (TreeNode neighbor : graph.neighbors(s))
        traverse(neighbor);
    // 离开节点 s
    visited[s] = false;   
}
// 有向圖含有環的時候才需要 visited 數組輔助。
// 如果沒有環，連visited 都可以省略了，等同於樹的遍歷

• 算法中文手冊
• hello-algorithm
• Algorithm Problem Classification