Leetcode - 周赛389

本文主要是介绍Leetcode - 周赛389，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一，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;}
}

这篇关于Leetcode - 周赛389的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！