[TOC]

フロントエンドとアルゴリズムleetcode 66.プラス1

タイトルの説明

整数からなる非空配列で表される非負の整数を与え、その数に1を加える.
最上位の数値は配列の先頭に格納され、配列内の各要素には単一の数値のみが格納されます.
整数0を除いて、この整数はゼロで始まると仮定できます.
例1:

  : [1,2,3]
  : [1,2,4]
  :          123。

例2:

  : [4,3,2,1]
  : [4,3,2,2]
  :          4321。

66.プラス1

概要

キャリーの場合を考慮して、空の配列を新規作成します.長さは入力配列の長さ+1で、最初のビット+1にこの配列を返します.

ヒント

解析

解法一

問題の意味はただ1を加えるだけで、これはその情況が2種類しかないことを意味して、末位は9あるいは9ではありません
最下位が9の場合に1桁加算する場合は0となり、キャリー演算が発生しない場合はループを終了します
特殊な場合99999999などを考慮して、配列を手動で作成して0に記入します.

解法二

後ろから順番に数ごとに1を足して、1をプラスして10をプラスして余りを取って、配列の頭部までの時i===0配列の頭部に1位を加えるだけでいいです

アルゴリズム#アルゴリズム#

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
  for (let i = digits.length - 1; i >= 0; i--) {
    digits[i]++
    digits[i] = digits[i] % 10
    if (digits[i] !== 0) return digits
  }
  digits = new Array(digits.length + 1)
  for (let i = 1; i < digits.length; i++) {
    digits[i] = 0
  }
  digits[0] = 1
  return digits
  //   2
  // for (let i = digits.length - 1; i >= 0; i--) {
  //   digits[i]++
  //   if (digits[i] >= 10) {
  //     digits[i] = digits[i] % 10
  //     if (i === 0) {
  //       digits.unshift(1)
  //       break
  //     }
  //   } else {
  //     break
  //   }
  // }
  // return digits
};

[1,2,3]に転送された実行結果

[1,2,4]

実行結果

     :44 ms,     javascript       100.00%    
     :33.7 MB,     javascript       33.81%