上岸算法

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

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

No.1 重新排列字符串

★解题思路

由于 Java 的 String 不可变, 所以需要借助 char[] 或者 StringBuilder 来构建新字符串.

代码展示

class Solution {
   public String restoreString(String s, int[] indices) {
       char[] str = new char[s.length()];
       for (int i = 0; i < s.length(); i++) {
           str[indices[i]] = s.charAt(i);
       }
       return String.copyValueOf(str);
   }
}

No.2 灯泡开关IV

★解题思路

从最左边的灯开始, 模拟解决即可 (若灯和需要的状态不同, 则反转)

代码展示

class Solution {
   public int minFlips(String target) {
       int cur = 0;
       int res = 0;
       for (int i = 0; i < target.length(); i++) {
           char c = target.charAt(i);
           if (c != cur + '0') {
               res++; 
               cur ^= 1;
           }
       }
       return res;
   }
}

No.3 好叶子节点对的数量

★解题思路

统计每个节点的子树中, 叶子节点到自己的距离列表.

然后根据左右子树返回的列表统计经过自己的好叶子节点对的数量.

代码展示

class Solution {
   private int res = 0;

   public int countPairs(TreeNode root, int distance) {
       res = 0;
       dfs(root, distance);
       return res;
   }

   private List<Integer> dfs(TreeNode node, int distance) {
       if (node == null) return new ArrayList<>();
       if (node.left == null && node.right == null) {
           List<Integer> a = new ArrayList<>();
           a.add(1);
           return a;
       }
       var left = dfs(node.left, distance);
       var right = dfs(node.right, distance);

       if (node.left == null) return add1(right);
       if (node.right == null) return add1(left);

       // 双指针, 统计有多少对
       int tmp = 0;
       for (int l = 0, r = right.size() - 1; l < left.size(); l++) {
           while (r >= 0 && left.get(l) + right.get(r) > distance) r--;
           if (r >= 0 && left.get(l) + right.get(r) <= distance) {
               tmp += r + 1;
               res += r + 1;
           }
       }

       left.addAll(right);
       Collections.sort(left);
       return add1(left);
   }

   private List<Integer> add1(List<Integer> list) {
       for (int i = 0; i < list.size(); i++) {
           list.set(i, list.get(i) + 1);
       }
       return list;
   }
}

No.4 压缩字符串II

★解题思路

动态规划, 状态和转移方程并不复杂, 代码也很简单, 但是转移的决策可能不太容易想到.

具体见代码注释.

代码展示

class Solution {
   public int getLengthOfOptimalCompression(String s, int k) {
       int n = s.length();
       char[] str = s.toCharArray();
       // dp[i][j] 表示前 i 个字符的子串, 删除 j 个字符时的最优解
       int[][] dp = new int[n + 1][k + 2];
       // 初始化 dp[i][j] = INF, dp[0][0] = 0
       for (int i = 0; i <= n; i++) {
           Arrays.fill(dp[i], 0x3f3f3f3f);
       }
       dp[0][0] = 0;
       for (int i = 1; i <= n; i++) {
           for (int j = 0; j <= k; j++) {
               int cnt = 0, del = 0;
               // 枚举决策, 删除第 i 个到第 t 个之间不同于第 i 个的字符
               for (int t = i; t <= n; t++) {
                   if (str[t - 1] == str[i - 1]) cnt++;
                   else del++;
                   if (j + del <= k) {
                       dp[t][j + del] = Math.min(dp[t][j + del], dp[i - 1][j] + getLen(cnt));
                   }
               }
               // 额外处理删除第 i 个
               dp[i][j + 1] = Math.min(dp[i][j + 1], dp[i - 1][j]);
           }
       }
       return dp[n][k];
   }

   private int getLen(int cnt) {
       return cnt == 0 ? 0 : (cnt == 1 ? 1 : (cnt < 10 ? 2 : 3));
   }
}

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

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

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

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