No.1 最富裕客户的资产总量
解题思路
求子数组和的最大值. 能够应用 Java 8 之后的 stream 一句话搞定.
代码展现
classSolution{ publicintmaximumWealth(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 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; }}