头像

AcJarNinLee




离线:17小时前


最近来访(8)
用户头像
明_43
用户头像
HZHZ
用户头像
不学完算法基础课不改名
用户头像
mei_24
用户头像
dancebyte
用户头像
Cristiano_Ronaldo
用户头像
小马珍珠
用户头像
ac_cjh

活动打卡代码 LeetCode 788. 旋转数字

模拟法

class Solution {
public:
    int res;

    bool get(int x){
        int t = 0;
        while(x){
            int a = x % 10;
            if(a == 2 || a == 5 || a == 6 || a == 9) t ++;
            else if(a == 3 || a == 4 || a == 7) return false;
            x /= 10;
        }
        if(t) return true;
        return false;
    }
    int rotatedDigits(int n) {
        for(int i = 1; i <= n; i ++)
        {
            if(get(i)) res ++;
        }

        return res;
    }
};



力扣

  • 367、27、904、76、59



class Solution {
public:
    int maxc = 0, curc = 0, last;  // maxc 全局最长区间;  curc 本区间长度; last 前一个节点值;
    vector<int> res;

    void dfs(TreeNode* root){
        if(!root) return;
        dfs(root->left);
        if(!curc || last == root->val){
            curc ++;
            last = root->val;
        }else{
            curc = 1;
            last = root->val;
        }
        if(curc > maxc) res = {last}, maxc = curc;  // res ={last};  -- 更新了众数
        else if(curc == maxc) res.push_back(last); 
        dfs(root->right);
    }
    vector<int> findMode(TreeNode* root) {
        dfs(root);
        return res;
    }
};



利用中序遍历有序 来以此判断相邻两数差值

class Solution {
public:
    int res = 1e5 + 10, pre = -1;
    void dfs(TreeNode* root){
        if(!root) return;
        dfs(root->left);
        if(pre == -1) pre = root->val;
        else{
            res = min(res, root->val - pre);
            pre = root->val;
        }
        dfs(root->right);
    }
    int getMinimumDifference(TreeNode* root) {
        dfs(root);
        return res;
    }
};



利用中序序列数组

class Solution {
public:
    vector<int> res;

    void dfs(TreeNode* root){
        if(!root) return;
        dfs(root->left);
        res.push_back(root->val);
        dfs(root->right);
    }
    bool isValidBST(TreeNode* root) {
        dfs(root);
        for(int i = 0; i < res.size(); i ++)
            if(i < res.size() - 1 && res[i] >= res[i + 1]) return false;
        return true;
    }
};

利用前驱结点

class Solution {
public:
    long long t = -1e10;
    bool dfs(TreeNode* root){
        if(!root) return true;
        if(!dfs(root->left)) return false;

        if(t >= root->val) return false;
        else t = root->val;

        if(!dfs(root->right)) return false;

        return true;
    }

    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        return dfs(root);
    }
};



class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(!root) return NULL;
        if(root->val == val) return root;

        if(root->val < val) return searchBST(root->right, val);
        else if(root->val > val) return searchBST(root->left, val);

        return NULL;
    }
};



class Solution {
public:
    vector<int> nums;
    vector<bool> st;
    int len;

    bool dfs(int start, int cur, int k){
        if(!k) return true;
        if(cur == len) return dfs(0,0, k - 1);

        for(int i = start; i < nums.size(); i ++){
            if(st[i]) continue;

            if(cur + nums[i] <= len){
                st[i] = true;
                if(dfs(i + 1, cur + nums[i], k)) return true;
                st[i] = false;
            }
            // 上面遍历失败后,程序进入此处
            while(i + 1 < nums.size() && nums[i] == nums[i + 1]) i ++; // 剪枝2:第i和第i+1数相等,由于第i个数搜索失败,所以第i + 1个数也会失败
            if(!cur || cur + nums[i] == len) return false;//剪枝3:cur ==0 即:第一个数就匹配失败,最大的数都不满足;
        }                                                  //剪枝4:cur+nums[i]=len即:第k组最后一个数选完了,后面搜索的结果失败了,无合法情况了。

        return false;
    }
    bool canPartitionKSubsets(vector<int>& _nums, int k) {
        nums = _nums;
        int n = _nums.size();
        st.resize(n);
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % k) return false;
        len = sum / k;
        sort(nums.begin(), nums.end(), greater<int>()); // 剪枝1:从大到小遍历,可以更快的找出一组

