剑指 Offer II 105. 岛屿的最大面积

  • 要细心，这里出现了粗心问题导致出现了错误。检查了好长时间。

    1. class Solution {
    2. public:
    3.   vector<int> dir = {-1, 0, 1, 0, -1};
    4.   vector<vector<bool>> flag;
    5.   int ret = 0, area = 1;
    6.   int maxAreaOfIsland(vector<vector<int>>& grid) {
    7.       flag.resize(grid.size(),(vector<bool>(grid[0].size(), false)));
    8.       for(int i = 0; i < grid.size(); i++) {
    9.           for(int j = 0; j < grid[0].size(); j++) {
    10.               if(grid[i][j]&&!flag[i][j]) {
    11.                   area = 1;
    12.                   dfs(grid, i, j);
    13.                   ret =max(ret, area);
    14.               }
    15.           }
    16.       }
    17.       return ret;
    18.   }
    19.   void dfs(vector<vector<int>>& grid, int i , int j) {
    20.           flag[i][j] = true;
    21.       for(int a = 0; a < 4; a++) {
    22.           int x = i+dir[a], y = j+dir[a+1];
    23.           if(x>=0&&x<grid.size()&&y>=0&&y<grid[0].size()&&!flag[x][y]&&grid[x][y]) {
    24.               area++;
    25.               dfs(grid, x, y);
    26.           }
    27.       }
    28.   }
    29. };

    剑指 Offer II 106. 二分图（染色法）

    我的错误写法

    这种写法当第一个数组为空的时候就会直接返回true，比如
    image.png

    1. class Solution {
    2. public:
    3.   bool isBipartite(vector<vector<int>>& graph) {
    4.       queue<int> q;
    5.       int n = graph.size(), color = 1;
    6.       vector<int> flag(n);
    7.       q.push(0);
    8.       while(!q.empty()) {
    9.           if(color == 1) color = 2;
    10.           else color = 1;
    11.           int m = q.size();
    12.           for(int i = 0; i < m; i++) {
    13.               int idx = q.front();
    14.               q.pop();
    15.               if(flag[idx] == 0||flag[idx] == color) {
    16.                   if(flag[idx] == 0) {
    17.                       for(auto j : graph[idx]) {
    18.                           q.push(j);
    19.                       }
    20.                       flag[idx] = color;
    21.                   } 
    22.               } else {
    23.                   return false;
    24.               }
    25.           }
    26.       }
    27.       return true;
    28.   }
    29. };

    正确写法

    每个节点只需要和自己下一层的颜色相比即可。

    1. class Solution {
    2. public:
    3.   bool isBipartite(vector<vector<int>>& graph) {
    4.       int n = graph.size();
    5.       vector<int> color(n);
    6.       queue<int> q;
    7.       for(int i = 0; i < n; i++) {//先经历一个for循环
    8.           if(color[i]==0) {
    9.               color[i] = 1;
    10.               q.push(i);
    11.           }
    12.           while(!q.empty()) {
    13.               int node = q.front();//前面一层的节点
    14.               q.pop();
    15.               for(auto it : graph[node]) {//遍历和当前节点相连接的下一层节点。
    16.                   if(color[it]==0) {
    17.                       q.push(it);
    18.                       color[it]=color[node]==1?2:1;//未到访的节点则
    19.                       //需要和前面一层的节点颜色不同
    20.                   } else if(color[it]==color[node]){//和前面一层的节点颜色相同，报错
    21.                       return false;
    22.                   }
    23.               }
    24.           }
    25.       }
    26.       return true;
    27.   }
    28. };

    剑指 Offer II 107. 矩阵中的距离（非常巧妙）

    中心开花策略

  • 首先将为0周围的都走一遍，他们的距离为1，然后将距离为1 的节点在入队，后续依次类推

  • 注意判断条件，如果下一个节点为0或者是已经走过，就直接跳过。 ```cpp class Solution { private: static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public: vector> updateMatrix(vector>& matrix) { int m = matrix.size(), n = matrix[0].size(); vector> dist(m, vector(n)); vector> seen(m, vector(n)); queue> q; // 将所有的 0 添加进初始队列中 for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (matrix[i][j] == 0) { q.emplace(i, j); seen[i][j] = 1;//是0的点标记为seen，还有去重的功能。 } } }

  1.     // 广度优先搜索
  2.     while (!q.empty()) {
  3.         auto [i, j] = q.front();//先从0开始出发，周围的都为1。
  4.         q.pop();
  5.         for (int d = 0; d < 4; ++d) {
  6.             int ni = i + dirs[d][0];
  7.             int nj = j + dirs[d][1];
  8.             if (ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj]) {//如果为0或者之前走到过就跳过不满足条件。
  9.                 dist[ni][nj] = dist[i][j] + 1;//下一步节点的距离都是前面的距离+1。
  10.                 q.emplace(ni, nj);//为1的点在push入队列。
  11.                 seen[ni][nj] = 1;
  12.             }
  13.         }
  14.     }
  16.     return dist;
  17. }

};

<a name="LQbKs"></a>
### [剑指 Offer II 108. 单词演变](https://leetcode.cn/problems/om3reC/)
<a name="IqvaX"></a>
#### 笨比解法

- 时间复杂度过高
```cpp
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string, vector<string>> hash;
        int ret = 0;
        for(int i = 0; i < wordList.size(); i++) {
            if(helper(beginWord, wordList[i])) {
                hash[beginWord].emplace_back(wordList[i]);
            }
            for(int j = i + 1; j < wordList.size(); j++) {
                if(helper(wordList[i], wordList[j])) {
                    hash[wordList[i]].emplace_back(wordList[j]);
                    hash[wordList[j]].emplace_back(wordList[i]);
                }
            }
        }
        queue<pair<string,int>> q;
        unordered_set<string> flag;
        flag.insert(beginWord);
        q.emplace(beginWord,1);
        while(!q.empty()) {
            auto it = q.front();
            q.pop();
            if(it.first == endWord) {
                return it.second;
            }
            for(auto str : hash[it.first]) {
                if(!flag.count(str)) {
                    flag.insert(str);
                    q.emplace(str, it.second+1);
                }
            }
        }
        return 0;
    }
    bool helper(string str1, string str2) {
        int num = 0;
        for(int i = 0; i < str1.size(); i++) {
            if(str1[i] == str2[i]) {
                num++;
            }
        }
        return num == str1.size()-1;
    }
};

