5-周赛331总结

都有思路，但是第三题第四题代码就差了一点点，还是时间不够+不大熟练

从数量最多的堆取走礼物【LC6348】

给你一个整数数组 gifts ，表示各堆礼物的数量。每一秒，你需要执行以下操作：

• 选择礼物数量最多的那一堆。
• 如果不止一堆都符合礼物数量最多，从中选择任一堆即可。
• 选中的那一堆留下平方根数量的礼物（向下取整），取走其他的礼物。

返回在 k 秒后剩下的礼物数量*。*

• 思路：使用大顶堆存储所有的礼物，每次选择礼物数量最多的一堆，即堆顶元素，然后将剩余礼物数量放入堆中，反复执行操作$k$次，返回剩余的礼物数量

• 实现

  class Solution {
      public long pickGifts(int[] gifts, int k) {
          PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2) -> (o2 - o1));
          long sum = 0L;
          for (int g : gifts){
              sum += g;
              pq.add(g);
          }
          for (int i = 0; i < k; i++){
              int max = pq.poll();
              if (max == 1) break;
              int s = (int)Math.sqrt(max);
              sum -= max - s;
              pq.add(s);
          }
          return sum;
      }
  }
  

  • 复杂度
    • 时间复杂度：$O(n)$
    • 空间复杂度：$O(1)$

统计范围内的元音字符串数【LC6347】

给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。

每个查询 queries[i] = [li, ri] 会要求我们统计在 words 中下标在 li 到 ri 范围内（包含 这两个值）并且以元音开头和结尾的字符串的数目。

返回一个整数数组，其中数组的第 i 个元素对应第 i 个查询的答案。

**注意：**元音字母是 'a'、'e'、'i'、'o' 和 'u' 。

• 思路：需要查询words中某个区间的元音字符串的个数，因此使用前缀和数组$sum[i+1]$计算出下标范围为$[0,i]$的元音字符串个数，区间$[l,r]$内的元音字符串的个数即为$sum[r+1]-sum[l]$

• 实现

  class Solution {
      public int[] vowelStrings(String[] words, int[][] queries) {
          int n = words.length;
          int m = queries.length;
          int[] sum = new int[n + 1];
          int[] res = new int[m];
          Arrays.fill(res, 0);
          for (int i = 0; i < n; i++){
              if (isVowel(words[i])){
                  sum[i + 1] = sum[i] + 1;
              }else{
                  sum[i + 1] = sum[i];
              }
          }
          for (int i = 0; i < m; i++){
              int l = queries[i][0], r = queries[i][1];
              res[i] = sum[r + 1] - sum[l];
          }
          return res;
  
      }
      public boolean isVowel(String word){
          char c = word.charAt(0);
          char c1 = word.charAt(word.length() - 1);
          if ( (c == 'a' || c  == 'e' || c == 'i' || c == 'o' || c == 'u') 
              && (c1 == 'a' || c1  == 'e' || c1 == 'i' || c1 == 'o' || c1 == 'u')){
              return true;
          }
          return false;
      }
  }
  

  • 复杂度
    • 时间复杂度：$O(n)$
    • 空间复杂度：$O(n)$

打家劫舍 IV【LC6346】

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。

由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。

小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。

给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。

另给你一个整数数组 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。

返回小偷的 最小 窃取能力。

回溯【超时】

• 思路：枚举每一种可能的窃取方案，返回最小窃取能力

• 实现

  class Solution {
      int ans = Integer.MAX_VALUE;
      public int minCapability(int[] nums, int k) {
          backtracking(nums, k, 0, 0, 0);
          return ans;
      }
      public void backtracking(int[] nums, int k, int count, int max, int start){
          if (count == k) ans = Math.min(ans, max);
          if (start >= nums.length || start + (k - count - 1) * 2 >= nums.length) return;
          backtracking(nums, k, count, max, start + 1);// 不取
          backtracking(nums, k, count + 1, Math.max(max,nums[start]), start + 2);// 取
      }
  }
  

  • 复杂度
    • 时间复杂度：$O(n^k)$
    • 空间复杂度：$O(1)$

二分答案

卡在了check没想明白

• 思路：

  • 由于当窃取能力越大，可以偷取的房屋数越打，因此可以通过二分查找搜索最小窃取能力。
  • 那么，可以将题意转化为，当偷取房屋数量一定时，寻找最小的窃取能力$y$，二分查找的下限为$min(nums[i])$，上限为$max(nums[i])$

• 实现

  • 当二分查找窃取能力$y$是否合法时，需要判断可以偷取的房屋数量是否大于等于k，如果可以偷取的房屋数量大于等于k，那么我们可以减小窃取能力；如果不能，那么增大窃取能力
    • 我们从左到右枚举每座房子，同时记录上一次抢夺的房子的下标 j。如果当前房子可以抢夺（价值小于等于 $y$，且不和 j 相邻）就进行抢夺。因为越早抢夺，留给右边的抢夺机会就越多。如果抢夺的房屋数量，大于等于$k$，那么返回true，减小窃取能力，以减小房屋数量；反之返回false，增大窃取能力，以增大房屋数量

  class Solution {
      public int minCapability(int[] nums, int k) {
          int n = nums.length;
          int res = Integer.MAX_VALUE;
          int l = Integer.MIN_VALUE, r = 0;
          for (int num : nums){
              r = Math.max(r, num);
              l = Math.min(l, num);            
          }
          while (l <= r){
              int mid = (l + r) / 2;
              if (check(nums, mid, k)){
                  r = mid - 1;
                  res = Math.min(res, mid);
              }else{
                  l = mid + 1;
              }
          }
          return res;
  
      }
      public boolean check(int[] nums, int target, int k){
          int n = nums.length;
          int j = -2;
          int count = 0;
          for (int i = 0; i < n; i++){
              if (j + 2 <= i && nums[i] <= target){
                  count++;
                  j = i;
                  if (count >= k) return true;
              }     
          }
          return false;
      }
  }
  

  • 复杂度
    • 时间复杂度：$O(nlogmax)$，$max$为nums中的最大值
    • 空间复杂度：$O(1)$

