上岸算法

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

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

No.1 换酒问题

★解题思路

循环计算即可.

代码展示

class Solution {
   public int numWaterBottles(int numBottles, int numExchange) {
       int res = numBottles;
       while (numBottles >= numExchange) {
           // 换到了 numBottles / numExchange
           res += numBottles / numExchange; 
           // 喝完之后酒瓶数量 = numBottles / numExchange + 之前没能换的酒瓶
           numBottles = numBottles / numExchange + (numBottles % numExchange);
       }
       return res;
   }
}

还可以借助 HashMap 实现时空复杂度均为 o(n)的解法.

No.2 子树中标签相同的节点数

★解题思路

由于标签只有 26 种, 所以我们 dfs 返回子树中每种标签的数量即可, 返回前可以统计答案.

代码展示

class Solution {
   public int[] countSubTrees(int n, int[][] edges, String labels) {
       Map<Integer,List<Integer>> neighbors = new HashMap<>();
       for (int i = 0; i < n; i++) {
           neighbors.put(i, new ArrayList<>());
       }
       for (var edge : edges) {
           neighbors.get(edge[0]).add(edge[1]);
           neighbors.get(edge[1]).add(edge[0]);
       }
       int[] res = new int[n];
       dfs(0, -1, neighbors, labels, res);
       return res;
   }

   private int[] dfs(int cur, int fa, Map<Integer, List<Integer>> neighbors, String labels, int[] res) {
       int[] count = new int[26]; 
       count[labels.charAt(cur) - 'a']++;
       for (int next : neighbors.get(cur)) {
           if (next != fa) {
               int[] subCount = dfs(next, cur, neighbors, labels, res);
               for (int i = 0; i < 26; i++) {
                   count[i] += subCount[i];
               }
           }
       }
       res[cur] = count[labels.charAt(cur)-'a'];
       return count;
   }
}

No.3 最多的不重叠子字符串

★解题思路

贪心, 首先统计出所有的满足条件的尽可能短的子串区间. 然后就变成了选择最多的不相交的区间问题.

代码展示

class Solution {
   public List<String> maxNumOfSubstrings(String s) {
       char[] str = s.toCharArray();

       // left[i], right[i] 表示字符 i 出现的最左/最右位置
       // left[i] = -1 表示未出现过
       int[] left = new int[26];
       int[] right = new int[26];
       Arrays.fill(left, -1);
       for (int i = 0; i < str.length; i++) {
           int c = str[i] - 'a';
           if (left[c] < 0) left[c] = i;
           right[c] = i;
       }

       // 统计出所有符合条件的子串
       // intervalR[i] 表示我们要以字符 i 为左端点时, 右端点的位置
       // intervalR[i] = -1 表示无法做左端点
       int[] intervalR = new int[str.length];
       int count = 0;
       Arrays.fill(intervalR, -1);
       for (int i = 0; i < str.length; i++) {
           int c = str[i] - 'a';
           if (i != left[c]) continue;
           int r = right[c];
           boolean ok = true;
           for (int j = i + 1; j <= r; j++) {
               int c2 = str[j] - 'a';
               if (left[c2] < i) {
                   ok = false;
                   break;
               }
               r = Math.max(r, right[c2]);
           }
           if (ok) {
               intervalR[i] = r;
               count++;
           }
       }

       // 转换成 intervals
       int[][] intervals = new int[count][2];
       for (int i = 0, j = 0; i < str.length; i++) {
           if (intervalR[i] >= 0) {
               intervals[j][0] = i;
               intervals[j][1] = intervalR[i];
               j++;
           }
       }

       // 选择最多的不相交的区间
       Arrays.sort(intervals, (o1, o2) -> o1[1] - o2[1]);
       List<String> res = new ArrayList<>();
       int R = -1;
       for (var interval : intervals) {
           if (interval[0] > R) {
               R = interval[1];
               res.add(s.substring(interval[0], interval[1] + 1));
           }
       }
       return res;
   }
}

No.4 找到最接近目标值的函数值

★解题思路

我们枚举 l, 依次计算对于每个 l, 能得到的最接近 target 的 位与和.

由于 与 运算只能把 1 变成 0, 而不能把 0 变成 1, 所以我们从高到低位依次考虑每一个二进制位.

假设 target 是 1010101, 而 arr[l] 是 1100101, 我们要优先让两个数高位的二进制位保持一致.

比如从左数第二个二进制位, target 是 0 而 arr[l] 是 1, 这时我们就可以通过位与后面的数, 把 位与和 这一位变成 0, 但是前提是不能影响第一个二进制位.

代码展示

class Solution {
   public int closestToTarget(int[] arr, int target) {
       // f[i][j] 表示 arr[i] 后二进制第 j 为上是 0 的数字的最近距离
       // f[i][j] = 0 或 f[i+1][j] + 1
       // 枚举 l, 从高到低枚举 j
       // 若 arr[l] 的第 j 位为 0, 无法改变为 1, 跳过
       // 若 arr[l] 的第 j 位为 1:
       //   target 的第 j 位为 0 则要求 r >= l + f[l][j]
       //   target 的第 j 位为 1 则要求 r <  l + f[l][j]
       int n = arr.length;
       int[][] f = new int[n][32];
       for (int j = 0; j < 32; j++) {
           f[n - 1][j] = getBit(arr[n-1], j) == 1 ? 0x3f3f3f3f : 0; // inf 表示后方没有 0
       }
       for (int i = n - 2; i >= 0; i--) {
           for (int j = 0; j < 32; j++) {
               f[i][j] = getBit(arr[i], j) == 1 ? f[i + 1][j] + 1 : 0;
           }
       }

       int res = Math.abs(target - arr[0]);

       for (int l = 0; l < n; l++) {
           int minR = l, maxR = n - 1;
           int tempRes = 0; // 保存位与和
           for (int j = 31; j >= 0; j--) {
               // 根据 arr[l] 的第 j 位的值进行处理
               if (getBit(arr[l], j) == 0) continue; // 是 0 无法改变
               // 是 1 则可以尝试变成与 target 一样的
               if (getBit(target, j) == 0) {
                   // 此时要求 r >= l + f[l][j], 即 minR = l + f[l][j]
                   if (maxR >= l + f[l][j]) { // 不能满足则跳过
                       minR = Math.max(minR, l + f[l][j]);
                   } else {
                       tempRes += 1 << j;
                   }
               } else {
                   // 此时要求 r <  l + f[l][j], 即 maxR = l + f[l][j] - 1
                   if (minR <= l + f[l][j] - 1) {
                       maxR = Math.min(maxR, l + f[l][j] - 1);
                       tempRes += 1 << j;
                   }
               }
           }
           res = Math.min(res, Math.abs(tempRes - target));
           res = Math.min(res, Math.abs(arr[l] - target)); // 处理特殊情况
       }

       return res;
   }

   private int getBit(int num, int pos) {
       return (num >> pos) & 1;
   }
}

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

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

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

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