ch9-of-programmercarl-2

C++ C 代码随想录 贪心
刷题
发布日期:   2022-04-19

1 根据身高重建队列

1.1 题目描述

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj]是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例1:

输入: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释:
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例2:

输入: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

1.2 思路

先对身高序列按第一维进行降序排序，若第一维相等，则按第二维升序排序。

完整代码如下：

  • Cpp
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        vector<vector<int>> res;
        sort(people.begin(), people.end(),[](vector<int>& a, vector<int>&b){
            if(a[0] == b[0]){
                return a[1] < b[1];
            }
            return a[0] > b[0];
        });
        for(vector<int> iter: people){
            int pos = iter[1];
            res.insert(res.begin()+pos, iter);
        }
        return res;
    }
};
  • C
typedef struct MyListNode {
    int val;
    int cnt;
    struct MyListNode *next;
};


int cmp(const void *a, const void *b){
    int *a_ = *(int **)a, *b_ = *(int **)b;
    if(a_[1] == b_[1]){
        return (a_[0] < b_[0]);
    }
    return a_[1] > b_[1];
}

int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes){
    *returnColumnSizes = (int *)malloc(sizeof(int)*peopleSize);
    int** ret = (int**)malloc(sizeof(int*)*peopleSize);
    *returnSize = 0;
    if(peopleSize == 1){
        *returnSize = 1;
        (*returnColumnSizes)[0] = 2;
        return people;
    }
    qsort(people, peopleSize, sizeof(int *), cmp);
    struct MyListNode *dummyHead = (struct MyListNode *)malloc(sizeof(struct MyListNode)), *cur;
    struct MyListNode *node = (struct MyListNode *)malloc(sizeof(struct MyListNode));
    node->val = people[0][0];
    node->cnt = people[0][1];
    node->next = NULL;
    dummyHead->next = node;
    cur = dummyHead;
    int cnt;
    for(int i = 1; i < peopleSize; i++){
        struct MyListNode *newNode = (struct MyListNode *)malloc(sizeof(struct MyListNode));
        cur = dummyHead;
        cnt = people[i][1];
        if(cnt){
            while(cnt){
                if(cur && cur->next && cur->next->val >= people[i][0]){
                    cnt--;
                }
                cur = cur->next;
            }
        }else{
            while(cur && cur->next && cur->next->val < people[i][0]){
                cur = cur->next;
            }
        }
        newNode->val = people[i][0];
        newNode->cnt = people[i][1];
        newNode->next = cur->next;
        cur->next = newNode;
    }
    cur = dummyHead->next;
    while(cur!= NULL){
        ret[*returnSize] = (int *)malloc(sizeof(int)*2);
        ret[*returnSize][0] = cur->val;
        ret[*returnSize][1] = cur->cnt;
        (*returnColumnSizes)[(*returnSize)++] = 2;
        cur = cur->next;
    }
    return ret;
}

2 用最少数量的箭引爆气球

2.1 题目描述

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

示例1:

输入: points = [[10,16],[2,8],[1,6],[7,12]]
输出: 2
解释: 气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例2:

输入: points = [[1,2],[3,4],[5,6],[7,8]]
输出: 4
解释: 每个气球需要射出一支箭，总共需要4支箭。

示例3:

输入: points = [[1,2],[2,3],[3,4],[4,5]]
输出: 2
解释:
解释：气球可以用2支箭来爆破:

  • 在x = 2处发射箭，击破气球[1,2]和[2,3]。
  • 在x = 4处射出箭，击破气球[3,4]和[4,5]。

2.2 思路

先对points按某一维进行排序，排完序遍历数组，求相邻两个区间的交集，当交集不为空时则说明截止目前的区间可以被消去，当为空时说明需要再多一个操作才可以把当前的消去。

简单一点，就是按区间左端点或右端点进行排序：

  1. 以左端点排序: 遍历数组，创建一个变量right用于记录当前的交集的右端点。当当前的区间的左端点小于当前交集的右端点时，说明有交集，更新交集右端点为min(right, points[i][1]); 当当前的区间的左端点大于当前交集的右端点时，说明无交集，计数器cnt加1，然后将交集右端点置为当前区间右端点，继续遍历数组。
  2. 以右端点排序：遍历数组，创建一个变量right用于记录当前的交集的右端点。当当前的区间的左端点小于当前交集的右端点时，说明有交集，继续遍历(注意，这里按区间右端点排序，因而交集的右端点必定还是原来的那个右端点)；当当前的区间的左端点大于当前交集的右端点时，说明无交集，计数器cnt加1，然后将交集右端点置为当前区间右端点，继续遍历数组。