重排水果【LC6345】

你有两个果篮，每个果篮中有 n 个水果。给你两个下标从 0 开始的整数数组 basket1 和 basket2 ，用以表示两个果篮中每个水果的成本。

你希望两个果篮相等。为此，可以根据需要多次执行下述操作：

• 选中两个下标 i 和 j ，并交换 basket1 中的第 i 个水果和 basket2 中的第 j 个水果。
• 交换的成本是 min(basket1i,basket2j) 。

根据果篮中水果的成本进行排序，如果排序后结果完全相同，则认为两个果篮相等。

返回使两个果篮相等的最小交换成本，如果无法使两个果篮相等，则返回 -1 。

卡在了越界

• 思路：【贪心】

  • 首先使用哈希表记录basket1 和 basket2 中不相同的数及其个数

    • 个数为正数表示该水果在basket1中
    • 个数为负数表示该水果在basket2中

  • 然后遍历哈希表，如果个数为奇数，那么无法使两个果篮相等，直接返回-1；如果个数为偶数，那么放入相应的堆中，贪心交换果篮，一个堆从小到大排序，另一个堆从大到小排序

    • 局部最优：每次交换的交换成本最小，此时的交换方式有两种

      • 直接将果篮的待交换的最小成本val和另一个果篮的待交换的最大成本进行交换
      • 使用一个中间值交换两次，即果篮中的最小成本m，此时的交换成本为$2\ast m$

      因此每次交换的最小成本为$min(val,2\ast m)$

    • 全局最优：当两个果篮相等时，交换成本最小

• 实现

  class Solution {
      public long minCost(int[] basket1, int[] basket2) {
          Map<Integer,Integer> map = new HashMap<>();
          int n = basket1.length;
          // 记录每个成本对应的次数
          for (int i = 0; i < n; i++){
              map.put(basket1[i], map.getOrDefault(basket1[i], 0) + 1);
              map.put(basket2[i], map.getOrDefault(basket2[i], 0) - 1);
          }       
          PriorityQueue<int[]> pq1 = new PriorityQueue<>((o1,o2) -> o1[0] - o2[0]);// 果篮1待交换的成本
          PriorityQueue<int[]> pq2 = new PriorityQueue<>((o1,o2) -> o2[0] - o1[0]);// 果篮2待交换的成本
          int min = Integer.MAX_VALUE;// 两个果篮中的最小成本
          for (var node : map.entrySet()){
              int key = node.getKey(), val = node.getValue();
              min = Math.min(min, key);
              if (val % 2 != 0) return -1;
              if (val > 0){// 果篮1
                  pq1.add(new int[]{key, val});
              }else if (val < 0){// 果篮2
                  pq2.add(new int[]{key, -val});
              }
          }
          long res = 0L;
          while (!pq1.isEmpty()){// 两个堆一定同时为空
              int[] poll1 = pq1.poll();
              int[] poll2 = pq2.poll();
              // 测试用例35错误 结果为负数，越界
              // int count = Math.min(poll1[1] / 2, poll2[1] / 2);
              long count = Math.min(poll1[1] / 2, poll2[1] / 2);
              res += Math.min(Math.min(poll1[0], poll2[0]) * count, min * count * 2);
              poll1[1] -= count * 2;
              poll2[1] -= count * 2;
              if (poll1[1] != 0){                
                  pq1.add(poll1);
              } 
              if (poll2[1] != 0){                
                  pq2.add(poll2);
              }
          }
          return res;
      }
  }
  

  • 复杂度
    • 时间复杂度：$O(n+logn)$，遍历数组和交换水果的时间复杂度为$O(n)$，向优先队列存放元素的时间复杂度为$O(logn)$
    • 空间复杂度：$O(n)$

• 优化：假设果篮1中待交换的水果有$count$个，由于在交换过程中val为两个果篮待交换成本中最小的成本，因此可以将两个果篮中待交换的水果拼接在一起，遍历前$count$个最小的数即可

  class Solution {
      public long minCost(int[] basket1, int[] basket2) {
          var cnt = new HashMap<Integer, Integer>();
          for (int i = 0; i < basket1.length; ++i) {
              cnt.merge(basket1[i], 1, Integer::sum);
              cnt.merge(basket2[i], -1, Integer::sum);
          }
  
          int mn = Integer.MAX_VALUE;
          var a = new ArrayList<Integer>();
          for (var e : cnt.entrySet()) {
              int x = e.getKey(), c = e.getValue();
              if (c % 2 != 0) return -1;
              mn = Math.min(mn, x);
              for (c = Math.abs(c) / 2; c > 0; --c)
                  a.add(x);
          }
  
          long ans = 0;
          a.sort((x, y) -> x - y); // 也可以用快速选择
          for (int i = 0; i < a.size() / 2; ++i)
              ans += Math.min(a.get(i), mn * 2);
          return ans;
      }
  }
  
  作者：灵茶山艾府
  链接：https://leetcode.cn/problems/rearranging-fruits/solutions/2093878/tan-xin-gou-zao-by-endlesscheng-c2ui/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  

  • 复杂度
    • 时间复杂度：$O(nlogn)$
    • 空间复杂度：$O(n)$