上岸算法

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

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

No.1存在连续三个奇数的数组

★解题思路

一次循环即可判断.

代码展示

class Solution {
   public boolean threeConsecutiveOdds(int[] arr) {
       for (int i = 2; i < arr.length; i++) {
           if (isOdd(arr[i-2]) && isOdd(arr[i-1]) && isOdd(arr[i])) {
               return true;
           }
       }
       return false;
   }

   private boolean isOdd(int i) {
       return i % 2 == 1;
   }
}

No.2 使数组中所有元素相等的最小操作数

★ 解题思路

操作可以遵循一个策略: 每次挑选差距最大的两个数来操作.

其实这是一个等差数列, 并且平均数是 n, 也就是说, 最终所有的数字都会变成 n.

1, 3, 5, 7, ..., 2n-1

1 和 2n-1 需要操作 n - 1 次, 就可以都变成 n.

3 和 2n-3 需要操作 n - 3 次, 就可以都变成 n.

5 和 2n-5, n - 5 次.

...

操作次数也是一个等差数列, 首项是 n - 1, 公差为 -2, 项数为 n / 2

代码展示

class Solution {
   public int minOperations(int n) {
       int a = n - 1;
       int b = n - 1 - 2 * (n / 2 - 1);
       return (a + b) * (n / 2) / 2;
   }
}

No.3 两球之间的磁力

★解题思路

二分答案 + 贪心.

代码展示

class Solution {
   public int maxDistance(int[] position, int m) {
       Arrays.sort(position);
       int l = 0, r = 1000000000;
       while (l + 1 < r) {
           int mid = (l + r) / 2;
           if (check(position, m, mid)) {
               l = mid;
           } else {
               r = mid;
           }
       }
       return check(position, m, r) ? r : l;
   }

   // 检查 position 位置上的篮子, 至少隔 min 放一个球的情况下
   // 能否放下 m 个球
   private boolean check(int[] position, int m, int min) {
       int cnt = 1;
       int last = position[0];
       // 贪心法, 从最左侧的篮子开始枚举, "能放就放"
       for (int i = 1; i < position.length; i++) {
           if (position[i] - last >= min) {
               last = position[i];
               cnt++;
           }
       }
       return cnt >= m;
   }
}

No.4 吃掉 N 个橘子的最少天数

★

解题思路

动态规划. 不过由于这个题目的数据比较大, 所以不能直接用数组, 使用 Map.

定义状态 dp[i] 表示吃掉 i 个橘子花费的最少天数.

简单来说可以想到: dp[i] = min(dp[i-1], dp[i/2] if i % 2 == 0, dp[i/3] if i % 3 == 0) + 1

但是如果真这么转移, 那么时间复杂度将会是 o(n) 的.

实际上我们 "吃一个" 的目的就是为了达到 2 的倍数或者 3 的倍数, 然后就可以缩小到 1/2 或者 1/3, 所以我们的决策就是吃到 2 的倍数还是 3 的倍数.

dp[i] = min(dp[i/2] + n % 2 + 1, dp[i/3] + n % 3 + 1)

这样转移, 时间复杂度就是 log 级别的.

代码展示

class Solution {
   private Map<Integer, Integer> dp = new HashMap<>();

   public int minDays(int n) {
       if (n <= 2) {
           return n;
       }
       if (dp.containsKey(n)) {
           return dp.get(n);
       }
       int res = Math.min(
               minDays(n / 2) + n % 2 + 1, 
               minDays(n / 3) + n % 3 + 1
       );
       dp.put(n, res);
       return res;
   }
}

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

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

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

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