总结一下：
- 大家的刷题经验都比我丰富，找到最适合自己的方法就好了
- 200～300题刷2-3边，至少100+小时的投入
- 同一类型题目一起刷，总结规律和差异
- 多看别人的（优秀）代码
- 完整的手写实现，不要copy代码，增强肌肉记忆（视频中没提到）
- 培养代码风格
Huahua's Tech Road
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Example 1:
|
1 2 3 4 5 6 7 8 |
<strong>Input:</strong> matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 <strong>Output:</strong> true |
Example 2:
|
1 2 3 4 5 6 7 8 |
<strong>Input:</strong> matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 <strong>Output:</strong> false |
Solution: Binary Search
Treat the 2D array as a 1D array. matrix[index / cols][index % cols]
Time complexity: O(log(m*n))
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty()) return false; int l = 0; int r = matrix.size() * matrix[0].size(); const int cols = matrix[0].size(); while (l < r) { const int m = l + (r - l) / 2; if (matrix[m / cols][m % cols] == target) { return true; } else if (matrix[m / cols][m % cols] > target) { r = m; } else { l = m + 1; } } return false; } }; |
Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a label (int) and a list (List[UndirectedGraphNode]) of its neighbors. There is an edge between the given node and each of the nodes in its neighbors.
OJ’s undirected graph serialization (so you can understand error output):
Nodes are labeled uniquely.We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
- First node is labeled as
0. Connect node0to both nodes1and2. - Second node is labeled as
1. Connect node1to node2. - Third node is labeled as
2. Connect node2to node2(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ \
/ \
0 --- 2
/ \
\_/
Note: The information about the tree serialization is only meant so that you can understand error output if you get a wrong answer. You don’t need to understand the serialization to solve the problem.
Solution: Queue + Hashtable
Time complexity: O(V+E)
Space complexity: O(V+E)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua, 44ms, 16.8MB class Solution { public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if (!node) return nullptr; typedef UndirectedGraphNode Node; unordered_set<Node*> done; unordered_map<Node*, Node*> m; queue<Node*> q; q.push(node); while (!q.empty()) { Node* s = q.front(); q.pop(); if (done.count(s)) continue; done.insert(s); if (!m.count(s)) m[s] = new Node(s->label); Node* t = m[s]; for (Node* ss : s->neighbors) { if (!m.count(ss)) m[ss] = new Node(ss->label); q.push(ss); t->neighbors.push_back(m[ss]); } } return m[node]; } }; |
Solutions
- https://zxi.mytechroad.com/blog/simulation/leetcode-989-add-to-array-form-of-integer/
- https://zxi.mytechroad.com/blog/graph/leetcode-990-satisfiability-of-equality-equations/
- https://zxi.mytechroad.com/blog/greedy/leetcode-991-broken-calculator/
- https://zxi.mytechroad.com/blog/two-pointers/leetcode-992-subarrays-with-k-different-integers/
Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.
(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)
Return the number of good subarrays of A.
Example 1:
Input: A = [1,2,1,2,3], K = 2 Output: 7 Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
Example 2:
Input: A = [1,2,1,3,4], K = 3 Output: 3 Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].
Note:
1 <= A.length <= 200001 <= A[i] <= A.length1 <= K <= A.length
Solution: Two pointers + indirection
Let f(x) denote the number of subarrays with x or less distinct numbers.
ans = f(K) – f(K-1)
It takes O(n) Time and O(n) Space to compute f(x)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // vector: 56 ms, 10.1 MB // Hashtable: 126 ms, 25 MB class Solution { public: int subarraysWithKDistinct(vector<int>& A, int K) { // Returns the number of subarrays with k or less distinct numbers. auto subarrys = [&A](int k) { vector<int> count(A.size() + 1); int ans = 0; int i = 0; for (int j = 0; j < A.size(); ++j) { if (count[A[j]]++ == 0) --k; while (k < 0) if (--count[A[i++]] == 0) ++k; ans += j - i + 1; } return ans; }; return subarrys(K) - subarrys(K - 1); } }; |