Add Two Numbers
2つの非負整数が与えられます。それぞれの整数は、最下位の桁が先頭になるように、各桁を単方向連結リストに格納しています。1つ目のリストでは、ノード i に桁 values1[i] が格納され、ノード next1[i] につながっています。2つ目のリストも同様に、next2 と values2 を使います。どちらのリストも -1 で終端し、先頭ノードは 0 です。ノードはリストの順番どおりには格納されていないため、リンクをたどってください。
2つの整数の和の各桁を、最下位の桁から順に返してください。
関数
- next1integer-array
- 最初の数値の各ノードがリンクするノードのインデックス。最後のノードの場合は -1
- values1integer-array
- 最初の数の各ノードが保持する数字
- next2integer-array
- 2つ目の数値の各ノードがリンクするノードのインデックス。最後のノードの場合は -1
- values2integer-array
- 2つ目の数の各ノードが保持する桁
- 戻り値integer-array
- 合計の各桁を、最下位桁から順に
制約
1 ≤ L1 ≤ 100。ここで、L1はnext1およびvalues1の長さです。1 ≤ L2 ≤ 100。ここで、L2はnext2とvalues2の長さです。0 ≤ values1[i], values2[j] ≤ 9-
next1の各要素は-1または最初のリストのノードインデックスであり、next2の各要素は-1または2番目のリストのノードインデックスです。 - ノード
0から始めて、各リストはそれぞれのノードを一度ずつすべて訪れ、その後-1に到達します。サイクルはありません。 - どの数にも先頭のゼロはありません。リストが1桁の
0だけである場合を除き、リストの最後のノードには0以外の数字が格納されています。
例
- 入力
- next1 = [2, -1, 1]values1 = [8, 6, 1]next2 = [2, -1, 1]values2 = [7, 5, 2]
- 出力
- [5, 4, 1, 1]
- 説明
- 最初のリストはノード
0, 2, 1を順にたどり、8, 1, 6を読み取ります。これは数値の618です。2つ目のリストからは7, 2, 5を読み取り、数値の527になります。合計は1145なので、答えは5, 4, 1, 1です。
- 入力
- next1 = [-1]values1 = [9]next2 = [3, 2, -1, 1]values2 = [1, 9, 9, 9]
- 出力
- [0, 0, 0, 0, 1]
- 説明
- 2つ目のリストは
1, 9, 9, 9と読み、数値は9991です。9を足すと10000になります。各桁で0と繰り上がりが生じ、最後の繰り上がりが5桁目になります。
- 入力
- next1 = [-1]values1 = [0]next2 = [1, -1]values2 = [7, 5]
- 出力
- [7, 5]
- 説明
- 最初の数は0で、2番目のリストは
7, 5、つまり数値57です。0を足しても何も変わらないので、答えは[7, 5]です。
発展問題
リストに最上位桁が先に格納されている場合、どのようにして数値を足しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
各リストを数値に変換する方法はうまくいきません。100桁の数はどの整数型にも収まりません。紙の上で2つの大きな数をどう足しますか？
リストは一の位から始まります。これは、筆算の足し算が始まる位置とまったく同じです。各桁では、それぞれの数から1桁ずつ取り出し、前の桁からの繰り上がりを加算します。その桁には
sum % 10を書き、sum / 10を切り捨てて繰り上げます。それぞれのリストにポインターを1つずつ使い、両方のリストを同時にたどります。最後までたどり終えたリストには
0を加えます。どちらかのポインターが-1でないか、繰り上がりが1である間は処理を続け、最後の繰り上がりももう1桁として扱います。
解説
数値がどの整数型にも収まらないほど長いため、筆算のように桁ごとに足し、桁の合計が10に達したら1を繰り上げます。リストは1の位を先頭に格納しているため、リストをたどると足し合わせる順に各桁を訪れます。
数字を書き出してから、列ごとに足します。
考え方
ここでポインターはノードのインデックスで、前に進む操作は node = next[node] です。各リストの桁を配列にコピーし、インデックス i が 10^i の位の数字を保持するようにします。最初の例では [8, 1, 6] と [7, 2, 5] です。
次に、筆算のように足し、欠けている桁は 0 として数えます。各桁では sum % 10 を書き、残りを繰り上げます。8 + 7 = 15 では 5 を書いて 1 を繰り上げ、1 + 2 + 1 = 4、そして 6 + 5 = 11 では 1 を書きます。最後の繰り上がりは最終桁になります。[5, 4, 1, 1]。
コピーには、加算では必要のない追加メモリ O(L1 + L2) がかかります。
アルゴリズム
- 各リストをノード
0からたどり、各桁を配列にコピーします。 carry = 0に設定します。長い方の配列の長さまで、各インデックスiについて、存在するi番目の桁と carry を加算します。sum % 10を追加し、carryをsum / 10を切り捨てた値に設定します。- 最後の列の後に carry が
1なら、それを追加します。
def readDigits(next, values):
# The digits in list order: least significant first.
digits = []
node = 0
while node != -1:
digits.append(values[node])
node = next[node]
return digits
def addTwoNumbers(next1, values1, next2, values2):
first = readDigits(next1, values1)
second = readDigits(next2, values2)
result = []
carry = 0
for i in range(max(len(first), len(second))):
column = carry
if i < len(first):
column += first[i]
if i < len(second):
column += second[i]
result.append(column % 10)
carry = column // 10
if carry > 0:
result.append(carry)
return result繰り上がりを使って、両方のリストを同時にたどる
考え方
列 i では各リストの i 番目のノードだけを使うので、リストごとにポインター a と b を1つずつ保持し、列が進むにつれて両方を進めます。
a が -1 ではない、または b が -1 ではない、または繰り上がりが 1 である間、1つのループを実行します。ノードが残っているポインターはその桁を加えて先に進み、-1 を指しているポインターは何も加えません。これにより、2つ目のループを使わずに桁数の異なる数を処理でき、繰り上がりの条件によって最後に余分な桁を書き込みます。
2つ目の例では、9 と 9991 の各列の合計が 10 となり、0 を書き込みます。4列目まで処理すると両方のリストが終わりますが、繰り上がりが 1 なので、ループはもう1回実行されます。結果は [0, 0, 0, 0, 1] です。答えを除くと、保持するのは整数3つです。
アルゴリズム
a = 0、b = 0、carry = 0に設定します。a != -1またはb != -1またはcarry > 0である間、桁の合計をcarryから始めます。a != -1の場合、values1[a]を加算し、a = next1[a]に設定します。2つ目のリストについても、bで同じことをします。sum % 10を追加し、carryをsum / 10を切り捨てた値に設定します。- 追加した桁を返します。
def addTwoNumbers(next1, values1, next2, values2):
a = 0 # current node of the first number
b = 0 # current node of the second number
carry = 0
result = []
# Keep going while either number has digits left or a carry is waiting.
while a != -1 or b != -1 or carry > 0:
column = carry
if a != -1:
column += values1[a]
a = next1[a]
if b != -1:
column += values2[b]
b = next2[b]
result.append(column % 10) # the digit this column writes
carry = column // 10 # 1 when the column reached 10, else 0
return result
落とし穴と境界ケース
- 各リストを整数に変換して足すこと。100桁の数は、どの64ビット型でもオーバーフローします。
- 最後の繰り上がりを捨てること。両方のリストが終わった時点で停止するループでは、2つ目の例で
[0, 0, 0, 0]が返されます。 - 短い方のリストが終わった時点で停止すること。すると2つ目の例では、9991の3つの9と、それらを通って進む繰り上がりが失われます。
- 配列の順序で桁を読むこと。1つ目の例では、
values1は[8, 6, 1]ですが、リンクをたどって読む数は618です。 - 配列のインデックスが1から始まるLuaとRで、オフセットを忘れること。ノードIDは0始まりのままにして、
next1[node + 1]を読み取ってください。
よくある質問3
「2 つの数の加算」では、なぜ数字は逆順に格納されているのですか？
加算は1の位から始まり、単方向連結リストは先頭からしかたどれません。最下位桁を先頭にすると、たどる順序が加算する桁の順序と一致するため、繰り上がりはポインターとともに前へ進みます。
連結リストに格納された2つの数値を加算する場合の時間計算量はどれくらいですか？
O(max(L1, L2))です。各桁につき1ステップで、最後に繰り上がりが残っている場合はさらに1ステップです。答えを除けば、1回の走査で処理するバージョンが使うメモリはO(1)です。2つのポインターと繰り上がりだけです。
桁上がりが1より大きくなることはありますか？
いいえ。1つの桁では、最大9の数字2つと最大1の繰り上がりを足すため、合計は最大19です。10で割って切り捨てると、0または1になります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def addTwoNumbers(next1, values1, next2, values2):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
next1 = [2, -1, 1] values1 = [8, 6, 1] next2 = [2, -1, 1] values2 = [7, 5, 2]
期待される出力
[5, 4, 1, 1]