到目标字符串的最短距离

题目

Solution

class Solution {
public:
    int closetTarget(vector<string>& words, string target, int startIndex) {
        int n = words.size();
        int ans = -1;
        for(int i = 0;i <= n/2;i++){//i为目标words与startIndex的相对位置
            if(words[(startIndex + i) % n] == target){
                ans = i;
                break;
            }
            if(words[(startIndex - i + n) % n] == target){
                ans = i;
                break;
            }
        }
        return ans;
    }
};

每种字符至少取 K 个

题目

Solution

class Solution {
public:
    int takeCharacters(string s, int k) {
        int n = s.size();
        int numsa = count(s.begin(),s.end(),'a');//串中a的个数
        int numsb = count(s.begin(),s.end(),'b');//串中b的个数
        int numsc = count(s.begin(),s.end(),'c');//串中c的个数
        if(numsa < k || numsb < k|| numsc < k) return-1;
        int a = numsa - k,b = numsb - k,c = numsc - k;
        vector<int> sum(3), check{a,b,c};
        int i,j,ans = INT_MAX;
        for(i = 0, j = 0;j < s.size();j++){
            sum[s[j] - 'a']++;
            if(sum[s[j] - 'a'] > check[s[j] - 'a']){
                while(sum[s[j] - 'a'] > check[s[j] - 'a']){
                    sum[s[i] - 'a']--;
                    i++;
                }
            }
            ans=min(n-(j-i+1),ans);
        }
        return ans;
    }
};

礼盒的最大甜蜜度

题目

Solution

这道题需要用到二分答案。

class Solution {
public:
    int maximumTastiness(vector<int>& price, int k) {
        sort(price.begin(),price.end());
        int n = price.size();
        int l = 0,r = 1e9;//二分边界
        auto check = [&](int u){
            int cnt = 1;//拿了几类糖果计数
            for(int i = 0,j = 0;j < n;j++){
                if(price[j] - price[i] >= u){//该糖果可以拿
                    cnt++;
                    i = j;
                }
            }
            return cnt < k;
        };
        while(l < r){//开始二分
            int mid = (l + r) / 2;
            if(check(mid)){//取大了
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return l-1;
    }
};

好分区的数目

题目

Solution