遇到两次的笔试题：求连续区间

最近除了准备华为面试外，两次也在面其他公司，试题每一轮面试都会有几道笔试题。求连这些笔试题里面难免有类型相似的续区。

最近我就遇到两道类型相似的两次题，都是试题求连续区间的。

虽然不是求连啥算法题，但还是续区比较考验逻辑能力的，所以这篇文章来梳理一下。两次

下面是试题题目，大家可以看下有啥思路没，求连就当这是续区在面试了??。

第一道

输入是两次 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 来判断的，而且格式化的方式也复杂一些。

总结

连续区间的题是我最近遇到两次的笔试题，虽然变形比较多，连续区间的判断和格式化的方式都不同，但思路是一致的，都是先求出连续区间，然后格式化输出。