0618刷题

0618刷题

class Solution {
public:
    static bool cmp(vector& a,vector& b)
    {
        return a[0]>& points) {
        sort(points.begin(),points.end(),cmp);

        int count=1;
        int left=points[0][0];
        int right=points[0][1];
        for(int i=1;i
            if(points[i][0]>=left&&points[i][0]<=right) 
            {
                left=max(left,points[i][0]);
                right=min(right,points[i][1]);
            } 
            if(points[i][0]>right)
            {
                count++;
                left=points[i][0];
                right=points[i][1];
            }
        }
        return count;
    }
};

首先，按照第一个元素从小到大的顺序对数组进行排序：

points = [[10,16],[2,8],[1,6],[7,12]]

排序之后的数组如下：

points = [[1,6],[2,8],[7,12],[10,16]]

然后利用贪心算法，使得一支箭可以射中足够多的区间。

1.设定初始区间为[1,6]，count=1,left=1,right=6.

2.从下标1开始遍历数组，下一个vector是[2,8]，因为1<2<8，则可以用一支箭射中这个区间，count不需要+1，更新区间left=2，right=6.

3.遍历到下标2，vector为[7,12]，因为7>right，则count+1，此时需要更新left和right为7和12.

4.继续向后遍历直至结束。

class Solution {
public:
    static bool cmp(vector& a,vector& b)
    {
        if(a[0]==b[0]) return a[1]>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);

        int count=1;
        int left=intervals[0][0];
        int right=intervals[0][1];
        for(int i=1;i
            if(intervals[i][0]>left&&intervals[i][0]
                left=max(left,intervals[i][0]);
                right=min(right,intervals[i][1]);
            } 
            if(intervals[i][0]>=right)//!!!
            {
                count++;
                left=intervals[i][0];
                right=intervals[i][1];
            }
        }
        return intervals.size()-count;//!!!
    }
};

同LeetCode 452. 用最少数量的箭引爆气球，略加修改即可，修改的地方已经加//！！！

//因为边缘相等不算重叠，所以去掉等号
if(intervals[i][0]>left&&intervals[i][0] 
由于coun记录的是可以有多少个不重叠的区间，所以需要
 
return intervals.size()-count
 
方法2 
class Solution {
public:
    // 按照区间右边界排序
    static bool cmp (const vector& a, const vector& b) {
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector>& intervals) {
        if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 1; // 记录非交叉区间的个数
        int end = intervals[0][1]; // 记录区间分割点
        for (int i = 1; i < intervals.size(); i++) {
            if (end <= intervals[i][0]) {
                end = intervals[i][1];
                count++;
            }
        }
        return intervals.size() - count;
    }
};
 
按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
 
右边界排序之后，局部最优：优先选右边界小的区间，所以从左向右遍历，留给下一个区间的空间大一些，从而尽量避免交叉。全局最优：选取最多的非交叉区间。
 
LeetCode 763. 划分字母区间 
LeetCode 763. 划分字母区间 
class Solution {
public:
    vector partitionLabels(string s) {
        vector position=vector (26,-1);
        for(int i=0;i
            position[s[i]-'a']=i;
        }
        
        int left=0;
        int right = 0;
        vector result;
        for(int i=0;i
            right = max(right, position[s[i] - 'a']);
            if(i==right)
            {
                result.push_back(right - left + 1);
                left = i + 1;
            }   
        }
        return result;
    }
};
 
思考过程：
 
ababc bacad efegd ehijh klij
01234 56789 01234 56789 0123
0           1           2
a=8
b=5
c=7
d=14
e=15
f=11
g=13
h=19
i=22
j=23
k=20 
l=21
[8,5,7, 14,15,11,13, 19,22,23,20,21,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]
i到position[i]中间出现的所有元素的最大position
//8,5,7 14,15,11,13 19,22,23,20,21
8 15 23
//9 16 24
//9 16-9=7 24-16=8
 
在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。
 
可以分为如下两步：
 
统计每一个字符最后出现的位置
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
 
 
LeetCode 738. 单调递增的数字 
LeetCode 738. 单调递增的数字 
自己的复杂解法 
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        //120
        //第一个不满足递增的地方记为下标x
        //下标x处的数字减一，后面的元素全部补9
        if(n==0) return 0;
        vector result;
        
        //result数组中存数字
        while(n)
        {
            result.push_back(n%10);
            n=n/10;
        }
        	
        //倒序
        int left=0;
        int right=result.size()-1;
        while(left<=right)
        {
            int tmp=result[left];
            result[left]=result[right];
            result[right]=tmp;
            left++;
            right--;
        }

        for(int i=0;i
            //332
            if(result[i]>result[i+1]) 
            {
                //向左边找是否有和它相等的元素，如果相等，则下标-1
                while(i>0&&result[i-1]==result[i])  i--;
                
                result[i]-=1;
                for(int j=i+1;j
                    result[j]=9;
                }
                break;
            }
        }

        int num=0;
        for(int i=0;i
            num=num*10+result[i];
        }
        return num;
    }
};
 
