【LeetCode周赛】第 389 场周赛

3083. 字符串及其反转中是否存在同一子字符串 简单

3083. 字符串及其反转中是否存在同一子字符串

分析：
易得：当存在 长度≥2 的反转子字符串时，一定会有 长度=2 的反转子字符串，因此只需要判断长度为2的子字符串即可。

法一：直接判断。
法二：哈希表。

代码：

直接判断：

class Solution {
public:
    bool isSubstringPresent(string s) {
        int n=s.size();
        for(int i=0;i<n-1;i++){
            string str = s.substr(i,2);reverse(str.begin(), str.end());
            if(s.find(str)!=string::npos) return true;
        }
        return false;
    }
};

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        n = len(s)
        for i in range(n-1):
            if s[i:i+2] in s[::-1]:
                return True
        return False

哈希表：

class Solution {
public:
    bool isSubstringPresent(string s) {
        int n = s.size();
        vector<long long> vis(26,0);
        for(int i=1;i<n;i++){
            int x = s[i-1]-'a', y = s[i]-'a';
            vis[x] |= 1<<y;// 数字中二进制位 0~25 为分别表示26个字母，对二进制位为 1，则表示 x 代表字母之后出现了该字母
            if(vis[y] >> x & 1) return true;
        } 
        return false;
    }
};

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        vis = [0] * 26
        for x, y in pairwise(map(ord, s)):
            x -= ord('a')
            y -= ord('a')
            vis[x] |= 1<<y
            if vis[y] >> x&1:
                return True
        return False

3084. 统计以给定字符开头和结尾的子字符串总数 中等

3084. 统计以给定字符开头和结尾的子字符串总数

分析：
统计给定字符在字符串中出现的次数 cnt。
以该字符串开头和结尾的子字符串，即任意选择两个该字符组成的子字符串的个数。$C_2^{cnt}$

代码：

class Solution {
public:
    long long countSubstrings(string s, char c) {
        int n=s.size();
        long long ans=0,cnt=0;
        for(int i=0;i<n;i++){
            if(s[i]==c){
                ans+=cnt;
                cnt++;
            }
        }
        return ans+cnt;
    }
};

class Solution {
public:
    long long countSubstrings(string s, char c) {
        int cnt=0;
        for(auto& t : s) if(t == c) cnt++;
        return 1LL*(1+cnt)*cnt/2;
    }
};

class Solution:
    def countSubstrings(self, s: str, c: str) -> int:
        cnt = s.count(c)
        return (cnt+1)*cnt//2

3085. 成为 K 特殊字符串需要删除的最少字符数 中等

3085. 成为 K 特殊字符串需要删除的最少字符数

分析：
需要得到最少删除字符数，我们反向思考，构造字符串。因为要得到最少的删除数，出现次数最少的字符，要么完全删除，要么完全保留。如果删除一部分，那么出现次数过多的也要一起删除，则不会是最少字符数。
枚举最少的字符的数量，再不断枚举其余字符的数量，构建 K特殊字符串，取最长的构造的字符串，结果即为原字符串长度 - 最长的构造的字符串的长度。

代码：

class Solution {
public:
    int minimumDeletions(string word, int k) {
        vector<int> cnt(26,0),t;
        int n=word.size();
        for(int i=0;i<n;i++) cnt[word[i]-'a']++;
        for(int i=0;i<26;i++) if(cnt[i]>0) t.push_back(cnt[i]);
        sort(t.begin(),t.end());
        int all = accumulate(t.begin(), t.end(), 0),ans=all;
        for(int i=0;i<t.size();i++){
            int c=t[i];
            for(int j=i+1;j<t.size();j++){
                c+=min(t[i]+k,t[j]);
            }
            ans=min(ans, all-c);
        }
        return ans;
    }
};

class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:
        cnt,ans = [0]*26,0
        for i in word:
            cnt[ord(i) - ord('a')]+=1
        cnt = sorted(cnt)
        for i,x in enumerate(cnt):
            if x == 0:
                continue
            c = x
            for j in cnt[i+1:]:
                c+=min(x+k,j)
            ans = max(ans,c)
        return sum(cnt) - ans

3086. 拾起 K 个 1 需要的最少行动次数 困难

3086. 拾起 K 个 1 需要的最少行动次数

分析：
对于获取转换后的1，至少需要两次操作(方法一+方法二)
对于获取原本就存在的1，则需要看对应下标与 $index$。

注意：并非获取转换后的 1 操作数更少，设原本存在的 1 的下标为x

• 当 $x==index$ ，不需要操作。
• 当 $|x-index|==1$，仅需要一个操作。

因此在统计时，查看是否存在连续2或者3个 1 出现，同时再看是否能通过生成 1 来获取，否则只能一点一点移动。

代码：

class Solution {
public:
    long long minimumMoves(vector<int>& nums, int k, int maxChanges) {
        int c=0, n=nums.size();
        vector<int> point;
        for(int i=0;i<n;i++){
            if(nums[i]==0) continue;
            point.push_back(i);
            c=max(c,1);// 至少有一个连续的 1
            if(i>0 && nums[i-1]==1){
                if(i>1 && nums[i-2]==1){
                    c=3; // 有三个连续的 1
                }else{
                    c=max(c,2); // 至少有两个连续的 1
                }
            }
        }
        c=min(c,k); // 判断 c 是否满足 k，如果 c>k，那么就不需要这么多连续的 1。
        if(maxChanges >= k-c){ // 在取完连续 1，后，变化操作是否满足
            return max(c-1,0) + (k-c)*2; // 满足的话 直接返回操作次数
        }
        int m=point.size();
        vector<long long> sum(m+1,0);
        for(int i=0;i<m;i++){
            sum[i+1] = sum[i] + 1LL*point[i];
        }
        int size = k-maxChanges; // 还剩下多少需要一个一个移位
        long long ans = LLONG_MAX;
        for(int r = size;r<=m;r++){
            int l = r-size, i=l+size/2;
            long long index = point[i];
            long long s1 = index * (i-l) - (sum[i] - sum[l]); // 将中位数 i 左边的所有 1 移位到 index 所需的操作数
            long long s2 = sum[r] - sum[i]-index*(r-i); // 将中位数 i 右边的所有 1 移位到 index 所需的操作数
            ans = min(ans, s1+s2);
        }
        return ans + maxChanges*2;
    }
};

class Solution:
    def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:
        pos = []
        n,c = len(nums),0
        for i,n in enumerate(nums):
            if n==0:
                continue
            c=max(c,1)
            pos.append(i)
            if i>0 and nums[i-1]==1:
                if i>1 and nums[i-2]==1:
                    c=3
                else:
                    c=max(c,2)
        c=min(c,k)
        if maxChanges>=k-c:
            return max(c-1,0) + (k-c)*2
        n,ans = len(pos), inf
        pre_sum = list(accumulate(pos, initial=0))
        s = k - maxChanges
        for r in range(s, n+1):
            l = r - s
            i = l + s//2
            index = pos[i]
            s1 = (index * (i-l)) - (pre_sum[i] - pre_sum[l]) 
            s2 = (pre_sum[r] - pre_sum[i]) - index * (r-i)
            ans = min(ans , s1+s2)
        return ans + maxChanges*2