Let's challenge LeetCode!! _3

こんにちは
今回は初めて medium にチャレンジしてみました。

******
time stamp
2020 12/16 :Add Q2
2020 12/22 :Add Q2 別解, Q82
2020 12/28 :Add Q103,別解 Q103
******

[**2.Add Two Numbers**](https://leetcode.com/problems/add-two-numbers/)
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.

--ザックリ翻訳--
正の整数が必ずいくつか詰まったリンクリストをプレゼントします。
リスト内の数字は各桁を表しており、反転して格納してあります。
両者をリンクリストとして合算してください。

これは↓ なにを言いたいのか今一でした。分かる方、教えてください m(_ _)m
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

**Example**
*Input: l1 = [2,4,3], l2 = [5,6,4]
*Output: [7,0,8]
*Explanation: 342 + 465 = 807.

なるほど、とりあえず、
以下のステップでアプローチでどうでしょう。

**Step1**
link list になっているので、演算用に編集

**Step2**
演算したものをリストに埋め込み直す。

すいません、説明が雑スギかもしれません(笑)
スマートではないですが、こんな感じで一応通りました。

```AddTwoNumbers.py
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        str_l1,str_l2="",""
        
        while l1:
            str_l1 += str(l1.val)
            l1 =l1.next
        while l2:
            str_l2 += str(l2.val)
            l2 =l2.next
        
        Ans = str( int(str_l1[::-1]) + int(str_l2[::-1]) )[::-1]
        self.p = ListNode(int(Ans[0]))
        
        for i in range(1,len(Ans)):
            self.addNode(int(Ans[i]))
        return self.p
        
    def addNode(self,val):
        
        if self.p is None:
            self.p.val = val
        else:
            runner = self.p
            while runner.next is not None:
                runner = runner.next
            runner.next =ListNode(val)
#72ms
```

リンクリストに埋め込み直すスマートな方法が思いつかなかったので、
泥臭いですが、別途 def addNode を用意しました。

自分の成長の為には、ほかの人のコードから
アプローチを学ぶのはありかもしれません。
面白いものがあれば、パクって、この記事にアップすると思います、、こっそり。

シンプルな書き方は python 特有のライブラリを使う感じなんでしょうか？
汎用性が高くないと、実用性が低いかもしれません。
とりあえず、ほかの人のコード読みに行ってきます(｡･ω･)ﾉﾞ ｲｯﾃｷﾏ-ｽ

**12/22 update**
別の問題とか、色々やっていたので
頭から Q2 が抜けたので,腕試しに改めてやってみました。

```Add2Number.py
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        L1,L2 = "",""
        while l1:
            L1 += str(l1.val)
            l1 = l1.next
        while l2:
            L2 += str(l2.val)
            l2 = l2.next
        
        #print(L1,L2)
        L1L2 = str(int(L1[::-1]) + int(L2[::-1]))[::-1]
        
        head = ListNode(L1L2[0])
        runner = head
        
        for k in range(1,len(L1L2)):
            runner.next = ListNode(L1L2[k])
            runner = runner.next
        
        return head
#68ms
```

大分スッキリかけたので、Linklist が
自分の中で整理ができ始めたのかもしれません。
では、次の問題行ってみましょう。

[**82. Remove Duplicates from Sorted List II**](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/)
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Return the linked list sorted as well.

--ザックリ翻訳--
linklist をあげるので、重複した要素を全て削除してください。
勿論、linklist はちゃんとソートした状態で返してね( *´艸｀)

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:

Input: 1->1->1->2->3
Output: 2->3

```delDecoup.py
class Solution:
    def __init__(self):
        self.root = None
    
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return
        if head.val and not head.next:
            return head
        
        front = head
        rear = front.next
        self.DM =[]
        #self.root = None
        
        if front.val == rear.val and not rear.next:
            return
        
        while rear:
            if front.val == rear.val:
                self.DM.append(front.val)
            front = rear
            rear = rear.next
        
        return self.GEN(head)
    
    def GEN(self,head):
        p = head
        
        while p:
            if p.val in self.DM:
                p = p.next
            else:
                self.ADD(p.val)
                p = p.next
                
        return self.root
    
    def ADD(self,val):
        newdata = ListNode(val)
        if self.root == None:
            self.root = newdata
        else:
            runner = self.root
            while runner.next:
                runner = runner.next
            runner.next = newdata
        
        return self.root
#48ms
```

スマートじゃない記述で申し訳ないm(_ _)m
Submit を押して通った時は思わず声に出して喜んでしまいました(笑)
取り組み当初は行き詰まったのですが、基本を徹底的に見直して、
なんとか糸口を見つけられました。

もっとスマートに書きたいなー(*´з`)

[**103. Binary Tree Zigzag Level Order Traversal**](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/)
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

```image.py
    3
   / \
  9  20
    /  \
   15   7
```

return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]

```Zigzag_grouping.py
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        q = deque()
        q.append(root)
        ans = []
        level = 0
        while q:
            ans.append([])
            layer_length = len(q)
            for _ in range(layer_length):
                nums = q.popleft()
                ans[level].append(nums.val)
                
                if nums.left:
                    q.append(nums.left)
                if nums.right:
                    q.append(nums.right)

            if level%2 == 1:
                ans[level].reverse()
            level += 1
        return ans
#28ms
```

[**ココ**](https://qiita.com/AKpirion/items/19075d3fd365cd853bd7) で色々あがいてます(笑)
その結果、Q103 が出来ました

この問題は deque における append,appendleft,pop,popleft を
使い分ける良い練習になると思います。是非やってみましょう。

```Zigzag_grouping.py
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        q = deque()
        q.append(root)
        ans = []
        level = 0
        
        while q:
            ans.append([])
            layer_length = len(q)
            
            for _ in range(layer_length):
                
                if level%2 == 0:
                    nums = q.popleft()
                else:
                    nums = q.pop()
                    
                ans[level].append(nums.val)
                
                if level%2 == 0:
                    if nums.left:
                        q.append(nums.left)
                    if nums.right:
                        q.append(nums.right)
                else:
                    if nums.right:
                        q.appendleft(nums.right)       
                    if nums.left:
                        q.appendleft(nums.left)
            
            level += 1
        return ans
#32ms
```

一応解けましたが、時間が長くなりました。
これは if 文が多いからだと思います。
もっとシンプルに出来ればスピードが上がるかもしれません。

if 文を最低限にしながら、ジグザグに読みに行くやり方が
あるなら、非常に興味があります。
有識者のコードを拝見してきます(@^^)/~~~