上岸算法 | LeetCode Weekly Contest 第 262 场周赛解题报告 算法 刷题解法 题目求助

卖大米 3月前 74


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

解题思路

签到题。

代码展示

class Solution {

   public List 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 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> sums1 = getSums(half1);

       List<List> 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 half1Sums = sums1.get(select);

           List 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> sums

   // 其中 sums[i] 表示 nums 的所有大小为 i 的子集的和

   // 去重并排序

   private List<List> getSums(int[] nums) {

       int n = nums.length;

       List<Set> set = new ArrayList<>();

       List<List> 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;

  }

}

最新回复 (0)
返回