起因

最近面試web全棧開發工程師崗位，接觸到一個算法題，覺得很考驗分析能力並且在實際中是有一定作用的算法，因此分享出來跟大家探討。

題目

根據運營需求，你要為我們的數值發佈系統增加一項數字輸入框校驗功能。我們通常會對一些數字輸入進行大小限制。
比如要求輸入的值必須在300 - 347之間（包括300和347）。聰明的你發現，有時你可以不必等用户輸入完就知道他的輸入是否非法的了。
比如，上面這種情況，當用户輸入37時，肯定他的輸入就是非法的了。

現在你需要用程序來做這件事。
輸入：
第一行為輸入框的下界
第二行為輸入框的上界
第三行為一些用逗號分割的整數，這些整數作為用户輸入的數字
輸出：
僅有一行，為一些用逗號分割的字符串。
每個字符串對應一個用户輸入的數字，如果用户輸入為非法則輸出INVALID，否則輸出VALID

輸入約束
上下界均位於[1, 2000000000]之間，且下界小於等於上界，第三行的數字個數位於[1, 50]之間，且每個數字也位於[1, 2000000000]之間

舉例1：
輸入
300
347
37
輸出
INVALID

舉例2：
輸入
310
320
3,31,317,3174,310,320
輸出
VALID,VALID,VALID,INVALID,VALID,VALID
解釋：前3個是輸入317時的順序輸入，所以都是合法的。最後2個時上界和下界，也是合法的

題目分析

1. 輸入大於上限直接返回INVALID
2. 輸入在下限和上限之間，直接返回VALID

3. 只有輸入小於下限的情況，才會產生校驗，因此代碼重點在於這一步

   • 上限和下限數字位數相差1位以上，比如下限31是兩位數, 上限7001是四位數，因為輸入是小於下限31的，又因為上下限中間可以包含全部的三位數字，三位數字都是符合條件的，因此直接返回VALID
   • 上限和下限數字位數相等的情況，只需要把上下限數字縮短到和輸入數字一樣的長度（從右邊去除），這時輸入必須在縮短後的上下限之間，才能返回VALID，否則你在輸入之後無論怎麼補充數字都無法保證在上下限之間。

   • 上限和下限數字位數正好相差1位的情況

     • 下限首位小於上限首位，比如下限50，上限618，又因為輸入小於50，因此你在輸入後面隨便加一位都大於50小於618，直接返回VALID
     • 下限首位大於等於上限首位，同樣把上下限數字縮短到和輸入數字一樣的長度（從右邊去除），這時候你必須保證輸入大於等於縮短後的下限，或者小於等於縮短後的上限（此時縮短後的下限 > 縮短後的上限），才能返回VALID，否則你在輸入後再次添加任何數字都是不合法的
4. 其他情況，一律返回INVALID

代碼實現

const readline = require('readline');
const rl = readline.createInterface(process.stdin, process.stdout);
let min = 0;
let minLen = 0;
let max = 0;
let maxLen = 0;
let strArr = null;
let outputArr = [];
let index = 0;
rl.on('line', function(line) {
    if (index === 0) {
      min = parseInt(line);
      if (min < 1 || min > 12000000000) {
        console.log('輸入有誤!');
        rl.close();
      }
      minLen = line.length;
    }
    if (index === 1) {
      max = parseInt(line);
      if (max < 1 || max > 12000000000) {
        console.log('輸入有誤!');
        rl.close();
      }
      if (min > max){
        console.log('上界不能小於下界!');
        rl.close();
      }
      maxLen = line.length;
    }

    if (index === 2) {
      strArr = line.split(',');
      const len = strArr.length;
      if (len < 1 || len > 50) {
        console.log('輸入有誤!');
        rl.close();
      }

      for (const str of strArr) {
        const num = parseInt(str);
        if (num < 1 || num > 12000000000) {
          console.log('輸入有誤!');
          rl.close();
        }
        // 大於上限直接返回INVALID
        if (num > max) {
          outputArr.push('INVALID');
          continue;
        }
        // 大於等於下限且小於等於上限直接返回VALID
        if (num <= max && num >= min) {
          outputArr.push('VALID');
          continue;
        }
        // 小於下限的情況

        // 上下限位數相差1以上，直接返回VALID
        if (maxLen - minLen > 1) {
          outputArr.push('VALID');
          continue;
        }
        // 上下限位數相等的情況，即maxLen = minLen;
        const len = str.length;
        const offsetMin = String(min).slice(0, len);
        const offsetMax = String(max).slice(0, len);
        if (maxLen === minLen && str >= offsetMin && str <= offsetMax) {
          outputArr.push('VALID');
          continue;
        }
        // 上下限位數相差1位的情況
        if (maxLen - minLen === 1) {
          // 下限首位小於上限首位
          if (String(min)[0] < String(max)[0]) {
            outputArr.push('VALID');
            continue;
          }
          // 下限首位大於等於上限首位
          if (str >= offsetMin || str <= offsetMax ){
            outputArr.push('VALID');
            continue;
          }
        }
        
        // 其他情況
        outputArr.push('INVALID');
      }
      console.log(outputArr.join(','));
      rl.close();
    }
    index++;
}).on('close',function(){
    // It's important to exit, otherwise the execution will time out
    process.exit(0);
});

總結

此代碼跑通了測試端全部測試用例並且沒有超出響應時間限制，各位同學可以做個參考，也歡迎有其他更好思路的朋友留言分享。