遇到两次的笔试题：求连续区间
最近我就遇到两道类型相似的题，都是求连续区间的。
虽然不是啥算法题，但还是比较考验逻辑能力的，所以这篇文章来梳理一下。
下面是题目，大家可以看下有啥思路没，就当这是在面试了。
第一道
输入是 1,2,3,5,7,8,10 输出要求是 1~3 5 7~8 10
第二道
将48位的时间位图格式化成字符串
要求：写一个函数timeBitmapToRanges，将下述规则描述的时间位图转换成一个选中时间区间的数组。
规则描述：
将一天24小时按每半小划分成48段，我们用一个位图表示选中的时间区间，例如110000000000000000000000000000000000000000000000， 表示第一个半小时和第二个半小时被选中了，其余时间段都没有被选中，也就是对应00:00~01:00这个时间区间。一个位图中可能有多个不连续的 时间区间被选中，例如110010000000000000000000000000000000000000000000，表示00:00-1:00和02:00-02:30这两个时间区间被选中了。
示例输入："110010000000000000000000000000000000000000000000"
示例输出：["00:00~01:00", "02:00~02:30"]
第一道题的题解
输入是 1,2,3,5,7,8,10 输出要求是 1~3 5 7~8 10
这题明显是要求出连续区间来，然后格式化成字符串。
当 arr[i+1] 是 arr[i] + 1 的时候，那就是连续的，需要继续往下找。否则就到了区间的边界，记录下区间的起始位置就行。
我们循环一遍数组，把区间 push 到数组里
function calcContinuousRanges(arr) {
let continuousRanges = [];
let index = 0;
while(index < arr.length) {
const range = {
start: arr[index],
end: arr[index]
};
continuousRanges.push(range);
index++;
}
}
但是，如果中间有连续的数字，那区间的 end 要做一下调整：
function calcContinuousRanges(arr) {
let continuousRanges = [];
let index = 0;
while( index < arr.length) {
const range = {
start: arr[index],
end: arr[index]
};
while (index < arr.length && arr[index + 1] === arr[index] + 1) {
range.end = arr[index + 1];
index++;
}
continuousRanges.push(range);
index++;
}
console.log(JSON.stringify(continuousRanges));
}
我们先打印一下 continuousRanges：
calcContinuousRanges([1,2,3,5,7,8,10]);
连续区间是对的：
之后做下格式化就行
const formatted = continuousRanges.map(({start, end}) => {
return start === end ? start : `${start}~${end}`;
}).join(' ');
完整代码如下：
function calcContinuousRanges(arr) {
let continuousRanges = [];
let index = 0;
while( index < arr.length) {
const range = {
start: arr[index],
end: arr[index]
};
while (index < arr.length && arr[index + 1] === arr[index] + 1) {
range.end = arr[index + 1];
index++;
}
continuousRanges.push(range);
index++;
}
// console.log(JSON.stringify(continuousRanges));
const formatted = continuousRanges.map(({start, end}) => {
return start === end ? start : `${start}~${end}`;
}).join(' ');
console.log(formatted);
}
calcContinuousRanges([1,2,3,5,7,8,10]);
小结
这道题的思路就是先求出连续区间，然后格式化输出。连续区间就是判断 arr[i+1] 和 arr[i] 的关系，如果连续就 index++ 继续往下找，直到找到区间的结束
第二道题的题解
将48位的时间位图格式化成字符串 要求：写一个函数timeBitmapToRanges，将下述规则描述的时间位图转换成一个选中时间区间的数组。 规则描述： 将一天24小时按每半小划分成48段，我们用一个位图表示选中的时间区间，例如
110000000000000000000000000000000000000000000000， 表示第一个半小时和第二个半小时被选中了，其余时间段都没有被选中，也就是对应00:00~01:00这个时间区间。一个位图中可能有多个不连续的 时间区间被选中，例如110010000000000000000000000000000000000000000000，表示00:00-1:00和02:00-02:30这两个时间区间被选中了。 示例输入："110010000000000000000000000000000000000000000000"示例输出：["00:00~01:00", "02:00~02:30"]
这道题也是连续区间的题。先遍历一遍时间位图，找到所有的连续时间段的区间，然后格式化成时间的格式输出就行。
连续区间的话，如果当前位是 1 就记录下区间的开始，一直 index++ 找区间的结束，直到不为 1，就记录下一个连续区间。这样遍历完一遍就求出了所有连续区间。
格式化成时间的字符串找规律就行。
我们来写下代码。
先找连续区间，如果是 0 就 continue，如果是 1 就记录下区间的开始，然后找区间的结束，之后记录下连续区间：
function timeBitmapToRanges(timeBitmap) {
let index = 0;
let ranges = [];
while(index < timeBitmap.length) {
if (timeBitmap[index] === '0') {
index++;
continue;
}
let curRange = { start: index, end: index};
while (timeBitmap[index] === '1') {
curRange.end = index;
index++;
}
ranges.push(curRange);
}
}
测试一下，连续区间是对的：
格式化部分找规律即可。
半小时为单位，所以要乘以 0.5，然后区间的结束要多加个 0.5
ranges.map(range => {
let str = 0;
return format(range.start * 0.5) + '~' + format(range.end * 0.5 + 0.5);
});
然后格式化的实现分为小时和分钟两部分：
小时就是整数部分，个位数要补 0；
分钟是小数部分，只有 30 和 0 两种情况。
function format(num) {
const left = Math.floor(num);
const leftStr = left < 10 ? '0' + left : left;
const right = num % 1 === 0.5 ? 30 : 0;
const rightStr = right < 10 ? '0' + right : right;
return leftStr + ':' + rightStr;
}
经测试，结果是对的：
完整代码如下：
function timeBitmapToRanges(timeBitmap) {
let index = 0;
let ranges = [];
while(index < timeBitmap.length) {
if (timeBitmap[index] === '0') {
index++;
continue;
}
let curRange = { start: index, end: index};
while (timeBitmap[index] === '1') {
curRange.end = index;
index++;
}
ranges.push(curRange);
}
return ranges.map(range => {
let str = 0;
return format(range.start * 0.5) + '~' + format(range.end * 0.5 + 0.5);
});
}
function format(num) {
const left = Math.floor(num);
const leftStr = left < 10 ? '0' + left : left;
const right = num % 1 === 0.5 ? 30 : 0;
const rightStr = right < 10 ? '0' + right : right;
return leftStr + ':' + rightStr;
}
console.log(timeBitmapToRanges('110010000000000000000000000000000000000000000000'))
小结
这道题也是求连续区间再格式化输出的思路，只是连续区间是通过当前位是否为 1 来判断的，而且格式化的方式也复杂一些。
总结
连续区间的题是我最近遇到两次的笔试题，虽然变形比较多，连续区间的判断和格式化的方式都不同，但思路是一致的，都是先求出连续区间，然后格式化输出。