完整代码如下：

  • Cpp实现
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), 
          [](const vector<int>&a, const vector<int>&b){
              return a[1] < b[1];
          });
        int res = 0, right = points[0][1];
        for(vector<int> p : points){
            if(p[0] > right){
                ++res;
                right = p[1];
            }
        }
        return res+1;
    }
};
  • C实现

int findMinArrowShots(int** points, int pointsSize, int* pointsColSize){
    qsort(points, pointsSize, sizeof(int *), compare);
    int ans = 0, index = 0;
    for(; index < pointsSize;){
        int right = points[index][1];
        while(index < pointsSize && right >= points[index][0]){
            index++;
        }
        ans++;
    }
    return ans;
}

3 无重叠区间

3.1 题目描述

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

3.2 思路

  按左端点进行排序，当左端点相等时，则按右端点进行排序。然后创建一个变量right记录当前区间的右端点，当right <= intervals[i][0]时说明无重叠，将right``intervals[i][1];否则结果+1，并将right更新为min(right, p[1])，贪心的思想就体现在这，为什么是更新为min(right, p[1])？相比小区间，我们更偏向于删去区间较大的那个，这才能使得删去后区间的重复概率更小。(代码见Cpp实现)

  另一种做法是按区间右端点排序，然后遍历数组，如果当相邻的区间没交集，则计数器加1，然后将右端点更新为当前遍历到的区间右端点。这里的计数器实际上是计算没有重叠区间的个数，那么最后需要删去的区间数就是intervals.size() - cnt。但需要注意的是，计数器cnt需要初始化为1而不是0，因为只有一个区间的时候，是没有重复区间的。(代码见C实现)

完整代码如下：

Cpp实现

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), 
          [](const vector<int>&a, const vector<int>&b){
              if(a[0] == b[0])  return a[1] < b[1];
              return a[0] < b[0];
          });
        int res = 0, right = intervals[0][1];
        for(vector<int> p: intervals){  //注意这里是从下标0开始
            if(p[0] >= right){
                right = p[1];
            }else{
                right = min(right, p[1]);
                ++res;
            }
        }
        return res-1;     //所以要减1，从下标1开始就不用减1
    }
};

C实现

int cmp(const void *a, const void *b){
    return ((*(int **)a)[1] - (*(int **)b)[1]);
}

int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize){
    qsort(intervals, intervalsSize, sizeof(int *), cmp);

    int cnt = 1, end = intervals[0][1];
    for(int i = 1; i < intervalsSize; i++){
        if(end <= intervals[i][0]){
            cnt++;
            end = intervals[i][1];
        }
    }
    return intervalsSize - cnt;
}

4 划分字母区间

4.1 题目描述

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例1:

输入: S = “ababcbacadefegdehijhklij”
输出: [9,8,7]
解释: 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

4.2 思路

  遍历字符串map[26],将当前遍历到的字符的下标插入到map中，最后就相当于得到字符串中每个字符的最远位置。然后创建两个变量，一个表示当前片段的起始位置left，另一个表示当前片段的终点位置right，遍历该字符串，如果当前字符的最远位置大于right,则将right更新为当前字符的最远位置；而当当前遍历的字符的下标刚好等于right，说明从left到right刚好就是题目所要求的一个片段，将当前片段的长度right - left + 1插入到答案中，然后将片段起始位置移动到right的下一个位置，继续遍历字符串。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> res;
        int map[26] = {-1};
        for(int i = 0; i < s.length(); ++i){
            map[s[i] - 'a'] = i;
        }
        int left = 0, right = map[s[0] - 'a'];
        for(int i = 0; i < s.length(); ++i){
            right = max(right, map[s[i] - 'a']);
            if(i == right){
                res.emplace_back(right - left + 1);
                left = right + 1;
            }
        }
        return res;
    }
};
  • C 实现
int* partitionLabels(char * s, int* returnSize){
    int cnt = 0, len = strlen(s);
    *returnSize  = 0;
    int *ret = (int *)malloc(sizeof(int)*26);
    int pos[26];
    for(int i = 0; i < len; i++){
        pos[s[i] - 'a'] = i;
    }
    int left = 0, right = pos[s[0] - 'a'];    //第一个的最远
    for(int i = 0;i < len; i++){
        right = fmax(right, pos[s[i]-'a']);
        if(left == right){
            ret[(*returnSize)++] = 1;
            left = right + 1;
        }else if(i == right){
            ret[(*returnSize)++] = right-left+1;
            left = right + 1;
        }
    }
    
    return ret;
}

