上岸算法 发表于 2021-10-10 21:06:08

上岸算法LeetCode Weekly Contest 262解题报告

【 NO.1 至少在两个数组中出现的值】

解题思路
签到题。

代码展示

class Solution {
   public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
       int[] count1 = new int;
       int[] count2 = new int;
       int[] count3 = new int;
       for (int n : nums1) {
         count1 = 1;
      }
       for (int n : nums2) {
         count2 = 1;
      }
       for (int n : nums3) {
         count3 = 1;
      }
       List<Integer> result = new ArrayList<>();
       for (int i = 0; i < 200; i++) {
         if (count1 + count2 + count3 >= 2) {
               result.add(i);
          }
      }
       return result;
}
}

【 NO.2 获取单值网格的最小操作数】

解题思路
网格可以转换成一维数组,然后排序。

不返回 -1 的条件就是:任意两个元素的差都是 x 的整倍数,我们只需要检查相邻元素即可。

然后枚举最终的唯一值,可以利用前缀、后缀和快速计算出把所有数字变成该值的操作次数。

代码展示

class Solution {
   public int minOperations(int[][] grid, int x) {
       int[] arr = new int.length];
       for (int i = 0; i < grid.length; i++) {
         for (int j = 0; j < grid.length; j++) {
               arr.length + j] = grid;
          }
      }
       Arrays.sort(arr);
       for (int i = 1; i < arr.length; i++) {
         if ((arr - arr) % 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;
         result = Math.min(result, calc(prefixSum, suffixSum, i, arr.length - i - 1, arr, x));
         prefixSum += arr;
      }
       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;
       System.arraycopy(nums, half, half2, 0, half2.length);
       // sums1 表示从 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 表示 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;
                   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;
}
}
页: [1]
查看完整版本: 上岸算法LeetCode Weekly Contest 262解题报告