Topic with starred leetcode problems

Array

Problem	Solution
48. Rotate Image	Solution
54. Spiral Matrix	注意半边之后要重新判断
287. Find the Duplicate Number	Binary Search(C++) | Cycle Detection(Java)
418. Sentence Screen Fitting	建立退格的mapping

Binary Search

Problem	Solution
33. Search in Rotated Sorted Array	Solution
81. Search in Rotated Sorted Array II	多考虑重复的情况
34. Find First and Last Position of Element in Sorted Array	Solution
1044. Longest Duplicate Substring	String Hashing(Rabin Karp's Algorithm) + Binary Search
1268. Search Suggestions System	lower_bound&upper_bound, use emplace_back

Binary Search Tree(BST)

Problem	Solution
162. Find Peak Element	binary search找peak
315. Count of Smaller Numbers After Self	Java Solution
1008. Construct Binary Search Tree from Preorder Traversal	递归O(n)解

Bit Manipulation

Problem	Solution
137. Single Number II	解决n个重复数字找不同问题
260. Single Number III	xor + lowbit
1239. Maximum Length of a Concatenated String with Unique Characters	bit and找intersection优化combination问题 | C++ bitset

Dynamic Programming

Problem	Solution
5. Longest Palindromic Substring	Manacher's Algorithm
10. Regular Expression Matching	字符串匹配类dp
152. Maximum Product Subarray	记录当前结尾的subarray
42. trapping rain water	DP优化为two pointer
72. Edit Distance	Solution
96. Unique Binary Search Trees	Solution
188. Best Time to Buy and Sell Stock IV	局部最优vs全局最优
300. Longest Increasing Subsequence(LIS)	DP + binary search(C++)
368. Largest Divisible Subset	LIS问题变种
354. Russian Doll Envelopes	Binary Search+DP(思路同lc300)
518. Coin Change 2	Unbounded Knapsack Problem(C++) | 优化为1维数组(Java)
688. Knight Probability in Chessboard	dfs + memo算概率
741. Cherry Pickup	转化为两个同时进行的子问题+ dfs + memo
1320. Minimum Distance to Type a Word Using Two Fingers	dfs+memorization
221. Maximal Square	从对应边长找状态转移方程
1143. Longest Common Subsequence	LCS问题
1312. Minimum Insertion Steps to Make a String Palindrome	区间dp(小区间->大区间)
818. Race Car	BFS找最短路径 | DP

Fenwick Tree / Binary Indexed Tree(BIT)

Problem	Solution
315. Count of Smaller Numbers After Self	C++ Solution

Graph

Problem	Solution
863. All Nodes Distance K in Binary Tree	由tree建无向图BFS
207. Course Schedule	Topological Sort
210. Course Schedule II	Topological Sort
332. Reconstruct Itinerary	Eularian Path & Hierholzer’s Algorithm
886 Possible Bipartition	Graph Coloring
934.Shortest Bridge	Graph coloring: dfs + bfs
743. Network Delay Time	Dijkstra
787. Cheapest Flights Within K Stops	Dijkstra
1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance	Dijkstra
1192. Critical Connections in a Network	todo

Greedy

Problem	Solution
55. Jump Game	Solution
45. Jump Game II	Solution
135. Candy	一次遍历 spaceO(1)解
763. Partition Labels	greedy + two pointer
757. Set Intersection Size At Least Two	Solution
630. Course Schedule III	按照结束时间和duration结合greedy
1029. Two City Scheduling	Greedy | DP

Iterator

Problem	Solution
341. Flatten Nested List Iterator	List Iterator

Linked-List

Problem	Solution
148. Sort List	merge sort | space O(1) Solution

Math

Problem	Solution
43. Multiply Strings	Solution
50. Pow(x, n)	Solution
837. New 21 Game	算累加条件概率

Monotonic Queue

Problem	Solution
84. Largest Rectangle in Histogram	Monotinic Stack
85. Maximal Rectangle	思路同84
402. Remove K Digits	Monotonic Stack
907. Sum of Subarray Minimums	Monotonic stack确定元素范围
239. Sliding Window Maximum	Monotic Queue + sliding window
862. Shortest Subarray with Sum at Least K	Monotonic Queue + Sliding Window

OOD

Problem	Solution
146. LRU Cache	HashMap + Doubly Linked List | Java LinkedHashMap
460. LFU Cache	HashMap + TreeSet(Ologn) | HashMap + DList(O(1))
642. Design Search Autocomplete System	Trie + PriorityQueue
895. Maximum Frequency Stack	思路同LFU Cache
705. Design HashSet	linkedlist handle hashing collision
706. Design HashMap	linkedlist handle hashing collision
981. Time Based Key-Value Store	hashMap + binarySearch
1146. Snapshot Array	list数组 or TreeMap

Random

Problem	Solution
528. Random Pick with Weight	Random + binarySeach
384. Shuffle an Array	inside-out shuffle
470. Implement Rand10() Using Rand7()	Solution

Search

Problem	Solution
60. Permutation Sequence	找到确定每个位置的数字的规律
90.subsets II	subset去重
127. Word Ladder	双向BFS
126. Word Ladder II	双向BFS + DFS + path建图(Java) | 单向BFS(C++)
310. Minimum Height Trees	建图+BFS
140. Word Break II	DFS + memo
329. Longest Increasing Path in a Matrix	DFS + memo
472. Concatenated Words	DFS + memo Solution(C++) | Trie Solution(Java)
489. Robot Room Cleaner	模拟dfs, 注意当前robot朝向

Segment Tree

Problem	Solution
307. Range Sum Query - Mutable	Segment Tree模版

Sliding Window

Problem	Solution
76. Minimum Window Substring	Java Solution
424. Longest Repeating Character Replacement	互补sliding window
480. Sliding Window Median	minHeap + maxHeap
438. Find All Anagrams in a String	Sliding window + hashmap模版
560. Subarray Sum Equals K	有负数不能用two pointer做sliding window, 换成hashmap的变种
1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit	Sliding window + monotonic queue

String

Problem	Solution
468.Validate IP Address	String split, NumberFormatException

Quick Select(TopK)

Problem	Solution
215. Kth Largest Element in an Array	quick select
973 K Closest Points to Origin	Quick Select
347. Top K Frequent Elements	freq有上限, bucket sort

Tree

Problem	Solution
199. Binary Tree Right Side View	preorder + level check
662. Maximum Width of Binary Tree	Solution
1110. Delete Nodes And Return Forest	Solution

TreeMap(Ordered Map)

Problem	Solution
846. Hand of Straights	注意follow up

Trie

Problem	Solution
208. Implement Trie	Trie模版
212. Word Search II	Dfs + Trie剪枝
421. Maximum XOR of Two Numbers in an Array	Bitwise Trie(按照unsigned int建trie)
472. Concatenated Words	Trie Solution(Java) | DFS + memo Solution(C++)
1268. Search Suggestions System	Trie

Union Find

Problem	Solution
695. Max Area of Island	Union Find | DFS
803. Bricks Falling When Hit	Union Find
947. Most Stones Removed with Same Row or Column	Union-Find Golang模版
952. Largest Component Size by Common Factor	连接公因数的UF