220211刷题

1004. 最大连续1的个数 III

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

提示：

1 <= nums.length <= 105
nums[i] 不是 0 就是 1
0 <= k <= nums.length

C++

第二部分正常二维遍历会超时
lower_bound使用二分法返回参数1，参数2 范围内第一个不小于参数3的迭代器

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        vector<int> preZero(nums.size() + 1); // [i]表示在nums[i]前共有多少0
        for(int i = 1; i <= nums.size(); i ++){
            preZero[i] = preZero[i - 1];
            if(!nums[i - 1])  preZero[i] ++;
        }
        
        int res = 0;
        for(int r = 0; r < nums.size(); r ++){
            int l = lower_bound(preZero.begin(), preZero.end(), preZero[r + 1] - k) - preZero.begin(); // 不减begin()返回元素 ， 减begin()返回该元素下标
            res = max(res, r - l + 1);
        }
        return res;
    }
};

554. 砖墙

你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和相等。

你现在要画一条 自顶向下 的、穿过最少砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。

给你一个二维数组 wall ，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。

示例 1：

输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
输出：2

示例 2：

输入：wall = [[1],[1],[1]]
输出：3

提示：

n == wall.length
1 <= n <= 104
1 <= wall[i].length <= 104
1 <= sum(wall[i].length) <= 2 * 104
对于每一行 i ，sum(wall[i]) 是相同的
1 <= wall[i][j] <= 231 - 1

C++

public:
    int leastBricks(vector<vector<int>>& wall) {
        map<int, int> mp; // mp[i]表示 该列有空隙的层数
        for(auto e : wall){
            int sum = 0;
            int len = e.size();
            for(int j = 0; j < len - 1; j ++){
                sum += e[j];
                mp[sum] ++;
            }
        }
        int res = 0;
        for(auto & e : mp)
            res = max(res, e.second);
        return wall.size() - res;
    }
};

1011. 在 D 天内送达包裹的能力

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。

示例 1：

输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10

请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。

示例 2：

输入：weights = [3,2,2,4,1,4], days = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4

示例 3：

输入：weights = [1,2,3,1,1], days = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1

提示：

1 <= days <= weights.length <= 5 * 104
1 <= weights[i] <= 500

C++

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int start = *max_element(weights.begin(), weights.end());
        
        for(int res = start; ; res ++){
            vector<int> buckets(days, res); 
            if(check(buckets, weights)) return res;            
        }
        return -1;
    }

    bool check(vector<int>& buckets, vector<int>& weights){
        if(accumulate(weights.begin(), weights.end(), 0) > buckets.size() * buckets[0]) return false;
        int j = 0;
        for(int i = 0; i < weights.size(); i ++){
            if(j < buckets.size()){
                if(buckets[j] < weights[i]){
                    if(j == buckets.size() - 1) return false;
                    j ++;
                }
                buckets[j] -= weights[i];
            }
        }
        return true;
    }
};

1190. 反转每对括号间的子串

给出一个字符串 s（仅含有小写英文字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

注意，您的结果中不应包含任何括号。

示例 1：

输入：s = "(abcd)"
输出："dcba"

示例 2：

输入：s = "(u(love)i)"
输出："iloveu"
解释：先反转子字符串 "love" ，然后反转整个字符串。

示例 3：

输入：s = "(ed(et(oc))el)"
输出："leetcode"
解释：先反转子字符串 "oc" ，接着反转 "etco" ，然后反转整个字符串。

示例 4：

输入：s = "a(bcdefghijkl(mno)p)q"
输出："apmnolkjihgfedcbq"

提示：

1 <= s.length <= 2000
s 中只有小写英文字母和括号
题目测试用例确保所有括号都是成对出现的

C++

class Solution {
public:
    string reverseParentheses(string s) {
        stack<char> stk;
        for(auto e: s){
            if(e =='(' || isalpha(e)) stk.push(e);
            else if(e == ')'){
                string temp = "";
                while(stk.top() != '('){
                    temp += stk.top();
                    stk.pop();
                }
                stk.pop();
                for(auto e : temp){
                    stk.push(e);
                }
            }
        }
        string res = "";
        while(!stk.empty()){
            res += stk.top();
            stk.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

递归

class Solution {
public:
    string reverseParentheses(string s) {
        int idx = 0;
        return dfs(s, idx);
    }

    string dfs(string& s, int& idx){
        string res = "";
        
        while(idx < s.size()){
            if(s[idx] == '(') {
                idx ++;
                res += dfs(s, idx);
            }
            else if(s[idx] == ')') {
                idx ++;
                reverse(res.begin(), res.end());
                return res;
            }
            else res += s[idx ++];
        }

        return res;
    }
};

781. 森林中的兔子

森林中有未知数量的兔子。提问其中若干只兔子 “还有多少只兔子与你（指被提问的兔子）颜色相同?” ，将答案收集到一个整数数组 answers 中，其中 answers[i] 是第 i 只兔子的回答。

给你数组 answers ，返回森林中兔子的最少数量。

示例 1：

输入：answers = [1,1,2]
输出：5
解释：
两只回答了 "1" 的兔子可能有相同的颜色，设为红色。 
之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。 
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。 
因此森林中兔子的最少数量是 5 只：3 只回答的和 2 只没有回答的。

示例 2：

输入：answers = [10,10,10]
输出：11

提示：

1 <= answers.length <= 1000
0 <= answers[i] < 1000

C++

class Solution {
public:
    int numRabbits(vector<int>& answers) {
        // 13只 answers[i]==5 的; 
        // mp[5(x)] = 13(y)   ceil(y / x + 1) * (x + 1)
        int res = 0;
        map<int , int> mp;
        for(int e : answers)
            mp[e] ++;
        for(auto &[k,v] : mp)
            res += (v%(k + 1) ? v/(k + 1) + 1 : v/(k + 1)) * (k + 1);
        return res;
    }
};