上岸算法

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

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

No.1 判断能否形成等差数列

★解题思路

排序之后依次判断每两对相邻的差是否相等即可.

代码展示

class Solution { 
   public boolean canMakeArithmeticProgression(int[] arr) { 
       Arrays.sort(arr); 
       for (int i = 2; i < arr.length; i++) { 
           if (arr[i] - arr[i - 1] != arr[i - 1] - arr[i - 2]) { 
               return false; 
           } 
       } 
       return true; 
   } 
}

No.2 所有蚂蚁掉下来前的最后一刻

★ 解题思路

两只蚂蚁相遇改变方向等价于两只蚂蚁穿过了对方.

代码展示

class Solution { 
   public int getLastMoment(int n, int[] left, int[] right) { 
       int res = 0; 
       for (int l : left) { 
           res = Math.max(l, res); 
       } 
       for (int r : right) { 
           res = Math.max(n - r, res); 
       } 
       return res; 
   } 
}

No.3 统计全1子矩形

★解题思路

见注释.

代码展示

class Solution { 
   public int numSubmat(int[][] mat) { 
       int n = mat.length, m = mat[0].length; 
       // 预处理, 计算前缀和. sum[i][j] 表示 (0, 0) 到 (i, j) 的子矩形的和  
       int[][] sum = new int[n][m]; 
       for (int i = 0; i < n; i++) { 
           sum[i][0] = mat[i][0] + (i == 0 ? 0 : sum[i - 1][0]); 
           for (int j = 1; j < m; j++) { 
               sum[i][j] = sum[i][j - 1] + mat[i][j]; 
               if (i == 0) { 
                   sum[i][j] = sum[i][j - 1] + mat[i][j]; 
               } else { 
                   sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + mat[i][j]; 
               } 
           } 
       } 

       int res = 0; 
       // 依次统计以每个点 (i, j) 为左上角的全 1 子矩阵的数量 
       for (int i = 0; i < n; i++) { 
           for (int j = 0; j < m; j++) { 
               // 依次统计右下角在每一行 (k) 时有多少个子矩阵 
               for (int k = i; k < n; k++) { 
                   if (!checkAllOne(i, j, k, j, sum)) break; 
                   // 二分计算右下角在第 k 行时, 最大的全 1 矩阵 
                   int l = j, r = m - 1; 
                   while (l + 1 < r) { 
                       int mid = (l + r) / 2; 
                       if (checkAllOne(i, j, k, mid, sum)) { 
                           l = mid; 
                       } else { 
                           r = mid; 
                       } 
                   } 
                   if (checkAllOne(i, j, k, r, sum)) { 
                       res += r - j + 1; 
                   } else { 
                       res += l - j + 1; 
                   } 
               } 
           } 
       } 
       return res; 
   } 

   private boolean checkAllOne(int i, int j, int i2, int j2, int[][] sum) { 
       // 检查以 (i, j) 为左上角, (i2, j2) 为右下角的子矩阵是否全为 1 
       int size = (j2 - j + 1) * (i2 - i + 1); 
       int _all = sum[i2][j2]; 
       int _left = j == 0 ? 0 : sum[i2][j - 1]; 
       int _up = i == 0 ? 0 : sum[i - 1][j2]; 
       int _upLeft = i == 0 || j == 0 ? 0 : sum[i - 1][j - 1]; 
       int allSum = _all - _left - _up + _upLeft; 
       return allSum == size; 
   } 
}

No.4

最多K次交换相邻数位后得到的最小整数

★

解题思路

基本思路:

优先缩小高位

尝试缩小一个数即找它后面最小的能在 k 次交换之后移动到这个位置的数

需要使用数状数组辅助维护第 2 点

代码展示

class Solution { 
   private int[] _sum; // 树状数组 

   void add(int x, int v) { 
       while (x < _sum.length) { 
           _sum[x] += v; 
           x += x & (-x); 
       } 
   } 

   int sum(int x) { 
       int ret = 0; 
       while (x != 0) { 
           ret += _sum[x]; 
           x -= x & (-x); 
       } 
       return ret; 
   } 

   String minInteger(String num, int k) { 
       _sum = new int[num.length() + 1]; 
       StringBuilder res = new StringBuilder(); 
       Map<Character, LinkedList<Integer>> rawPos = new HashMap<>(); // rawPos[i] 表示字符 i 出现的位置序列 
       int[] next = new int[10]; // next[i] 表示 rawPos[i] 用到了哪一个 
       // 初始化计算 rawPos 
       for (char c = '0'; c <= '9'; c++) { 
           rawPos.put(c, new LinkedList<>()); 
       } 
       for (int i = 0; i < num.length(); i++) { 
           char c = num.charAt(i); 
           rawPos.get(c).add(i); 
       } 
       // 计算答案 
       for (int i = 0; i < num.length(); i++) { 
           // 尝试将字符 j 从后面一个一个地交换, 直到换到 i 位置 
           // (若 jChar 就是 num[i] 本身, 则不消耗交换次数) 
           for (int j = 0; j < 10; j++) { 
               char jChar = (char)(j + '0'); 
               if (next[j] == rawPos.get(jChar).size()) { // j 已经用完了, continue 
                   continue; 
               } 
               int p = rawPos.get(jChar).get(next[j]); 
               if (k >= p + sum(p + 1) - i) { // 加上整体偏移量 
                   k -= p + sum(p + 1) - i; 
                   next[j]++; 
                   res.append(jChar); 
                   // 使用数状数组维护整体偏移量 
                   add(1, 1);  
                   add(p + 1, -1); 
                   break; 
               } 
           } 
       } 
       return res.toString(); 
   } 
}

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

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

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

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