刷題 | YuAn

基礎資料結構

Prefix Sum and diff [6]

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

Sliding Window [5]

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

Binary Search [8]

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)

Linked List [13]

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)

Stack and Queue [2]
232 Implement Queue using Stacks (Easy)
225 Implement Stack using Queues (Easy)

括號問題 [5]

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)

Monotonic stack and Monotonic queue [9]

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)

Design data structure [8]

*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

Heap [4]

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)

Binary Tree [30]

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)

Binary Search Tree [14]

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)

*Trie [5]

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)

DFS/BFS [21]

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)

*Graph [17]

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)

動態規劃基本問題 [8]

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)

子序列問題 [12]

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)

背包問題 [3]

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

698 Partition to K Equal Sum Subsets
*494 Target Sum (Medium)

股票問題 [6]

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)

搶劫問題 [3]

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

貪心問題 Greedy [8]

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)

Boats to Save People

Broken Calculator

Smallest String With A Given Numeric Value

Minimum Domino Rotations For Equal Row

Candy

Two City Scheduling

遊戲問題 [10]

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)

Other algo and Math

Math [7]

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)

nSum 問題 [5]

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

區間問題 [6]

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)
1. Partition Labels

計算機 [3]

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

高頻面試 [5]

659 Split Array into Consecutive Subsequences (Medium)
391 Perfect Rectangle (Hard)
969 Pancake Sorting (Medium)
43 Multiply Strings (Medium)
855 Exam Room (Medium)

Other Algo [4]

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

Bit Manipulation [9]

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)

Array [17]
448 Find All Numbers Disappeared in an Array (Easy)
26 Remove Duplicates from Sorted Array (Easy)
1. Remove Duplicates from Sorted Array II
83 Remove Duplicates from Sorted List (Easy)
1. 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)

Matrix [3]

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 vs merge sort

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

Tips

小知識

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

小訣竅

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

	遞回	迭代
	花費較多的時間、較無效率	執行時間較短
	需要額外的 Stack 支持	不需要額外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

好用的框架 summary

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

Dynamic programming

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

Backtracking

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

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

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

BFS


// 计算从起点 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)
    // 后序遍历
}

Binary search


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

Sliding Window

int left = 0, right = 0;

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

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

Binary Search Tree

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

Graph traverse

/* 多叉树遍历框架 */
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 都可以省略了，等同於樹的遍歷

目錄