目录
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. 统计以给定字符开头和结尾的子字符串总数
原题链接
思路分析
简单递推
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 特殊字符串需要删除的最少字符数
原题链接
思路分析
滑动窗口
先统计词频，然后词频升序排序
然后一共就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];//index
long long tot = 0;
for(auto x : {-1, 1})//opt2
if(res && i + x >= 0 && i + x < n) res -= nums[i + x], tot += nums[i + x];
tot += min(maxChanges, res) * 2, res -= min(maxChanges, res);//opt1
if(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;
}
};
