本文主要是介绍LeetCode第389场周赛个人题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
100248. 字符串及其反转中是否存在同一子字符串
原题链接
思路分析
AC代码
100236. 统计以给定字符开头和结尾的子字符串总数
原题链接
思路分析
AC代码
100255. 成为 K 特殊字符串需要删除的最少字符数
原题链接
思路分析
AC代码
100227. 拾起 K 个 1 需要的最少行动次数
原题链接
思路分析
AC代码
100248. 字符串及其反转中是否存在同一子字符串
原题链接
100248. 字符串及其反转中是否存在同一子字符串
思路分析
签到题，直接模拟
AC代码
class Solution:def isSubstringPresent(self, s: str) -> bool:return any(s[i:i+2] in s[::-1] for i in range(len(s) - 1))100236. 统计以给定字符开头和结尾的子字符串总数
原题链接
100236. 统计以给定字符开头和结尾的子字符串总数
思路分析
简单递推
f[i]为前i个元素中以c开头c结尾的子字符串总数，cnt[i]为前i个元素中c的数目
有 f[i] = f[i - 1]，s[i] != c时
f[i] = f[i - 1] + cnt[i - 1] + 1，s[i] != c时
时间复杂度：O(n)
AC代码
class Solution {
public:long long countSubstrings(string s, char c) {long long ret = 0, cnt = 0;for(auto x : s)if(x == c) ret = ret + cnt + 1, cnt++;return ret;}
};100255. 成为 K 特殊字符串需要删除的最少字符数
原题链接
100255. 成为 K 特殊字符串需要删除的最少字符数
思路分析
滑动窗口
先统计词频，然后词频升序排序
然后一共就26个字符，枚举每个字符为左端的长度为k + 1的滑动窗口，计算对于每个窗口而言最少删除多少元素
时间复杂度：O(n)
AC代码
class Solution {
public:int minimumDeletions(string s, int k) {int cnt[26]{0}, pre[26]{0}, ret = 1e5, n = s.size();for(auto x : s) cnt[x - 'a']++;sort(cnt, cnt + 26);for(int i = 0; i < 26; i++) pre[i] = (i ? pre[i - 1] : 0) + cnt[i];if(cnt[25] - cnt[0] <= k) return 0;for(int i = 0, t; i < 26; i++){if(!cnt[i]) continue;auto p = lower_bound(cnt, cnt + 26, cnt[i] + k) - cnt;t = i ? pre[i - 1] : 0;for(; p < 26; p++) t += cnt[p] - cnt[i] - k;ret = min(ret, t);}return ret;}//a bb ccc ddddd
};
100227. 拾起 K 个 1 需要的最少行动次数
原题链接
思路分析
中位数贪心+二分
其实不用二分的，比赛的时候写红温了直接二分着来了（
1：我们考虑选取index后，对于相邻的1，可以一步得到
2：然后可以操作一以步数为2的代价造1并得到
3：对于其它的1，可以以其下标到index的距离的步数得到1
不难发现3的代价是大于1、2的
然后我们考虑如果1、2就能得到k个1，那就不考虑3了，因为代价会更大
如果要考虑3，那就等效于在剩余的1中挑出(k - maxChanges - 1中拿掉的1的个数)个1
然后要使得挑出来的1的下标到index距离和最小
那这一步是可以中位数贪心的
所以我们就枚举每个位置，然后先求1、2能拿的1，如果还要拿，就以index为中位数，去二分区间半径
如果区间内1的数目够了，就r = mid，否则l = mid + 1
然后求代价即可，这个可以前缀和预处理然后O(1)获得
然后有一个坑就是区间内的1的数目可能会多一个，所以如果多了要减去多出来的代价
时间复杂度O(nlogn)
可优化之处：
上面我们枚举中位数的过程中枚举了很多为0的位置，其实没必要，所以我们可以提前得到所有1的下标数组，然后在下标数组上枚举中位数，这样可以O(n)解决，而且不用二分
AC代码
class Solution {
public:long long minimumMoves(vector<int>& nums, int k, int maxChanges) {int n = nums.size();vector<int> cnt(n);vector<long long> pre(n);auto getcnt = [&](int i)->long long{if(i < 0) return 0;if(i >= n) return cnt[n - 1];return cnt[i];};auto getpre = [&](int i)->long long{if(i < 0) return 0;if(i >= n) return pre[n - 1];return pre[i]; };for(int i = 0; i < n; i++) cnt[i] = getcnt(i - 1) + nums[i], pre[i] = getpre(i - 1) + i * nums[i];long long ret = 1e12;for(int i = 0; i < n; i++){int res = k - nums[i];//indexlong long tot = 0;for(auto x : {-1, 1})//opt2if(res && i + x >= 0 && i + x < n) res -= nums[i + x], tot += nums[i + x];tot += min(maxChanges, res) * 2, res -= min(maxChanges, res);//opt1if(res){//二分int l = 1, r = n;while(l < r){int mid = l + r >> 1;if(getcnt(i - 2) - getcnt(i - mid - 1) + getcnt(i + mid) - getcnt(i + 1) >= res) r = mid;else l = mid + 1;}int lc = getcnt(i - 2) - getcnt(i - r - 1), rc = getcnt(i + r) - getcnt(i + 1);tot += getpre(i + r) - getpre(i + 1) - 1LL * rc * i + 1LL * lc * i - getpre(i - 2) + getpre(i - r - 1);tot -= (lc + rc - res) * r;}ret = min(ret, tot);}return ret;}
};这篇关于LeetCode第389场周赛个人题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