题解优化

  • 优化在于虚拟节点

    class Solution {
public:
  unordered_map<string, int> wordId;
  vector<vector<int>> edge;
  int nodeNum = 0;

  void addWord(string& word) {
      if (!wordId.count(word)) {
          wordId[word] = nodeNum++;
          edge.emplace_back();
      }
  }

  void addEdge(string& word) {
      addWord(word);
      int id1 = wordId[word];
      for (char& it : word) {
          char tmp = it;
          it = '*';
          addWord(word);
          int id2 = wordId[word];
          edge[id1].push_back(id2);
          edge[id2].push_back(id1);
          it = tmp;
      }
  }

  int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
      for (string& word : wordList) {
          addEdge(word);
      }
      addEdge(beginWord);
      if (!wordId.count(endWord)) {
          return 0;
      }
      vector<int> dis(nodeNum, INT_MAX);
      int beginId = wordId[beginWord], endId = wordId[endWord];
      dis[beginId] = 0;

      queue<int> que;
      que.push(beginId);
      while (!que.empty()) {
          int x = que.front();
          que.pop();
          if (x == endId) {
              return dis[endId] / 2 + 1;
          }
          for (int& it : edge[x]) {
              if (dis[it] == INT_MAX) {
                  dis[it] = dis[x] + 1;
                  que.push(it);
              }
          }
      }
      return 0;
  }
};

    双向bfs

    class Solution {
public:
  int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
      // 将vector转化成哈希表方便后续操作 由于不用考虑个数 且元素总数量未知 因此用unordered_set
      unordered_set<string> wordsDict(wordList.begin(),wordList.end());
      // 先验证题目要求
      if (wordsDict.count(endWord) == 0) return 0;
      // 初始化两个哈希表存储单层的搜索情况来表示双向奔赴的进度 如果二者有交叉了 说明奔赴成功了
      unordered_set<string> beginDict{beginWord}, endDict{endWord};
      // 初始化步数为1 
      int step = 1;
      while (!beginDict.empty()) {
          ++step; // 先把步数加上
          unordered_set<string> temp; // 生成一个中间者来存放单层深度的搜索结果 顺便判断二者是否有交叉
          // 记得在搜索前把自己的人在鱼塘中清除 注意这个for不能合并到下一个for中
          for (auto word : beginDict) wordsDict.erase(word); 
          for (auto word : beginDict) {
              for (int i = 0; i < word.size(); ++i) {  // 判断流程开始 将每一位字母轮番变化
                  string str = word;                   // 
                  for (char c = 'a'; c <= 'z'; ++c) {  // 亲测这种方法比用count记录不同位的个数返回T/F要快不少
                      str[i] = c;
                      if (wordsDict.count(str) == 0) continue; // 鱼塘里没有这个元素 跳过
                      if (endDict.count(str)) return step; // 鱼塘里有 你也有 奔赴成功
                      temp.insert(str); // 鱼塘里有 你没有 就把单层深度的所有结果存放起来 等待下一层搜索
                  }
              }
          }
          // 关键： 如果temp的规模比endDict大，下一次单层搜索任务就交给endDict 否则继续由beginDict执行
          if (temp.size() > endDict.size()) {beginDict = endDict; endDict = temp;}
          else beginDict = temp;
      }
      return 0;
  }
};

    剑指 Offer II 109. 开密码锁

    class Solution {
public:
  int openLock(vector<string>& deadends, string target) {
      unordered_set<string> hash;
      for(auto str : deadends) {//先把死亡数字输入哈希表
          hash.insert(str);
      }
      queue<pair<string,int>> q;//第二个值为旋转次数
      q.push(pair("0000", 0));//初始值
      while(!q.empty()) {
          auto it = q.front();
          q.pop();
          if(hash.count(it.first)) continue;//如果是死亡数字，或者之前已经转到过，则跳过
          hash.insert(it.first);//当前的路径输入哈希表，防止重复。
          if(it.first == target) {
              return it.second;
          }
          for(int i = 0; i < 4; i++) {//后续的所有情况
              string str = it.first, str1 = it.first;
              if(it.first[i] == '0') {
                  str1[i] = '9';
              } else {
                  str1[i] = str1[i]-1;
              }
              if(it.first[i] == '9') {
                  str[i] = '0';
              } else {
                  str[i] = str[i]+1;
              }
              q.push(pair(str, it.second+1));
              q.push(pair(str1, it.second+1));
          }
      }
      return -1;
  }
};

    剑指 Offer II 110. 所有路径(dfs)

    这题很简单，只需要注意路径提前有一个0。

    class Solution {
public:
  vector<vector<int>> ans;
  vector<int> stk;

  void dfs(vector<vector<int>>& graph, int x, int n) {
      if (x == n) {
          ans.push_back(stk);
          return;
      }
      for (auto& y : graph[x]) {
          stk.push_back(y);
          dfs(graph, y, n);
          stk.pop_back();
      }
  }

  vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
      stk.push_back(0);
      dfs(graph, 0, graph.size() - 1);
      return ans;
  }
};

    剑指 Offer II 111. 计算除法（没写出来）

  • 需要先建图

    class Solution {
public:
  vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
      int nvars = 0;
      unordered_map<string, int> variables;//通过哈希表将不同的字符串映射成整数

      int n = equations.size();
      for (int i = 0; i < n; i++) {
          if (variables.find(equations[i][0]) == variables.end()) {
              variables[equations[i][0]] = nvars++;
          }
          if (variables.find(equations[i][1]) == variables.end()) {
              variables[equations[i][1]] = nvars++;
          }
      }//结束之后的nvars就是节点的数量

      // 对于每个点，存储其直接连接到的所有点及对应的权值
      vector<vector<pair<int, double>>> edges(nvars);//第一维就代表被编号的点，第二维代表连接的点与对应的权值。
      for (int i = 0; i < n; i++) {
          int va = variables[equations[i][0]], vb = variables[equations[i][1]];
          edges[va].push_back(make_pair(vb, values[i]));//va/vb
          edges[vb].push_back(make_pair(va, 1.0 / values[i]));//vb/va
      }

      vector<double> ret;//返回值
      for (const auto& q: queries) {
          double result = -1.0;
          if (variables.find(q[0]) != variables.end() && variables.find(q[1]) != variables.end()) {//在首尾都能够哈希表中找到的时候
              int ia = variables[q[0]], ib = variables[q[1]];
              if (ia == ib) {//如果是同一个字符串
                  result = 1.0;
              } else {
                  queue<int> points;
                  points.push(ia);
                  vector<double> ratios(nvars, -1.0);
                  ratios[ia] = 1.0;//ratios[i]就表示从开始到编号为i的字符串的计算结果。

                  while (!points.empty() && ratios[ib] < 0) {//这里就代表还没有搜索到ib的时候
                      int x = points.front();
                      points.pop();
                      //以图的形式向后推导
                      for (const auto [y, val]: edges[x]) {
                          if (ratios[y] < 0) {
                              ratios[y] = ratios[x] * val;
                              points.push(y);
                          }
                      }
                  }
                  result = ratios[ib];
              }
          }
          ret.push_back(result);
      }
      return ret;
  }
};

    剑指 Offer II 112. 最长递增路径

    dfs写法

    class Solution {
public:
  static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  int rows, columns;

  int longestIncreasingPath(vector< vector<int> > &matrix) {
      if (matrix.size() == 0 || matrix[0].size() == 0) {
          return 0;
      }
      rows = matrix.size();
      columns = matrix[0].size();
      auto memo = vector< vector<int> > (rows, vector <int> (columns));
      int ans = 0;
      for (int i = 0; i < rows; ++i) {
          for (int j = 0; j < columns; ++j) {
              ans = max(ans, dfs(matrix, i, j, memo));
          }
      }
      return ans;
  }

  int dfs(vector< vector<int> > &matrix, int row, int column, vector< vector<int> > &memo) {
      if (memo[row][column] != 0) {
          return memo[row][column];
      }
      ++memo[row][column];
      for (int i = 0; i < 4; ++i) {
          int newRow = row + dirs[i][0], newColumn = column + dirs[i][1];
          if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] > matrix[row][column]) {
              memo[row][column] = max(memo[row][column], dfs(matrix, newRow, newColumn, memo) + 1);
          }
      }
      return memo[row][column];
  }
};

    拓扑排序

    class Solution {
public:
  static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  int rows, columns;

  int longestIncreasingPath(vector< vector<int> > &matrix) {
      if (matrix.size() == 0 || matrix[0].size() == 0) {
          return 0;
      }
      rows = matrix.size();
      columns = matrix[0].size();
      auto outdegrees = vector< vector<int> > (rows, vector <int> (columns));
      for (int i = 0; i < rows; ++i) {
          for (int j = 0; j < columns; ++j) {
              for (int k = 0; k < 4; ++k) {
                  int newRow = i + dirs[k][0], newColumn = j + dirs[k][1];
                  if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] > matrix[i][j]) {
                      ++outdegrees[i][j];
                  }
              }
          }
      }
      queue < pair<int, int> > q;
      for (int i = 0; i < rows; ++i) {
          for (int j = 0; j < columns; ++j) {
              if (outdegrees[i][j] == 0) {
                  q.push({i, j});
              }
          }
      }
      int ans = 0;
      while (!q.empty()) {
          ++ans;
          int size = q.size();
          for (int i = 0; i < size; ++i) {
              auto cell = q.front(); q.pop();
              int row = cell.first, column = cell.second;
              for (int k = 0; k < 4; ++k) {
                  int newRow = row + dirs[k][0], newColumn = column + dirs[k][1];
                  if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] < matrix[row][column]) {
                      --outdegrees[newRow][newColumn];
                      if (outdegrees[newRow][newColumn] == 0) {
                          q.push({newRow, newColumn});
                      }
                  }
              }
          }
      }
      return ans;
  }
};

    剑指 Offer II 113. 课程顺序（拓扑排序）

    经典的拓扑排序题目，先将入度为0的入队，先把这个课上了，然后以这个课为前置条件的课入度都减1，然后再判断是否为0。以此类推

    class Solution {
public:
  vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
      unordered_map<int , vector<int>> hash;
      queue<int> q;
      vector<int> indgree(numCourses), ret;//indgree是入度
      for(auto vec : prerequisites) {
          hash[vec[1]].push_back(vec[0]);
          indgree[vec[0]]++;
      }
      for(int i = 0; i < numCourses; i++) {
          if(indgree[i] == 0) {
              q.push(i);
          }
      }
      while(!q.empty()) {
          int idx = q.front();
          q.pop();
          ret.push_back(idx);
          for(auto it : hash[idx]) {
              indgree[it]--;
              if(indgree[it] == 0) q.push(it);
          }
      }
      if(ret.size() < numCourses) {
          ret.clear();
      }
      return ret;
  }
};

    剑指 Offer II 114. 外星文字典

    class Solution {
public:
  string alienOrder(vector<string>& words) {
      unordered_map<char, unordered_set<char>> graph;//这里应该是每个字母的后面的字母。
      unordered_map<char, int> inDegress;

      // 建图
      for (auto& word : words) {
          for (auto& ch : word) {
              if (!graph.count(ch)) {
                  graph[ch] = {};
              } 
              if (!inDegress.count(ch)) {
                  inDegress[ch] = 0;
              }
          }
      }

      // 计算邻接表和入度
      for (int i = 1; i < words.size(); ++i) {//通过对比相邻的两个字符串来计算入度。
          int j = 0;
          int len = min(words[i - 1].size(), words[i].size());
          for (; j < len; ++j) {
              char ch1 = words[i - 1][j];
              char ch2 = words[i][j];
              if (ch1 != ch2) {//出现不等直接break，因为ch1排序在ch2之前。
                  if (!graph[ch1].count(ch2)) {
                      graph[ch1].insert(ch2);
                      inDegress[ch2]++;
                  }
                  break;
              }
          }
          // 特殊判断
          //如果后面的单词是前面单词的前缀，并且后面的单词小于前面的单词的长度。直接返回空即可
          if (j == len && words[i - 1].size() > words[i].size()) {//如果是无效字母顺序
              return {};
          }
      }

      string ret{""};
      queue<char> que;
      // 入度为 0 的点，先入队
      for (auto& d : inDegress) {
          if (d.second == 0) {
              que.push(d.first);
          }
      }
      // BFS，进行搜索
      while (!que.empty()) {
          char ch = que.front();
          que.pop();
          ret.push_back(ch);

          for (auto& c : graph[ch]) {
              inDegress[c]--;
              if (inDegress[c] == 0) {
                  que.push(c);
              }
          }
      }

      if (ret.size() != inDegress.size()) {//存在字符的入度无法为0，非法
          return "";
      }
      return ret;
  }
};

    剑指 Offer II 115. 重建序列（拓扑排序）

    class Solution {
public:
  bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
      //按照seqs的要求 唯一的复现出序列 时间n*n就能过
      //关键点是唯一
      //有向图 不成环 从头能唯一的遍历所有节点,拓扑排序一旦出现两个0入结点 即为不唯一
      int n = org.size();
      map<int, vector<int>> mp;  //手动去重 为了后面的索引  index-》vector 指向的节点

      int size = seqs.size();
      if (size == 0) return false;

      for (int i = 0; i < size; ++i){
          int s = seqs[i].size();

          if (s < 1) continue; 
          if (s == 1){
              if (seqs[i][0] > n || seqs[i][0] < 1) return false;
          }
          for (int j = 0; j < s - 1; ++j){
              if (seqs[i][j] > n || seqs[i][j] < 1 || seqs[i][j + 1] > n || seqs[i][j + 1] < 1) return false;
              if (find(mp[seqs[i][j]].begin(), mp[seqs[i][j]].end(), seqs[i][j+1]) == mp[seqs[i][j]].end()){
                  mp[seqs[i][j]].emplace_back(seqs[i][j+1]);
              }
          }
      }

      vector<int> count(n+1, 0); // 保存入度，已经被取出 就是 -1
      count[0] = -1;

      for (auto it = mp.begin(); it != mp.end(); it++){
          int s = it->second.size();
          for (int i = 0; i < s; ++i){
              count[it->second[i]] ++;
          }
      }

      queue<int> que;
      vector<int> res;

      for (int i = 1; i < n+1; ++i){
          if (count[i] == 0) que.push(i);
      }

      while (res.size() != n){
          int s = que.size();
          for (int i = 0; i < s; ++i){
              if (count[que.front()] == 0) que.push(que.front());
              que.pop();
          }

          if (que.size() != 1) return false; //有且必须只有 1个 0入度作为当前选择

          int choice = que.front();
          count[choice] = -1;
          res.emplace_back(choice);
          que.pop();

          //移除该节点，更新所有入度,把这个结点指向的所有下一个节点放入queue中,在这之中查询下一个唯一0入点
          s = mp[choice].size();
          for (int i = 0; i < s; ++i){
              count[mp[choice][i]] --; // 入度减少
              que.push(mp[choice][i]);
          }
      }

      //比对两个结果
      for (int i = 0; i < n; ++i){
          if (res[i] != org[i]) return false;
      }

      return true;
  }
};

    剑指 Offer II 116. 省份数量（dfs）

    这一题和之前的岛屿最大面积有些不同，但是思想是类似的。先用循环遍历所有未标记的城市，对每个城市都是用dfs来搜索相连的城市，并且标记。累加即可。

    class Solution {
public:
  vector<int> dir = {-1, 0, 1, 0, -1};
  int findCircleNum(vector<vector<int>>& isConnected) {
      int n = isConnected.size(), ret = 0;
      vector<bool> flags(n);
      for(int i = 0; i < n; i++){
              if(!flags[i]){
                  ret++;
                  dfs(isConnected, flags, i);
              }
      }
      return ret;
  }
  void dfs(vector<vector<int>>& isConnected,vector<bool>&flags, int c){
      if(flags[c] == true) return;
      flags[c] = true;
      for(int i = 0; i < isConnected.size(); i++){
          if(!flags[i]&&isConnected[c][i]==1){
              dfs(isConnected, flags, i);
          }
      }
      return;
  }
};

    剑指 Offer II 117. 相似的字符串（并查集）

    class Solution {
public:
  vector<int> f;//父亲数组

  int find(int x) {
      return f[x] == x ? x : f[x] = find(f[x]);
  }

  bool check(const string &a, const string &b, int len) {//判断是不是相似的
      int num = 0;
      for (int i = 0; i < len; i++) {
          if (a[i] != b[i]) {
              num++;
              if (num > 2) {
                  return false;
              }
          }
      }
      return true;
  }

  int numSimilarGroups(vector<string> &strs) {
      int n = strs.size();
      int m = strs[0].length();
      f.resize(n);
      for (int i = 0; i < n; i++) {//初始时都是孤立的，父节点都是自己
          f[i] = i;
      }
      for (int i = 0; i < n; i++) {
          for (int j = i + 1; j < n; j++) {//这里两层循环，判断所有组合。
              int fi = find(i), fj = find(j);
              if (fi == fj) {//如果是同一个根
                  continue;
              }
              if (check(strs[i], strs[j], m)) {//如果根不同且相似
                  f[fi] = fj;//做union操作。fi的根节点的父节点设置为fj的根节点
              }
          }
      }
      int ret = 0;
      for (int i = 0; i < n; i++) {
          if (f[i] == i) {
              ret++;
          }
      }
      return ret;
  }
};

    剑指 Offer II 118. 多余的边（并查集）

    笨比写法

    单独写一个helper函数判断是否连通。

    class Solution {
public:
  unordered_map<int, vector<int>> hash;
  vector<int> findRedundantConnection(vector<vector<int>>& edges) {
      int n = edges.size();
      vector<int> ret;
      for(int i = 0; i < n; i++) {
          int a1 = edges[i][0], a2 = edges[i][1];
          hash[a1].push_back(a2);
          hash[a2].push_back(a1);
      }
      for(int i = n-1; i >= 0; i--) {
          if(helper(edges[i][0], edges[i][1])) {
              return edges[i];
          }    
      }
      return ret;
  }
  bool helper(int a1, int a2) {//判断除了直接相邻之外有没有连通。
      queue<pair<int,int>> q;
      unordered_set<int> hashset;
      hashset.insert(a1);
      q.emplace(a1, 0);
      while(!q.empty()) {
          auto it = q.front();
          q.pop();
          if(it.first == a2) {
              return true;
          }
          for(auto num : hash[it.first]) {
              if(num == a2 && it.second == 0) continue;//这里就是排除相邻的情况
              if(!hashset.count(num)) {//这里是避免重复
                  hashset.insert(num);
                  q.emplace(num, it.second+1);
              }
          }
      }
      return false;
  }
};

    拓扑排序

    先将入度为1的点删除，最后留下来的一定是环，然后再edges中从后往前搜索即可。

    class Solution {
public:
  unordered_map<int, vector<int>> hash;
  vector<int> findRedundantConnection(vector<vector<int>>& edges) {
      int n = edges.size();
      vector<int> indgree(n+1);
      unordered_set<int> hashset;
      queue<int> q;
      for(int i = 0; i < n; i++) {
          int a1 = edges[i][0], a2 = edges[i][1];
          hash[a1].push_back(a2);
          hash[a2].push_back(a1);
          indgree[a1]++;
          indgree[a2]++;
      }
      for(int i = 1; i <= n; i++) {
          hashset.insert(i);
          if(indgree[i] == 1) {
              q.push(i);
          }
      }
      while(!q.empty()) {
          int idx = q.front();
          q.pop();
          hashset.erase(idx);
          for(auto i : hash[idx]) {
              indgree[i]--;
              if(indgree[i] == 1) {
                  q.push(i);
              }
          }
      }
      for(int i = n-1; i >= 0; i--) {
          if(hashset.count(edges[i][0])&&hashset.count(edges[i][1])) {
              return edges[i];
          }
      }
      return {};
  }
};

    并查集

    参考连接
    https://blog.csdn.net/weixin_51379191/article/details/117262725
    在一棵树中，边的数量比节点的数量少 11。如果一棵树有 nn 个节点，则这棵树有 n-1n−1 条边。这道题中的图在树的基础上多了一条边，因此边的数量也是 nn。
    树是一个连通且无环的无向图，在树中多了一条边之后就会出现环，因此多余的边即为导致环出现的边。
    可以通过并查集寻找多余的边。初始时，每个节点都属于不同的连通分量。遍历每一条边，判断这条边连接的两个顶点是否属于相同的连通分量。

  • 如果两个顶点属于不同的连通分量，则说明在遍历到当前的边之前，这两个顶点之间不连通，因此当前的边不会导致环出现，合并这两个顶点的连通分量。

  • 如果两个顶点属于相同的连通分量，则说明在遍历到当前的边之前，这两个顶点之间已经连通，因此当前的边导致环出现，为多余的边，将当前的边作为答案返回

    class Solution {
public:
  //查找操作
  int Find(vector<int>& parent, int index) {//找出给定节点所在树的根节点。
      while(parent[index] != index)//如果不为根节点
          index = parent[index];//这一步是向上寻找。
      }
      return index;
  }
  //合并操作
  void Union(vector<int>& parent, int index1, int index2) {//联合，让index2的根节点成为index1的根节点的父节点
      parent[Find(parent, index1)] = Find(parent, index2);
  }

  vector<int> findRedundantConnection(vector<vector<int>>& edges) {
      int n = edges.size();
      vector<int> parent(n + 1);//存储每个节点的父节点
      for (int i = 1; i <= n; ++i) {
          parent[i] = i;//初始的时候每个节点都是孤立的，因此父节点是他们本身。
      }
      for (auto& edge: edges) {
          int node1 = edge[0], node2 = edge[1];
          if (Find(parent, node1) != Find(parent, node2)) {
              Union(parent, node1, node2);
          } else {//两个节点已经有相同的根节点了，那就证明加入当前会出现环，就是我们想要的答案。
              return edge;
          }
      }
      return vector<int>{};
  }
};

    剑指 Offer II 119. 最长连续序列（思路非常巧妙）

  • 字节二面原题

  • 将所有的元素都输入哈希表，找到开头元素之后，根据哈希表寻找连续的数字num+1。寻找开头元素根据能不能找到num-1来确定。
    class Solution {
public:
  int longestConsecutive(vector<int>& nums) {
      unordered_set<int> hashset;
      int ret = 0;
      for(auto num : nums) {
          hashset.insert(num);
      }
      for(auto num : hashset) {
          if(!hashset.count(num-1)) {
              int length = 1;
              while(hashset.count(num+1)) {
                  num++;
                  length++;
              }
              ret = max(length, ret);
          }
      }
      return ret;
  }
};