头像

Oyasumi1024




离线:1小时前


最近来访(108)
用户头像
顽童
用户头像
立花春水
用户头像
violet_garden
用户头像
L-China
用户头像
不许对我狗叫
用户头像
哥哥的真爱粉
用户头像
Grinder
用户头像
CS10086
用户头像
noobcode091
用户头像
Amaryllis_
用户头像
lnyx
用户头像
dushucheng0901
用户头像
Caesar123
用户头像
拾一.
用户头像
种花家的傻逼
用户头像
爱算法爱生活
用户头像
甜菜巨擘_3
用户头像
yxc的小迷妹
用户头像
将离_2
用户头像
我才不认识这个人


Oyasumi1024
4小时前


活动打卡代码 LeetCode 218. 天际线问题

Oyasumi1024
5小时前
class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<vector<int>> res;
        vector<pair<int, int>> height;

        /*
        正负用于判别是左端点还是右端点,同时保证排序后:
        1. 左端点相同时,最高的楼排在前面,insert的一定是相同左端点中最大的高度
        2. 右端点相同时,最低的楼排在前面,erase的时候不会改变最大高度
        */
        for (auto &b : buildings)
        {   
            height.push_back({b[0], -b[2]});    // 左端点
            height.push_back({b[1], b[2]});     // 右端点
        }
        sort(height.begin(), height.end()); // 排序

        multiset<int> S;    // 维护当前最大高度
        /*
        由于题目中最后的x轴的点算入了答案中,所以可以认为x轴这个也是一个楼
        所以这里把x轴也加入到高度里面,也就是在高度的multiset里加入0
        */
        S.insert(0);        // 保证端点全部删除之后能得到当前最大高度为 0
        // preMaxHeight 表示遇到一个端点之前的最大高度
        // curMaxHeight 表示遇到一个端点之后的当前最大高度
        int preMaxHeight = 0, curMaxHeight = 0;
        for (auto &h : height)
        {
            // 左端点
            if (h.second < 0)   S.insert(-h.second);
            // 右端点
            else    S.erase(S.find(h.second));

            curMaxHeight = *S.rbegin();
            // 最大高度发生改变,一定是一个关键点,即一个水平线段的左端点
            if (curMaxHeight != preMaxHeight)
            {
                res.push_back({h.first, curMaxHeight});
                preMaxHeight = curMaxHeight;
            }
        }

        return res;
    }
};



Oyasumi1024
22小时前



Oyasumi1024
22小时前
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root)  return 0;
        auto l = root->left, r = root->right;
        int x = 1, y = 1;

        while (l)
        {
            l = l->left;
            x ++ ;
        }

        while (r)
        {
            r = r->right;
            y ++ ;
        }

        if (x == y )    return (1 << x) - 1;

        return countNodes(root->left) + 1 + countNodes(root->right); 
    }
};






class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        typedef long long LL;
        multiset<LL> S;
        S.insert(1e18), S.insert(-1e18);
        for (int i = 0, j = 0; i < nums.size(); i ++ )
        {
            if (i - j > k)
            {
                S.erase(S.find(nums[j]));
                j ++ ;
            }
            int x = nums[i];
            auto it = S.lower_bound(x);
            if (*it - x <= t)   return true;
            -- it;
            if (x - *it <= t)   return true;
            S.insert(x);
        }

        return false;
    }
};



class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        for (int i = 0; i < nums.size(); i ++ )
        {
            int x = nums[i];
            if (mp.count(x) && abs(i - mp[x]) <= k )    return true;
            mp[x] = i; 
        }
        return false;
    }
};



class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> S;
        for (auto &x : nums)
        {
            // 说明x之前已经出现过   那么在此时又遍历到x  因此x至少出现了两次
            if (S.count(x) )    return true;
            S.insert(x); 
        }
        return false;
    }
};





活动打卡代码 LeetCode 518. 零钱兑换 II

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size(), m = amount;
        vector<int> f(m + 1);

        f[0] = 1;
        for (int i = 0; i < n; i ++ )   // 枚举物品
            for (int j = coins[i]; j <= m; j ++ )   // 枚举背包容量
                f[j] += f[j - coins[i]];

        return f[m];
    }
};