算法1:到目标字符串的最短距离（6269）
给你一个下标从 0 开始的 环形 字符串数组 words 和一个字符串 target 。环形数组 意味着数组首尾相连。
- 形式上，
words[i] 的下一个元素是 words[(i + 1) % n] ，而 words[i] 的前一个元素是 words[(i - 1 + n) % n] ，其中 n 是 words 的长度。
从 startIndex 开始，你一次可以用 1 步移动到下一个或者前一个单词。
返回到达目标字符串 target 所需的最短距离。如果 words 中不存在字符串 target ，返回 -1 。
示例 1：
1
2
3
4
5
6
7
8
| 输入：words = ["hello","i","am","leetcode","hello"], target = "hello", startIndex = 1
输出：1
解释：从下标 1 开始，可以经由以下步骤到达 "hello" ：
- 向右移动 3 个单位，到达下标 4 。
- 向左移动 2 个单位，到达下标 4 。
- 向右移动 4 个单位，到达下标 0 。
- 向左移动 1 个单位，到达下标 0 。
到达 "hello" 的最短距离是 1 。
|
示例 2：
1
2
3
4
5
6
| 输入：words = ["a","b","leetcode"], target = "leetcode", startIndex = 0
输出：1
解释：从下标 0 开始，可以经由以下步骤到达 "leetcode" ：
- 向右移动 2 个单位，到达下标 3 。
- 向左移动 1 个单位，到达下标 3 。
到达 "leetcode" 的最短距离是 1 。
|
示例 3：
1
2
3
| 输入：words = ["i","eat","leetcode"], target = "ate", startIndex = 0
输出：-1
解释：因为 words 中不存在字符串 "ate" ，所以返回 -1 。
|
+++++++++++++
简单题
思路：自己的思路，感觉想复杂了，首先先求出目标字符串在字符串数组中的什么位置，通过从start开始取最小的位置。。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int closetTarget(String[] words, String target, int startIndex) {
boolean f = false;
List<Integer> list = new ArrayList<>();
for (int i = 0;i<words.length;i++){
if (words[i].equals(target)) {
f = true;
list.add(i);
}
}
if (!f) return -1;
if (list.size()==1){
return Math.min(Math.abs(startIndex-list.get(0)),Math.min(startIndex,list.get(0))+words.length-Math.max(startIndex,list.get(0)));
}else {
int min = Integer.MAX_VALUE;
for (int i = 0;i<list.size();i++){
min = Math.min(Math.min(min,Math.min(startIndex,list.get(i))+words.length-Math.max(startIndex,list.get(i))),Math.abs(startIndex-list.get(i)));
}
return min;
}
}
}
|
大佬的思路：就是妙~~，从start出发，分别判断向左移和向右移，是否相等，如果相等直接返回，相当于中心扩散法，从start扩散，则首先返回的一定是距离start最近的一个。
代码为：
1
2
3
4
5
6
7
8
9
| class Solution {
public int closetTarget(String[] words, String target, int startIndex) {
int n = words.length;
for (int i = 0;i<words.length;i++){
if (target.equals(words[(startIndex+i)%n]) || target.equals(words[(startIndex-i+n)%n])) return i;
}
return -1;
}
}
|
算法2
给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。
你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。
示例 1：
1
2
3
4
5
6
7
| 输入：s = "aabaaaacaabc", k = 2
输出：8
解释：
从 s 的左侧取三个字符，现在共取到两个字符 'a' 、一个字符 'b' 。
从 s 的右侧取五个字符，现在共取到四个字符 'a' 、两个字符 'b' 和两个字符 'c' 。
共需要 3 + 5 = 8 分钟。
可以证明需要的最少分钟数是 8 。
|
示例 2：
1
2
3
| 输入：s = "a", k = 1
输出：-1
解释：无法取到一个字符 'b' 或者 'c'，所以返回 -1 。
|
++++++++++++
中等题
思路：滑动窗口求出，先求出，中间最多能删除几个字符可以使条件成立，最后再根据总长度-中间长度为答案
代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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']++;
}
for (int i =0 ;i<3;i++){
if (count[i]<k) return -1;
}
int res = 0;
int n = s.length();
for (int l = 0,r = 0;r<s.length();r++) {
count[s.charAt(r) - 'a']--;
while (count[s.charAt(r) - 'a'] < k) {
count[s.charAt(l) - 'a']++;
l++;
}
res = Math.max(res, r - l + 1);
}
return n-res;
}
}
|
算法3
给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。
商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。
返回礼盒的 最大 甜蜜度。
示例 1：
1
2
3
4
5
| 输入：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 。
|
示例 2：
1
2
3
4
5
| 输入：price = [1,3,1], k = 2
输出：2
解释：选出价格分别为 [1,3] 的两类糖果。
礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2 。
可以证明能够取得的最大甜蜜度就是 2 。
|
示例 3：
1
2
3
| 输入：price = [7,7,7,7], k = 2
输出：0
解释：从现有的糖果中任选两类糖果，甜蜜度都会是 0 。
|
+++++++++++++++++
中等题
思路：二分法，对可能的结果进行二分。最小值取0，最大值为所给数组中的最大值。结果一定在这个最小值和最大值区间 ，所以对该区间进行二分。对于一个二分结果，进行判断，是否能取到k个数，如果能说明这个mid取小了，还可以再大，所以在区间【mid，max】中找，如果不能取到k个数，说明mid值取大了，就要在【min，mid】中找。
代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int maximumTastiness(int[] price, int k) {
Arrays.sort(price);
int n = price.length;
int l = 0;
int r = price[n-1];
while (l<r){
int mid = (l+r)>>1;
if (check(mid,k,price)){
l = mid+1;
}else {
r = mid;
}
}
return l-1;
}
public boolean check(int mid,int k,int price[]){
int pre = price[0];
int count = 1;
for (int i = 1;i<price.length;i++){
if (price[i]-pre>=mid){
count++;
pre = price[i];
}
}
return count>=k;
}
}
|
算法4