6269. Shortest Distance to Target String in a Circular Array
给你一个下标从 0 开始的 环形 字符串数组 words 和一个字符串 target 。环形数组 意味着数组首尾相连。
形式上， words[i] 的下一个元素是 words[(i + 1) % n] ，而 words[i] 的前一个元素是 words[(i - 1 + n) % n] ，其中 n 是 words 的长度。
从 startIndex 开始，你一次可以用 1 步移动到下一个或者前一个单词。返回到达目标字符串 target 所需的最短距离。如果 words 中不存在字符串 target ，返回 -1 。
测试样例：
输入：words = ["hello","i","am","leetcode","hello"], target = "hello", startIndex = 1
输出：1解释：从下标 1 开始，可以经由以下步骤到达 "hello" ：
- 向右移动 3 个单位，到达下标 4 。
- 向左移动 2 个单位，到达下标 4 。
- 向右移动 4 个单位，到达下标 0 。
- 向左移动 1 个单位，到达下标 0 。
到达 "hello" 的最短距离是 1 。
解答: 按照题意计算距离，注意循环队列问题。
class Solution {
public int closetTarget(String[] words, String target, int startIndex) {
List<Integer> pos = new ArrayList<>();
for (int i = 0; i < words.length; ++i) {
if (words[i].equals(target)) {
pos.add(i);
}
}
if (!pos.isEmpty()) {
int res = Integer.MAX_VALUE;
for (int i : pos) {
res = Math.min(res, Math.abs(i - startIndex));
if (i < startIndex) {
res = Math.min(res, words.length - startIndex + i);
} else {
res = Math.min(res, startIndex + words.length - i);
}
}
return res;
}
return -1;
}
}6270. Take K of Each Character From Left and Right
给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。
你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。
测试样例：
输入：s = "aabaaaacaabc", k = 2
输出：8解释：
从 s 的左侧取三个字符，现在共取到两个字符 'a' 、一个字符 'b' 。
从 s 的右侧取五个字符，现在共取到四个字符 'a' 、两个字符 'b' 和两个字符 'c' 。
共需要 3 + 5 = 8 分钟。
可以证明需要的最少分钟数是 8 。
解答：队列左右2边进行双指针计算。
class Solution {
public int takeCharacters(String s, int k) {
int[] count = new int[3];
for (int i = 0; i < s.length(); ++i) {
count[s.charAt(i) - 'a'] += 1;
}
if (count[0] < k || count[1] < k || count[2] < k) {
return -1;
}
int res = s.length();
int r = s.length();
for (int i = s.length() - 1; i >= -1; --i) {
while (count[0] < k || count[1] < k || count[2] < k) {
--r;
count[s.charAt(r) - 'a'] += 1;
}
res = Math.min(res, i + 1 + s.length() - r);
if (i >= 0) count[s.charAt(i) - 'a'] -= 1;
}
return res;
}
}6271. Maximum Tastiness of Candy Basket
给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。
商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。
返回礼盒的 最大 甜蜜度。
测试样例：
输入：price = [13,5,1,8,21,2], k = 3输出：8
解释：选出价格分别为 [13,5,21] 的三类糖果。
礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8 。
可以证明能够取得的最大甜蜜度就是 8 。
解答： 排序+二分查找
class Solution {
public int maximumTastiness(int[] price, int k) {
Arrays.sort(price);
int min = 0, max = price[price.length - 1] - price[0] + 1;
while (min < max) {
int mid = min + (max - min + 1) / 2;
int last = price[0], count = 1;
for (int i : price) {
if (i - last >= mid) {
last = i;
++count;
}
}
if (count >= k) {
min = mid;
} else {
max = mid - 1;
}
}
return min;
}
}6272. Number of Great Partitions
给你一个正整数数组 nums 和一个整数 k 。
分区 的定义是：将数组划分成两个有序的 组 ，并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k ，则认为分区是一个好分区。
返回 不同 的好分区的数目。由于答案可能很大，请返回对 109 + 7 取余 后的结果。
如果在两个分区中，存在某个元素 nums[i] 被分在不同的组中，则认为这两个分区不同。
测试样例：
输入：nums = [1,2,3,4], k = 4输出：6
解释：好分区的情况是 ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) 和 ([4], [1,2,3]) 。
解答：这道题目真的阅读理解，完全没理解这个有序组的含义。。。实际就是简单的动态规划。反向思维，计算所有可能，然后排出不可能的组合。代码仅供参考，如果判断sum不符合条件的情况，计算会出错。总觉得哪里还有bug。
class Solution {
private static final int mod = 1_000_000_007;
public int countPartitions(int[] nums, int k) {
if (!isValid(nums, k)) {
return 0;
}
int res = 1;
for (int i = 0; i < nums.length; ++i) {
res = res * 2 % mod;
}
int[] count = new int[k];
count[0] = 1;
for (int i : nums) {
for (int j = k - 1; j >= i; --j) {
count[j] = (count[j] + count[j - i]) % mod;
}
}
for (int i : count) {
res = (res + mod - (i * 2 % mod)) % mod;
}
return res;
}
private boolean isValid(int[] nums, int k) {
long sum = 0;
for (int i : nums) {
sum += i;
}
return nums.length > 1 && sum >= k * 2;
}
}