56. 合并区间【中等】
自己写的：
class Solution { public: static bool cmp(const vector<int>& a, const vector<int>& b){ if(a[0] == b[0]) return a[1] < b[1]; return a[0] < b[0]; } vector<vector<int>> merge(vector<vector<int>>& intervals) { if(intervals.size() == 1) return intervals; //1.处理size==1的情况 sort(intervals.begin(), intervals.end(), cmp); //2.排序 vector<vector<int>> res; for(int i = 1; i < intervals.size(); ++i){ if(intervals[i][0] <= intervals[i-1][1]){ //核心代码 intervals[i][0] = intervals[i-1][0]; intervals[i][1] = max(intervals[i-1][1], intervals[i][1]); intervals[i-1][1] = -1; } else{ res.push_back(intervals[i-1]); } } //处理最后一个 if(intervals[intervals.size()-1][0] > intervals[intervals.size()-2][1]){ res.push_back(intervals[intervals.size()-1]); } return res; } };
- 官方答案
class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { if (intervals.size() < 2) return intervals; // 排序的参数使用了lamda表达式 sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];}); vector<vector<int>> res; res.push_back(intervals[0]); for (int i = 1; i < intervals.size(); i++) { if (res.back()[1] >= intervals[i][0]) { // 合并区间 res.back()[1] = max(res.back()[1], intervals[i][1]); //这里实现合并 } else { res.push_back(intervals[i]); } } return res; } };
- 时间复杂度：O(n\log n)，有一个快排
- 空间复杂度：O(1)，我没有算result数组（返回值所需容器占的空间
738. 单调递增的数字【中等】
思路一：暴力破解
一个一个减1判断是否满足条件
class Solution { //暴力破解 //时间复杂度：O(nm) m为n的数字长度 //空间复杂度：O(1) public: bool checkNum(int num) { int low_pos = 10; //记录最低位 while (num) { int temp_pos = num % 10; //拿出最低位 if (low_pos >= temp_pos) low_pos = temp_pos; //最低位大于次低位 更新最低位 else return false; //如果低位比高位小 false num = num / 10; } return true; } int monotoneIncreasingDigits(int N) { for (int i = N; i > 0; i--) { //一个一个判断 if (checkNum(i)) return i; } return 0; } };
思路二：贪心
class Solution { public: int monotoneIncreasingDigits(int N) { string strNum = to_string(N); //数字转字符串 string头文件的函数 //1.找到标记位置，并使标记位的前一位-1 int flag = strNum.size(); for (int i = strNum.size() - 1; i > 0; i--) { //必须从后面遍历到前面 反过来实现不了 if (strNum[i - 1] > strNum[i]) { //前一位>后一位 flag = i; //后一位改9 strNum[i - 1]--; //前一位减1 332 -> 322 -> 222 } } //2.标记位起改9 for (int i = flag; i < strNum.size(); i++) { //标记位置开始改9 strNum[i] = '9'; //222 -> 299 } return stoi(strNum); //字符串转数字 } };
- 时间复杂度：O(n)，n 为数字长度
- 空间复杂度：O(n)，需要一个字符串，转化为字符串操作更方便
968. 监控二叉树【困难，不会】
有如下三种：
- 该节点无覆盖
- 本节点有摄像头
- 本节点有覆盖
我们分别有三个数字来表示：
- 0：该节点无覆盖
- 1：本节点有摄像头
- 2：本节点有覆盖
可以使用后序遍历也就是左右中的顺序，这样就可以在回溯的过程中从下到上进行推导了。
单层逻辑处理，主要有如下四类情况：
- 情况1：左右节点都有覆盖
- 左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。
- 情况2：左右节点至少有一个无覆盖的情况
- 如果是以下情况，则中间节点（父节点）应该放摄像头
- 情况3：左右节点至少有一个有摄像头
- 如果是以下情况，其实就是 左右孩子节点有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）
- 情况4：头结点没有覆盖
// 版本一 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; } };
跳跃游戏
55. 跳跃游戏【中等】
class Solution { public: bool canJump(vector<int>& nums) { if (nums.size() < 2) return true; // 只有0,1个元素，就是能达到 int cover = 0; for (int i = 0; i < nums.size(); i++) { if(i <= cover){ //i在覆盖范围内 cover = max(i + nums[i], cover); //更新覆盖范围 if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了 } else return false; } return false; //这句走不到 } };
45. 跳跃游戏 II【中等】
题目意思：最少的次数到达最后位置，假设总能到达最后位置
从图中可以看出来，就是移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。
这里还是有个特殊情况需要考虑，当移动下标达到了当前覆盖的最远距离下标时
- 如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
- 如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。
class Solution { public: int jump(vector<int>& nums) { if (nums.size() < 2) return 0; int curDistance = 0; // 当前覆盖最远距离下标 int ans = 0; // 记录走的最大步数 int nextDistance = 0; // 下一步覆盖最远距离下标 for (int i = 0; i < nums.size(); i++) { nextDistance = max(nums[i] + i, nextDistance); // 记录下一步覆盖最远距离下标 if (i == curDistance) { // 遇到当前覆盖最远距离下标 if (curDistance < nums.size() - 1) { // 如果当前覆盖最远距离下标不是终点 ans++; // 需要走下一步 curDistance = nextDistance; // 更新当前覆盖最远距离下标（相当于加油了） if (nextDistance >= nums.size() - 1) break; // 下一步的覆盖范围已经可以达到终点，结束循环 } else break; // 当前覆盖最远距离下标是集合终点，不用做ans++操作了，直接结束 } } return ans; } };
在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。
- [x]
class Solution { public: int jump(vector<int>& nums) { int curDistance = 0; // 当前覆盖的最远距离下标 int ans = 0; // 记录走的最大步数 int nextDistance = 0; // 下一步覆盖的最远距离下标 for (int i = 0; i < nums.size() - 1; i++) { // 注意这里是小于nums.size() - 1，这是关键所在 nextDistance = max(nums[i] + i, nextDistance); // 记录下一步覆盖的最远距离下标 if (i == curDistance) { // 遇到当前覆盖的最远距离下标 curDistance = nextDistance; // 更新当前覆盖的最远距离下标 ans++; } } return ans; } };
两个维度权衡问题
135. 分发糖果【困难】
- 思路一：贪心
时间复杂度：O(n)
空间复杂度：O(n)
两次遍历，一次向后，一次向前
class Solution { public: int candy(vector<int>& ratings) { //1. 分发糖果 vector<int> candyVec(ratings.size(), 1); //1.1 先每人分一个 // 从前向后 for (int i = 1; i < ratings.size(); i++) { if (ratings[i] > ratings[i - 1]) { //1.2 右边的比左边多一个 candyVec[i] = candyVec[i - 1] + 1; } } // 从后向前 for (int i = ratings.size() - 2; i >= 0; i--) { //确定左边>右边 if (ratings[i] > ratings[i + 1] ) { candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1); //选取max是因为要保持上面的不变 } } // 2. 统计结果 int res = 0; for (int i = 0; i < candyVec.size(); i++) { res += candyVec[i]; } return res; } };
方法二：常数空间遍历
时间复杂度：O(n)
空间复杂度：O(1)
https://leetcode-cn.com/problems/candy/solution/fen-fa-tang-guo-by-leetcode-solution-f01p/
class Solution { public: int candy(vector<int>& ratings) { int res = 1; int inc = 1; //最近递增序列长度 int dec = 0; //当前递减序列长度 int pre = 1; //前一个同学的苹果数量 for (int i = 1; i < ratings.size(); i++) { if (ratings[i] >= ratings[i - 1]) { dec = 0; pre = (ratings[i] == ratings[i - 1]) ? 1 : pre + 1; res += pre; inc = pre; } else { dec++; if (dec == inc) { dec++; } res += dec; pre = 1; } } return res; } };
406. 根据身高重建队列【中等】
思路：先排序，后插入
插入的过程：
- 插入[7,0]：[[7,0]]
- 插入[7,1]：[[7,0],[7,1]]
- 插入[6,1]：[[7,0],[6,1],[7,1]]
- 插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
- 插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
- 插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
- 时间复杂度：O(n\log n + n^2)
- 空间复杂度：O(n)
class Solution { public: static bool cmp(const vector<int>& a, const vector<int>& b) { if (a[0] == b[0]) return a[1] < b[1]; return a[0] > b[0]; } vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { sort (people.begin(), people.end(), cmp); //1.排序 高->低 vector<vector<int>> que; for (int i = 0; i < people.size(); i++) { int position = people[i][1]; que.insert(que.begin() + position, people[i]); //2.插序 } return que; } };
但使用vector是非常费时的，C++中vector（可以理解是一个动态数组，底层是普通数组实现的）如果插入元素大于预先普通数组大小，vector底部会有一个扩容的操作，即申请两倍于原先普通数组的大小，然后把数据拷贝到另一个更大的数组上。
- [x]
class Solution { public: // 身高从大到小排（身高相同k小的站前面） static bool cmp(const vector<int>& a, const vector<int>& b) { if (a[0] == b[0]) return a[1] < b[1]; return a[0] > b[0]; } vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { sort (people.begin(), people.end(), cmp); list<vector<int>> que; // list底层是链表实现，插入效率比vector高的多 for (int i = 0; i < people.size(); i++) { int position = people[i][1]; // 插入到下标为position的位置 list<vector<int>>::iterator it = que.begin(); while (position--) { // 寻找在插入位置 it++; } que.insert(it, people[i]); //链表的插入速度快 } return vector<vector<int>>(que.begin(), que.end()); //list容器->vector容器 } };
该方法速度更快，但是以空间换取时间
动态数组底层会进行全量拷贝扩容，所以消耗时间
股票系列
121. 买卖股票的最佳时机【简单】
相同题目：剑指 Offer 63. 股票的最大利润
题目意思：只能买入一次，卖出一次，最大利润
思路一：双for暴力破解；思路和53.最大子序和很像
时间复杂度：O(n^2)
空间复杂度：O(1)
class Solution { public: //双for循环暴力破解 超出时间限制 int maxProfit(vector<int>& prices) { int max_fit = 0; for (int i = 0; i < prices.size(); i++) { for (int j = i + 1; j < prices.size(); j++) { max_fit = max(max_fit, prices[j] - prices[i]); } } return max_fit; } };
- 思路二：贪心
股票，去数组左边的最小值，右边的最大值，差值即为最大利润
时间复杂度：O(n) 一次for循环遍历
空间复杂度：O(1)
class Solution { public: int maxProfit(vector<int>& prices) { int low = INT_MAX; int res = 0; for (int i = 0; i < prices.size(); i++) { //从左到右遍历 low = min(low, prices[i]); // 动态更新最小价格 res = max(res, prices[i] - low); // 动态更新最大利润 } return res; } };
思路三：动态规划
有点难，下次再来补充
122. 买卖股票的最佳时机 II【中等】
题目意思：
- 只有一只股票！
- 当前只有买股票或者买股票的操作
思路：把每一题的股价描点画成折线图，求所有上升线段的累加；借鉴376题
- 贪心：
时间复杂度：O(n)
空间复杂度：O(1)
class Solution { public: int maxProfit(vector<int>& prices) { int res = 0; for(int i = 1; i < prices.size(); i++){ res += max(0, prices[i]-prices[i-1]); } return res; } };
714. 买卖股票的最佳时机含手续费【中等，不会】
- 思路一：贪心
- 时间复杂度：O(n)
- 空间复杂度：O(1)
我们在做收获利润操作的时候其实有三种情况：
- 情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
- 情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。
- 情况三：不作操作，保持原有状态（买入，卖出，不买不卖）
class Solution { public: int maxProfit(vector<int>& prices, int fee) { int res = 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) { res += prices[i] - minPrice - fee; minPrice = prices[i] - fee; // 情况一，这一步很关键 } } return res; } };
当我们卖出一支股票时，我们就立即获得了以相同价格并且免除手续费买入一支股票的权利
- [x]
class Solution { public: int maxProfit(vector<int>& prices, int fee) { int buy = prices[0] + fee; int profit = 0; for (int i = 1; i < prices.size(); ++i) { if (prices[i] + fee < buy) { //更新买入价 buy = prices[i] + fee; } else if (prices[i] > buy) { //收集利润 profit += prices[i] - buy; buy = prices[i]; } } return profit; } };
思路二：动态规划
