上岸算法

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

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

No.1整理字符串

★解题思路

在无限循环中判断: 只要还有满足题目条件的字符对, 就删除.

代码展示

class Solution { 
   public String makeGood(String s) { 
       StringBuilder sb = new StringBuilder(s); 
       while (true) { 
           int pos = -1; 
           // 查找满足题目条件的字符对 
           for (int i = 1; i < sb.length(); i++) { 
               char c1 = sb.charAt(i), c2 = sb.charAt(i - 1); 
               if (Character.toLowerCase(c1) == Character.toLowerCase(c2) && c1 != c2) { 
                   pos = i - 1; 
                   break; 
               } 
           } 
           if (pos < 0) { 
               break; 
           } 
           sb.delete(pos, pos + 2); 
       } 
       return sb.toString(); 
   } 
}

从良好的编程习惯来讲, 慎用无限循环. 而在这个场景中我们可以手动设限: 最多循环 s.length() / 2 次.

No.2找出第N个二进制字符串中的K位

★解题思路

分析出该题目数据范围不大, 最终字符串长度最长 100 万左右 (2 ^ 20), 所以可以直接模拟生成 S_n.

代码展示

class Solution { 
   public char findKthBit(int n, int k) { 
       StringBuilder sb = new StringBuilder("0"); 
       for (int i = 2; i <= n; i++) { 
           StringBuilder inv = invert(sb); 
           sb.append("1"); 
           sb.append(inv.reverse()); 
       } 
       return sb.charAt(k - 1); 
   } 

   private StringBuilder invert(StringBuilder sb) { 
       StringBuilder res = new StringBuilder(sb); 
       for (int i = 0; i < res.length(); i++) { 
           res.setCharAt(i, (char) (((res.charAt(i) - '0') ^ 1) + '0')); 
       } 
       return res; 
   } 
}

No.3和为目标值的最大数目不重叠非空子数组数目

★解题思路

贪心法. 利用前缀和相减得到区间和. 详见注释.

代码展示

class Solution { 
   public int maxNonOverlapping(int[] nums, int target) { 
       int res = 0; 
       int sum = 0; 
       Set<Integer> set = new HashSet<>(); 
       for (int num : nums) { 
           // sum 表示当前累计的前缀和 
           // set 储存之前的前缀和 
           sum += num; 
           // 若 sum 直接等于 target 或者之前的前缀和中存在 sum - target 
           //  说明找到了一个子数组 (这个子数组以 num 结尾) 
           //  然后 res++, 并清空 set 和 sum 继续寻找下一个子数组 
           // 否则, 将 sum 添加到 set 中, 继续寻找 
           if (set.contains(sum - target) || sum == target) { 
               res++; 
               set.clear(); 
               sum = 0; 
           } else { 
               set.add(sum); 
           } 
       } 
       return res; 
   } 
}

No.4切棍子的最小成本

★解题思路

区间动态规划问题.

设定 f[i][j] 表示 [i, j] 切割点之间的棍子, 切割的最优解.

状态转移 f[i][j] = min{ f[i][k] + f[k][j] + length(i, j) }, 其中 length(i, j) 表示 [i, j] 切割点之间的棍子的长度.

边界 f[i][i] = 0, f[i][i + 1] = 0

注意, 为了使得状态包含整根棍子, 我们需要增加两个切割点, 分别位于 0 和 n.

代码展示

class Solution { 
   public int minCost(int n, int[] cuts) { 
       Arrays.sort(cuts); // 根据样例 2 知, 题目输入未必有序. 所以需要排序. 
       int m = cuts.length; 
       int[][] f = new int[m + 2][m + 2]; 
       for (int len = 2; len <= m+1; len++) { 
           for (int start = 0; start + len <= m+1; start++) { 
               int i = start, j = start + len; 
               f[i][j] = 0x3f3f3f3f; 
               for (int k = i; k <= j; k++) { 
                   f[i][j] = Math.min(f[i][k] + f[k][j] + point(j, n, cuts) - point(i, n, cuts), f[i][j]); 
               } 
           } 
       } 
       return f[0][m+1]; 
   } 

   // 由于我们添加了两个切割点, 所以使用 point 函数获取第 i 个切割点的位置 
   private int point(int i, int n, int[] cuts) { 
       if (i == 0) { 
           return 0; 
       } else if (i > cuts.length) { 
           return n; 
       } 
       return cuts[i - 1]; 
   } 
}

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

上岸科技，一家位于西雅图致力于帮助北美小伙伴们上岸的团体。

团队主要由一群怀揣情怀于美国高校毕业的一线IT公司工程师构成。我们坚持采用小班课形式，并结合大量”面试式“和”白板“的教学和交流形式，最终帮助大家提升求职成功概率同时大大减少刷题的痛苦。

正如我们的信仰：我们教的是如何上岸而不仅是算法。