218. The Skyline Problem

218. The Skyline Problem

思路:

扫描线算法:

想像一根竖线,从左到右进行扫描,记录下当前竖线所有线段的高度(除去左端点),每遇到一个端点就挑选出最高点,并输出即可。这里可以观察到,此算法把一根直线拆分两个端点来看待,遇到右端点就记录维持该线段的高度,遇到左端点就删除该线段的高度。

具体算法,直接看代码,其中左端点的Height取负值记录非常巧妙,既利用了set集合的升序性质,同时在遍历的时优先选择了新建筑,不至于产生“建筑间的空隙”。

代码:

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        multiset<pair<int, int>> loc;
        for(auto &e : buildings){
            loc.insert({e[0], -e[2]});
            loc.insert({e[1], e[2]});
        }
        vector<vector<int>> ans;
        vector<int> last{0,0};
        multiset<int> height{0}; //多个高度可能相同
        cout << last[0] << endl;

        for(auto &[pos, h] : loc){
            if(h < 0) height.insert(-h);
            else height.erase(height.find(h));

            int maxh = *height.rbegin();
            // cout << pos << ' ' << h << ' ' << maxh << endl;
            if(maxh != last[1]){
                last[0] = pos;
                last[1] = maxh;
                ans.emplace_back(last);                
            }
        }
        return ans;

    }
};

240. Search a 2D Matrix II

240. Search a 2D Matrix II

思路:

由于matrix在行和列上的递增, 在左下角和右上角有特殊的性质。在左下角有,A[i][j]比上面的数字都打, 比右边的数字都小。所以可以比较targetA[i][j]数字大小来排除,上面一列或者右边一行的所有数字。递归的下去可以搜索到应有的数字。

如果没有就会出界。

Read more

48. Rotate Image

48. Rotate Image

思路:

原地翻转的思路:比较简单。

  1. 翻转做法。先上下翻转, 后对角线翻转
  2. 四个对应的矩阵元素作为旋转点,顺势将矩阵划分为四个旋转部分。遍历一个部分并旋转其中成组的所有元素即可。
Read more

88. Merge Sorted Array

思路:

双指针从后向前合并即可,时间复杂度为$n(o)$,空间复杂度$O(1)$。

代码:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {        
        int pos = m + n - 1, p1 = m - 1, p2 = n - 1;
        while(p1 >= 0 && p2 >= 0){
            if(nums1[p1] > nums2[p2]){
                nums1[pos] = nums1[p1--];
            }else{
                nums1[pos] = nums2[p2--];
            }
            pos--;
        }
        while(p2 >= 0){
            nums1[pos--] = nums2[p2--];
        }
    }
};

406. Queue Reconstruction by Height

思路:

贪心策略,因为队列的唯一性,从头到尾reconstruct即可。

k升序再按h降序,再按k值插入。需要在插入的同时统计维护前面身高大于h的人数即可。

代码:

class Solution {
public:
    int countBigger(int pos, vector<vector<int>> &people){
        int res = 0;
        for(int i = pos -1; i >= 0; --i){
            if(people[i][0] >= people[pos][0]) res++;
        }
        return res;
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](vector<int>a, vector<int>b){
            if(a[1] == b[1]) return a[0] < b[0];
            else return a[1] < b[1];
        });
        int n = people.size();
        for(int i = 0; i < n; ++i){
            int c = countBigger(i, people);
            int k = i;
            while(c > people[k][1]){
                if(people[k-1][0] >= people[k][0]) c--;
                swap(people[k], people[k - 1]);
                k--;
                
            }

            
        }
        return people;
    }
};

122. Best Time to Buy and Sell Stock II

思路:

贪心做每一个可以交易的交易就行

image-20201226081801949

代码:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sum = 0;
        for(int i = 0; i < prices.size() - 1; ++i){
            sum += (prices[i] < prices[i + 1] )? prices[i + 1] - prices[i] : 0; 
        }
        return sum;
    }
};

605. Can Place Flowers

605. Can Place Flowers

这题还是典型的贪心,不过写的时候nt;

思路:

用贪心的策略尽可能先种花,这种策略不会影响结果。只需要在遍历下考虑两边和边界情况就行了。

代码:


class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int res = 0, fn = flowerbed.size();

        for(int i = 0; i < flowerbed.size(); ++i){
            if(flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (fn - 1 == i ||flowerbed[i + 1] == 0 )){
                 ++res;
                 flowerbed[i] = 1;
             }

        }
        return res >= n;
    }
};

版本二:

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int res = 0, fn = flowerbed.size();
        if(fn == 1 && flowerbed[0] == 0)
            return n <= 1;
        for(int i = 0; i < flowerbed.size(); ++i){
            if(flowerbed[i] == 0 &&
             ( i == 0 && flowerbed[1] == 0 || i == (fn - 1) && flowerbed[fn - 2] == 0 || (i < fn - 1 && i > 0 && flowerbed[i -1] ==0 && flowerbed[i + 1] == 0))){
                 ++res;
                 flowerbed[i] = 1;
             }

        }
        return res >= n;
    }
};