上岸算法

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

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

No.1 圆形赛道上经过次数最多的扇区

★解题思路

使用差分数组可以做到 o(1) 的 "区间增" 操作. 然后将原数组扩展一倍来做到化环为链. (或者也可以将一段经过了 n 和 1 的阶段拆分成两段来 "区间增")

代码展示

class Solution {
   public List<Integer> mostVisited(int n, int[] rounds) {
       // arr[i] + arr[i+n] 表示扇区 i 被访问了多少次
       int[] arr = new int[n * 2];
       int m = rounds.length;
       for (int i = 1; i < m; i++) {
           int start = rounds[i - 1] - 1;
           if (i != 1) start = (start + 1) % n;
           int end = rounds[i] - 1;
           if (end < start) end += n;
           // 当前这一轮访问了 [start, end] 的扇区
           arr[start]++;
           if (end < n * 2 - 1) arr[end + 1]--;
       }
       // 差分数组加和, 得到访问次数
       for (int i = 1; i < n * 2; i++) {
           arr[i] += arr[i - 1];
       }
       // 排序, 统计答案
       int[][] cnt = new int[n][2];
       for (int i = 0; i < n; i++) {
           cnt[i][0] = i + 1; // 扇区编号
           cnt[i][1] = arr[i] + arr[i + n]; // 扇区访问次数
       }
       Arrays.sort(cnt, (a, b) -> (a[1] == b[1] ? (a[0] - b[0]) : (b[1] - a[1])));
       List<Integer> res = new ArrayList<>();
       res.add(cnt[0][0]);
       for (int i = 1; i < n && cnt[i][1] == cnt[i - 1][1]; i++) {
           res.add(cnt[i][0]);
       }
       return res;
   }
}

No.2 你可以获得的最大硬币数目

★ 解题思路

每一轮拿出两个最大的和一个最小的, Alice 拿到最大的, Bob 拿到最小的, 我们拿到第二大的.

相当于每一轮我们都会拿到数组中的第二大的数, 然后从数组中删除前两大的和最小的数, 进行下一轮.

代码展示

class Solution {
   public int maxCoins(int[] piles) {
       Arrays.sort(piles);
       int res = 0;
       int n = piles.length / 3;
       for (int i = 0; i < n; i++) {
           res += piles[n * 3 - 2 - i * 2];
       }
       return res;
   }
}

No.3 查找大小为M的最新分组

★解题思路

倒着做, 第一次出现大小为 M 的时候即可返回答案.

相当于最初有一个 [1, n] 的区间, 每一次操作会拿出一个区间, 一分为二.

使用 TreeSet 维护当前剩余的区间.

代码展示

class Range implements Comparable<Range> {
   public int left, right;

   public Range(int left, int right) {
       this.left = left;
       this.right = right;
   }

   // 按照左端点排序 (该题目区间不会重叠)
   @Override
   public int compareTo(Range o) {
       return left - o.left;
   }
}

class Solution {
   public int findLatestStep(int[] arr, int m) {
       TreeSet<Range> treeSet = new TreeSet<>();
       int n = arr.length;
       if (m == n) return n;
       treeSet.add(new Range(1, n));
       for (int i = n; i >= 1; i--) {
           int pos = arr[i - 1];
           // 当前操作要断开某个区间的 pos 位置, 一分为二
           // 使用 TreeSet 的 floor 方法来找到这个区间
           Range range = treeSet.floor(new Range(pos, 0));
           treeSet.remove(range);
           Range l = new Range(range.left, pos - 1);
           Range r = new Range(pos + 1, range.right);
           if (l.right - l.left + 1 == m) {
               return i - 1;
           }
           if (r.right - r.left + 1 == m) {
               return i - 1;
           }
           if (l.right >= l.left) treeSet.add(l);
           if (r.right >= r.left) treeSet.add(r);
       }
       return -1;
   }
}

No.4 石头游戏V

★解题思路

动态规划.

定义状态 f[i][j] 表示 [i, j] 区间的石子可以得到的最高分数.

枚举从哪里分开即可, 最终取最优解.

代码展示

class Solution {
   public int stoneGameV(int[] stoneValue) {
       int n = stoneValue.length;
       int[] sum = new int[n]; // 前缀和数组, 方便求区间和
       sum[0] = stoneValue[0];
       for (int i = 1; i < n; i++) {
           sum[i] += sum[i - 1] + stoneValue[i];
       }
       int[][] f = new int[n][n]; // 记忆化数组, 初始值 -1, 表示尚未计算
       for (int i = 0; i < n; i++) {
           Arrays.fill(f[i], -1);
       }
       return dp(0, n - 1, f, sum);
   }

   private int dp(int i, int j, int[][] f, int[] sum) {
       if (f[i][j] >= 0) {
           return f[i][j];
       }
       if (i == j) {
           return 0;
       }
       int res = 0;
       for (int k = i; k < j; k++) { // 枚举从哪个位置分开
           int left = sum[k] - (i == 0 ? 0 : sum[i - 1]);
           int right = sum[j] - sum[k];
           if (left == right) { // 左右和相等时, 我们决定取哪一堆, 两种情况求 max
               int t = Math.max(dp(i, k, f, sum), dp(k + 1, j, f, sum));
               res = Math.max(res, t + left);
           } else if (left < right) { // 左右和不相等时, 我们取较小的那一堆
               res = Math.max(res, dp(i, k, f, sum) + left);
           } else {
               res = Math.max(res, dp(k + 1, j, f, sum) + right);
           }
       }
       f[i][j] = res;
       return res;
   }
}

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

上岸算法网络科技有限公司是一家致力于用高质量，高互动性小班课程来帮助学生更好的在就业市场中定位以及求职的公司。我们以顶级的课程质量，高互动性的教学方式以及独特的小班教学模式来帮助学生更快的跨过求职的鸿沟，用最高效，经济，合理的方式帮助更多学生快速找到梦寐以求的工作。