上岸算法

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

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

No.1 数组中两元素的最大乘积

★解题思路

一次循环即可统计出第一大和第二大的元素.

代码展示

class Solution {   public int maxProduct(int[] nums) {       int first = Math.max(nums[0], nums[1]);       int second = Math.min(nums[0], nums[1]);       for (int i = 2; i < nums.length; i++) {           if (nums[i] > first) {               second = first;               first = nums[i];           } else {               second = Math.max(second, nums[i]);           }       }       return (first - 1) * (second - 1);   } }

No.2 切割后面积最大的蛋糕

★解题思路

找出切割后的最大子矩形的长和宽即可.

代码展示

class Solution {   public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {       long maxw = maxLength(h, horizontalCuts);       long maxh = maxLength(w, verticalCuts);       return (int) (maxw * maxh % 1000000007);   }   // 返回边长为 n, 切点为 cuts 的情况, 切割之后的最大边长   private long maxLength(int n, int[] cuts) {       Arrays.sort(cuts);       long res = Math.max(cuts[0], n - cuts[cuts.length - 1]);       for (int i = 1; i < cuts.length; i++) {           res = Math.max(res, cuts[i] - cuts[i - 1]);       }       return res;   } }

No.3 重新规划路线

★解题思路

原本所有的有向边 (a, b) 的含义可以理解为从 a 走到 b 的耗费是 0, 而从 b 走到 a 的耗费为 1. 那么从城市 x 走到城市 0, 需要改变的道路方向的数量就是这条路径的累积耗费.

但是依次从每一个点走向 0 并不容易实现, 我们改为求解对称的问题: 从 0 走到每一个点 —— 对应地将每条边也反向.

代码展示

class Solution {   public int minReorder(int n, int[][] connections) {       Map<Integer,List<Integer>> neighbors = new HashMap<>();       // 构造邻接表, 便于 dfs       // neighbors[i] 表示 i 可以到达的点以及距离       for (var conn : connections) {           int a = conn[0], b = conn[1];           // 因为求解对称问题, 所以原图 a -> b 的有向边对应           // a->b (1) 和 b->a (0)           neighbors.computeIfAbsent(a, k -> new ArrayList<>());           neighbors.computeIfAbsent(b, k -> new ArrayList<>());           neighbors.get(a).add(b);           neighbors.get(a).add(1);           neighbors.get(b).add(a);           neighbors.get(b).add(0);       }       return dfs(0, -1, neighbors);   }   private int dfs(int cur, int pre, Map<Integer, List<Integer>> neighbors) {       int res = 0;       int n = neighbors.get(cur).size();       for (int i = 0; i < n; i += 2) {           int next = neighbors.get(cur).get(i);           int len = neighbors.get(cur).get(i + 1);           if (next != pre) {               res += dfs(next, cur, neighbors) + len;           }       }       return res;   } }

No.4 两个盒子中球的颜色数相同的概率

★ 解题思路

最终答案 = 使得两个盒子中球的颜色数相同的方案数量 / 总方案数量

其中总方案数量即组合数 "从 2n 个球中拿出 n 个球的方案数".

使得两个盒子中球的颜色数相同的方案数量可以通过枚举求解.

代码展示

class Solution {   private int sum;   public double getProbability(int[] balls) {       sum = 0;       for (int ball : balls) {           sum += ball;       }       return 1.0 * dfs(0, 0, 0, 0, 0, 1, balls) / C(sum / 2, sum);   }   // i 表示枚举到哪种球了   // j1, j2 表示两个盒子中球的数量, 最终两个盒子中球的数量都是 sum / 2   // k1, k2 表示两个盒子中颜色的数量, 最终 k1 == k2   // cnt 表示走到当前这一种状态的方案数量   private long dfs(int i, int j1, int j2, int k1, int k2, long cnt, int[] balls) {       if (j1 > sum / 2 || j2 > sum / 2) {           return 0;       }       if (i == balls.length) {           return k1 == k2 ? cnt : 0;       }       long res = 0;       // 考虑 balls[i] 有多少个球放进了盒子 1       // 把 j 个球放进盒子 1 的方案数为 C(j, balls[i])       // 乘法原理       res += dfs(i + 1, j1, j2 + balls[i], k1, k2 + 1, cnt * 1, balls);       res += dfs(i + 1, j1 + balls[i], j2, k1 + 1, k2, cnt * 1, balls);       for (int j = 1; j < balls[i]; j++) {           res += dfs(i + 1, j1 + j, j2 + balls[i] - j, k1 + 1, k2 + 1,                   cnt * C(j, balls[i]), balls);       }       return res;   }   private long[][] memC = new long[25][50];   private long C(int a, int b) {       if (a == b || a == 0) {           return 1;       }       if (memC[a][b] > 0) {           return memC[a][b];       }       memC[a][b] = C(a - 1, b - 1) + C(a, b - 1);       return memC[a][b];   } }

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

上岸科技是一家【死磕100%上岸率】的小公司。

核心团队和老师均来自于行业内知名公司，我们坚持采用小班课形式，并结合大量”面试式“和”白板“的教学和交流形式，最终做到摆渡【每个人】成功上岸的承诺。

我们对每个人负责，上岸，一个都不能少！