Java教程

labuladong的一些刷题记录

本文主要是介绍labuladong的一些刷题记录,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

labuladong

岛屿问题

200. 岛屿数量

  • 思路+解法:

    1. 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;
          }
      };
      
    2. 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;
          }
      };
      
    3. 并查集 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. 统计封闭岛屿的数目

  • 思路+解法:

    1. 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. 飞地的数量

  • 思路+解法:

    1. 对于每个点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;
          }
      };
      
    2. 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. 岛屿的最大面积

  • 思路+解法:

    1. 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. 统计子岛屿

  • 思路+解法:

    1. 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. 所有可能的路径

  • 思路+解法:

    1. 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.课程表

  • 思路+解法:

    1. 拓扑排序 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

  • 思路+解法:

    1. 拓扑排序 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. 网络延迟时间

  • 思路+解法:

    1. 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. 概率最大的路径

  • 思路+解法:

    1. 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]; 
          }
      };
      
  • 一点收获:

    1. 用邻接矩阵会超时,体现出什么时候用邻接矩阵、邻接表

1631. 最小体力消耗路径

  • 思路+解法:

    1. 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. 连接所有点的最小费用

  • 思路+解法:

    1. 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. 判断二分图

  • 思路+解法:

    1. 染色法 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. 可能的二分法

  • 思路+解法:

    1. 染色法 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. 循环找最低位的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 的幂

  • 思路+解法:

    1. 2的倍数的话只有一个1 O(1)

      class Solution {
      public:
          bool isPowerOfTwo(int n) {
              if(n <= 0) return false;
              return (n & (n - 1)) == 0;
          }
      };
      

136. 只出现一次的数字

  • 思路+解法:

    1. 异或性质 O(n)

      class Solution {
      public:
          int singleNumber(vector<int>& nums) {
              int ans = 0;
              for(auto& x : nums) ans ^= x;
              return ans;
          }
      };
      

172.阶乘后的零

  • 思路+解法:

    1. 数学 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 个零

  • 思路+解法:

    1. 数学+二分找左右边界 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;
          }
      };
      
  • 亿点收获:

    1. **LONG_LONG_MAX **
    2. long long

204.计数质数

  • 思路+解法:

    1. 埃氏筛选 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. 超级次方

  • 思路+解法:

    1. 快速幂 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. 丢失的数字

  • 思路+解法:

    1. 位置和值异或

    2. 等差数列求和公式 Sn=n*a1+n(n-1)d/2或Sn=n(a1+an)/2

    3. 比较下标和元素值的合的差值

      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. 错误的集合

  • 思路+解法:

    1. 数组下标 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};
          }
      };
      
    2. 异或运算 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. 链表随机节点

  • 解法+思路:

    1. 蓄水池抽样随机算法 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. 随机数索引

  • 解法+思路:

    1. 蓄水池抽样随机算法 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.删除有序数组中的重复项

  • 思路+解法:

    1. 快慢指针 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.删除排序链表中的重复元素

  • 思路+解法:

    1. 快慢指针 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.移除元素

  • 思路+解法:

    1. 快慢指针 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.移动零

  • 思路+解法:

    1. 快慢指针 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游戏

  • 思路+解法:

    1. 博弈 O(1)

      class Solution {
      public:
          bool canWinNim(int n) {
              return n % 4 != 0;
          }
      };
      

877.石子游戏

  • 思路+解法:

    1. 博弈 O(1)

      class Solution {
      public:
          bool stoneGame(vector<int>& piles) {
              return true;
          }
      };
      

319.灯泡开关

  • 思路+解法:

    1. 找规律 O(n)

      class Solution {
      public:
          //第i轮,每i个灯泡切换一次开关
          //第i个灯泡的反转次数等于它因子的个数
          //只有翻转奇数次才会亮
          int bulbSwitch(int n) {
              return sqrt(n);
          }
      };
      
这篇关于labuladong的一些刷题记录的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!