1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();

        auto check = [&](int m) -> bool{
            int index = -1;
            for(int i=0; i<n; i++){
                if(citations[i] >= m){
                    index = i;
                    break;
                }
            }
            if(index == -1) return false;
            return n - index >= m; 
        };

         //check(l)恒为true, check(r)恒为false
        int l = 0, r = n + 1;
        while(l + 1 < r){
            int mid = l + (r - l) / 2;
            if(check(mid)){
                l = mid;
            }else{
                r = mid;
            }
        }
        return l;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    int maximumCandies(vector<int>& candies, long long k) {
        int n = candies.size();

        auto check = [&](int m) -> bool{
            long long total = k;
            for(int i=0; i<n; i++){
                total -= candies[i] / m;
                if(total <= 0){
                    return true;
                }
            }
            return false;
        };

        int l = 0, r = ranges::max(candies) + 1;
        while(l + 1 < r){
            int mid = l + (r - l) / 2;
            if(check(mid)){
                l = mid;
            }else{
                r = mid;
            }
        }
        return l;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
public:
    int maximumLength(string s) {
        int n = s.length();
        auto check = [&](int m) -> bool{
            map<string, int> mp;
            for(int i=0; i<n; i++){
                string ss = "";
                ss += s[i];
                int j = 1;
                while(j < m && s[i] == s[i + j]){
                    ss += s[i + j];
                    j++;
                }

                if(j < m){
                    i += j - 1;
                    continue;
                }else{
                    mp[ss]++;
                    if(mp[ss] >= 3){
                        return true;
                    }
                }
            }
            return false;
        };

        int l = 0, r = n - 1;
        while(l + 1 < r){
            int mid = l + (r - l) / 2;
            if(check(mid)){
                l = mid;
            }else{
                r = mid;
            }
        }
        return l == 0 ? -1 : l;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    int maxNumOfMarkedIndices(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();

        auto check = [&](int m) -> bool{
            for(int i=0; i<m; i++){
                if(nums[i] * 2 > nums[n - m + i]){
                    return false;
                }
            }
            return true;
        };

        //匹配的对数
        int l = 0, r = n / 2 + 1; 
        while(l + 1 < r){
            int mid = l + (r - l) / 2;
            if(check(mid)){
                l = mid;
            }else{
                r = mid;
            }
        }
        return l * 2;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
public:
    int maximumRemovals(string s, string p, vector<int>& removable) {
        int n = s.size();

        auto check = [&](int m) -> bool{
            vector<bool> marked(n);
            for(int i=0; i<m; i++){
                marked[removable[i]] = true;
            }

            string ss = "";
            for(int i=0; i<n; i++){
                if(!marked[i]){
                    ss += s[i];
                }
            }
            
            int nn = ss.length();
            int j = 0;
            for(int i=0; i<nn; i++){
                if(ss[i] == p[j]){
                    j++;
                }
            }
            if(j == p.size()) return true;
            else return false;
        };

        int l = 0, r = removable.size() + 1;
        while(l + 1 < r){
            int mid = l + (r - l) / 2;
            if(check(mid)){
                l = mid;
            }else{
                r = mid;
            }
        }
        return l;
    }
};