目录
一，3083. 字符串及其反转中是否存在同一子字符串
二，3084. 统计以给定字符开头和结尾的子字符串总数
三，3085. 成为 K 特殊字符串需要删除的最少字符数
四，3086. 拾起 K 个 1 需要的最少行动次数
一，3083. 字符串及其反转中是否存在同一子字符串
本题是一道字符串题，问原字符串s中是否存在两个连续的字符，使得这两个字符还存在于s的逆序字符串中，有返回true，没有返回false，直接上代码：
class Solution {
public boolean isSubstringPresent(String s) {
char[] ch = s.toCharArray();
boolean[][] bool = new boolean[26][26];
for(int i=1; i<ch.length; i++){
int x = ch[i-1]-'a';
int y = ch[i]-'a';
bool[x][y] = true;
if(bool[y][x])
return true;
}
return false;
}
}二，3084. 统计以给定字符开头和结尾的子字符串总数
本题看上去是一道字符串题，实际是一道排列组合题，先算出字符转 s 中出现字符 c 的个数，记作 n ，从这 n 个字符中选取1个或两个，问有多少种情况，代码如下：
class Solution {
public long countSubstrings(String s, char c) {
long ans = 0;
long cnt = 0;
for(char ch : s.toCharArray()){
if(ch == c)
cnt++;
}
return (cnt+1)*cnt/2;
}
}三，3085. 成为 K 特殊字符串需要删除的最少字符数
本题题意：在只能执行删除操作的情况下，问最少删除几个字符，才能满足任意两个字符在字符串word中出现的次数之差要小于等于k。
思路：先统计每一个字符在字符串中的出现次数，再枚举要保留的字符的出现次数，求出要删除字符串的个数，最后在其中找出最小值并返回。
代码如下：
class Solution {
public int minimumDeletions(String word, int k) {
int[] cnt = new int[26];
for(char ch : word.toCharArray()){
cnt[ch-'a']++;
}
int ans = Integer.MAX_VALUE;
int sum = 0;
Arrays.sort(cnt);
for(int i=0; i<26; i++){
if(i>0)
sum += cnt[i-1];
int t = 0;
int mx = cnt[i]+k;
for(int j=i+1; j<26; j++){
if(mx < cnt[j])
t += cnt[j]-mx;
}
ans = Math.min(ans, sum+t);
}
return ans;
}
}
四，3086. 拾起 K 个 1 需要的最少行动次数
本题题意，选择任意一个下标 idx 作为起始点(固定不动)，如果nums[idx]==1，就可以不需要操作直接拿到1，nums[idx]重新变成0，可以执行以下操作：
- 选择任意一个nums[i]==0 && i != idx，将nums[i]变成1，该操作最多执行 maxChange次
- 选择相邻的两个下标 x，y，且两个值相加必须为1(即一个值为0，另一个值为1)，将这两个下标的值交换，如果交换后，nums[idx] == 1，可以拿走1，nums[idx]重新变成0
返回拾起 k 个 1 所需的最少行动次数
可以得到以下拾起1的操作：
- nums[idx]==1，需要 0 次操作
- 与nums[idx]相邻的值为1，需要执行1次操作
- 使用操作一，需要执行2次操作才能拿到1 (1次操作一+1次操作二)
- 只用操作二，需要执行 |i - idx| 次操作才能拿到1
根据上述操作，可以得出一些操作优先级：
- idx，idx+1，idx-1 这些下标的值为1
- 执行操作一来获得1
- 执行操作二来获得1
先把maxChange比较大的情况处理了，设 c 为连续1的出现次数，如果maxChange >= k - c，说明剩下的 k-c 个 1 可以使用操作一得到，直接返回 2*(k-c)+Math.max(c-1,0)。
如果maxChange比较小，优先执行操作一，也就是说还需要 size = k - maxChange 个 1，因这size个1只能通过操作二获得，所以接下的问题就变成了货舱选址问题，即如何选择一个地点，使得所有的货舱到达该地点的距离之和最小，这里直接告诉你们结论，选择中位数的地方。
注：可能会疑惑为什么这里没有优先考虑连续1的操作？因为选取连续1的操作本质上也是操作二，也就是说，这里的货舱选址问题已经包含了这种情况。
代码如下：
class Solution {
//当出现连续的三个1时，收取3个1的最少操作是2次，操作二两次
//当出现连续的两个1时，收取2个1的最少操作是1次，操作二一次
public long minimumMoves(int[] nums, int k, int maxChanges) {
List<Integer> list = new ArrayList<>();//统计1的下标
int c = 0;//统计连续出现的1的最大次数(0，1，2，3)，再大就不赚了
for(int i=0; i<nums.length; i++){
if(nums[i] == 1){
list.add(i);
c = Math.max(c, 1);
if(i>0 && nums[i-1]==nums[i]){
c = Math.max(c, 2);
if(i>1 && nums[i-2]==nums[i-1])
c = Math.max(c, 3);
}
}
}
c = Math.min(c,k);
if(c + maxChanges >= k)
return 2*(k-c)+Math.max(c-1,0);
int n = list.size();
long[] pre = new long[n+1];
long ans = Long.MAX_VALUE;
for(int i=0; i<n; i++)
pre[i+1] = pre[i] + list.get(i);
int size = k - maxChanges;
for(int l=0,r=size-1; r<n; l++,r++){
int i = (l+r)/2;
long s1 = (i-l)*list.get(i)-(pre[i]-pre[l]);
long s2 = (pre[r+1]-pre[i])-(r+1-i)*list.get(i);
ans = Math.min(ans, s1+s2);
}
return ans + 2*maxChanges;
}
}
