Leetcode算法题1201-1300

1201-1210¶

1211-1220¶

1221-1230¶

1231-1240¶

1234.替换子串得到平衡字符串¶

class Solution {
public:
    int map(char s) {
        if (s == 'Q') return 0;
        if (s == 'W') return 1;
        if (s == 'E') return 2;
        return 3;
    }

    int balancedString(string s) {
        int total[4] = {0}, sum[4] = {0};
        int res = s.size(), size = s.size(), n = s.size() / 4;
        for (auto &it: s) total[map(it)] += 1;
        if (total[0] == n && total[1] == n && total[2] == n && total[3] == n)
            return 0;
        for (int i = 0, j = 0; i < size; ++i) {
            sum[map(s[i])] += 1;
            if (total[0] - sum[0] <= n && total[1] - sum[1] <= n && total[2] - sum[2] <= n && total[3] - sum[3] <= n) {
                while (j <= i && total[map(s[j])] - sum[map(s[j])] + 1 <= n)
                    sum[map(s[j++])] -= 1;
                res = min(res, i - j + 1);
            }
        }
        return res;
    }
};

1241-1250¶

1251-1260¶

1261-1270¶

1271-1280¶

1281-1290¶

1283. 使结果不超过阈值的最小除数

class Solution {
public:
    int sum(const vector<int> &nums, int x) {
        int sum = 0;
        for (auto it: nums) sum += it / x + (bool) (it % x);
        return sum;
    }

    int smallestDivisor(vector<int> &nums, int threshold) {
        if (!nums.size())return 0;
        int l = 1, r = 1e6, mid = 0;
        while (l < r) {
            mid = l + r >> 1;
            if (sum(nums, mid) <= threshold)r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

1291-1300¶