上岸算法

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

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

No.1 最富有客户的资产总量

★解题思路

求子数组和的最大值. 可以使用 Java 8 之后的 stream 一句话搞定.

代码展示

class Solution { 
   public int maximumWealth(int[][] accounts) { 
       return Arrays.stream(accounts). 
               map(i -> Arrays.stream(i).sum()). 
               max(Integer::compareTo).get(); 
   } 
}

No.2 找出最具竞争力都子序列

★解题思路

即找到长度为 k 的字典序最小的子序列. 贪心地每次取最小的数即可.

但是我们不能取全局范围的最小数, 比如说第一次取, 我们只能在 [0, n - k] 的下标范围内取最小的, 假设取到的最小值的下标为 x, 那么第二次取就应该在 [x, n - k + 1] 的下标范围内取最小的.

可以使用优先队列完成.

代码展示

class Solution { 
   class Number { 
       int num; 
       int idx; 

       public Number(int num, int idx) { 
           this.num = num; 
           this.idx = idx; 
       } 
   } 

   public int[] mostCompetitive(int[] nums, int k) { 
       // 优先按照数值大小排序, 大小相同则按照下标排序 
       PriorityQueue<Number> heap = new PriorityQueue<>((a, b) -> a.num == b.num ? a.idx - b.idx : a.num - b.num); 

       // idx 表示区间的右端点 
       int idx; 
       for (idx = 0; idx <= nums.length - k; idx++) { 
           heap.add(new Number(nums[idx], idx)); 
       } 

       int[] res = new int[k]; 
       int latestIdx = -1; 
       for (int i = 0; i < k; i++) { 
           Number num = heap.poll(); 
           // 利用 latestIdx 移动区间左端点 
           while (num.idx < latestIdx) { 
               num = heap.poll(); 
           } 
           // 取到了当前区间 [x, n - k + i] 中的最小值 
           res[i] = num.num; 
           latestIdx = num.idx; 
           // 右端点更新, 继续向优先队列里加数 
           for (; idx <= nums.length - k + i + 1 && idx < nums.length; idx++) { 
               heap.add(new Number(nums[idx], idx)); 
           } 
       } 
       return res; 
   } 
}

No.3 使数组互补的最少操作数

★解题思路

核心仍然是枚举: 枚举最终的和是多少. 通过预处理的数据快速计算要使每组数达到这个和, 需要改动多少个数字.

代码展示

class Solution { 
   public int minMoves(int[] nums, int limit) { 
       int halfLen = nums.length / 2; 

       // 提取每组数, 便于后续处理 
       int[] smallPart = new int[halfLen]; 
       int[] bigPart = new int[halfLen]; 
       for (int i = 0, j = nums.length - 1; i < j; i++, j--) { 
           smallPart[i] = Math.min(nums[i], nums[j]); 
           bigPart[i] = Math.max(nums[i], nums[j]); 
       } 

       // 数值数量的前缀和 
       int[] smallCntPreSum = new int[limit + 1]; 
       int[] bigCntPreSum = new int[limit + 1]; 
       for (int i = 0; i < halfLen; i++) { 
           smallCntPreSum[smallPart[i]]++; 
           bigCntPreSum[bigPart[i]]++; 
       } 
       for (int i = 1; i <= limit; i++) { 
           smallCntPreSum[i] += smallCntPreSum[i - 1]; 
           bigCntPreSum[i] += bigCntPreSum[i - 1]; 
       } 

       // 原有的加和数值计数 
       int[] sumCnt = new int[limit * 2 + 1]; 
       for (int i = 0; i < halfLen; i++) { 
           sumCnt[smallPart[i] + bigPart[i]]++; 
       } 

       int res = nums.length; 
       for (int sum = 2; sum <= limit + limit; ++sum) { 
           // 最终的和为 sum 时, 需要改动 tot 个数 
           int tot = halfLen - sumCnt[sum]; 
           if (sum <= limit) 
               tot += halfLen - smallCntPreSum[sum - 1]; 
           else 
               tot += bigCntPreSum[sum - limit - 1]; 
           res = Math.min(res, tot); 
       } 
       return res; 
   } 
}

No.4 数组的最小偏移量

★解题思路

每个数都有一定的变化范围, 比如 5 只能变成 5 或 10, 而 8 可以变成 1, 2, 4, 8

双向变化不好处理, 我们可以先将每个数都变成它的最大值的形式: 偶数不变, 奇数可以乘以 2.

然后我们需要做的就是把一些数缩小, 以使得最大值和最小值的差最小.

我们需要缩小的就是最大值——因为只有缩小最大值才能影响结果. 所以, 不断缩小最大值即可.

代码展示

class Solution { 
   public int minimumDeviation(int[] nums) { 
       TreeSet<Integer> set = new TreeSet<>(); 
       for (int num : nums) { 
           set.add(num % 2 == 0 ? num : num * 2); 
       } 
       int res = set.last() - set.first(); 
       while (res > 0 && set.last() % 2 == 0) { 
           int max = set.last(); 
           set.remove(max); 
           set.add(max / 2); 
           res = Math.min(res, set.last() - set.first()); 
       } 
       return res; 
   } 
}

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

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