网站建设的技术可行性,网站建设 排行,打开网站弹出广告js,wordpress淘宝客类网站建设目录
①力扣56. 合并区间
解析代码
②力扣435. 无重叠区间
解析代码
③力扣452. 用最少数量的箭引爆气球
解析代码
④力扣397. 整数替换
解析代码1_递归改记忆化搜索
解析代码2_贪心策略
⑤力扣354. 俄罗斯套娃信封问题
解析代码1_动态规划#xff08;超时#xf…目录
①力扣56. 合并区间
解析代码
②力扣435. 无重叠区间
解析代码
③力扣452. 用最少数量的箭引爆气球
解析代码
④力扣397. 整数替换
解析代码1_递归改记忆化搜索
解析代码2_贪心策略
⑤力扣354. 俄罗斯套娃信封问题
解析代码1_动态规划超时
解析代码2_重写排序贪心二分
⑥力扣1262. 可被三整除的最大和
解析代码
⑦力扣1054. 距离相等的条形码
解析代码
⑧力扣767. 重构字符串
解析代码
本篇完。 ①力扣56. 合并区间
56. 合并区间
难度 中等
以数组 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] 可被视为重叠区间。提示
1 intervals.length 10^4intervals[i].length 20 starti endi 10^4
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {}
}; 解析代码
贪心策略
先按照区间的左端点排序此时会发现能够合并的区间都是连续的。然后从左往后如果可以合并就按照求并集的方式合并区间如果不可以合并就把区间丢到结果数组再往后遍历。
如何求并集
由于区间已经按照左端点排过序了因此当两个区间合并的时候合并后的区间
左端点就是前一个区间的左端点。右端点就是两者右端点的最大值。
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {sort(intervals.begin(), intervals.end());vectorvectorint ret;int left intervals[0][0], right intervals[0][1];for(auto e : intervals){if(e[0] right) // 可以合并{right max(right, e[1]);}else{ret.push_back({left, right});left e[0], right e[1];}}ret.push_back({left, right});return ret;}
}; ②力扣435. 无重叠区间
435. 无重叠区间
难度 中等
给定一个区间的集合 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
解释: 你不需要移除任何区间因为它们已经是无重叠的了。提示:
1 intervals.length 10^5intervals[i].length 2-5 * 10^4 starti endi 5 * 10^4
class Solution {
public:int eraseOverlapIntervals(vectorvectorint intervals) {}
}; 解析代码
贪心策略
先按照区间的左端点排序。当两个区间重叠的时候为了能够在移除某个区间后保留更多的区间我们应该把区间范围较大的区间移除。
如何移除区间范围较大的区间
由于已经按照左端点排序了因此两个区间重叠的时候我们应该保留右端点较小的区间。
class Solution {
public:int eraseOverlapIntervals(vectorvectorint intervals) {sort(intervals.begin(), intervals.end());int ret 0;int left intervals[0][0], right intervals[0][1];for(auto e : intervals){if(e[0] right) // 不重叠{left e[0], right e[1];}else // 重叠{ret;right min(right, e[1]); // 保留右端点较小的区间}}return ret - 1; // 从第一个区间开始比较就删掉第一个区间}
}; ③力扣452. 用最少数量的箭引爆气球
452. 用最少数量的箭引爆气球
难度 中等
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points 其中points[i] [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭若有一个气球的直径的开始和结束坐标为 xstartxend 且满足 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]。提示:
1 points.length 105points[i].length 2-2^31 xstart xend 2^31 - 1
class Solution {
public:int findMinArrowShots(vectorvectorint points) {}
}; 解析代码
贪心策略
先按照区间的左端点排序此时会发现互相重叠的区间都是连续的。这样在射箭的时候要发挥每一支箭最大的作用应该把互相重叠的区间统一引爆。
如何求互相重叠区间
由于我们是按照左端点排序的因此对于两个区间我们求的是它们的交集注意合并区间用的是并集求重叠区间求的是交集
左端点为两个区间左端点的最大值但是左端点不会影响我们的合并结果所以可以忽略。右端点为两个区间右端点的最小值。
class Solution {
public:int findMinArrowShots(vectorvectorint points) {sort(points.begin(), points.end());int ret 1, right points[0][1];for(auto e : points){if(e[0] right) // 能合并求交集一起击破{// left max(left, e[0]); // left不影响合并结果right min(right, e[1]);}else // 不能合并继续往后遍历{ret;// left e[0]; // left不影响合并结果right e[1];}}return ret; // 加上最后的区间}
}; ④力扣397. 整数替换
397. 整数替换
难度 中等
给定一个正整数 n 你可以做如下操作
如果 n 是偶数则用 n / 2替换 n 。如果 n 是奇数则可以用 n 1或n - 1替换 n 。
返回 n 变为 1 所需的 最小替换次数 。
示例 1
输入n 8
输出3
解释8 - 4 - 2 - 1示例 2
输入n 7
输出4
解释7 - 8 - 4 - 2 - 1
或 7 - 6 - 3 - 2 - 1示例 3
输入n 4
输出2提示
1 n 2^31 - 1
class Solution {
public:int integerReplacement(int n) {}
}; 解析代码1_递归改记忆化搜索 此题的贪心策略很难想出来先看看记忆化搜索的方法记忆化搜索在之前专题已经学过用爆搜模拟也可以过但是加上备忘录优化
class Solution {unordered_mapint, int memo;
public:int integerReplacement(int n) {// 时间O(logN) 空间O(logN)return dfs(n);}int dfs(long long n){if(n 1)return 0;if(memo[n] ! 0)return memo[n];if(n % 2 0){memo[n] 1 dfs(n / 2);return memo[n];}else{memo[n] 1 min(dfs(n - 1), dfs(n 1));return memo[n];}}
}; 解析代码2_贪心策略
贪心策略任何选择都应该让这个数尽可能快地变成 1 。
对于偶数只执行除 2 操作。对于奇数
当 n 1 的时候不用执行任何操作。当 n 3 的时候变成 1 的最优操作数是 2 。当 n 1 n % 4 1的时候那么它的二进制表示是 ......01 最优的方式应该选择 -1 这样就可以把末尾的 1 干掉接下来执行除法操作能够更快地变成1 。当 n 3 n % 4 3的时候那么它的二进制表示是 ......11 最优的方式应该选择 1 这样可以把一堆连续的 1 转换成 0 更快地变成 1 。
class Solution {
public:int integerReplacement(int n){// 时间O(logN) 空间O(1)int ret 0;while(n ! 1){if(n % 2 0){n n / 2;ret;}else{ret 2; // 下面操作都是两步if(n 3)break;else if(n % 4 1) // ......01n / 2; // 和减1除2结果一样else // ......01n n / 2 1; // 和加1除2结果一样防溢出}}return ret;}
}; ⑤力扣354. 俄罗斯套娃信封问题
354. 俄罗斯套娃信封问题
难度 困难
给你一个二维整数数组 envelopes 其中 envelopes[i] [wi, hi] 表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候这个信封就可以放进另一个信封里如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封即可以把一个信封放到另一个信封里面。
注意不允许旋转信封。
示例 1
输入envelopes [[5,4],[6,4],[6,7],[2,3]]
输出3
解释最多信封的个数为 3, 组合为:
[2,3] [5,4] [6,7]。
示例 2
输入envelopes [[1,1],[1,1],[1,1]]
输出1提示
1 envelopes.length 10^5envelopes[i].length 21 wi, hi 10^5
class Solution {
public:int maxEnvelopes(vectorvectorint envelopes) {}
}; 解析代码1_动态规划超时 将数组按照左端点排序之后问题就转化成了最长递增子序列模型那接下来我们就可以用解决最长递增子序列的经验来解决这个问题会超时但还是建议敲一下代码。
状态表示dp[i] 表示以 i 位置的信封为结尾的所有套娃序列中最长的套娃序列的长度。状态转移方程dp[i] max(dp[j] 1) 其中 0 j i e[i][0] e[j][0] e[i][1] e[j][1] 。初始化全部初始化为 1 。填表顺序从左往右。返回值整个 dp 表中的最大值。
class Solution {
public:int maxEnvelopes(vectorvectorint envelopes) {sort(envelopes.begin(), envelopes.end());int n envelopes.size(), ret 1;vectorint dp(n, 1);for(int i 1; i n; i){for(int j 0; j i; j){if(envelopes[i][0] envelopes[j][0] envelopes[i][1] envelopes[j][1]){dp[i] max(dp[i], dp[j] 1);}}ret max(ret, dp[i]);}return ret;}
}; 解析代码2_重写排序贪心二分
当我们把整个信封按照下面的规则排序之后
左端点不同的时候按照左端点从小到大排序。左端点相同的时候按照右端点从大到小排序 此时问题就变成了仅考虑信封的右端点完完全全的变成的最长递增子序列的模型。那么我们就可以用贪心 二分优化我们的算法。
class Solution {
public:int maxEnvelopes(vectorvectorint envelopes) {sort(envelopes.begin(), envelopes.end(), [](vectorint e1, vectorint e2){return e1[0] ! e2[0] ? e1[0] e2[0] : e1[1] e2[1];});vectorint ret;ret.push_back(envelopes[0][1]);for(auto e : envelopes){if(e[1] ret.back()){ret.push_back(e[1]);}else // 二分找到要放的位置找大于等于e[1]的左端点{int left 0, right ret.size() - 1;while(left right){int mid (left right) 1;if(ret[mid] e[1])left mid 1;elseright mid;}ret[left] e[1];}}return ret.size();}
}; ⑥力扣1262. 可被三整除的最大和
1262. 可被三整除的最大和
难度 中等
给你一个整数数组 nums请你找出并返回能被三整除的元素最大和。
示例 1
输入nums [3,6,5,1,8]
输出18
解释选出数字 3, 6, 1 和 8它们的和是 18可被 3 整除的最大和。
示例 2
输入nums [4]
输出0
解释4 不能被 3 整除所以无法选出数字返回 0。示例 3
输入nums [1,2,3,4,4]
输出12
解释选出数字 1, 3, 4 以及 4它们的和是 12可被 3 整除的最大和。提示
1 nums.length 4 * 10^41 nums[i] 10^4
class Solution {
public:int maxSumDivThree(vectorint nums) {}
}; 解析代码
正难则反 可以先把所有的数累加在一起然后根据累加和的结果贪心地删除一些数。
分类讨论设累加和为 sum 用 x 标记 %3 1 的数用 y 标记 % 3 2 的数。那么根据 sum 的余数可以分为下面三种情况求最小的值和次小的值可以直接sort也可以在求数组和的时候记录下来时间就变为了ON。
sum % 3 0 此时所有元素的和就是满足要求的直接返回。sum % 3 1此时数组中要么存在一个xx % 3 1要么存在两个yy % 3 2。因为我们要的是最大值所以应该选择 x 中最小的那么数记为 x1 或者是 y 中最小以及次小的两个数记为 y1, y2 。那么我们应该选择这两种情况下的最大值 max(sum - x1, sum - y1 - y2) 。sum % 3 2此时数组中要么存在一个 yy % 3 2要么存在两个 xx % 3 1 。因为我们要的是最大值所以应该选择 y 中最小的那个数记为 y1 或者是 x 中最小以及次小的两个数记为 x1, x2 。那么我们应该选择这两种情况下的最大值 max(sum - y1, sum - x1 - x2) 。
那么应该选择下面两种情况下的最大值 max(sum - y1, sum - x1 - x2)
class Solution {
public:int maxSumDivThree(vectorint nums) {const int INF 0x3f3f3f3f;int sum 0, x1 INF, x2 INF, y1 INF, y2 INF;for(auto x : nums){sum x;if(x % 3 1) // 找出x % 3 1中x最小的和次小的{if(x x1)x2 x1, x1 x;else if(x x2) x2 x;}else if(x % 3 2) // 找出x % 3 2中x最小的和次小的{if(x y1)y2 y1, y1 x;else if(x y2)y2 x;}}if(sum % 3 1)sum max(sum - x1, sum - y1 - y2);else if(sum % 3 2)sum max(sum - y1, sum - x1 - x2);return sum;}
}; ⑦力扣1054. 距离相等的条形码
1054. 距离相等的条形码
难度 中等
在一个仓库里有一排条形码其中第 i 个条形码为 barcodes[i]。
请你重新排列这些条形码使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案此题保证存在答案。
示例 1
输入barcodes [1,1,1,2,2,2]
输出[2,1,2,1,2,1]示例 2
输入barcodes [1,1,1,1,2,2,3,3]
输出[1,3,1,3,2,1,2,1]提示
1 barcodes.length 100001 barcodes[i] 10000
class Solution {
public:vectorint rearrangeBarcodes(vectorint barcodes) {}
}; 解析代码
贪心策略
每次处理一批相同的数字往 n 个空里面摆放。每次摆放的时候隔一个格子摆放一个数。先处理出现次数最多的那个数剩下的数可任意。此题保证存在答案-出现次数最多的那个数不会超过n 1/ 2下一个数想相邻的话只能“填一圈”不可能。
class Solution {
public:vectorint rearrangeBarcodes(vectorint barcodes) {unordered_mapint, int hash; // 数和其出现的次数int mostVal 0, maxCount 0;for(auto e : barcodes) // 统计每个数出现的频次{hash[e];if(maxCount hash[e]){maxCount hash[e];mostVal e;}}int n barcodes.size(), index 0;vectorint ret(n);for(int i 0; i maxCount; i) // 先处理出现次数最多的数{ret[index] mostVal;index 2;}hash.erase(mostVal);for(auto [a, b] : hash) // 处理剩下的数{for(int i 0; i b; i){if(index n)index 1;ret[index] a;index 2;}}return ret;}
}; ⑧力扣767. 重构字符串
767. 重构字符串
难度 中等
给定一个字符串 s 检查是否能重新排布其中的字母使得两相邻的字符不同。
返回 s 的任意可能的重新排列。若不可行返回空字符串 。
示例 1:
输入: s aab
输出: aba示例 2:
输入: s aaab
输出: 提示:
1 s.length 500s 只包含小写字母
class Solution {
public:string reorganizeString(string s) {}
}; 解析代码
和力扣1054. 距离相等的条形码基本一致。
贪心策略
每次处理一批相同的字母往 n 个空里面摆放。每次摆放的时候隔一个格子摆放一个字母。先处理出现次数最多的那个字母剩下的字母可任意。如果出现次数最多的那个字母不超过n 1/ 2则有解下一个字母想相邻的话只能“填一圈”不可能。
class Solution {
public:string reorganizeString(string s) {int hash[26] {0};char mostVal s[0];int maxCount 0;for(auto e : s) // 统计每个数出现的频次{hash[e - a];if(maxCount hash[e - a]){maxCount hash[e - a];mostVal e;}}int n s.size(), index 0;if(maxCount (n 1) / 2)return ;string ret(n, );for(int i 0; i maxCount; i) // 先处理出现次数最多的数{ret[index] mostVal;index 2;}hash[mostVal - a] 0;for(int i 0; i 26; i) // 处理剩下的数{for(int j 0; j hash[i]; j){if(index n)index 1;ret[index] i a;index 2;}}return ret;}
}; 本篇完。 此专栏暂时就不更新了常见的算法的学了一遍了先完结撒花后面再更新高阶数据结构图等内容然后更新力扣的每日一题或者更新一些牛客的题。
