题解

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;
    }
};

题解

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;
    }
};

题解

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];
    }
};