5 合并区间

5.1 题目描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例1:

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例2:

输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

5.2 思路

  先按区间左端点进行排序，然后找交集，如果有交集则更新右端点，否则将合并后的区间加入到答案中并更新左右端点为当前遍历的区间的左右端点。

完整代码如下：

  • Cpp实现
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        sort(intervals.begin(), intervals.end(), 
          [](const vector<int>& a, const vector<int>& b){
              return a[0] < b[0];
          });
        int left = intervals[0][0], right = intervals[0][1];
        for(int i = 1; i < intervals.size(); ++i){
            if(right >= intervals[i][0]){
                right = max(right, intervals[i][1]);
            }else{
                res.push_back({left, right});
                left = intervals[i][0]; 
                right = intervals[i][1];
            }
        }
        res.push_back({left, right});
        return res;
    }
};
  • C实现
int cmp(const void *a, const void *b){
    return ((*(int **)a)[0] - (*(int **)b)[0]);
}

int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes){
    qsort(intervals, intervalsSize, sizeof(int *), cmp);

    int** ret = (int **)malloc(sizeof(int *) * intervalsSize);
    *returnSize = 0;
    *returnColumnSizes = (int *)malloc(sizeof(int)*intervalsSize);
    int left = intervals[0][0], right = intervals[0][1];
    for(int i = 1; i <= intervalsSize; i++){
        if(i == intervalsSize){
            ret[*returnSize] = (int *)malloc(sizeof(int)*2);
            ret[*returnSize][0] = left;
            ret[*returnSize][1] = right;
            (*returnColumnSizes)[(*returnSize)++] = 2;
        }else if(right >= intervals[i][0]){    //重叠
            right = fmax(right, intervals[i][1]);
        }else if(right < intervals[i][0]){
            ret[*returnSize] = (int *)malloc(sizeof(int)*2);
            ret[*returnSize][0] = left;
            ret[*returnSize][1] = right;
            (*returnColumnSizes)[(*returnSize)++] = 2;
            left = intervals[i][0], right = intervals[i][1];
        }
    }
    return ret;
}

6 单调递增的数字

6.1 题目描述

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

示例1:

输入: n = 10
输出: 9

示例2:

输入: n = 1234
输出: 1234

示例3:

输入: 332
输出: 299

6.2 思路

由低位到高位遍历数字，当找到当前位小于其高一位，则将高一位减1，当前位及其低位均置为9，然后继续遍历直至满足条件即可。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        int ans = n;
        int tmp = n, cnt = 0;
        while(tmp){
            int rest = tmp % 10;    //最低位
            ++cnt;
            tmp /= 10;
            if(tmp % 10 > rest){
                ans = tmp * pow(10, cnt) - 1;
                tmp = ans;
                cnt = 0;
            }
        }
        return ans;
    }
};
  • C 实现
char *num2str(int n){
    char *res = (char*)malloc(sizeof(char)*12);
    int index = 11;
    res[index--] = '\0';
    while(n){
        res[index--] = n%10 + '0';
        n /= 10;
    }
    return res+index+1;
}

int monotoneIncreasingDigits(int n){
    char *str = num2str(n);
    int len = strlen(str);
    int pos = len;
    for(int i = len-1; i >= 1; --i){
        if(str[i-1] > str[i]){
            str[i-1]--;
            pos = i;
        }
    }
    for(int i = pos; i < len; ++i){
        str[i] = '9';
    }
    return atoi(str);

    /*
    int i = 0;
    for(; i < len-1; ++i){
        if(str[i] > str[i+1]){
            while(i && str[i-1] == str[i]) --i;
            str[i]--;
            break;
        }
    }
    for(i += 1; i < len; ++i){
        str[i] = '9';
    }
    return atoi(str);
    */
}

7 买卖股票的最佳时机含手续费

7.1 题目描述

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例1:

输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例2:

输入: prices = [1,3,7,5,10,3], fee = 3
输出: 6

