头像

Carlo




离线:1天前


活动打卡代码 LeetCode 263. 丑数

Carlo
2天前
class Solution {
public:
    int nthUglyNumber(int n) {
        priority_queue<double,vector<double>,greater<double>> q;
        double ans = 1;
        for(int i = 1;i < n;i ++){
            q.push(ans * 2);
            q.push(ans * 3);
            q.push(ans * 5);
            ans = q.top();
            while(!q.empty() && ans == q.top()) q.pop();
        }
        return ans;
    }
};



Carlo
11天前
class Solution {
public:
    int trap(vector<int>& height) {
        if(height.) return;
        int n = height.size();
        vector<int> left(n),right(n);
        left[0] = height[0],right[n - 1] = height[n - 1];
        for(int i = 1;i < n;i ++) left[i] = max(left[i - 1],height[i]);
        for(int i = n - 2;i >= 0;i --)
            right[i] = max(right[i + 1],height[i]);
        int res = 0;
        for(int i = 0;i < n;i ++)
            res += min(left[i],right[i]) - height[i];
        return res;
    }
};



Carlo
11天前
class Solution {
public:
    int longestCommonSubsequence(string s1, string s2) {
        s1 = " " + s1,s2 = " " + s2;
        vector<vector<int>> f(1010,vector<int>(1010,0));
        for(int i = 1;i <= s1.size();i ++){
            for(int j = 1;j <= s2.size();j ++)
            {
                f[i][j] = max(f[i - 1][j],f[i][j - 1]);
                if(s1[i] == s2[j]) f[i][j] = max(f[i][j],f[i - 1][j - 1] + 1); 
            }
        }
        return f[s1.size() - 1][s2.size() - 1];
    }
};


活动打卡代码 LeetCode 1006. 笨阶乘

Carlo
12天前
class Solution {
public:
    int clumsy(int N) {
        int index = 0;
        stack<int> stk;
        stk.push(N);
        N --;
        while(N > 0){
            if(index % 4 == 0){
                stk.top() *= N;
            }else if(index % 4 == 1){
                stk.top() /= N;
            }else if(index % 4 == 2){
                stk.push(N);
            }else{
                stk.push(-N);
            }
            index ++;
            N --;
        }
        int sum = 0;
        while(!stk.empty()){
            sum += stk.top();
            stk.pop();
        }
        return sum;
    }
};


活动打卡代码 LeetCode 90. 子集 II

Carlo
12天前
class Solution {
public:
    unordered_map<int,int> cnt;
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        for(auto x : nums) cnt[x] ++;
        dfs(-10);
        return ans;
    }

    void dfs(int u){
        if(u > 10) ans.push_back(path);
        else {
            // 0 1 2 ... cnt[u] + 1种选法
            for(int i = 0;i < cnt[u] + 1;i ++){
                dfs(u + 1);
                path.push_back(u);
            }
            for(int i = 0;i < cnt[u] + 1;i ++){
                path.pop_back();
            }
        }
    }
};



Carlo
15天前
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for(int i = 0;i < 32;i ++){
            res = res * 2 + (n >> i & 1);
        }
        return res;
    }
};


活动打卡代码 LeetCode 74. 搜索二维矩阵

Carlo
15天前
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = 0,n = matrix.size(),m = matrix[0].size();
        for(int i = 0;i < n;i ++)
            if(matrix[i][0] > target && (i - 1) >= 0)
            {
                row = i - 1;
                break;
            }else if(matrix[i][0] == target){
                // row = i;
                return true;
            }else if(i == n - 1){
                row = i;
            }
        for(int i = 0;i < m;i ++)
            if(matrix[row][i] == target) return true;
        return false;
    }
};


新鲜事 原文

Carlo
15天前
中位数/列数=第几行,中位数%列数=第几列的第几个数,定位二维数组太庙啦!


活动打卡代码 LeetCode 721. 账户合并

Carlo
16天前
class Solution {
public:
    vector<int> p;
    int find(int x){
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    unordered_map<string,vector<int>> hash;
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int n = accounts.size();
        for(int i = 0;i < n;i ++) p.push_back(i);
        for(int i = 0;i < n;i ++)
            for(int j = 1;j < accounts[i].size();j ++)
                hash[accounts[i][j]].push_back(i);
        for(auto& [k,v] : hash)
            for(int i = 0;i < v.size();i ++)
                p[find(v[i])] = find(v[0]);
        vector<set<string>> res(n);
        for(int i = 0;i < n;i ++)
            for(int j = 1;j < accounts[i].size();j ++)
                res[find(i)].insert(accounts[i][j]);
        vector<vector<string>> ans;
        for(int i = 0;i < n;i ++)
        {
            if(res[i].size()){
                vector<string> t;
                t.push_back(accounts[i][0]);
                for(auto e:res[i]) t.push_back(e);
                ans.push_back(t);
            }
        }
        return ans;
    }
};



Carlo
16天前
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for(int i = 0;i < 32;i ++){
            res = res * 2 + (n >> i & 1);
        }
        return res;
    }
};