上岸算法

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

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

No.1 统计好三元组

★解题思路

简单地枚举即可, 三层循环.

代码展示

class Solution {
   public int countGoodTriplets(int[] arr, int a, int b, int c) {
       int n = arr.length;
       int res = 0;
       for (int i = 0; i < n; i++) {
           for (int j = i + 1; j < n; j++) {
               for (int k = j + 1; k < n; k++) {
                   if (isGood(arr, i, j, a) && isGood(arr, j, k, b) && isGood(arr, i, k, c)) {
                       res++;
                   }
               }
           }
       }
       return res;
   }

   boolean isGood(int[] arr, int a, int b, int c) {
       return Math.abs(arr[a] - arr[b]) <= c;
   }
}

No.2 找出数组游戏的赢家

★ 解题思路

需要用单调栈求出每个元素后第一个比自己大的元素的位置 nextLarger 最终胜利的元素就是 nextLarger 与自己的距离超过 k 的第一个元素.

代码展示

class Solution {
   public int getWinner(int[] arr, int k) {
       // 单调栈
       int[] nextLarger = new int[arr.length];
       Stack<Integer> stack = new Stack<>();
       stack.push(0);
       for (int i = 1; i < arr.length; ) {
           if (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
               nextLarger[stack.pop()] = i;
           } else {
               stack.push(i++);
           }
       }
       while (!stack.isEmpty()) {
           nextLarger[stack.pop()] = arr.length;
       }

       for (int i = 0; i < arr.length; i++) {
           int win = i == 0 ? 0 : 1; // 若 i 不是第一个, 那么会赢一个前面的元素
           win += nextLarger[i] - i - 1; // 然后会连续赢到 nextLarger
           if (win >= k) return arr[i];
       }

       // 没有 win >= k 的, 即 k 过大 (大于数组长度), 此时直接返回数组最大值
       return Collections.max(Arrays.stream(arr).boxed().collect(Collectors.toList()));
   }
}

No.3 排布二进制网格的最少交换次数

★解题思路

模拟交换即可.

由于要主对角线上全部是 0, 所以行数越靠前, 要求越苛刻 —— 一行中 0 的数量越多.

所以我们从前面的行开始看, 只要不满足条件, 就在后面找到一行换上来.

代码展示

class Solution {
   public int minSwaps(int[][] grid) {
       int n = grid.length;
       int m = grid[0].length;

       // last1[i] 表示第 i 行的最后一个 1 的位置
       int[] last1 = new int[n];
       Arrays.fill(last1, -1);
       for (int i = 0; i < n; i++) {
           for (int j = 0; j < m; j++) {
               if (grid[i][j] == 1) last1[i] = j;
           }
       }

       int res = 0;
       for (int i = 0; i < n; i++) {
           // last1[i] <= i 说明这一行满足题目条件
           if (last1[i] <= i) continue;
           // 不满足则在后面找到满足条件的一行
           int pos = -1;
           for (int j = i + 1; j < n; j++) {
               if (last1[j] <= i) {
                   pos = j;
                   break;
               }
           }
           if (pos < 0) return -1;
           // 交换
           res += pos - i;
           int[] gBak = grid[pos];
           int lBak = last1[pos];
           for (int j = pos; j > i; j--) {
               grid[j] = grid[j - 1];
               last1[j] = last1[j - 1];
           }
           grid[i] = gBak;
           last1[i] = lBak;
       }
       return res;
   }
}

No.4 最大得分

★解题思路

贪心法.

找出共同的元素, 两个数组中共同的元素将两个数组分成若干段, 取比较大的那一段即可.

代码展示

class Common {
   public int pos1;
   public int pos2;

   public Common(int pos1, int pos2) {
       this.pos1 = pos1;
       this.pos2 = pos2;
   }
}

class Solution {
   public int maxSum(int[] nums1, int[] nums2) {
       int n = nums1.length;
       int m = nums2.length;

       // 前缀和, 稍后求区间和所用
       long[] presum1 = new long[n];
       long[] presum2 = new long[m];
       presum1[0] = nums1[0];
       for (int i = 1; i < n; i++) {
           presum1[i] = presum1[i - 1] + nums1[i];
       }
       presum2[0] = nums2[0];
       for (int i = 1; i < m; i++) {
           presum2[i] = presum2[i - 1] + nums2[i];
       }

       // 求出二者相同元素的位置
       List<Common> commons = new ArrayList<>();
       commons.add(new Common(-1, -1)); // 边界
       for (int i = 0, j = 0; i < n && j < m; ) {
           if (nums1[i] == nums2[j]) {
               commons.add(new Common(i, j));
               i++;
               j++;
           } else if (nums1[i] < nums2[j]) i++;
           else j++;
       }
       commons.add(new Common(n, m)); // 边界

       // 两个相邻的相同元素切割出一段, 取较大的那一段
       long res = 0;
       long MOD = 1000000007;
       for (int i = 1; i < commons.size(); i++) {
           Common last = commons.get(i - 1);
           Common curr = commons.get(i);
           long sum1 = getSum(last.pos1, curr.pos1, presum1);
           long sum2 = getSum(last.pos2, curr.pos2, presum2);
           res = (res + (Math.max(sum1, sum2) % MOD)) % MOD;
       }
       return (int) res;
   }

   private long getSum(int l, int r, long[] presum) {
       long lsum = 0, rsum = presum[presum.length - 1];
       if (l >= 0) lsum = presum[l];
       if (r < presum.length) rsum = presum[r];
       return rsum - lsum;
   }
}

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

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

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

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