備忘録 LeetCode-2. Add Two Numbers #初心者

はじめに

この記事はアルゴリズム振り返り用メモ，
言語化練習用に作成した記事です．

URL

対象者

・初心者

code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* node = new ListNode(-1);
        ListNode* copy = node;
        
        //商を入れる用
        int curry = 0;
      
        while(l1 || l2 || curry){
            //作成 & 更新
            copy->next = new ListNode(-1);
            copy = copy->next;
            
            //前回の商で初期値にする
            int n = curry;
            //値があるnodeと計算
            if(l1 != nullptr)n += (l1->val);
            if(l2 != nullptr)n += (l2->val);

            //余剰を入れる
            copy->val = (n) % 10;
            //商の更新
            curry = (n) / 10;
            
            //今,値がある場合更新する
            if(l1)l1 = l1->next;
            if(l2)l2 = l2->next;
        }
        return node->next;
    }
};

結果

Runtime: 75 ms, faster than 20.05% of C++ online submissions for Add Two Numbers.
Memory Usage: 71.5 MB, less than 51.04% of C++ online submissions for Add Two Numbers.

詳細

画像の結果では答えは 7 0 8　になる

手順

1, l1,l2,前回の商がある場合ループをする
2, l1,l2どちらかの値がある場合nodeを新しく作る
3, 値のある位と前回の商で計算する
4, 計算した物の余剰をnodeに入れる
5, 商を更新する
6, l1,l2　値がある場合はnextに更新する

画像と手順を合わせると

1週目

1, l1,l2,前回の商があるのでループをする
2, l1,l2どちらも値があるのでnodeを新しく作る
3, l1,l2の一の位である 2 と 5 を計算して 7 を出す
4, nodeに7の余剰である7を入れる
5, 7の商は0なので0を次回に持ち越す
6, l1,l2どちらも値があるので更新する

2週目

1, l1,l2,前回の商があるのでループをする
2, l1,l2どちらも値があるのでnodeを新しく作る
3, l1,l2の十の位である 4 と 6 を計算して 10 を出す
4, nodeに 10 の余剰である 1 を入れる
5, 10 の商は 1 なので 1 を次回に持ち越す
6, l1,l2どちらも値があるので更新する

3週目

1, l1,l2 前回の商があるのでループをする
2, l1,l2 どちらも値があるのでnodeを新しく作る
3, l1,l2 の百の位である 3 と 4 を計算して 7 を出す
4, nodeに 7 の余剰である 7 と前回の余剰である 1 を計算して 8 を入れる
5, 8 の商は 0 なので 0 を次回に持ち越す
6, l1,l2 どちらも値があるので更新する

4週目

1, l1,l2,前回の商,すべて無いのでループしない

参照

分かりやすく説明してくださっている方の動画URL
youtube

おわりに

今回は約15分程度で解けたので次回以降もこの調子で解いていきたいです．