labuladong
岛屿问题
200. 岛屿数量
-
思路+解法：
-
DFS O(mn)
class Solution { public: int nr, nc; void dfs(vector<vector<char>>& g, int r, int c){ if(!(r >= 0 && r < nr)) return; if(!(c >= 0 && c < nc)) return; if(g[r][c] == '0') return; g[r][c] = '0'; dfs(g, r + 1, c); dfs(g, r - 1, c); dfs(g, r, c + 1); dfs(g, r, c - 1); } int numIslands(vector<vector<char>>& grid) { int ans = 0; nr = grid.size(); nc = grid[0].size(); for(int i = 0; i < nr; i++){ for(int j = 0; j < nc; j++){ if(grid[i][j] == '1'){ ans++; dfs(grid, i, j); } } } return ans; } }; -
BFS O(mn)
class Solution { public: int numIslands(vector<vector<char>>& grid) { int ans = 0; int nr = grid.size(); int nc = grid[0].size(); queue<pair<int,int>> q; for(int i = 0; i < nr; i++){ for(int j = 0; j < nc; j++){ if(grid[i][j] == '1'){ ans++; q.push({i, j}); while(!q.empty()){ pair<int, int> loc = q.front(); q.pop(); int x = loc.first, y = loc.second; if(x >= 1 && grid[x - 1][y] == '1'){ q.push({x - 1, y}); grid[x - 1][y] = '0'; } if(x < nr - 1 && grid[x + 1][y] == '1'){ q.push({x + 1, y}); grid[x + 1][y] = '0'; } if(y >= 1 && grid[x][y - 1] == '1'){ q.push({x, y - 1}); grid[x][y - 1] = '0'; } if(y < nc - 1 && grid[x][y + 1] == '1'){ q.push({x, y + 1}); grid[x][y + 1] = '0'; } } } } } return ans; } }; -
并查集 O(mn**α*(mn))
class Solution { public: int nr, nc; int cnt; vector<int> par; int find(int x){ if(par[x] == x) return x; return par[x] = find(par[x]); } //关键 void unite(int a, int b){ if(find(a) == find(b)) return; par[find(b)] = find(a); cnt--; } int numIslands(vector<vector<char>>& grid) { vector<vector<char>> copy_grid = grid; nr = grid.size(); nc = grid[0].size(); for(int i = 0; i < nr; i++){ for(int j = 0; j < nc; j++){ par.push_back(i * nc + j); } } cnt = nr * nc; for(int i = 0; i < nr; i++){ for(int j = 0; j < nc; j++){ if(grid[i][j] == '1'){ if(i > 0 && grid[i - 1][j] == '1') unite(i * nc + j, (i - 1) * nc + j); if(i < nr - 1 && grid[i + 1][j] == '1') unite(i * nc + j, (i + 1) * nc + j); if(j > 0 && grid[i][j - 1] == '1') unite(i * nc + j, i * nc + (j - 1)); if(j < nc - 1 && grid[i][j + 1] == '1') unite(i * nc + j, i * nc + (j + 1)); grid[i][j] = '0'; } else cnt--; } } return cnt; } }
-
1254. 统计封闭岛屿的数目
-
思路+解法：
-
DFS O(mn) 把靠边的岛屿先都淹了
class Solution { public: //把靠边的岛屿淹了 int nr, nc; void dfs(vector<vector<int>>& g, int r, int c){ if(r < 0 || r >= nr || c < 0 || c >= nc) return; if(g[r][c] == 1) return; g[r][c] = 1; dfs(g, r + 1, c); dfs(g, r - 1, c); dfs(g, r, c + 1); dfs(g, r, c - 1); } int closedIsland(vector<vector<int>>& grid) { nr = grid.size(), nc = grid[0].size(); for(int i = 0; i < nr; ++i){ dfs(grid, i, 0); dfs(grid, i, nc - 1); } for(int j = 0; j < nc; ++j){ dfs(grid, 0, j); dfs(grid, nr - 1, j); } int ans = 0; for(int i = 1; i < nr; ++i){ for(int j = 1; j < nc; ++j){ if(grid[i][j] == 0){ ans++; dfs(grid, i, j); } } } return ans; } };
-
1020. 飞地的数量
-
思路+解法：
-
对于每个点dfs找出口 超时
class Solution { public: int nr; int nc; vector<vector<int>> dir = {{1, 0},{-1, 0},{0, 1},{0, -1}}; vector<vector<bool>> vis; bool dfs(vector<vector<int>>& g, int r, int c){ if(r < 0 || r >= nr || c < 0 || c >= nc) return true; if(vis[r][c]) return false; if(g[r][c] == 0) return false; bool flag = false; for(int i = 0; i < 4; ++i){ int next_r = r + dir[i][0]; int next_c = c + dir[i][1]; vis[r][c] = true; if(dfs(g, next_r, next_c)) flag = true; vis[r][c] = false; } return flag; } int numEnclaves(vector<vector<int>>& grid) { nr = grid.size(); nc = grid[0].size(); vector<vector<bool>> _vis(nr, vector<bool>(nc, false)); vis = _vis; int ans = 0; for(int i = 0; i < nr; i++){ for(int j = 0; j < nc; j++){ if(grid[i][j] == 1 && !dfs(grid, i, j)){ ans++; } } } return ans; } }; -
dfs O(mn)先淹周围
class Solution { public: int nr, nc; void dfs(vector<vector<int>>& grid, int r, int c){ if(r < 0 || r >= nr || c < 0 || c >= nc) return; if(grid[r][c] == 0) return; grid[r][c] = 0; dfs(grid, r + 1, c); dfs(grid, r - 1, c); dfs(grid, r, c + 1); dfs(grid, r, c - 1); } int numEnclaves(vector<vector<int>>& grid) { nr = grid.size(), nc = grid[0].size(); for(int i = 0; i < nr; ++i){ if(grid[i][0] == 1) dfs(grid, i, 0); if(grid[i][nc - 1] == 1) dfs(grid, i, nc - 1); } for(int j = 0; j < nc; ++j){ if(grid[0][j] == 1) dfs(grid, 0, j); if(grid[nr - 1][j] == 1) dfs(grid, nr - 1, j); } int ans = 0; for(int i = 0; i < nr; ++i){ for(int j = 0; j < nc; ++j){ if(grid[i][j] == 1) ans++; } } return ans; } };
-
695. 岛屿的最大面积
-
思路+解法：
-
DFS O(mn)
class Solution { public: int ans = 0; int nr, nc; int cnt; void dfs(vector<vector<int>>& grid, int r, int c){ if(r < 0 || r >= nr || c < 0 || c >= nc) return; if(grid[r][c] == 0) return; cnt++; if(cnt > ans) ans = cnt; grid[r][c] = 0; dfs(grid, r + 1, c); dfs(grid, r - 1, c); dfs(grid, r, c + 1); dfs(grid, r, c - 1); } int maxAreaOfIsland(vector<vector<int>>& grid) { nr = grid.size(), nc = grid[0].size(); for(int i = 0; i < nr; i++){ for(int j = 0; j < nc; j++){ if(grid[i][j] == 1){ cnt = 0; dfs(grid, i, j); } } } return ans; } };
-
1905. 统计子岛屿
-
思路+解法：
-
DFS O(mn)
class Solution { private: int nr, nc; public: void dfs(vector<vector<int>>& grid2, int x, int y){ if(x < 0 || x >= nr || y < 0 || y >= nc) return; if(grid2[x][y] == 0) return; grid2[x][y] = 0; dfs(grid2, x + 1, y); dfs(grid2, x - 1, y); dfs(grid2, x, y + 1); dfs(grid2, x, y - 1); } int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) { nr = grid1.size(); nc = grid1[0].size(); for(int i = 0; i < nr; i++){ for(int j = 0; j < nc; j++){ if(grid2[i][j] == 1 && grid1[i][j] == 0){ dfs(grid2, i, j); } } } int ans = 0; for(int i = 0; i < nr; i++){ for(int j = 0; j < nc; j++){ if(grid2[i][j] == 1){ ans++; dfs(grid2, i, j); } } } return ans; } };
-
694.
305.
图遍历
797. 所有可能的路径
-
思路+解法：
-
DFS 数组表示的邻接表 O(n∗2^n)
class Solution { public: vector<vector<int>> ans; vector<int> path; void dfs(vector<vector<int>>& graph, int loc){ if(loc == graph.size() - 1){ ans.push_back(path); return; } for(int i = 0; i < graph[loc].size(); i++){ path.push_back(graph[loc][i]); dfs(graph, graph[loc][i]); path.pop_back(); } } vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) { path.push_back(0); dfs(graph, 0); return ans; } };
-
拓扑排序
207.课程表
-
思路+解法：
-
拓扑排序 O(n + m)
class Solution { private: vector<int> indegree; //入度 vector<vector<int>> edges;//储存边 public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { indegree.resize(numCourses); edges.resize(numCourses); for(int i = 0; i < prerequisites.size(); i++){ edges[prerequisites[i][1]].push_back(prerequisites[i][0]); indegree[prerequisites[i][0]]++; } queue<int> q; vector<int>ans; //最终排序后的序列 for(int i = 0; i < numCourses; i++) { if(indegree[i] == 0) q.push(i); } while(!q.empty()){ int x = q.front(); q.pop(); ans.push_back(x); for(int i = 0; i < edges[x].size(); i++){ indegree[edges[x][i]]--; if(indegree[edges[x][i]] == 0) q.push(edges[x][i]); } } return ans.size() == numCourses; } };
-
210.课程表 II
-
思路+解法：
-
拓扑排序 O(n + m)
class Solution { public: vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { vector<int> indegree(numCourses, 0); vector<vector<int>> g(numCourses); for(auto& x: prerequisites){ g[x[1]].emplace_back(x[0]); indegree[x[0]]++; } queue<int> q; vector<int> ans; for(int i = 0; i < numCourses; i++){ if(indegree[i] == 0){ q.push(i); } } while(!q.empty()){ int course = q.front(); q.pop(); ans.emplace_back(course); for(int i = 0; i < g[course].size(); i++){ int out = g[course][i]; if(indegree[out] >= 0) indegree[out]--; if(indegree[out] == 0) q.push(out); } } if(ans.size() == numCourses) return ans; return {}; } };
-
最短路 Dijkstra
- 稀疏图 - 邻接表、稠密图 - 邻接矩阵
- 记堆的版本吧，毕竟nlogn
743. 网络延迟时间
-
思路+解法：
-
Dijkstra O(mlogm)
class Solution { public: int networkDelayTime(vector<vector<int>>& times, int n, int k) { vector<vector<int>> g(n + 1, vector<int>(n + 1, 0x3f3f3f3f)); vector<int> dis(n + 1, 0x3f3f3f3f); vector<int> used(n + 1, 0); for(auto& x : times){ g[x[0]][x[1]] = x[2]; } //used[k] = 1; //得用第一个点更新一遍最短路径，要不然都是max dis[k] = 0; for(int i = 1; i <= n; i++){ int t = -1; for(int j = 1; j <= n; j++){ if(!used[j] && (t == -1 || dis[t] > dis[j])) t = j; } used[t] = 1; for(int j = 1; j <= n; j++){ if(dis[j] > dis[t] + g[t][j]){ dis[j] = dis[t] + g[t][j]; } } } int ans = 0; for(int i = 1; i <= n; i++){ ans = max(ans, dis[i]); } return ans == 0x3f3f3f3f ? -1 : ans; } };
-
1514. 概率最大的路径
-
思路+解法：
-
Dijkstra O(mlogm)
typedef pair<double, int> PDI; class Solution { public: double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) { vector<vector<pair<int, double>>> g(n); for (int i = 0; i < succProb.size(); i++) { /* 建立邻接表 */ g[edges[i][0]].emplace_back(edges[i][1], succProb[i]); g[edges[i][1]].emplace_back(edges[i][0], succProb[i]); } vector<int> vis(n, 0); vector<double> por(n, 0); //到每个点的最大概率 priority_queue<PDI, vector<PDI>, less<PDI>> q; por[start] = 1; q.push({1.0, start}); while(!q.empty()){ PDI x = q.top(); q.pop(); int p = x.first; int d = x.second; if(vis[d]) continue; vis[d] = true; for (auto [v, w] : g[d]) { if (por[v] < por[d] * w) { por[v] = por[d] * w; q.emplace(por[v], v); } } for(int i = 0; i < g[d].size(); i++){ if(por[g[d][i].first] < por[d] * g[d][i].second){ por[g[d][i].first] = por[d] * g[d][i].second; q.push({por[g[d][i].first], g[d][i].second}); } } } return por[end]; } };
-
-
一点收获：
- 用邻接矩阵会超时，体现出什么时候用邻接矩阵、邻接表
1631. 最小体力消耗路径
-
思路+解法：
-
Dijkstra O(mnlog(mn))
typedef pair<int, int> PII; class Solution { public: int minimumEffortPath(vector<vector<int>>& heights) { int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int n = heights.size(); int m = heights[0].size(); int ans = 0; vector<int> vis(n * m, 0); priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, 0}); while(!heap.empty()){ PII d = heap.top(); heap.pop(); if(vis[d.second] == 1) continue;; vis[d.second] = true; int x = d.second / m; int y = d.second % m; if(d.second == n * m - 1) return d.first; //if(x == n - 1 && y == m - 1) return d.first; for(int i = 0; i < 4; i++){ int next_x = x + dir[i][0]; int next_y = y + dir[i][1]; if(next_x < 0 || next_x >= n || next_y < 0 || next_y >= m || vis[next_x * m + next_y]) continue; heap.push({max(d.first, abs(heights[x][y] - heights[next_x][next_y])), next_x * m + next_y}); } } return 0; } };
-
最小生成树 Kruskal
261. 以图判树
1135. 最低成本联通所有城市
1584. 连接所有点的最小费用
-
思路+解法：
-
Kruskal O(mlogm)
class Solution { //边的基本结构 struct Edge{ int a, b; int w; bool operator < (const Edge& W) const{ return w < W.w; } }; // 并查集操作 vector<int> par; int find(int x){ if(par[x] == x) return x; else return par[x] = find(par[x]); } public: int minCostConnectPoints(vector<vector<int>>& points) { vector<Edge> Edges; int n = points.size(); int m = 0; //初始化边 for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(i != j){ Edges.push_back({i, j, abs(points[j][0] - points[i][0]) + abs(points[j][1] - points[i][1])}); m++; } } } sort(Edges.begin(), Edges.end()); //初始化并查集 par.resize(n); for(int i = 0; i < n; i++) par[i] = i; int cnt = 0, ans = 0; //从最小的边开始遍历 for(int i = 0; i < m; i++){ int a = Edges[i].a, b = Edges[i].b, w = Edges[i].w; a = find(a), b = find(b); //如果不连通的话连通起来 if(a != b){ par[a] = b; ans += w; cnt++; } } return ans; } };
-
二分图 染色法
785. 判断二分图
-
思路+解法：
-
染色法 O(n + m)
class Solution { private: vector<int> color; public: bool dfs(vector<vector<int>>& g, int x, int c){ color[x] = c; for(int i = 0; i < g[x].size(); i++){ int j = g[x][i]; if(color[j] == 0){ if(!dfs(g, j, -c)) return false; } else if(color[j] == c) return false; } return true; } bool isBipartite(vector<vector<int>>& graph) { int n = graph.size(); color.resize(n); for(int i = 0; i < n; i++){ if(color[i] == 0){ if(!dfs(graph, i, 1)) return false; } } return true; } };
-
886. 可能的二分法
-
思路+解法：
-
染色法 O(n + m)：
class Solution { private: vector<int> color; public: bool dfs(vector<vector<int>>& g, int x, int c){ color[x] = c; for(int i = 0; i < g[x].size(); i++){ int j = g[x][i]; if(color[j] == 0){ dfs(g, j, -c); } else if(color[j] == c) return false; } return true; } bool possibleBipartition(int n, vector<vector<int>>& dislikes) { color.resize(n + 1, 0); vector<vector<int>> g(n + 1); for(int i = 0; i < dislikes.size(); i++){ g[dislikes[i][0]].push_back(dislikes[i][1]); g[dislikes[i][1]].push_back(dislikes[i][0]); } for(int i = 1; i <= n; i++){ if(color[i] == 0){ if(!dfs(g, i, 1)) return false; } } return true; } };
-
BFS
752. 打开转盘锁
-
BFS O(10 ^ 4 * 4 ^ 2 + len * 4)
class Solution { public: int openLock(vector<string>& deadends, string target) { unordered_set<string> vis; vis.insert(deadends.begin(), deadends.end()); if(vis.count("0000")){ return -1; } vis.insert("0000"); queue<string> q; q.push("0000"); int cnt = 0; while(!q.empty()){ int size = q.size(); for(int i = 0; i < size; i++){ string s = q.front(); q.pop(); if(s == target) return cnt; //if(find(deadends.begin(), deadends.end(), s) != deadends.end()) continue; string s_copy = s; for(int i = 0; i < 4; i++){ if(s[i] == '9'){ s[i] = '0'; if(!vis.count(s)){ q.push(s); vis.insert(s); } s[i] = '9'; s[i] -= 1; if(!vis.count(s)){ q.push(s); vis.insert(s); } }else if(s[i] == '0'){ s[i] += 1; if(!vis.count(s)){ q.push(s); vis.insert(s); } s[i] = '0'; s[i] = '9'; if(!vis.count(s)){ q.push(s); vis.insert(s); } }else{ s[i] += 1; if(!vis.count(s)){ q.push(s); vis.insert(s); } s[i] -= 1; s[i] -= 1; if(!vis.count(s)){ q.push(s); vis.insert(s); } } s = s_copy; } } cnt++; } return -1; } };
773
127
数学运算技巧
191. 位1的个数
-
思路+解法：
-
循环找最低位的1 O(logn)
class Solution { public: int hammingWeight(uint32_t n) { int ans = 0; while(n != 0){ n = n & (n - 1); ans ++; } return ans; } };
-
231. 2 的幂
-
思路+解法：
-
2的倍数的话只有一个1 O(1)
class Solution { public: bool isPowerOfTwo(int n) { if(n <= 0) return false; return (n & (n - 1)) == 0; } };
-
136. 只出现一次的数字
-
思路+解法：
-
异或性质 O(n)
class Solution { public: int singleNumber(vector<int>& nums) { int ans = 0; for(auto& x : nums) ans ^= x; return ans; } };
-
172.阶乘后的零
-
思路+解法：
-
数学 O(logn)
//计算末尾0转换为计算有多少个10->多少个2*5->多少个5 //5贡献1个5，25贡献2个5，125贡献3个5.. //查看有多少个5、25、125...的倍数 class Solution { public: int trailingZeroes(int n) { int ans = 0; int x = 5; while(x <= n){ ans += (n / x); x *= 5; } return ans; } };
-
793.阶乘后 K 个零
-
思路+解法：
-
数学+二分找左右边界 O(lognlogn)
class Solution { public: long long cal_zero(long long n){ long long ans = 0; long long x = 5; while(x <= n){ ans += (n / x); x *= 5; } return ans; } int preimageSizeFZF(int k) { long long ans1 = 0; long long ans2 = 0; long long l = 0, r = INT_MAX; while(l <= r){ long long mid = (r - l) / 2 + l; long long tar = cal_zero(mid); if(tar == k){ ans1 = mid; r = mid - 1; }else if(tar > k){ r = mid - 1; }else if(tar < k){ l = mid + 1; } } l = 0, r = INT_MAX; while(l <= r){ long long mid = (r - l) / 2 + l; long long tar = cal_zero(mid); if(tar == k){ ans2 = mid; l = mid + 1; }else if(tar > k){ r = mid - 1; }else if(tar < k){ l = mid + 1; } } if(ans2 == ans1) return 0; else return ans2 - ans1 + 1; } };
-
-
亿点收获：
- **LONG_LONG_MAX **
- long long
204.计数质数
-
思路+解法：
-
埃氏筛选 O(nloglogn)
class Solution { public: int shai(int n){ vector<int> v(n, 1); int ans = 0; v[0] = 0; v[1] = 0; for(int i = 2; i < n; i++){ if(!v[i]) continue; ans++; int x = i + i; while(x < n){ v[x] = 0; x = x + i; } } return ans; } int countPrimes(int n) { if(n <= 2) return 0; return shai(n); } };
-
372. 超级次方
-
思路+解法：
-
快速幂 O(logn)
//a^1023 = (a^1000)^1 * (a^100)^0 * (a^10)^2 * (a^1)^3 class Solution { public: int qpow(int a, int b){ int ans = 1; int base = a; while(b > 0){ if(b & 1) ans = ans * base % 1337; base = base * base % 1337; b >>= 1; } return ans; } int superPow(int a, vector<int>& b) { int n = b.size(); int ans = 1; a %= 1337; for(int i = n - 1; i >= 0; i--){ ans = ans * qpow(a, b[i]) % 1337; a = qpow(a, 10) ; } return ans; } };
-
268. 丢失的数字
-
思路+解法：
-
位置和值异或
-
等差数列求和公式 Sn=n*a1+n(n-1)d/2或Sn=n(a1+an)/2
-
比较下标和元素值的合的差值
class Solution { public: int missingNumber(vector<int>& nums) { int ans = nums.size(); for(int i = 0; i < nums.size(); ++i){ ans += (i - nums[i]); } return ans; } };
-
645. 错误的集合
-
思路+解法：
-
数组下标 O(n)
class Solution { public: vector<int> findErrorNums(vector<int>& nums) { //一个元素对应下标，下标被重复访问则说明重复元素 //没有被访问的下标说明缺失该数 int dup, miss; for(int i = 0; i < nums.size(); i++){ int index = abs(nums[i]) - 1; if(nums[index] < 0){ dup = index + 1; } else{ nums[index] *= -1; } } for(int i = 0; i < nums.size(); i++){ if(nums[i] > 0){ miss = i + 1; } } return {dup, miss}; } }; -
异或运算 O(n)
class Solution { public: vector<int> findErrorNums(vector<int>& nums) { int xorsum = 0; int n = nums.size(); for(auto& x : nums) xorsum ^= x; for(int i = 1; i <= n; i++){ xorsum ^= i; } int a = 0, b = 0; int lowone = xorsum & (-xorsum); for(auto& x : nums){ if(x & lowone){ a ^= x; }else{ b ^= x; } } for(int i = 1; i <= n; i++){ if(i & lowone){ a ^= i; }else{ b ^= i; } } for(auto& x : nums){ if(a == x){ return {a, b}; } } return {b, a}; } };
-
382. 链表随机节点
-
解法+思路：
-
蓄水池抽样随机算法 O(n)
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* head; Solution(ListNode* head) { this->head = head; } int getRandom() { int ans = -1; ListNode* node = head; int k = 1; while(node){ if(rand() % k == 0){ ans = node->val; } k++; node = node->next; } return ans; } }; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(head); * int param_1 = obj->getRandom(); */
-
398. 随机数索引
-
解法+思路：
-
蓄水池抽样随机算法 O(n)
class Solution { public: vector<int> nums; Solution(vector<int>& nums) : nums(nums) { } int pick(int target) { int ans = -1; int k = 1; for(int i = 0; i < nums.size(); i++){ if(nums[i] == target){ if(rand() % k == 0) ans = i; k++; } } return ans; } }; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(nums); * int param_1 = obj->pick(target); */
-
26.删除有序数组中的重复项
-
思路+解法：
-
快慢指针 O(n)
class Solution { public: int removeDuplicates(vector<int>& nums) { if(nums.size() == 0) return 0; int slow = 0, fast = 0; while(fast < nums.size()){ if(nums[slow] == nums[fast]){ fast++; }else{ slow++; swap(nums[slow], nums[fast]); fast++; } } return slow + 1; } };class Solution { public: int removeDuplicates(vector<int>& nums) { if(nums.size() == 0) return 0; int slow = 0, fast = 0; while(fast < nums.size()){ if(nums[slow] != nums[fast]){ slow++; swap(nums[slow], nums[fast]); } fast++; } return slow + 1; } };
-
83.删除排序链表中的重复元素
-
思路+解法：
-
快慢指针 O(n)
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if(!head) return head; ListNode* slow = head, *fast = head; while(fast != nullptr){ if(slow->val != fast->val){ slow = slow->next; swap(slow->val, fast->val); } fast = fast->next; } slow->next = nullptr; return head; } };
-
27.移除元素
-
思路+解法：
-
快慢指针 O(n)
class Solution { public: int removeElement(vector<int>& nums, int val) { int slow = 0, fast = 0; while(fast < nums.size()){ if(nums[fast] != val){ swap(nums[slow], nums[fast]); slow++; fast++; }else{ fast++; } } return slow; } };
-
283.移动零
-
思路+解法：
-
快慢指针 O(n)
class Solution { public: void moveZeroes(vector<int>& nums) { int slow = 0, fast = 0; while(fast < nums.size()){ if(nums[fast] != 0){ swap(nums[slow], nums[fast]); slow++; fast++; }else{ fast++; } } } };
-
292.Nim游戏
-
思路+解法：
-
博弈 O(1)
class Solution { public: bool canWinNim(int n) { return n % 4 != 0; } };
-
877.石子游戏
-
思路+解法：
-
博弈 O(1)
class Solution { public: bool stoneGame(vector<int>& piles) { return true; } };
-
319.灯泡开关
-
思路+解法：
-
找规律 O(n)
class Solution { public: //第i轮，每i个灯泡切换一次开关 //第i个灯泡的反转次数等于它因子的个数 //只有翻转奇数次才会亮 int bulbSwitch(int n) { return sqrt(n); } };
-