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
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
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
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

ココ で色々あがいてます(笑)
その結果、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 文を最低限にしながら、ジグザグに読みに行くやり方が
あるなら、非常に興味があります。
有識者のコードを拝見してきます(@^^)/~~~