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∗m
因此每次交换的最小成本为min(val,2∗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 ( n l o g n )
- 空间复杂度：O ( n )
