2021刷题打卡

2021/08/08

Backtracking

79. Word Search
489. Robot Room Cleaner

• This solution is based on the same idea as maze solving algorithm called right-hand rule
• backtrack: how to restore to original position
  

✅ HashTable
✅ Depth-First Search
✅ Dynamic Programming
✅ Union Find
✅ Backtracking
⏹ Heap (Priority Queue)
⭕ Breadth-First Search
⭕ Stack
⭕ Queue
⭕ Graph
⭕ Two Pointers
⭕ Prefix Sum
⭕ Binary Search

2021/08/09
Backtracking

126. Word Ladder II

• The key here is to treat word as vertexes, so we will translate this question to a graph problem
• The trickiest part is to build the graph and there are several places need to be cautious about: 1) previously traversed nodes should not be treated as curr node's neighbor; 2) the nodes at the same level should not be treated as curr node's neighbor; 3) next level's nodes, if it's already enqueued, we shouldn't enqueue it again.
• By doing this, we built a DAG, which ensures shortedst path for to reach the destination. We only need to do DFS/backtracking to search for the destination node
  

47. Permutations II

• use boolean[] to track if current element is used or not
• to remove duplication, when curr element == prev element, and prev element is not used, we should skip.
  

131. Palindrome Partitioning

• Nothing specital, just need careful thought processing
  

46. Permutations
17. Letter Combinations of a Phone Number

Heap (PriorityQueue)
973. K Closest Points to Origin

• maxHeap approach and minHeap approach
  

347. Top K Frequent Elements
23. Merge k Sorted Lists

✅ HashTable
✅ Depth-First Search
✅ Dynamic Programming
✅ Union Find
✅ Backtracking
⏹ Heap (Priority Queue)
⭕ Breadth-First Search
⭕ Stack
⭕ Queue
⭕ Graph
⭕ Two Pointers
⭕ Prefix Sum
⭕ Binary Search


2021/09/07
Heap (PriorityQueue)

1263. Minimum Moves to Move a Box to Their Target Location

• Two BFS: the first one to check if the box can be moved to target, the second one to check if the person can reach to the position to move the box
  

658. Find K Closest Elements

• Used PriorityQueue but the time complexity is O(NlogK + KlogK)
• Binary search is the optimal solution, time complexity is O(log(N-K))
  

1424. Diagonal Traverse II

• Draw diagram to figure out the solution