[[432661]]

最近除了準(zhǔn)備華為面試外，也在面其他公司，每一輪面試都會(huì)有幾道筆試題。這些筆試題里面難免有類(lèi)型相似的。

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

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

下面是題目，大家可以看下有啥思路沒(méi)，就當(dāng)這是在面試了??。

第一道

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

第二道

將48位的時(shí)間位圖格式化成字符串

要求：寫(xiě)一個(gè)函數(shù)timeBitmapToRanges，將下述規(guī)則描述的時(shí)間位圖轉(zhuǎn)換成一個(gè)選中時(shí)間區(qū)間的數(shù)組。

規(guī)則描述：

將一天24小時(shí)按每半小劃分成48段，我們用一個(gè)位圖表示選中的時(shí)間區(qū)間，例如110000000000000000000000000000000000000000000000， 表示第一個(gè)半小時(shí)和第二個(gè)半小時(shí)被選中了，其余時(shí)間段都沒(méi)有被選中，也就是對(duì)應(yīng)00:00~01:00這個(gè)時(shí)間區(qū)間。一個(gè)位圖中可能有多個(gè)不連續(xù)的 時(shí)間區(qū)間被選中，例如110010000000000000000000000000000000000000000000，表示00:00-1:00和02:00-02:30這兩個(gè)時(shí)間區(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ū)間來(lái)，然后格式化成字符串。

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

我們循環(huán)一遍數(shù)組，把區(qū)間 push 到數(shù)組里

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ù)的數(shù)字，那區(qū)間的 end 要做一下調(diào)整：

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ū)間是對(duì)的：

之后做下格式化就行

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

小結(jié)

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

第二道題的題解

將48位的時(shí)間位圖格式化成字符串

要求：寫(xiě)一個(gè)函數(shù)timeBitmapToRanges，將下述規(guī)則描述的時(shí)間位圖轉(zhuǎn)換成一個(gè)選中時(shí)間區(qū)間的數(shù)組。

規(guī)則描述：

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

示例輸入："110010000000000000000000000000000000000000000000"

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

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

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

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

我們來(lái)寫(xiě)下代碼。

先找連續(xù)區(qū)間，如果是 0 就 continue，如果是 1 就記錄下區(qū)間的開(kāi)始，然后找區(qū)間的結(jié)束，之后記錄下連續(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); 
    } 
} 

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

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

半小時(shí)為單位，所以要乘以 0.5，然后區(qū)間的結(jié)束要多加個(gè) 0.5

ranges.map(range => { 
    let str = 0; 
    return format(range.start * 0.5) + '~' + format(range.end * 0.5 + 0.5); 
}); 

然后格式化的實(shí)現(xiàn)分為小時(shí)和分鐘兩部分：

小時(shí)就是整數(shù)部分，個(gè)位數(shù)要補(bǔ) 0;

分鐘是小數(shù)部分，只有 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; 
} 

經(jīng)測(cè)試，結(jié)果是對(duì)的：

完整代碼如下：

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')) 

小結(jié)

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

總結(jié)

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