室友面试作弊，被我举报了。。

最近一网友在网上发文称：自己和室友在同一家公司面试，结果室友过了，他没过，本来也无所谓，结果室友在他面前炫耀，说自己面试用ai工具作弊了，面试官没发现。他一怒之下跟hr举报了，结果他室友的offer被取消了。并且还和他大吵一架，说他多管闲事。 作弊面试过了也不是什么光荣的事，我觉得没必要炫耀，即便是靠自己真本事面试通过，也要学会低调。要做到不露圭角，韬光养晦。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第1129题：颜色交替的最短路径，难度是中等。

给定一个整数 n，即有向图中的节点数，其中节点标记为 0 到 n - 1。图中的每条边为红色或者蓝色，并且可能存在自环或平行边。 给定两个数组 redEdges 和 blueEdges，其中： 1，redEdges[i] = [ai, bi] 表示图中存在一条从节点 ai 到节点 bi 的红色有向边。 2，blueEdges[j] = [uj, vj] 表示图中存在一条从节点 uj 到节点 vj 的蓝色有向边。
返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。 示例1：

输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []

输出：[0,1,-1]

示例2：

输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]

输出：[0,1,-1]

• 1 <= n <= 100

• 0 <= redEdges.length, blueEdges.length <= 400

• redEdges[i].length == blueEdges[j].length == 2

• 0 <= ai, bi, uj, vj < n

问题分析

这题说的是从起点0开始，查找最长的路径，路径必须是红边和蓝边交替出现。我们可以使用BFS遍历，如果到下一个顶点的边是红色，那么从下一个顶点到下下一个顶点的边必须是蓝色。相反，如果到下一个顶点的边是蓝色，那么从下一个顶点到下下一个顶点的边必须是红色。 从起点0开始，我们有两条路径，一条是沿着蓝色的边，一条是沿着红色的边，查找最长的路径。在解之前我们先把二维数组转化为邻接表的形式。 JAVA：

public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
    List 
                  
 [][] g =  
         new List[2][n];
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < n; j++)
            g[i][j] = new ArrayList<>();
    for (int[] redEdge : redEdges) {// 红边
        g[0][redEdge[0]].add(redEdge[1]);
    }
    for (int[] blueEdge : blueEdges) {// 蓝边
        g[1][blueEdge[0]].add(blueEdge[1]);
    }
    Queue q = new LinkedList<>();
    // 两个方向，分别从红和蓝开始
    q.offer(newint[]{0, 0});
    q.offer(newint[]{0, 1});
    boolean[][] vis = newboolean[n][2];
    int[] ans = newint[n];
    Arrays.fill(ans, -1);
    int level = 0;// BFS遍历的层数
    while (!q.isEmpty()) {
        int size = q.size();// bfs每层节点的个数
        while (size-- > 0) {
            int[] cur = q.poll();
            int index = cur[0], color = cur[1];
            if (ans[index] == -1)
                ans[index] = level;
            vis[index][color] = true;
            color ^= 1;// 路径要红蓝交替
            for (int next : g[color][index]) {
                if (!vis[next][color])
                    q.offer(newint[]{next, color});
            }
        }
        level++;
    }
    return ans;
}

public:
    vector shortestAlternatingPaths(int n, vector> &redEdges, vector> &blueEdges) {
        // 创建邻接表，g[0]存储红色边，g[1]存储蓝色边
        vector> g[2];
        g[0].resize(n);
        g[1].resize(n);
        // 填充红色边的邻接表
        for (constauto &edge: redEdges) {
            g[0][edge[0]].push_back(edge[1]);
        }
        // 填充蓝色边的邻接表
        for (constauto &edge: blueEdges) {
            g[1][edge[0]].push_back(edge[1]);
        }
        // 队列存储当前节点和到达该节点的边的颜色
        queue 
                   
          int 
          ,  
          int 
          >> q;  
          // pair 
            <节点, 颜色> 
          
 
                  q.emplace( 
          0 
          ,  
          0 
          );  
          // 从红色边开始 
          
 
                  q.emplace( 
          0 
          ,  
          1 
          );  
          // 从蓝色边开始 
          
 
                   
          vector> vis(n, vector(2, false)) 
          ; 
          
 
                   
          // 结果数组，初始化为-1 
          
 
                   
          vector ans(n, -1) 
          ; 
          
 
                   
          int 
           level =  
          0 
          ;  
          // BFS层数 
          
 
                   
          while 
           (!q.empty()) { 
          
 
                       
          int 
           size = q.size();  
          // 当前层的节点数 
          
 
                       
          while 
           (size-- >  
          0 
          ) { 
          
 
                           
          auto 
           [index, color] = q.front(); 
          
 
                          q.pop(); 
          
 
                           
          // 如果是第一次到达该节点，更新最短路径长度 
          
 
                           
          if 
           (ans[index] ==  
          -1 
          ) { 
          
 
                              ans[index] = level; 
          
 
                          } 
          
 
                           
          // 标记当前状态已访问 
          
 
                          vis[index][color] =  
          true 
          ; 
          
 
                           
          // 切换到另一种颜色 
          
 
                          color ^=  
          1 
          ; 
          // 路径要红蓝交替 
          
 
                           
          // 遍历所有相邻节点 
          
 
                           
          for 
           ( 
          int 
           next: g[color][index]) { 
          
 
                               
          if 
           (!vis[next][color]) { 
          
 
                                  q.emplace(next, color); 
          
 
                              } 
          
 
                          } 
          
 
                      } 
          
 
                      level++; 
          
 
                  } 
          
 
                   
          return 
           ans; 
          
 
              }