        return dfs(0, 0, k);
    }
};



class Solution {
public:
    vector<int> nums;
    vector<bool> st;
    int len;

    bool dfs(int start, int cur, int k){
        if(!k) return true;
        if(cur == len) return dfs(0,0, k - 1);

        for(int i = start; i < nums.size(); i ++){
            if(st[i]) continue;

            if(cur + nums[i] <= len){
                st[i] = true;
                if(dfs(i + 1, cur + nums[i], k)) return true;
                st[i] = false;
            }

            while(i + 1 < nums.size() && nums[i] == nums[i + 1]) i ++;
            if(!cur || cur + nums[i] == len) return false;
        }

        return false;
    }
    bool canPartitionKSubsets(vector<int>& _nums, int k) {
        nums = _nums;
        int n = _nums.size();
        st.resize(n);
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % k) return false;
        len = sum / k;
        sort(nums.begin(), nums.end(), greater<int>());

        return dfs(0, 0, k);
    }
};


活动打卡代码 LeetCode 827. 最大人工岛

并查集

class Solution {
public:
    int n;
    int p[300010], sz[300010];
    int get(int i, int j)
    {
        return i * n + j;
    }

    int find(int x)
    {
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};

    int largestIsland(vector<vector<int>>& grid) {
        n = grid.size();

        for(int i = 0; i < n * n; i ++) p[i] = i, sz[i] = 1;

        int res = 1;
        for(int i = 0; i < n; i ++ ) 
            for(int j = 0; j < n; j ++)
            {
                if(grid[i][j])
                {
                    int a = get(i, j);
                    for(int k = 0; k < 4; k ++)
                    {
                        int x = dx[k] + i, y = dy[k] + j;
                        if(x >= 0 && x < n && y >= 0 && y < n && grid[x][y])
                        {
                            int b = get(x, y);
                            if(find(a) != find(b)){
                                sz[find(b)] += sz[find(a)];
                                p[find(a)] = find(b);
                            }
                        }
                    }
                    res = max(res, sz[find(a)]);
                }    
            }

        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
            {
                if(!grid[i][j])
                {
                    map<int, int> hash;
                    for(int k = 0; k < 4; k ++){
                        int x = dx[k] + i, y = dy[k] + j;
                        if(x >= 0 && x < n && y >= 0 && y < n && grid[x][y]){
                            int a = get(x, y);
                            hash[find(a)] = sz[find(a)];
                        }
                    }
                    int s = 1;
                    for(auto [k, v] : hash) s += v;
                    res = max(res, s);
                }
            }
            return res;
    }
};


活动打卡代码 LeetCode 850. 矩形面积 II

扫描线模板 先将竖线(x = t)进行排序, 在对相邻的两根线之间的横线(y = t)进行区间合并同时计算横线所构成矩形的高, 最后每一个矩形用高乘以宽求出面积 最终返回面积之和

typedef pair<int, int> PII;
typedef long long LL;
#define x first
#define y second

LL calc(vector<vector<int>>& rts, int a, int b)
{
    vector<PII> q;
    for(auto& c : rts)
        if(c[0] <= a && c[2] >= b) q.push_back({c[1], c[3]});

    sort(q.begin(),q.end());

    LL st = -1, ed = -1, res = 0;
    for(auto& c : q){
        if(ed < c.x){
            if(st != -1) res += ed - st;
            st = c.x, ed = c.y;
        }
        else ed = ed > c.y ? ed : c.y;

    }
    res += ed - st;
    return res * (b - a);
}

class Solution {
public:
    int rectangleArea(vector<vector<int>>& rts) {
        vector<int> a;

        for(auto& c : rts){
            a.push_back(c[0]);
            a.push_back(c[2]);
        }
        sort(a.begin(), a.end());
        LL ans = 0;
        for(int i = 1; i < a.size(); i ++){
            ans += calc(rts, a[i - 1], a[i]);
        }
        return ans % 1000000007;
    }
};