【 NO.1 至多在两个数组中呈现的值】
解题思路
签到题。
代码展现
class Solution {
public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
int[] count1 = new int[200]; int[] count2 = new int[200]; int[] count3 = new int[200]; for (int n : nums1) { count1[n] = 1; } for (int n : nums2) { count2[n] = 1; } for (int n : nums3) { count3[n] = 1; } List<Integer> result = new ArrayList<>(); for (int i = 0; i < 200; i++) { if (count1[i] + count2[i] + count3[i] >= 2) { result.add(i); } } return result;}
}
图片
【 NO.2 获取单值网格的最小操作数】
解题思路
网格能够转换成一维数组，而后排序。
不返回 -1 的条件就是：任意两个元素的差都是 x 的整倍数，咱们只须要查看相邻元素即可。
而后枚举最终的惟一值，能够利用前缀、后缀和疾速计算出把所有数字变成该值的操作次数。
代码展现
class Solution {
public int minOperations(int[][] grid, int x) {
int[] arr = new int[grid.length * grid[0].length]; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { arr[i * grid[0].length + j] = grid[i][j]; } } Arrays.sort(arr); for (int i = 1; i < arr.length; i++) { if ((arr[i] - arr[i - 1]) % x != 0) { return -1; } } int suffixSum = Arrays.stream(arr).sum(); int prefixSum = 0; int result = suffixSum / x; for (int i = 0; i < arr.length; i++) { suffixSum -= arr[i]; result = Math.min(result, calc(prefixSum, suffixSum, i, arr.length - i - 1, arr[i], x)); prefixSum += arr[i]; } return result;}
private int calc(int prefixSum, int suffixSum, int prefixNum, int suffixNum, int target, int step) {
return (prefixNum * target - prefixSum) / step + (suffixSum - suffixNum * target) / step;}
}
图片
【 NO.3 股票价格稳定】
解题思路
应用两个 TreeMap 即可，一个贮存工夫戳到价格的映射，一个贮存价格呈现了多少次。
代码展现
class StockPrice {
TreeMap<Integer, Integer> timestampToPrice;
TreeMap<Integer, Integer> priceCount;
public StockPrice() {
timestampToPrice = new TreeMap<>(); priceCount = new TreeMap<>();}
public void update(int timestamp, int price) {
if (timestampToPrice.containsKey(timestamp)) { int oldPrice = timestampToPrice.get(timestamp); int count = priceCount.get(oldPrice); if (count == 1) { priceCount.remove(oldPrice); } else { priceCount.put(oldPrice, count - 1); } } timestampToPrice.put(timestamp, price); priceCount.put(price, priceCount.getOrDefault(price, 0) + 1);}
public int current() {
return timestampToPrice.lastEntry().getValue();}
public int maximum() {
return priceCount.lastKey();}
public int minimum() {
return priceCount.firstKey();}
}
图片
【 NO.4 将数组分成两个数组并最小化数组和的差】
解题思路
枚举 + 双指针，具体思路见代码正文。
代码展现
class Solution {
public int minimumDifference(int[] nums) {
int half = nums.length / 2; int[] half1 = Arrays.copyOf(nums, half); int[] half2 = new int[nums.length - half]; System.arraycopy(nums, half, half2, 0, half2.length); // sums1[i] 示意从 half1 中选出 i 个数字失去的和的所有状况，并且从小到大排序 List<List<Integer>> sums1 = getSums(half1); List<List<Integer>> sums2 = getSums(half2); int sum = Arrays.stream(nums).sum(); int result = 0x3f3f3f3f; // 枚举从 half1 中选出 select 个，则须要从 half2 中选出 half - select 个 for (int select = 0; select <= half; select++) { List<Integer> half1Sums = sums1.get(select); List<Integer> half2Sums = sums2.get(half - select); // 从 half1Sums 和 half2Sums 中各选出一个数字，使得它们的和最靠近 sum / 2 int i = 0, j = half2Sums.size() - 1; result = Math.min(result, Math.abs(sum - (half1Sums.get(i) + half2Sums.get(j)) * 2)); for (; i < half1Sums.size(); i++) { while (j > 0 && Math.abs(sum - (half1Sums.get(i) + half2Sums.get(j - 1)) * 2) <= Math.abs(sum - (half1Sums.get(i) + half2Sums.get(j)) * 2)) { j--; } result = Math.min(result, Math.abs(sum - (half1Sums.get(i) + half2Sums.get(j)) * 2)); } } return result;}
// getSums 求出 nums 的所有子集的和
// 返回 List<List<Integer>> sums
// 其中 sums[i] 示意 nums 的所有大小为 i 的子集的和
// 去重并排序
private List<List<Integer>> getSums(int[] nums) {
int n = nums.length; List<Set<Integer>> set = new ArrayList<>(); List<List<Integer>> sums = new ArrayList<>(); for (int i = 0; i <= n; i++) { sums.add(new ArrayList<>()); set.add(new HashSet<>()); } for (int i = 0; i < (1 << n); i++) { int sum = 0; int num = 0; for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) { sum += nums[j]; num++; } } if (!set.get(num).contains(sum)) { set.get(num).add(sum); sums.get(num).add(sum); } } for (int i = 0; i < n; i++) { Collections.sort(sums.get(i)); } return sums;}
}