首先祝大家元宵节快乐！
6348. Take Gifts From the Richest Pile
给你一个整数数组 gifts ，表示各堆礼物的数量。每一秒，你需要执行以下操作：
- 选择礼物数量最多的那一堆。
- 如果不止一堆都符合礼物数量最多，从中选择任一堆即可。
- 选中的那一堆留下平方根数量的礼物（向下取整），取走其他的礼物。
返回在 k 秒后剩下的礼物数量。测试样例
输入：gifts = [25,64,9,4,100], k = 4
输出：29
解释：
按下述方式取走礼物：
- 在第一秒，选中最后一堆，剩下 10 个礼物。
- 接着第二秒选中第二堆礼物，剩下 8 个礼物。
- 然后选中第一堆礼物，剩下 5 个礼物。
- 最后，再次选中最后一堆礼物，剩下 3 个礼物。
最后剩下的礼物数量分别是 [5,8,9,4,3] ，所以，剩下礼物的总数量是 29 。
解答：优先队列寻找最大值，按照题意硬编码即可
class Solution {
public long pickGifts(int[] gifts, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> (b.compareTo(a)));
for (int i : gifts) {
queue.add(i);
}
for (int i = 0; i < k; ++i) {
int tmp = queue.poll();
queue.add((int) Math.sqrt(tmp));
}
long res = 0;
for (int i : queue) {
res += i;
}
return res;
}
}6347. Count Vowel Strings in Ranges
给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。
每个查询 queries[i] = [li, ri] 会要求我们统计在 words 中下标在 li 到 ri 范围内（包含 这两个值）并且以元音开头和结尾的字符串的数目。
返回一个整数数组，其中数组的第 i 个元素对应第 i 个查询的答案。
注意：元音字母是 'a'、'e'、'i'、'o' 和 'u' 。
测试样例：
输入：words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
输出：[2,3,0]
解释：
以元音开头和结尾的字符串是 "aba"、"ece"、"aa" 和 "e" 。查询 [0,2] 结果为 2（字符串 "aba" 和 "ece"）。查询 [1,4] 结果为 3（字符串 "ece"、"aa"、"e"）。查询 [1,1] 结果为 0 。返回结果 [2,3,0] 。
解答: 按照题意，生成满足要求的字符串前缀和数组。然后根据query范围计算满足要求的字符串数量
class Solution {
private static final char[] vowels = {'a','e','i','o','u'};
public int[] vowelStrings(String[] words, int[][] queries) {
int len = words.length;
int[] mem = new int[len + 1];
for (int i = 0; i < len; ++i) {
mem[i + 1] = mem[i] + (isBeginEndWithVowels(words[i]) ? 1 : 0);
}
int[] res = new int[queries.length];
for (int i = 0; i < queries.length; ++i) {
res[i] = mem[queries[i][1] + 1] - mem[queries[i][0]];
}
return res;
}
private boolean isBeginEndWithVowels(String w) {
return isVowels(w.charAt(0)) && isVowels(w.charAt(w.length() - 1));
}
private boolean isVowels(char c) {
for (char v : vowels) {
if (v == c) return true;
}
return false;
}
}6346. House Robber IV
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。
另给你一个整数数组 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。
返回小偷的 最小 窃取能力。
测试样例
输入：nums = [2,3,5,9], k = 2
输出：5
解释：
小偷窃取至少 2 间房屋，共有 3 种方式：
- 窃取下标 0 和 2 处的房屋，窃取能力为 max(nums[0], nums[2]) = 5 。
- 窃取下标 0 和 3 处的房屋，窃取能力为 max(nums[0], nums[3]) = 9 。
- 窃取下标 1 和 3 处的房屋，窃取能力为 max(nums[1], nums[3]) = 9 。
因此，返回 min(5, 9, 9) = 5 。
解答：这道题目又是比较经典的二分查找题目。直观可以知道，窃取能力越大，则满足要求的房间越多，小偷可以实施的偷窃数量越多，即存在单调性。我们利用二分查找，寻找第一个满足要求的盗窃能力
class Solution {
public int minCapability(int[] nums, int k) {
int min = 1, max = findMax(nums);
while (min < max) {
int mid = (min + max) / 2;
if (familyCount(nums, mid) >= k) {
max = mid;
} else {
min = mid + 1;
}
}
return min;
}
private int findMax(int[] nums) {
int max = 0;
for (int i : nums) {
max = Math.max(max, i);
}
return max;
}
private int familyCount(int[] nums, int mid) {
int[] steal = {0,0}, pos = {-1,-1};
for (int i = 0; i < nums.length; ++i) {
if (nums[i] <= mid) {
int cur;
if (i == pos[1] + 1) {
cur = steal[0] + 1;
} else {
cur = steal[1] + 1;
}
steal[0] = Math.max(steal[0], steal[1]);
steal[1] = Math.max(steal[1], cur);
pos[0] = pos[1];
pos[1] = i;
}
}
return steal[1];
}
}6345. Rearranging Fruits
你有两个果篮，每个果篮中有 n 个水果。给你两个下标从 0 开始的整数数组 basket1 和 basket2 ，用以表示两个果篮中每个水果的成本。
你希望两个果篮相等。为此，可以根据需要多次执行下述操作：
- 选中两个下标 i 和 j ，并交换 basket1 中的第 i 个水果和 basket2 中的第 j 个水果。
- 交换的成本是 min(basket1i,basket2j) 。
根据果篮中水果的成本进行排序，如果排序后结果完全相同，则认为两个果篮相等。
返回使两个果篮相等的最小交换成本，如果无法使两个果篮相等，则返回 -1 。
测试样例
输入：basket1 = [4,2,2,2], basket2 = [1,4,1,2]
输出：1
解释：
交换 basket1 中下标为 1 的水果和 basket2 中下标为 0 的水果，交换的成本为 1 。此时，basket1 = [4,1,2,2] 且 basket2 = [2,4,1,2] 。重排两个数组，发现二者相等。
解答：这道题又又又是脑筋急转弯。一共可以分成三步：
- 判断数组是否满足有求，即所有出现的元素都是偶数次数，否则无法做到2个数组一致
- 计算basket1缺少和多余的水果
- 尽量用cost小的水果换cost大的水果，同时注意如果cost小的水果也大于2倍最小水果cost话，可以利用最小cost的水果作为中转完成计算
class Solution {
public long minCost(int[] basket1, int[] basket2) {
if (!isValid(basket1, basket2)) return -1;
int min = Integer.MAX_VALUE;
Map<Integer, Integer> map = new HashMap<>();
for (int i : basket1) {
min = Math.min(min, i);
map.put(i, map.getOrDefault(i, 0) + 1);
}
for (int i : basket2) {
min = Math.min(min, i);
map.put(i, map.getOrDefault(i, 0) - 1);
}
List<Integer> more = new ArrayList<>(), less = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() > 0) {
int time = entry.getValue() / 2;
for (int i = 0; i < time; ++i) {
more.add(entry.getKey());
}
} else if (entry.getValue() < 0) {
int time = -entry.getValue() / 2;
for (int i = 0; i < time; ++i) {
less.add(entry.getKey());
}
}
}
long res = 0;
int l = 0, r = more.size() - 1;
while (r >= 0) {
int tm = Math.min(more.get(l), less.get(r));
if (tm >= 2L * min) {
res = res + 2L * min;
} else {
res = res + tm;
}
++l;
--r;
}
return res;
}
private boolean isValid(int[] basket1, int[] basket2) {
Map<Integer, Integer> map = new HashMap<>();
for (int i : basket1) {
map.put(i, map.getOrDefault(i, 0) + 1);
}
for (int i : basket2) {
map.put(i, map.getOrDefault(i, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() % 2 == 1) return false;
}
return true;
}
}