头像

烛之武

AcWing




离线:13小时前



烛之武
15小时前

最长上升子序列模型

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        vector<int> h(n+1,0);
        sort(envelopes.begin(),envelopes.end(),[&](auto a,auto b){
            if(a[0] != b[0]){
                return a[0] < b[0];
            }
            return a[1] > b[1];
        });

        // for(auto ele : envelopes){
        //     cout << ele[0] << ' ' << ele[1] << endl;
        // }

        int ans = 0;
        for(int i=1;i<=n;i++){
            h[i] = 1;
            for(int j=1;j<i;j++){
                if(envelopes[j-1][1] < envelopes[i-1][1]){
                    h[i] = max(h[j]+1,h[i]);
                }
            }
            ans = max(ans,h[i]);
        }
        return ans;
    }
};


活动打卡代码 LeetCode 338. 比特位计数

动态规划 + 位运算

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ans(num+1,0);
        for(int i=1;i<=num;i++){
            ans[i] = ans[(i & (i-1))] + 1;
        }
        return ans;
    }
};



二维前缀和

class NumMatrix {
public:
    vector<vector<int>> s;
    NumMatrix(vector<vector<int>>& matrix) {
        if(matrix.empty() || matrix[0].empty()) return;
        int n = matrix.size(),m = matrix[0].size();
        s.resize(n+1,vector<int>(m+1,0));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + matrix[i-1][j-1];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return s[row2 + 1][col2 + 1] - s[row2 + 1][col1] - s[row1][col2 + 1] + s[row1][col1];
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */



前缀和

class NumArray {
public:
    vector<int> s;

    NumArray(vector<int>& nums) {
        int n = nums.size();
        s.resize(n+1,0);
        for(int i=1;i<=n;i++){
            s[i] = s[i-1] + nums[i-1];
        }
    }

    int sumRange(int i, int j) {
        return s[j+1] - s[i];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(i,j);
 */


新鲜事 原文

2021,算法提高课必须刷完!加油鸭!!!--小武同学。
图片



双指针

class Solution {
public:
    bool canChoose(vector<vector<int>>& groups, vector<int>& nums) {
        int n = groups.size(), m = groups[0].size(), k = nums.size();
        int idx = 0;
        for(int i=0;i+m-1<k;i++){
            bool flag = false;
            int j = i;
            for(int l=0;j<i+m;j++,l++){
                if(nums[j] != groups[idx][l]){
                    flag = true;
                    break;
                }
            }
            if(!flag){
                idx ++;
                i = j-1;
            }
            if(idx == n) return true;
            m = groups[idx].size();
        }
        return false;
    }
};



枚举 + 位运算小技巧

class Solution {
public:

    bool check(string str){
        unordered_set<char> us;
        for(auto ele : str) us.insert(ele);
        for(auto ele : str){
            if(us.count(ele ^ 32) == 0) return false;
        }
        return true;
    }

    string longestNiceSubstring(string s) {
        string ans;
        int n = s.size();
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                string str = s.substr(i,j-i+1);
                if(check(str) && ans.size() < str.size()){
                    ans = str;
                }
            }
        }
        return ans;
    }
};



枚举 + 贪心

class Solution {
public:

    int work(vector<int> h,int aim){
        int sum = 0,cnt = 0;
        for(int i=1;i<=6;i++) sum += h[i] * i;
        if(sum > aim){
            int x = sum - aim;
            for(int i=6;i>1;i--){
                int t = i - 1;
                if(t * h[i] >= x) return cnt + (x + t - 1) / t;
                cnt += h[i];
                x -= h[i] * t;
            }
        }else{
            int x = aim - sum;
            for(int i=1;i<6;i++){
                int t = 6 - i;
                if(t * h[i] >= x) return cnt + (x + t - 1) / t;
                cnt += h[i];
                x -= h[i] * t;
            }
        }
        return -1;
    }

    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        vector<int> h1(7,0),h2(7,0);
        int n = nums1.size(), m = nums2.size();
        if(n > m) return minOperations(nums2,nums1);
        if(m > 6 * n) return -1;
        int ans = 1e8;

        for(auto ele : nums1) h1[ele] ++;
        for(auto ele : nums2) h2[ele] ++;

        for(int i=m;i<=6*n;i++){
            ans = min(ans,work(h1,i) + work(h2,i));
        }
        return ans;
    }
};


活动打卡代码 LeetCode 5692. 车队 II

单调栈 + 凸包

因为本题的车不受左边的车的影响,因此可以从右边开始枚举,速度利用单调维护,本质上是维护凸包的下凸壳
单调栈维护的是速度的从小到大

class Solution {
public:
    vector<double> getCollisionTimes(vector<vector<int>>& cars) {
        stack<int> stk;
        int n = cars.size();
        vector<double> ans(n);
        for(int i=n-1;i>=0;i--){
            auto cur = cars[i];
            while(stk.size()){
                if(cars[stk.top()][1] >= cur[1]) stk.pop();
                else{
                    if(ans[stk.top()] < 0) break;
                    double d = (double)ans[stk.top()] * (cur[1] - cars[stk.top()][1]);
                    if(d > cars[stk.top()][0] - cur[0]) break;
                    else stk.pop();
                }
            }
            if(stk.size()){
                double d = double(cars[stk.top()][0] - cur[0]) / double(cur[1] - cars[stk.top()][1]);
                ans[i] = d;
            }else{
                ans[i] = -1;
            }
            stk.push(i);
        }    
        return ans;
    }
};




方法1:采用dfs枚举

class Solution {
public:
    int sum,ans;
    vector<int> _t;

    void dfs(int u,int w,int aim){
        //cout << u << ' ' << w << ' ' << aim << ' ' << sum << ' ' << ans << endl;
        if(u == _t.size()){
            int num = w + sum - aim;
            if(abs(num) < abs(ans - aim)){
                ans = w + sum;
            }else if(abs(num) == abs(ans-aim)){
                if(w + sum < ans){
                    ans = w + sum;
                }
            }
            return;
        }
        dfs(u+1,w,aim);
        dfs(u+1,w+_t[u],aim);
        dfs(u+1,w+2*_t[u],aim);
    }

    int closestCost(vector<int>& b, vector<int>& t, int target) {
        int n = b.size(), m = t.size();
        _t = t;
        ans = 1e8;
        for(int i=0;i<n;i++){
            sum = b[i];
            dfs(0,0,target);
        }
        return ans;
    }
};

方法2:采用四进制的方式枚举三进制

class Solution {
public:
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        int n = baseCosts.size(), m = toppingCosts.size();
        int ans = INT_MAX;
        for(int i=0;i<n;i++){
            int s = baseCosts[i];
            for(int j=0;j<1<<m*2;j++){
                bool flag = false;
                int r = s;
                for(int k=0;k<m;k++){
                    int t = j >> k*2 & 3;
                    if(t == 3){
                        flag = true;
                        break;
                    }
                    r += toppingCosts[k] * t;
                }
                if(flag) continue;
                if(abs(r-target) < abs(ans-target) || abs(r-target) == abs(ans-target) && r < ans){
                    ans = r;
                }
            }
        }
        return ans;
    }
};