泰安网站建设有哪些,甘肃路桥建设集团有限公司官方网站,如何优化网站图片,中国机械加工网19易0下6拉en题目
给定一个 无重复元素 的 有序 整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说#xff0c;nums 的每个元素都恰好被某个区间范围所覆盖#xff0c;并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b]…题目
给定一个 无重复元素 的 有序 整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说nums 的每个元素都恰好被某个区间范围所覆盖并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出
a-b 如果 a ! ba 如果 a b
示例 1
输入nums [0,1,2,4,5,7]
输出[0-2,4-5,7]
解释区间范围是
[0,2] -- 0-2
[4,5] -- 4-5
[7,7] -- 7示例 2
输入nums [0,2,3,4,6,8,9]
输出[0,2-4,6,8-9]
解释区间范围是
[0,0] -- 0
[2,4] -- 2-4
[6,6] -- 6
[8,9] -- 8-9
自己的思路
也是双指针但是在边界情况不知道如何处理。
就是怎么可以避免fast len的时候再让它减1
class Solution {
public:vectorstring summaryRanges(vectorint nums) {vectorstring vs;mapint, int mp;int low 0, fast 0;int len nums.size();while(low ! len){fast;if((fast len) || (nums[fast] ! nums[low] fast - low)){mp[nums[low]] nums[fast - 1];low fast;} }for(mapint, int::iterator it mp.begin(); it! mp.end(); it){string str;if(it-first it-second){str to_string(it-first);}else {str to_string(it-first) - to_string(it-second);}vs.push_back(str);}return vs;}
}; 看了题解之后的做法
思路
双指针。从前往后遍历low在前high在后跑如果high跑着发现它跟前面那个值相差不为1说明这个区间在这里断了。就需要把这个区间存储起来然后low更新为现在的high继续跑。直到跑到len为止。
这里使用 map 来存储区间键key存区间开始值value存区间终点。最后在输出的时候判断键值是否相等如果相等就输出该值自己如果不相等就输出该区间。
代码
class Solution {
public:vectorstring summaryRanges(vectorint nums) {vectorstring vs;mapint, int mp;int low 0, high 0;int len nums.size();int i 0;while (i len) {low i;i;while (i len nums[i] nums[i - 1] 1) { // 注意点1i;}high i - 1;mp[nums[low]] nums[high];}for(mapint, int::iterator it mp.begin(); it! mp.end(); it){string str;if(it-first it-second){str to_string(it-first);}else {str to_string(it-first) - to_string(it-second);}vs.push_back(str);}return vs;}
};
需要注意的点
1.在判断区间断点时如果用 nums[i]-nums[i-1] 1 来判断的话会发生如下情况 原因分析
因为int型可以表示的范围是-2147483648 ~ 2147483647。
这里 2147483647- (-2147483647) 肯定就溢出了
