Exercise F

Summary for some exercise.

Functions

• collections.defaultdict()
  • collections.defaultdict(int)
  • collections.defaultdict(set)
  • collections.defaultdict(list)
• queue.PriorityQueue()
• queue.put(), queue.get()
• str.lower(), item.upper()

Linked-List, queue (deque, priority queue), stack, heap

Question	Answers
Copy List with Random Pointer	std::unordered_map, old node to new node
Insert into a Sorted Circular Linked List	Analysis, find p1 and p2 to insert between
Simplify Path	string processing, deque
Moving Average from Data Stream	deque or vector, maintain the sum
Nested List Weight Sum	std::queuestd::pair depthToInteger
Merge k Sorted Lists	std::priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> queue(comp)
Exclusive Time of Functions	Stack to store running thread id
Subarray Sum Equals K	std::unordered_map, sum to count
Top K Frequent Elements	std::unordered_map frequency to nums
Random Pick Index	std::unordered_map, num to indices
LRU Cache	std::unordered_map, key to node, doubled-linked list
Clone Graph	std::unordered_map, old node to new node
Strobogrammatic Number	std::unordered_map
Dot Product of Two Sparse Vectors	std::unordered_map

String

Question	Answers
Valid Word Abbreviation	string processing, 2 pointers
Group Shifted Strings	ASCII converting
Basic Calculator II	std::stoi, deque
Add Strings	char to int
Palindrome Permutation	count char frequency, check whether even number
Valid Palindrome	2 pointers
Valid Palindrome II	2 pointers, 1 recursion
Valid Palindrome III	2-d DP, or k recursion
Minimum Remove to Make Valid Parentheses	Analysis. Count left and right parentheses. Remove the extra right position and remained left position
Minimum Add to Make Parentheses Valid	Count left and right parentheses
Remove Invalid Parentheses	Count left and right parentheses, then DFS

Tree

Question	Answers
Lowest Common Ancestor of a Binary Tree	Current or left or right
Lowest Common Ancestor of a Binary Tree II	Count whether 2 nodes have been found
Lowest Common Ancestor of a Binary Tree III	unordered_set, traverse to the parent
Find Distance in a Binary Tree	LCA, Return distance between node to p OR q
Binary Tree Vertical Order Traversal	tree traversal, std::queuestd::pair levelToNode, std::unordered_map with tracking most left and most right column
Vertical Order Traversal of a Binary Tree	same as above, but when inserting the node, compare the value
Binary Tree Right Side View	BFS of tree
Binary Search Tree Iterator	In-order iteration traversal of tree
Sum Root to Leaf Numbers	tree recursion
Diameter of Binary Tree	tree recursion, check left and right at each node, return the max of left or right
Convert Binary Search Tree to Sorted Doubly Linked List	Recursion, return head and tail
Range Sum of BST	Tree recursion
Closest Binary Search Tree Value	tree recursion, or iteration
Construct Binary Tree from String	Recursion

Binary search, sort, union find, traversal, 2 pointers

Question	Answers
Find Peak Element	binary search
Missing Element in Sorted Array	binary search
Kth Smallest Element in a Sorted Matrix	binary search + matrix traversal
Random Pick with Weight	generate number for given distribution, binary search
Merge Intervals	sort, check intersection
Accounts Merge	union find
Custom Sort String	build dictionary, then custom lambda sorting
Maximum Swap	Break num into digits, then sort
Missing Ranges	1-d traversal
Buildings With an Ocean View	1-d traversal from right, keep tracking largest number, std::reverse(arr.begin(), arr.end())
Diagonal Traverse	2-d traversal
Diagonal Traverse II	2-d traversal
Toeplitz Matrix	2-d traversal
Leftmost Column with at Least a One	2-d traversal from top right
Minesweeper	2-d traversal, recursion
Shortest Path in Binary Matrix	2-d DP + BFS
Merge Sorted Array	3 pointers
Product of Two Run-Length Encoded Array	2 pointers

Recursion, BFS, DFS, DP

Question	Answers
Cutting Ribbons	analysis, binary search, if cut is possible
Continuous Subarray Sum	unordered_map, calculate the accumulated mod at each position, store idx into map. Check whether previous has same mod
Valid Number	Analysis
Pow(x, n)	Recursion, binary divide
Kth Largest Element in an Array	Top k-th problem. Quick sort, or count sort
K Closest Points to Origin	Top k problem, custom std::priority_queue
Friends Of Appropriate Ages	std::unordered_map, num to frequency. Then could 2 for loops or use binary search
Max Consecutive Ones III	2 pointers
Meeting Rooms II	scan start and end time, sort by time
Next Permutation	find the position smaller than right, then find the smallest number in the right that larger than current number
Robot Room Cleaner	DFS
Check if an Original String Exists Given Two Encoded Strings	DFS ??
Number of Visible People in a Queue	stack to store candidate idx could be observed
Add Bold Tag in String	trie tree ??
Stickers to Spell Word	DFS + memo, recursion search for remained string
Subsets	combination

Appendix

Array and string

• No.3 - Longest Substring Without Repeating Characters
• No.15 - 3Sum
  • Sort
  • One iterate, Two pointers
• No.76 - Minimum Window Substring
  • 2 Pointers
  • collection.Counter()
• No.340 - Longest Substring with At Most K Distinct Characters
  • Pointers, dict
• No.560 - Subarray Sum Equals K
• No.88 - Merge Sorted Array
  • 3 Pointers
• No.31 - Next Permutation
  • pointers
• No.986 - Interval List Intersections
• No.125 - Valid Palindrome
  • 2 pointers
• No.67 - Add Binary

HashTable

• No.1 - Two Sum

Queue, Stack

Heap / PriorityQueue

• No.973 - K Closest Points to Origin
• No.23 - Merge k Sorted Lists
• No.253 - Meeting Rooms II

Tree

• No.297 - Serialize and Deserialize Binary Tree
  • Use , to device elements
  • Use # to represent None
  • Use queue to store parents
• No.124 - Binary Tree Maximum Path Sum
  • Use recursive function to return 2 values
• No.98 - Validate Binary Search Tree
  • Traverse, dfs
• No.199 - Binary Tree Right Side View
  • Traverse, bfs

Graph

Search

• No.215 - Kth Largest Element in an Array

Sort

• No.56 - Merge Intervals
• No.269 - Alien Dictionary
  • Topological Sort

DP

• No.560 - Subarray Sum Equals K
  • accu_num

Backtracking

No.301 - Remove Invalid Parentheses

Complex

• No.10 - Tegular Expression Matching