上岸算法

死磕100%上岸率的精品小班课

关注我们，第一时间获得大厂面试真题讲解

No.1括号的最大嵌套深度

★解题思路

题目保证数据是合法的括号序列, 所以枚举一遍即可, 左括号和右括号数量的差值即是当前嵌套深度.

代码展示

class Solution { 
   public int maxDepth(String s) { 
       int res = 0; 
       for (int i = 0, left = 0, right = 0; i < s.length(); i++) { 
           if (s.charAt(i) == '(') { 
               left++; 
           } 
           if (s.charAt(i) == ')') { 
               right++; 
           } 
           res = Math.max(res, left - right); 
       } 
       return res; 
   } 
}

No.2 最大网络秩

★解题思路

枚举.

代码展示

class Solution { 
   public int maximalNetworkRank(int n, int[][] roads) { 
       int[] count = new int[n]; // count[i] 表示与点 i 连接的点的数量 
       int[][] connect = new int[n][n]; // connect[i][j] 表示 i j 是否连接 
       for (var road : roads) { 
           count[road[0]]++; 
           count[road[1]]++; 
           connect[road[0]][road[1]] = 1; 
           connect[road[1]][road[0]] = 1; 
       } 
       int res = 0; 
       for (int i = 0; i < n; i++) { 
           for (int j = i + 1; j < n; j++) { 
               res = Math.max(res, count[i] + count[j] - connect[i][j]); 
           } 
       } 
       return res; 
   } 
}

No.3 分割两个字符串得到回文串

★解题思路

类似判断一个字符串是否回文串, 用两根指针从首尾相向而行. 只不过一根指针在 a 上, 一根在 b 上.

而遇到不匹配的时候, 说明应该切开, 意味着将一根指针挪到另一个字符串上.

代码展示

class Solution { 
   public boolean checkPalindromeFormation(String a, String b) { 
       return check(a, b) || check(b, a); 
   } 

   private boolean check(String a, String b) { 
       int n = a.length(); 
       int status = 0; // 尚未切开 
       for (int i = 0, j = n - 1; i < j; ) { 
           if (status == 0 && a.charAt(i) != b.charAt(j)) { 
               status = 1; // 已经切开 
               continue; 
           } 
           if (status == 1 && b.charAt(i) != b.charAt(j) && a.charAt(i) != a.charAt(j)) { 
               return false; 
           } 
           i++; 
           j--; 
       } 
       return true; 
   } 
}

No.4

统计子树中城市之间最大距离

★

解题思路

枚举所有的子树, 然后判断子树的最大距离即可.

代码展示

class Solution { 
   public int[] countSubgraphsForEachDiameter(int n, int[][] edges) { 
       int[] res = new int[n - 1]; 
       // 利用二进制, 枚举所有的边取/不取的情况 
       // 一共 n - 1 条边, 有 2 ^ (n - 1) 个子集 
       for (int binary = 1; binary < (1 << (n - 1)); binary++) { 
           // 取边, 构图, 存入 children 
           List<List<Integer>> children = new ArrayList<>(); 
           for (int i = 0; i < n; i++) 
               children.add(new ArrayList<>()); 
           int start = 0; 
           int count = 1; 
           for (int i = 0; i < n - 1; i++) { 
               if ((binary & (1 << i)) > 0) { 
                   children.get(edges[i][0] - 1).add(edges[i][1] - 1); 
                   children.get(edges[i][1] - 1).add(edges[i][0] - 1); 
                   start = edges[i][0] - 1; 
                   count++; 
               } 
           } 

           // 有效性判断, 并不一定所有的边的子集都是合法的子树   
           boolean[] visited = new boolean[n]; 
           if (countNodes(start, visited, children) != count) { 
               continue; 
           } 

           // 计算子树的直径 (即最大距离), 两次 DFS 即可 
           Arrays.fill(visited, false); 
           int[] first = getMaxDistance(start, visited, children); 
           Arrays.fill(visited, false); 
           int[] second = getMaxDistance(first[0], visited, children); 
           res[second[1] - 1]++; 
       } 
       return res; 

   } 

   // arr[0] 表示距离当前点最远点是谁 
   // arr[1] 表示距离当前点最远点的距离 
   private int[] getMaxDistance(int start, boolean[] visited, List<List<Integer>> children) { 
       visited[start] = true; 
       int[] res = new int[]{start, 0}; 
       for (int child : children.get(start)) { 
           if (!visited[child]) { 
               int[] tmp = getMaxDistance(child, visited, children); 
               if (res[1] < tmp[1] + 1) { 
                   res[0] = tmp[0]; 
                   res[1] = tmp[1] + 1; 
               } 
           } 
       } 
       return res; 
   } 

   private int countNodes(int start, boolean[] visited, List<List<Integer>> children) { 
       visited[start] = true; 
       int res = 1; 
       for (int child : children.get(start)) { 
           if (!visited[child]) { 
               res += countNodes(child, visited, children); 
           } 
       } 
       return res; 
   } 
} 

    杭州上岸算法网络科技有限公司

上岸算法网络科技有限公司是一家致力于用高质量，高互动性小班课程来帮助学生更好的在就业市场中定位以及求职的公司。我们以顶级的课程质量，高互动性的教学方式以及独特的小班教学模式来帮助学生更快的跨过求职的鸿沟，用最高效，经济，合理的方式帮助更多学生快速找到梦寐以求的工作。