JavaScript：LeetCode'PlusOne'遞回超時問題-有解無憂

加一-leetcode問題

問題：

給定一個表示為整數陣列digits 的大整數，其中每個digits[i] 是整數的第i 個數字。數字按從左到右的順序從最高有效到最低有效排序。大整數不包含任何前導 0。

將大整數加一并回傳結果數字陣列。

示例 1：

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123   1 = 124.
Thus, the result should be [1,2,4].

示例 2：

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9   1 = 10.
Thus, the result should be [1,0].

約束：

1 <= 數字.長度 <= 100
0 <= 數字[i] <= 9
數字不包含任何前導 0。

我的解決方案：

// [9] becomes [1,0]
var plusOne = function(digits) {
    let len = digits.length;
    //count array backwards
    for(let i = len-1; i >= 0; i--) {
        // if the currently indexed value is 9, we will zero it (line 14)
        // we will also check if the previous entry is 9 via recursion (line 19)
        // if it is not 9, we increment it by 1 and return 'digits' (lines 22, 23)
        // if there is no previous entry we prepend one and return 'digits' (lines 16, 17)
        if(digits[i] == 9) {
            digits[i] = 0;
            if(!digits[i - 1]){
                digits.unshift(1);
                return digits;
            } else {
                plusOne(digits.slice(0, i-1));
            }
        } else {
            digits[i] = digits[i]   1;
            return digits;
        }
    }
};

let array = [9,9,9];

console.log(plusOne(array));

// This code breaks on input:
// [9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]

這個問題的困難在于 9，它自然會增加其更重要的鄰居的位置值。

我用遞回解決了這個問題。（您可以在代碼注釋中閱讀）。

問題是我在以下輸入的 Leetcode 上收到“超出時間限制”錯誤：

[9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9].

盡管它似乎通過了所有其他測驗用例。

這是堆疊大小問題嗎？有沒有辦法優化上述代碼的空間復雜度？

非常感謝。

我不知道如何降低問題的時間/空間復雜性，因為我是遞回新手。

uj5u.com熱心網友回復：

“有沒有辦法優化上述代碼的空間復雜度？”

是的，洗掉不必要的遞回呼叫。它什么也不做：

// [9] becomes [1,0]
var plusOne = function(digits) {
    let len = digits.length;
    //count array backwards
    for(let i = len-1; i >= 0; i--) {
        // if the currently indexed value is 9, we will zero it (line 14)
        // we will also check if the previous entry is 9 via recursion (line 19)
        // if it is not 9, we increment it by 1 and return 'digits' (lines 22, 23)
        // if there is no previous entry we prepend one and return 'digits' (lines 16, 17)
        if(digits[i] == 9) {
            digits[i] = 0;
            if(i === 0){
                digits.unshift(1);
                return digits;
            }
        } else {
            digits[i] = digits[i]   1;
            return digits;
        }
    }
};

let array = [9,9,9];

console.log(plusOne(array));

uj5u.com熱心網友回復：

無需遍歷整個輸入。只要沒有進位到下一位小數，該功能就可以停止。

var plusOne = function(digits) {
  // a single digit add that returns [sum, carry]
  const incr = num => num === 9 ? [0, 1] : [num   1, 0];
  // reverse the input so we can go least significant to most
  const reversed = digits.reverse();
  let index = 0,
    carry = 0,
    sum = 0;

  // increment digits, stopping as soon as there's no carry
  // worst case is a run through a lot of 9s  
  do {
    [sum, carry] = incr(reversed[index]);
    reversed[index] = sum;
  } while (carry &&   index < reversed.length)

  // push a 1 if we got to the most significant digit with a carry
  if (carry) reversed.push(1);
  return reversed.reverse();
}

// here it is running pretty fast on 10x the largest input
let lottaNines = Array(1000).fill(9);
console.log(plusOne(lottaNines))

uj5u.com熱心網友回復：

你可以這樣做：

const plusOne = arr =>
  {
  let 
    rem = 1
  , res = []
    ;
  for (let i=arr.length-1; i >= 0; i--)
    {
    res[i] = arr[i]   rem;
    rem    = res[i] > 9 ? 1 : 0;
    if (rem)
      res[i] = 0;
    }
  if (rem )
    res.unshift(1);
  return res;
  }

console.log( JSON.stringify(plusOne([1,2,3])))
console.log( JSON.stringify(plusOne([9])))
 
const outOfMaxInteger =[9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]

console.log( JSON.stringify(plusOne(outOfMaxInteger)))

事實上，這相當于增加了一個學校：

const arrAdd= (arrA,arrB) =>
  {
  let 
    iA = arrA.length -1
  , iB = arrB.length -1
  , res = []
  , rem = 0
    ;
  for (let i = 1   Math.max(iA,iB); i--; iA--,iB--)
    {
    res[i]  = rem   (iA<0?0:arrA[iA])   (iB<0 ? 0:arrB[iB]);
    rem     = 0 | (res[i] / 10);
    res[i] %= 10;
    }
  if (rem) res.unshift(rem);
  return res;
  }

console.log( '  [1,2,3]     [1] =', JSON.stringify(arrAdd(   [1,2,3],  [1])))
console.log( '[1,2,3,0]   [8,0] =', JSON.stringify(arrAdd( [1,2,3,0],[8,0])))
console.log( '  [1,9,3]     [8] =', JSON.stringify(arrAdd(   [1,9,3],  [8])))
console.log( '      [9]     [9] =', JSON.stringify(arrAdd(       [9],  [9])))

轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/527154.html

標籤：javascript递归

上一篇：使用遞回找出所有可能的笛卡爾積

下一篇：嘗試撰寫記憶裝飾器時出現遞回錯誤