[[432661]]

最近除了準備華為面試外，也在面其他公司，每一輪面試都會有幾道筆試題。這些筆試題里面難免有類型相似的。

最近我就遇到兩道類型相似的題，都是求連續(xù)區(qū)間的。

雖然不是啥算法題，但還是比較考驗邏輯能力的，所以這篇文章來梳理一下。

下面是題目，大家可以看下有啥思路沒，就當這是在面試了??。

第一道

輸入是 1,2,3,5,7,8,10 輸出要求是 1~3 5 7~8 10

第二道

將48位的時間位圖格式化成字符串

要求：寫一個函數timeBitmapToRanges，將下述規(guī)則描述的時間位圖轉換成一個選中時間區(qū)間的數組。

規(guī)則描述：

將一天24小時按每半小劃分成48段，我們用一個位圖表示選中的時間區(qū)間，例如110000000000000000000000000000000000000000000000， 表示第一個半小時和第二個半小時被選中了，其余時間段都沒有被選中，也就是對應00:00~01:00這個時間區(qū)間。一個位圖中可能有多個不連續(xù)的 時間區(qū)間被選中，例如110010000000000000000000000000000000000000000000，表示00:00-1:00和02:00-02:30這兩個時間區(qū)間被選中了。

示例輸入："110010000000000000000000000000000000000000000000"

示例輸出：["00:00~01:00", "02:00~02:30"]

第一道題的題解

輸入是 1,2,3,5,7,8,10 輸出要求是 1~3 5 7~8 10

這題明顯是要求出連續(xù)區(qū)間來，然后格式化成字符串。

當 arr[i+1] 是 arr[i] + 1 的時候，那就是連續(xù)的，需要繼續(xù)往下找。否則就到了區(qū)間的邊界，記錄下區(qū)間的起始位置就行。

我們循環(huán)一遍數組，把區(qū)間 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++; 
    } 
} 

但是，如果中間有連續(xù)的數字，那區(qū)間的 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]); 

連續(xù)區(qū)間是對的：

之后做下格式化就行

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]); 

小結

這道題的思路就是先求出連續(xù)區(qū)間，然后格式化輸出。連續(xù)區(qū)間就是判斷 arr[i+1] 和 arr[i] 的關系，如果連續(xù)就 index++ 繼續(xù)往下找，直到找到區(qū)間的結束

第二道題的題解

將48位的時間位圖格式化成字符串

要求：寫一個函數timeBitmapToRanges，將下述規(guī)則描述的時間位圖轉換成一個選中時間區(qū)間的數組。

規(guī)則描述：

將一天24小時按每半小劃分成48段，我們用一個位圖表示選中的時間區(qū)間，例如110000000000000000000000000000000000000000000000， 表示第一個半小時和第二個半小時被選中了，其余時間段都沒有被選中，也就是對應00:00~01:00這個時間區(qū)間。一個位圖中可能有多個不連續(xù)的 時間區(qū)間被選中，例如110010000000000000000000000000000000000000000000，表示00:00-1:00和02:00-02:30這兩個時間區(qū)間被選中了。

示例輸入："110010000000000000000000000000000000000000000000"

示例輸出：["00:00~01:00", "02:00~02:30"]

這道題也是連續(xù)區(qū)間的題。先遍歷一遍時間位圖，找到所有的連續(xù)時間段的區(qū)間，然后格式化成時間的格式輸出就行。

連續(xù)區(qū)間的話，如果當前位是 1 就記錄下區(qū)間的開始，一直 index++ 找區(qū)間的結束，直到不為 1，就記錄下一個連續(xù)區(qū)間。這樣遍歷完一遍就求出了所有連續(xù)區(qū)間。

格式化成時間的字符串找規(guī)律就行。

我們來寫下代碼。

先找連續(xù)區(qū)間，如果是 0 就 continue，如果是 1 就記錄下區(qū)間的開始，然后找區(qū)間的結束，之后記錄下連續(xù)區(qū)間：

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); 
    } 
} 

測試一下，連續(xù)區(qū)間是對的：

格式化部分找規(guī)律即可。

半小時為單位，所以要乘以 0.5，然后區(qū)間的結束要多加個 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')) 

小結

這道題也是求連續(xù)區(qū)間再格式化輸出的思路，只是連續(xù)區(qū)間是通過當前位是否為 1 來判斷的，而且格式化的方式也復雜一些。

總結

 

連續(xù)區(qū)間的題是我最近遇到兩次的筆試題，雖然變形比較多，連續(xù)區(qū)間的判斷和格式化的方式都不同，但思路是一致的，都是先求出連續(xù)區(qū)間，然后格式化輸出。