こんにちは
今回は初めて 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
演算したものをリストに埋め込み直す。
すいません、説明が雑スギかもしれません(笑)
スマートではないですが、こんな感じで一応通りました。
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 が抜けたので,腕試しに改めてやってみました。
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
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],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
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 を
使い分ける良い練習になると思います。是非やってみましょう。
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 文を最低限にしながら、ジグザグに読みに行くやり方が
あるなら、非常に興味があります。
有識者のコードを拝見してきます(@^^)/~~~