刷题

1.分割回文

题目：给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

第一步动态规划判断是否为回文（长度为len的string s，从第 i 位到第 j 位是否是回文）

for(int i=len-1; i>=0; --i){
    for(int j=0; j<len; ++j){
        if(i>=j) dp[i][j] = true;
        else dp[i][j] = dp[i+1][j-1]&&s[i]==s[j];
    }
}

第二步动态规划获取分割回文的最少次数

for(int i=1; i<len; ++i){
    if(dp[0][i]) {
        dpans[i] = 0;   //整体为回文 则为0
        continue;
    }
    dpans[i] = dpans[i-1];
    for(int j=i-1; j>0; --j){
        if(dp[j][i]){
            dpans[i] = min(dpans[i], dpans[j-1]);  //取从j-i是回文中左侧回文分割次数最小值 + 1
        }
    }
    dpans[i]++;
}

2. 有符号数和无符号数相减如果小于零会出问题

例如 int k=5; string s="123456789";

则 k - s.size() 则会出现bug， k为有符号数， s.size()为无符号数，则 k - s.size() 结果为一个无符号的极大的数，不为-4，因为无符号数不会有负数。

3. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

int majorityElement(vector<int>& nums) {
        int candidate = -1;
        int count = 0;
        for (int num : nums) {
            if (num == candidate)
                ++count;
            else if (--count < 0) {
                candidate = num;
                count = 1;
            }
        }
        return candidate;
    }

相当于两个不同的数相互抵消，最后剩下的数必然是多数元素。
4. D天内送达货物的能力

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力

int shipWithinDays(vector<int>& weights, int days) {  
//二分查找，最低运载里在[最大元素， 总和]之间，贪心得出该运载力时需要天数，并与需要天数比较，舍弃一半；
        int l = *max_element(weights.begin(), weights.end()), r = accumulate(weights.begin(), weights.end(), 0);
        while(l<r){
            int tem = (l+r)/2;
            int need = 1, sum_now = 0;
            for(auto weight:weights){
                sum_now += weight;
                if(sum_now>tem){
                    sum_now = weight;
                    need++;
                }
            }
            if(need>days) l=tem+1;
            else r = tem;
        }
        return l;
    }

5. 给定一个只包含三种字符的字符串：（，）和 *，写一个函数来检验这个字符串是否为有效字符串。

bool checkValidString(string s) {
    int minleft = 0, maxleft = 0;
    for(auto it:s){
        if(it=='(') {
            minleft++;
            maxleft++;
        }else if(it=='*'){
            minleft = max(minleft-1, 0);
            maxleft++;
        }else{
            minleft = max(minleft-1, 0);
            maxleft--;
            if(maxleft<0) return false;
        }
    }
    return minleft==0;
}

6.最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.empty() || matrix[0].empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();
        int ans = 0;
        vector<int> mat(n, 0);
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(matrix[i][j]=='0'){
                    mat[j] = 0;
                }else{
                    ++mat[j];
                }
            }
            ans = max(ans, get(mat));
        }
        return ans;
    }
    int get(vector<int> mat){
        stack<int> sta;
        sta.push(-1);
        int ans = 0, i = 0, tem = 0;
        for(; i<mat.size(); ++i){
            while(sta.size()>1 && mat[sta.top()] > mat[i]){
                tem = mat[sta.top()];
                sta.pop();
                ans = max(ans, tem*(i-sta.top()-1));
            }
            sta.push(i);
        }
        while(sta.size()>1){
            tem = mat[sta.top()];
            sta.pop();
            ans = max(ans, tem*(i-sta.top()-1));
        }
        return ans;
    }
};

7. 最小的数

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按任意顺序返回答案。

vector<int> singleNumber(vector<int>& nums) {
    int tem = 0;
    for(auto num:nums){
        tem ^= num;
    }
    tem = tem==INT_MIN ? tem : tem&(-tem);
    int n1 = 0, n2 = 0;
    for(auto num:nums){
        if(num&tem)
            n1 ^= num;
        else 
            n2 ^= num;
    } 
    return {n1, n2};
}

8.三等分

给定一个由 0 和 1 组成的数组 arr ，将数组分成 3 个非空的部分，使得所有这些部分表示相同的二进制值。

vector<int> threeEqualParts(vector<int>& arr) {
    int cntOne=accumulate(arr.begin(),arr.end(),0);
    if(cntOne%3!=0)return {-1,-1};
    if(cntOne==0)return {0,(int)arr.size()-1};
    cntOne/=3;
    int beg1=0,beg2=0,beg3=0;
    int curOneCnt=0;
    for(int i=0;i<arr.size();i++){
        if(curOneCnt==0)beg1=i;
        if(curOneCnt==cntOne)beg2=i;
        if(curOneCnt==cntOne*2)beg3=i;
        if(arr[i]==1){
            curOneCnt++;
        }
    }
    int subLen=arr.size()-beg3;
    for(int i=0;i<subLen;i++){
        if(arr[beg1+i]!=arr[beg2+i]||arr[beg1+i]!=arr[beg3+i])return {-1,-1};
    }
    return {beg1+subLen-1,beg2+subLen};
}

9. 计数质数

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

int countPrimes(int n) {
    vector<int> isPrime(n, 1);
    int ans = 0;
    for (int i = 2; i < n; ++i) {
        if (isPrime[i]) {
            ans += 1;
            if ((long long)i * i < n) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = 0;
                }
            }
        }
    }
    return ans;
}