基本思路： 第一个不满足递增的地方记为下标x，向左边找是否有和它相等的元素，如果相等，则下标-1，不相等的话直接将下标x处的数字减一，后面的元素全部补9。
 
相较于贪心算法，处理复杂的地方有：没有用string进行处理，没有从右向左进行处理。
 
贪心算法 
//代码随想录 用332举例
class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string strNum = to_string(N);
        // flag用来标记赋值9从哪里开始
        // 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
        int flag = strNum.size();
        for (int i = strNum.size() - 1; i > 0; i--) {
            if (strNum[i - 1] > strNum[i] ) {
                flag = i;
                strNum[i - 1]--;
            }
        }
        for (int i = flag; i < strNum.size(); i++) {
            strNum[i] = '9';
        }
        return stoi(strNum);
    }
};
 
局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]–，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。
 
全局最优：得到小于等于N的最大单调递增的整数。
 
但这里局部最优推出全局最优，还需要其他条件，即遍历顺序，和标记从哪一位开始统一改成9。
 
此时是从前向后遍历还是从后向前遍历呢？
 
从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。
 
这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。
 
所以从前后向遍历会改变已经遍历过的结果！
 
那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299
 
LeetCode 714. 买卖股票的最佳时机含手续费 
LeetCode 714. 买卖股票的最佳时机含手续费 
如果使用贪心策略，就是最低值买，最高值（如果算上手续费还盈利）就卖。
 
此时无非就是要找到两个点，买入日期，和卖出日期。
 
买入日期：其实很好想，遇到更低点就记录一下。
卖出日期：这个就不好算了，但也没有必要算出准确的卖出日期，只要当前价格大于（最低价格+手续费），就可以收获利润，至于准确的卖出日期，就是连续收获利润区间里的最后一天（并不需要计算是具体哪一天）。
 
所以我们在做收获利润操作的时候其实有三种情况：
 
情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。
情况三：不作操作，保持原有状态（买入，卖出，不买不卖）
 
class Solution {
public:
    int maxProfit(vector& prices, int fee) {
        int result = 0;
        int minPrice = prices[0]; // 记录最低价格
        for (int i = 1; i < prices.size(); i++) {
            // 情况二：相当于买入
            if (prices[i] < minPrice) minPrice = prices[i];

            // 情况三：保持原有状态（因为此时买则不便宜，卖则亏本）
            if (prices[i] >= minPrice && prices[i] <= minPrice + fee) {
                continue;
            }

            // 计算利润，可能有多次计算利润，最后一次计算利润才是真正意义的卖出
            if (prices[i] > minPrice + fee) {
                result += prices[i] - minPrice - fee;
                minPrice = prices[i] - fee; // 情况一，这一步很关键
            }
        }
        return result;
    }
};
 
说明情况1：
 
minPrice = prices[i] - fee; // 情况一，这一步很关键
 
[1,3,2,8,9]
 
当数值为8的时候，min=1，result+=8-1-2=5;
 
因为后面是9，答案是9-1-2=6.
 
因为需要将min更新为8-2=6，防止8到9的时候再减去一下fee
 
LeetCode 968. 监控二叉树（hard) 
LeetCode 968. 监控二叉树 
// 版本一
class Solution {
private:
    int result;
    int traversal(TreeNode* cur) {

        // 空节点，该节点有覆盖
        if (cur == NULL) return 2;

        int left = traversal(cur->left);    // 左
        int right = traversal(cur->right);  // 右

        // 情况1
        // 左右节点都有覆盖
        if (left == 2 && right == 2) return 0;

        // 情况2
        // left == 0 && right == 0 左右节点无覆盖
        // left == 1 && right == 0 左节点有摄像头，右节点无覆盖
        // left == 0 && right == 1 左节点有无覆盖，右节点摄像头
        // left == 0 && right == 2 左节点无覆盖，右节点覆盖
        // left == 2 && right == 0 左节点覆盖，右节点无覆盖
        if (left == 0 || right == 0) {
            result++;
            return 1;
        }

        // 情况3
        // left == 1 && right == 2 左节点有摄像头，右节点有覆盖
        // left == 2 && right == 1 左节点有覆盖，右节点有摄像头
        // left == 1 && right == 1 左右节点都有摄像头
        // 其他情况前段代码均已覆盖
        if (left == 1 || right == 1) return 2;

        // 以上代码我没有使用else，主要是为了把各个分支条件展现出来，这样代码有助于读者理解
        // 这个 return -1 逻辑不会走到这里。
        return -1;
    }

public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        // 情况4
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }
};
 
参考解法
 
1.后序遍历保证左右中的顺序，从下到上进行遍历
 
2.我们分别有三个数字来表示：
 
0：该节点无覆盖
1：本节点有摄像头
2：本节点有覆盖
 
主要有如下四类情况：
 
情况1：左右节点都有覆盖
情况2：左右节点至少有一个无覆盖的情况
情况3：左右节点至少有一个有摄像头
情况4：头结点没有覆盖：递归结束之后，还要判断根节点，如果没有覆盖，result++