😇

LeetCode 2. Add Two Numbers を完全に理解する by TypeScript

2022/07/31に公開

JavaScript

Add Two Numbers by TypeScript

問題文

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

日本語 by DeepL

2つの負でない整数を表す2つの空でないリンクリストが与えられている．数字は逆順に格納されており，それぞれのノードには1桁の数字が格納されている．2つの数値を加算し、その和をリンクリストとして返せ。

このとき、2つの数値には0以外の先行する0が含まれていないと仮定してよい。

例題

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

検討

これ、素直に配列でもらえたらめちゃくちゃ簡単なのに、リンクリスト(連結リスト)という形式なのでややこしい。
どうもinputが配列だと思っていろいろやってもうまくいかない。
リンクリストというのは今回の数字と(val)と次の数字(next)を持っているやつ。
こいつをどう扱うのか……が鍵となる。
下の回答は自分で考えたものではなく、discussionにあったものを拝借。

それを自分なりに追って暗記したもの。

回答

/*
    こいつ自体を再帰関数として解くので、carryについて考える。
    carryというのは繰り上がりのことである。
    最初は繰り上がりがないので0がデフォルト引数として入っている。
  */
function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null,
  carry = 0
): ListNode | null {
  /*
    まずはListNode1と2が存在していることを確認している
  */
  if (l1 || l2) {
    /* 
      ListNodeがL1,L2のどちらかが存在しているとき
      getNextNodeで次のノードを取得している
      一度getNextNodeのコメントを読んでから戻ってくるとわかりやすい
      [2,4,3]と[5,6,4]の場合
      next1: 2の次の4
      next2: 5の次の6
      である
    */
    const next1 = getNextNode(l1);
    const next2 = getNextNode(l2);

    /* 
      getNodeValue関数(下のほうにあるよ)でNodeの値を取得している。
      [2,4,3]と[5,6,4]の場合
      val1: 2
      val2: 5
      である

      sumで合計値を出している。(2+5=7)
      L1の1個めとL2の1個めの値を足している
      carryというのは繰り上がりのこと。
      前回の計算で繰り上がりがあったときに足す。
      初回ループ時は繰り上がりがないのでcarryは0である。
    */
    const sum = getNodeValue(l1) + getNodeValue(l2) + carry;

    /* 
      次回の計算の繰り上がりを出している。
      合計値が10以上の場合は1を返す。
      たとえば7 + 8 = 15で、1を返しているということ。
      sum >= 10 なので合計値が10以上なら……で
      ?の右がtrueなので1, :の右がfalseで0を返す。
      [2,4,3]と[5,6,4]の場合、2ループ目の4と6の計算で繰り上がりが発生する。
    */
    const nextCarry = sum >= 10 ? 1 : 0;

    /*
      ここで自分を再帰的に呼び出している。
      答えはListNodeで返さないといけないので、新しくつくっている。
      これはclassなので、渡した値をもとにコンストラクタでインスタンスを作っている。
      最初の引数が今回の計算値。
      sum%10なので、5が入る。
      次の引数が次回の計算部分。
      next1, next2, nextCarryを足したものが次回である。
      その次回の足し算結果を計算するために再帰的にaddTwoNumbersを呼び出している。
      [2,4,3] + [5,6,4]の場合、
      最初の計算が2 + 5で7なので、最初の引数は7。
      次の引数は、次の計算をするために、addTwoNumbersを呼び出して
      その関数に渡すのがnext1:4, next2:6, nextCarry:0。
      2回めの計算が終わったらまたここに戻ってきて
      4 + 6 + 0で10なので、最初の引数は0で、carry1。
      next1:3, next2:4, nextCarry:1。
      3回目の計算は3 + 4 + 1で8なので、最初の引数は8。
      あとはnextがないのでnullを渡して計算終了。
      再帰呼び出しが終わる。
    */
    return new ListNode(sum % 10, addTwoNumbers(next1, next2, nextCarry));
  } else if (carry) {
    /*
      最後の計算がないけれどcarry、繰り上がりだけあったとき。
      たとえば[1,2]と[1,8]の場合
      1 + 1 = 2;
      2 + 8 = 10;で繰り上がるから0
      ここでnextがないから計算できないけどcarryがあるから1だけListNodeに入れておく
    */
    return new ListNode(1);
  }

  return null;
}

/*
  getNodeValue関数は、nodeとnode.valが存在しているときに
  node.val(現在の値)を返す。
  それ以外は0を返すという簡単な関数
*/
function getNodeValue(node: ListNode | null): number {
  return node && node.val ? node.val : 0;
}

/*
  getNextNode関数は
  nodeとnode.nextが存在しているときに
  node.nextを返す。それ以外はnullを返すという簡単な関数 */
function getNextNode(node: ListNode | null): ListNode | null {
  return node && node.next ? node.next : null;
}

ということで再帰の考え方が学べる。
わざわざgetNodeValue関数やgetNextNode関数に切り出さなくても解決できるが
個人的には見通しが良くなるので関数を切り出したほうがわかりやすい。
再帰は条件を満たさなかったときに抜ける、という部分が肝要。
その条件を忘れると容易に無限ループに至ってしまうので注意。

自分なりに解法覚えて清書してみた。

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null, carry = 0): ListNode | null {
    
    const getNextNode = (node:ListNode):ListNode | null => node && node.next ? node.next : null;
    const getCurrentNode = (node:ListNode):number | null => node && node.val ? node.val : 0;

    if(l1 || l2) {
        const nextL1 = getNextNode(l1);
        const nextL2 = getNextNode(l2);
        
        const currentL1 = getCurrentNode(l1);
        const currentL2 = getCurrentNode(l2);
        const sum = currentL1 + currentL2 + carry;
        
        const nextCarry = sum >= 10 ? 1 : 0;
        
        return new ListNode(sum % 10, addTwoNumbers(nextL1, nextL2, nextCarry));
    } else if (carry) {
        return new ListNode(1);
    }
    return null;
};

Add Two Numbers by TypeScript

問題文

日本語 by DeepL

例題

検討

回答

Discussion