上岸算法

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

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

No.1 一堆数组的动态和

★解题思路

比较简单, 一次循环就可以计算出结果.

代码展示

class Solution { 
   public int[] runningSum(int[] nums) { 
       int[] sum = new int[nums.length]; 
       sum[0] = nums[0]; 
       for (int i = 1; i < nums.length; i++) { 
           sum[i] = sum[i - 1] + nums[i]; 
       } 
       return sum; 
   } 
}

No.2 不同整数的最少数目

★解题思路

贪心. 统计每种数字的出现次数, 然后从出现次数最少的删除即可.

代码展示

class Solution { 
   public int findLeastNumOfUniqueInts(int[] arr, int k) { 
       Map<Integer,Integer> cnt = new HashMap<>(); 
       for (int num : arr) { 
           cnt.put(num, cnt.getOrDefault(num, 0) + 1); 
       } 
       // 取出 cnt 的 value 列表, 转换成数组 
       int[] val = cnt.values().stream().mapToInt(i -> i).toArray(); 
       Arrays.sort(val); 
       int res = val.length; 
       for (int i : val) { 
           if (k < i) break; 
           else k -= i; 
           res--; 
       } 
       return res; 
   } 
}

No.3 制作m束花所需的最少天数

★解题思路

二分法. 二分答案, 然后判定在 mid 天内能否制作出 m 束花.

代码展示

class Solution { 
   public int minDays(int[] bloomDay, int m, int k) { 
       int n = bloomDay.length; 
       if (m * k > n) return -1; 
       int l = 0, r = 1000000000; 
       while (l + 1 < r) { 
           int mid = (l + r) / 2; 
           if (count(bloomDay, mid, k) >= m) { 
               r = mid; 
           } else { 
               l = mid; 
           } 
       } 
       return count(bloomDay, l, k) >= m ? l : r; 
   } 

   // 计数在 limit 天内可以制作出多少束花 
   private int count(int[] bloomDay, int limit, int k) { 
       int res = 0; 
       // pos 表示花的生长时间超过了 limit 的位置 
       List<Integer> pos = new ArrayList<>(); 
       pos.add(-1); 
       for (int i = 0; i < bloomDay.length; i++) { 
           if (bloomDay[i] > limit) { 
               pos.add(i); 
           } 
       } 
       pos.add(bloomDay.length); 
       // 查看每两个 pos 之间的距离, 除以 k (下取整) 即可得到这一段盛开的花可以制作多少束 
       for (int i = 1; i < pos.size(); i++) { 
           res += (pos.get(i) - pos.get(i - 1) - 1) / k; 
       } 
       return res; 
   } 
}

No.4 树节点的第k个祖先

★解题思路

如果我们要找节点 node 的第 k 个祖先, 一个一个地往上走肯定会超时, 所以我们提高速度, 两个, 四个, 八个...地往上走.

令 fa[i][j] 表示节点 i 的 $2^j$ 的祖先是谁, 有 fa[i][j] = fa[fa[i][j-1]][j-1], 一次 dfs 即可求出 fa 数组. (i的 $2^j$ 祖先即 i 的 $2^{j-1}$ 祖先的 $2^{j-1}$ 祖先)

一个整数 k 必然可以分解成 $2^{i1} + 2^{i2} + ... + 2^{in}$ 的形式, 我们利用 fa 数组往上走 n 次即可, 分别走 i1, i2, ..., in.

代码展示

class TreeAncestor { 

   Map<Integer,List<Integer>> children; 
   int[][] fa; 

   public TreeAncestor(int n, int[] parent) { 
       fa = new int[n][30]; 
       children = new HashMap<>(); 
       for (int i = 0; i < n; i++) { 
           Arrays.fill(fa[i], -1); 
           children.put(i, new ArrayList<>()); 
       } 
       for (int i = 1; i < n; i++) { // 0 节点无父节点 
           children.get(parent[i]).add(i); 
           fa[i][0] = parent[i]; 
       } 
       dfs(0); 
   } 

   private void dfs(int cur) { 
       for (int i = 1; fa[cur][i-1] >= 0; i++) { 
           fa[cur][i] = fa[fa[cur][i-1]][i-1]; 
       } 
       for (int nxt : children.get(cur)) { 
           dfs(nxt); 
       } 
   } 

   public int getKthAncestor(int node, int k) { 
       for (int i = 0; k > 0; i++, k>>=1) { // 依次查看 k 的每一个二进制位 
           if ((k & 1) > 0) { // 若满足, 则说明 k 拆开后含有 2^i 
               node = fa[node][i]; 
               if (node < 0) return -1; 
           } 
       } 
       return node; 
   } 
}

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

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

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

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