上岸算法

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

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

No.1 替换所有的问号

★ 解题思路

由于有 26 种字符可以选择, 而一个字符相邻的最多只有两个. 所以该题目一定有解.

暴力查找即可.

代码展示

class Solution { 
   public String modifyString(String s) { 
       char[] str = s.toCharArray(); 
       for (int i = 0; i < str.length; i++) { 
           if (str[i] == '?') { 
               Set<Character> forbidden = new HashSet<>(); 
               if (i > 0) 
                   forbidden.add(str[i - 1]); 
               if (i < str.length - 1 && str[i + 1] != '?') 
                   forbidden.add(str[i + 1]); 
               for (char c = 'a'; c <= 'z'; c++) { // 暴力查找 
                   if (!forbidden.contains(c)) { 
                       str[i] = c; 
                       break; 
                   } 
               } 
           } 
       } 
       return String.copyValueOf(str); 
   } 
}

No.2 数的平方等于两数乘积的方法数

★解题思路

由于两个条件是镜像的, 所以我们可以共用代码. 详细思路见 helper 函数注释.

代码展示

class Solution { 
   public int numTriplets(int[] nums1, int[] nums2) { 
       return helper(nums1, nums2) + helper(nums2, nums1); 
   } 

   private int helper(int[] nums1, int[] nums2) { 
       // 满足 nums1[i]*nums1[i] == nums2[k] * nums2[k] 的数量 
       Map<Long, Integer> count = new HashMap<>(); 
       count.put((long) nums2[nums2.length - 1], 1); 
       int res = 0; 
       // 倒序枚举 nums2 的元素, 并用 Map 统计数值的出现次数 
       for (int i = nums2.length - 2; i >= 0; i--) { 
           for (int num : nums1) { 
               // num 相当于 nums1[i] 
               // nums2[i] 相当于 nums2[j] 
               // num * num / nums2[i] 相当于 nums2[k] 
               if ((long) num * num % nums2[i] == 0) 
                   res += count.getOrDefault(((long) num * num / nums2[i]), 0); 
           } 
           count.put((long) nums2[i], count.getOrDefault((long) nums2[i], 0) + 1); 
       } 
       return res; 
   } 
}

No.3 避免重复字母的最小删除成本

★解题思路

找出每一段相同的字符, 留下删除成本最大的那个即可.

代码展示

class Solution { 
   public int minCost(String s, int[] cost) { 
       int res = 0; 
       for (int i = 0; i < s.length(); ) { 
           int j = i + 1; 
           for (; j < s.length() && s.charAt(i) == s.charAt(j); j++) ; 
           // [i, j) 是相同的字符, 留下来一个 
           int max = 0; 
           int sum = 0; 
           for (int t = i; t < j; t++) { 
               sum += cost[t]; 
               max = Math.max(max, cost[t]); 
           } 
           res += sum - max; 
           i = j; 
       } 
       return res; 
   } 
}

No.4

保证图可完全遍历

★

解题思路

保证图可遍历的最小要求就是一棵树.

我们的目的就是留下尽可能少的边, 对于 Alice 和 Bob 两人都是一颗树.

从贪心的角度思考, 我们应该优先留下 type 为 3 的边. 所以我们把边按照类型排序, 然后选边生成树即可.

代码展示

class Solution { 
   public int maxNumEdgesToRemove(int n, int[][] edges) { 
       Arrays.sort(edges, (e1, e2) -> (e2[0] - e1[0])); 
       int[] alice = helper(n, edges, 1); 
       int[] bob = helper(n, edges, 2); 
       if (alice == null || bob == null) 
           return -1; 
       return alice[1] + bob[2] + Math.min(alice[3], bob[3]); 
   } 

   // 使用 type 和 3 类型的边构造生成树 
   // 返回 arr[type] 表示 type 类型的边最多可以被删除多少个 
   private int[] helper(int n, int[][] edges, int type) { 
       int[] f = new int[n + 1]; 
       for (int i = 0; i <= n; i++) 
           f[i] = i; 
       int[] res = new int[4]; 
       int cnt = 0; 
       for (int[] e : edges) { 
           if (e[0] != type && e[0] != 3) 
               continue; 
           int fa = find(f, e[1]); 
           int fb = find(f, e[2]); 
           if (fa == fb) 
               res[e[0]]++; 
           else { 
               f[fa] = fb; 
               cnt++; 
           } 
       } 
       return cnt == n - 1 ? res : null; 
   } 

   private int find(int[] f, int i) { 
       return f[i] = (i == f[i] ? i : find(f, f[i])); 
   } 
} 

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

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