专业网站建设包括哪些,教育咨询,公司注销查询系统,关于网站开发的学校目录 一#xff0c;3083. 字符串及其反转中是否存在同一子字符串
二#xff0c;3084. 统计以给定字符开头和结尾的子字符串总数
三#xff0c;3085. 成为 K 特殊字符串需要删除的最少字符数
四#xff0c;3086. 拾起 K 个 1 需要的最少行动次数 一#xff0c;3083. 字符…目录 一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 i1; ich.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 (cnt1)*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 i0; i26; i){if(i0)sum cnt[i-1];int t 0;int mx cnt[i]k;for(int ji1; j26; j){if(mx cnt[j])t cnt[j]-mx;}ans Math.min(ans, sumt);}return ans;}
}四3086. 拾起 K 个 1 需要的最少行动次数 本题题意选择任意一个下标 idx 作为起始点(固定不动)如果nums[idx]1就可以不需要操作直接拿到1nums[idx]重新变成0可以执行以下操作 选择任意一个nums[i]0 i ! idx将nums[i]变成1该操作最多执行 maxChange次选择相邻的两个下标 xy且两个值相加必须为1(即一个值为0另一个值为1)将这两个下标的值交换如果交换后nums[idx] 1可以拿走1nums[idx]重新变成0 返回拾起 k 个 1 所需的最少行动次数 可以得到以下拾起1的操作 nums[idx]1需要 0 次操作与nums[idx]相邻的值为1需要执行1次操作使用操作一需要执行2次操作才能拿到1 (1次操作一1次操作二)只用操作二需要执行 |i - idx| 次操作才能拿到1 根据上述操作可以得出一些操作优先级 idxidx1idx-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) {ListInteger list new ArrayList();//统计1的下标int c 0;//统计连续出现的1的最大次数(0123)再大就不赚了for(int i0; inums.length; i){if(nums[i] 1){list.add(i);c Math.max(c, 1);if(i0 nums[i-1]nums[i]){c Math.max(c, 2);if(i1 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[n1];long ans Long.MAX_VALUE;for(int i0; in; i)pre[i1] pre[i] list.get(i);int size k - maxChanges;for(int l0,rsize-1; rn; l,r){int i (lr)/2;long s1 (i-l)*list.get(i)-(pre[i]-pre[l]);long s2 (pre[r1]-pre[i])-(r1-i)*list.get(i);ans Math.min(ans, s1s2);}return ans 2*maxChanges;}
}