7.2 思路

  • 动态规划: 这题用DP很好做，创建一个dp数组dp[n][2]，每天有两个状态，dp[i][0]表示第i天手上没有股票，dp[i][1]表示第i天手上有股票。dp[i][0]由前一天有股票但第i天卖出或前一天没有股票这两种状态转化而来，而dp[i][1]由前一天有股票或前一天没有股票第i天买入这两种状态转化而来，因而状态转换方程为：

  • 贪心: 将手续费在买入股票时就算入到股票的价格中，以prices[i]+fee作为股票的价格，用price来记录当前手里有股票时其最低的买入价格，然后遍历数组，如果prices[i]+fee < price说明前边买股票不如今天买，则将最低买入价格更新为prices[i]+fee；而当prices[i] > price时说明此时卖出可以获得利润，将二者的差值加到答案中，然后更新买入价格，注意，一找到prices[i] > price就卖出，而后如果有更大的获利空间，如果跟121题一样，连续买入卖出将会多次结算手续费，因而卖出时将最低价格置为当天的股票价格，这么一来，如果后边有买入价格prices[i]+fee<price时则自动更新为下一天再买股票，否则相当于股票还没卖出。这个思路要多想几次，想通透一点。

完整代码如下：

  • Cpp实现(DP)
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        int dp[n][2];
        memset(dp, 0 , sizeof(dp));
        dp[0][0] = 0, dp[0][1] = -prices[0];
        for(int i = 1; i < n; ++i){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);
            dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1]);
        }
        return dp[n-1][0];
    }
};

  • C实现(优化DP)

    int maxProfit(int* prices, int pricesSize, int fee){
    int dp[2] = {0, -prices[0]};
    for(int i = 1; i < pricesSize; i++){
        int newdp0 = fmax(dp[1]+prices[i]-fee, dp[0]);
        int newdp1 = fmax(dp[1], dp[0]-prices[i]);
        dp[0] = newdp0;
        dp[1] = newdp1;
    }
    return dp[0];
}

  • Cpp实现(贪心)

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int price = prices[0]+fee, profit = 0;
        for(int i = 1; i < prices.size(); ++i){
            if(prices[i] + fee < price){
                price = prices[i]+fee;
            }else if(prices[i] > price){
                profit += prices[i] - price;
                price = prices[i];
            }
        }
        return profit;
    }
};
  • C实现(贪心)
    int maxProfit(int* prices, int pricesSize, int fee){
    int price = prices[0] + fee, profit = 0;
    for(int i = 1; i < pricesSize; ++i){
        if(prices[i]+fee < price){
            price = prices[i]+fee;
        }else if(prices[i] > price){
            profit += prices[i] - price;
            price = prices[i];
        }
    }
    return profit;
}

8 监控二叉树

8.1 题目描述

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

示例1:

输入: [0,0,null,0,0]
输出: 1
解释: 如图所示，一台摄像头足以监控所有节点。

示例2:

输入: [0,0,null,0,null,0,null,null,0]
输出: 2
解释: 需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

8.2 思路

  • 0：无覆盖
  • 1：当前结点有摄像头
  • 2：有覆盖

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int ans;
    int dfs(TreeNode* root){
        if(!root) return 2;

        int left = dfs(root->left);
        int right = dfs(root->right);
        if(left == 2 && right ==2){
            return 0;
        }
        if(left == 0 || right == 0){
            ++ans;
            return 1;
        }
        if(left == 1 || right == 1){
            return 2;
        }
        return -1;
    }
    int minCameraCover(TreeNode* root) {
        ans = 0;
        if(dfs(root) == 0) ans++;
        return ans;
    }
};
  • C 实现
class Solution {
    int ans;
    // 2为有覆盖，1为有监控，0为未覆盖
    int dfs(TreeNode *root) {
        if(!root)   return 2;                   // 空节点显然是有覆盖的，返回2
        int left = dfs(root->left);
        int right = dfs(root->right);
        if(left == 2 && right == 2) {           // 如果左右孩子均有覆盖，说明当前节点未覆盖，即得安排监控在这个节点上
            return 0;
        }else if(left == 0 || right == 0) {     // 安排监控
            ++ans;
            return 1;                           // 返回上层表示当前节点已经安排了监控
        }else if(left == 1 || right == 1) {     // 左右孩子中至少有一个安排了监控，因而当前节点为已覆盖
            return 2;                           // 返回2
        }
        return 0;                               // 无所谓返回何值
    }
public:
    int minCameraCover(TreeNode* root) {
        ans = 0;
        if(dfs(root) == 0) ++ans;               // 当返回的是0时说明根节点需要安排监控，因而监控数+1
        return ans;
    }
};

总结

文章作者: Vyron Su
文章链接: http://example.com/2022/04/19/ch9-of-programmercarl-2/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Vyron Su !
C++ C 代码随想录 贪心