高校网站建设前景,做贷款在那些网站找客户,wordpress编辑器增强代码,一个域名做两个网站可以么1无重叠区间
给定一个区间的集合 intervals #xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量#xff0c;使剩余区间互不重叠 。 示例 1:
输入: intervals [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后#xff0c;剩下的区间没有…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
解释: 你不需要移除任何区间因为它们已经是无重叠的了。提示:
1 intervals.length 105intervals[i].length 2-5 * 104 starti endi 5 * 104
思路 按照区间的结束位置进行排序 首先对给定的区间集合按照结束位置进行排序。这样做的目的是我们希望尽量保留结束位置较早的区间这样可以为后面的区间留下更多的空间。 遍历排序后的区间集合 从第二个区间开始遍历排序后的区间集合。初始化一个计数器用于记录需要移除的区间数量初始值为0。 检查是否存在重叠 对于当前遍历到的区间与前一个区间比较。如果当前区间的起始位置小于前一个区间的结束位置说明存在重叠。在这种情况下将计数器加1并且选择保留结束位置较早的区间因为它可以为后面的区间留下更多的空间。 当确定区间 1 和 区间2 重叠后如何确定是否与 区间3 也重贴呢 就是取 区间1 和 区间2 右边界的最小值因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分如果这个最小值也触达到区间3那么说明 区间 123都是重合的。 返回移除的区间数量 最后返回计数器的值即为需要移除的区间数量。
代码
class Solution {
public:// 自定义比较函数按照区间起始位置从小到大排序static bool cmp(const vectorint a, const vectorint b) {return a[0] b[0];}// 求解无重叠区间的最大数量int eraseOverlapIntervals(vectorvectorint intervals) {// 若区间数量为0返回0if (intervals.size() 0) return 0;// 按照区间起始位置排序sort(intervals.begin(), intervals.end(), cmp);int count 0; // 记录重叠区间数量// 遍历区间数组for (int i 1; i intervals.size(); i) {// 若当前区间起始位置小于前一个区间的结束位置说明存在重叠if (intervals[i][0] intervals[i - 1][1]) {count; // 计数加1// 更新当前区间的结束位置为前一个区间结束位置与当前区间结束位置的最小值intervals[i][1] min(intervals[i - 1][1], intervals[i][1]);}}return count; // 返回重叠区间数量}
};
2划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。
注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。 示例 1
输入s ababcbacadefegdehijhklij
输出[9,7,8]
解释
划分结果为 ababcbaca、defegde、hijhklij 。
每个字母最多出现在一个片段中。
像 ababcbacadefegde, hijhklij 这样的划分是错误的因为划分的片段数较少。
示例 2
输入s eccbbbbdec
输出[10]提示
1 s.length 500s 仅由小写英文字母组成
思路
在遍历的过程中相当于是要找每一个字母的边界如果找到之前遍历过的所有字母的最远边界说明这个边界就是分割点了。此时前面出现过所有字母最远也就到这个边界了。
可以分为如下两步
统计每一个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点
具体过程
创建一个大小为27的数组 hash用于记录每个字母在字符串中最后出现的位置。第一个 for 循环遍历字符串 S记录每个字符的最后出现位置。创建一个存储结果的向量 result。定义区间的左边界 left 和右边界 right初始都为0。第二个 for 循环再次遍历字符串 S。right max(right, hash[S[i] - a]) 找到字符出现的最远边界。如果当前遍历的位置 i 与右边界相等说明当前位置是一个片段的结束位置记录当前片段的长度。更新下一个片段的左边界为 i 1。返回结果。
代码
class Solution {
public:vectorint partitionLabels(string S) {int hash[27] {0}; // 创建一个大小为27的数组hash用于记录每个字母在字符串中最后出现的位置for (int i 0; i S.size(); i) { // 遍历字符串Shash[S[i] - a] i; // 记录字符 S[i] 出现的最后位置}vectorint result; // 创建一个存储结果的向量int left 0; // 定义区间的左边界int right 0; // 定义区间的右边界for (int i 0; i S.size(); i) { // 再次遍历字符串Sright max(right, hash[S[i] - a]); // 找到字符出现的最远边界if (i right) { // 如果当前遍历的位置i与右边界相等说明当前位置是一个片段的结束位置result.push_back(right - left 1); // 记录当前片段的长度left i 1; // 更新下一个片段的左边界}}return result; // 返回结果}
};
3 合并区间
以数组 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 104intervals[i].length 20 starti endi 104
思路 排序 首先将输入的区间集合按照区间的左边界进行升序排序。这样排序后相邻的区间如果有重叠它们一定会相邻。 合并重叠区间 从排好序的区间集合中逐个考察每个区间。如果当前区间与结果集合中最后一个区间有重叠即当前区间的左边界小于等于结果集合中最后一个区间的右边界则将当前区间合并到结果集合中最后一个区间中更新最后一个区间的右边界为两者的最大值如果当前区间与结果集合中最后一个区间没有重叠则将当前区间直接加入结果集合中。 返回结果 最后返回合并后的结果集合
代码
class Solution {
public:// 定义一个静态函数作为比较函数用于排序static bool cmp(const vectorint a, const vectorint b) {return a[0] b[0]; // 按照区间的左边界进行升序排序}vectorvectorint merge(vectorvectorint intervals) {vectorvectorint result;if (intervals.empty()) return result; // 如果区间集合为空直接返回空结果// 使用cmp函数对区间进行排序sort(intervals.begin(), intervals.end(), cmp);// 第一个区间直接放入结果集合中result.push_back(intervals[0]); for (int i 1; i intervals.size(); i) {if (result.back()[1] intervals[i][0]) { // 发现重叠区间// 合并区间只需要更新结果集合中最后一个区间的右边界result.back()[1] max(result.back()[1], intervals[i][1]); } else {result.push_back(intervals[i]); // 区间不重叠将当前区间加入结果集合}}return result;}
};
4单调递增的数字
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时我们称这个整数是单调递增的。
给定一个整数 n 返回 小于或等于 n 的最大数字且数字呈 单调递增 。 示例 1:
输入: n 10
输出: 9示例 2:
输入: n 1234
输出: 1234示例 3:
输入: n 332
输出: 299
思路 将数字转换为字符串 首先将输入的数字 N 转换为字符串以便进行逐位操作。 从右向左遍历找到第一个不满足单调递增的位置 从数字的最右侧开始逐位比较当前位与前一位的大小。如果发现当前位比前一位小则将前一位减1并将标记 flag 设置为当前位的位置。 将 flag 位置后的所有数字都变为9 从标记位置 flag 开始将该位置及其后面的所有数字都变为9以确保最终结果是最大的且满足单调递增。 将字符串转换回数字并返回 最后将修改后的字符串转换为数字并返回结果。
举个例子数字332从前向后遍历的话那么就把变成了329此时2又小于了第一位的3了真正的结果应该是299。
那么从后向前遍历就可以重复利用上次比较得出的结果了从后向前遍历332的数值变化为332 - 329 - 299
代码
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]--; // 将当前位减1}}for (int i flag; i strNum.size(); i) {strNum[i] 9; // 从flag位置开始将后面所有位都变为9}return stoi(strNum);}
};
