LeetCodeをやっていき記録 2020 4/26 ~
easyしかやりません（宣言）。5月くらいまでひとまずゆるゆるやりたい。Two Sum (Easy)
これとAdd Two Numbers (Easy)
この二問はLeetCodeに慣れるために犠牲になりました。Reverse Integer (Easy)
なんかstrに直したりしてごちゃごちゃやりました。.reverse()とか使うと負けな気がするが正直どうなんでしょう。空気感がまだわからんわ。
class Solution:
def reverse(self, x: int) -> int:
if abs(x) > 9:
a = [x for x in str(x)]
sign = '+'
try:
int(a[0])
except:
sign = a[0]
a = a[1:]
# print(f'sign {sign}')
# print(f'a {a}')
# a = [int(x) for x in a]
a.reverse()
# print(f'reversed a {a}')
a = ''.join(a)
a = a.lstrip("0")
# print(f'joined a {a}')
a = int(a)
# print(f'int a {a}')
if sign == '-':
a = a * -1
print(f'final a {a}')
if abs(a) > 2**(31):
return 0
return a
else:
print(f'final a {x}')
return x
test_cases = [
123,
-321,
0,
120,
32000,
-5300,
90,
1103,
938918,
5,
-4
]
S = Solution()
for test in test_cases:
S.reverse(test)
Same Tree (Easy)
二つのBinary Treeが完全に同じ構造をしているかどうかTrueFalse返せだってさ。なんか、偶然にもリストに直して、一つのノードの親と右左だけに注目してノードを関数に渡し続けながらリストにappendし続けて、最後にリストが同じ形しているか比べようとしたら、通ってしまって鳥肌たったわ。 というか、LeetCode側から渡されるデータ構造がどんな感じなのかに気を配らなきゃいけないのにあんまり情報くれないっていうの、なんかよくないと思うわ。もうちょっとexampleくれればいいやん。そこに時間食われるんだよね。でもまあ、Binary Treeはどのノードでも立場が同じだから一つのNodeだけに集中して処理を綺麗に書けば全部終わるよというのは重要な感じがした。
class Solution:
def appendNoneOrValue(self, a, tree):
if ((tree == None) or tree == [] ):
a.append(None)
else:
a.append(tree.val)
a = self.appendNoneOrValue(a, tree.right)
a = self.appendNoneOrValue(a, tree.left)
return a
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
# to list
a = []
b = []
a = self.appendNoneOrValue(a, p)
b = self.appendNoneOrValue(b, q)
if a == b:
return True
else:
return False
Remove Linked Elements (Easy)
なんか、Linked List の扱いにPythonで慣れたらおしまいという感じしたやつ。 これ、最初に犠牲になった二問のうちのどっちかでこのLinked List出てきて、最初意味わからなかったけどもああそういう感じにやるのねとなってしまってからは、そうなのねという感じになるな。while headでLinked Listの中をグルグル回して、なんかやるっていう構文がもはやできている。nextに次のList渡すという流れもできてしまっている。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
result = ListNode(0)
result_tail = result
while head:
# print(head.val)
print(result_tail.val)
if (val == head.val):
pass
else:
result_tail.next = ListNode(head.val)
result_tail = result_tail.next
# print(result_tail)
head = head.next
return result.next
Bulls and Cows(Easy)
あの、ヌメロンっていうんですか？あれ英語だとこういう名前なんですね。ヌメロンのヒントを出せみたいな感じでした！ なんか、remove()を使った時点で負けな感じがあって悲しい。確かにこれらパズルをやりこむといやでも計算量について意識しなければならず、ほ〜〜〜うという気持ちになります。
class Solution:
def getHint(self, secret: str, guess: str) -> str:
# only contain digits, and their lengths are always equal
# both secret number and friend's guess may contain duplicate digits.
def fetchBulls(secret, guess):
bulls = 0
dropped_secret = []
dropped_guess = []
for sec, gue in zip(secret, guess):
if sec == gue:
bulls += 1
pass
else:
dropped_secret.append(sec)
dropped_guess.append(gue)
return dropped_secret, dropped_guess, bulls
def getCows(d_secret, d_guess):
cows = 0
for gue in d_guess:
if gue in d_secret:
cows += 1
d_secret.remove(gue)
else:
pass
return cows
d_secret, d_guess, bulls = fetchBulls(secret, guess) # drop bulls
cows = getCows(d_secret, d_guess)
return f'{bulls}A{cows}B'
test_cases = [
["1234", "2341"],
["4314", "5191"],
["9159", "0910"],
["0010", "1309"],
["1234", "5678"],
["1122", "2211"]
]
S = Solution()
for test in test_cases:
S.getHint(test[0], test[1])
Sum of Left Leaves(Easy)
Binary Treeは再帰関数みたいなやつで、一つずつのノードをていねいに調べる方針でやるっていう印象を持ってたからこの前かいたやつを思い出しながらもう一回似たようなの書いたら通った件。しかしこの関数初見で書くのってなかなかつらたんじゃない？しらんけども。意地でも解法とかググらんようにしてるのは草。しかし、この木構造のやつはデバッグしづらくてつらい、たぶんちゃんと理論としてデータ構造学んだ方がいいやつな感じする、この木に関しては。なんか、汚くオリジナル感満載でやっていて、まあそのうちなんか本読みたくなるだろうな。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
def getAllNode(nodes, tree):
if tree:
if (tree.left) and (tree.left.left == None) and (tree.left.right == None):
nodes.append(tree.left.val)
getAllNode(nodes, tree.right)
getAllNode(nodes, tree.left)
return left_nodes
left_nodes = []
left_nodes = getAllNode(left_nodes, root)
return sum(left_nodes)
Relative Ranks (Easy)
なんか、仕事感あふれる感じでいやでした。
class Solution:
def findRelativeRanks(self, nums: List[int]) -> List[str]:
numIndex = {num: [ind, None] for ind, num in enumerate(nums)}
sorted_scores = sorted(nums, reverse=True)
scores = [{'score': num, 'rank':ind+1} for ind, num in enumerate(sorted_scores)]
results = [None] * len(nums)
for score_rank in scores:
score = score_rank['score']
rank = score_rank['rank']
numIndex[score][1] = rank
index = numIndex[score][0]
if rank == 1:
results[index] = "Gold Medal"
elif rank == 2:
results[index] = "Silver Medal"
elif rank == 3:
results[index] = "Bronze Medal"
else:
results[index] = str(rank)
return results
Min Stack (Easy)
Stackを実装しようというものだけれども、Pythonがリッチすぎるから逆に戸惑ってしまう回。こんなんどうしろっていうんや。 min()を使わずに、sorted()して一番最初の要素とってこよと素直に書いたらなんかあかんかった模様。min()の効率的なアルゴリズムください。いやまあ、標準ライブラリ使うけどね。min()自力で実装する人とかいるんすか？え？ところで、ちゃんと全てにおいてtry/exceptで囲むようにしようと思います。今まで適当こいてたけど。
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
def push(self, x: int) -> None:
self.stack.append(x)
return
def pop(self) -> None:
try:
val = self.stack[len(self.stack)-1]
self.stack = self.stack[0:len(self.stack)-1]
return val
except ValueError:
raise ValueError
def top(self) -> int:
try:
return self.stack[len(self.stack)-1]
except ValueError:
raise ValueError
def getMin(self) -> int:
try:
return min(self.stack) # don't want to use stdlib, it is usually much more faster though
except ValueError:
raise ValueError
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
Implement Stack using Queues (Easy)
あれ？なんか約束を破ってやっているような気がしてならない。Queuesとはなんでしょうか、いやなんかなんとなくは知っているけども、やってはいけないことをしているのでは。ていうか、Pythonのリッチな配列使っていい時点でなんかよくわからんよ、私は。
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack = []
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.stack.append(x)
return
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
return self.stack.pop()
def top(self) -> int:
"""
Get the top element.
"""
try:
return self.stack[len(self.stack)-1]
except:
raise
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
length = len(self.stack)
if length == 0:
return True
else:
return False
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
Construct String from Binary Tree (Easy)
なんかパッと解けなかったんだけど（怒）ここで、流石に基礎知識つけた方が見通しが良くなるだろう&今なら学ぶモチベが高いと思い、データ構造の学習を決意。ここまでstackとかqueueとかtreeとかlinked listとかよくわからなかったです。これ以降はわかるようになるはずです。そのために、こちらのコースをチョイスしました。Data Structures by Coursera
これを終わらせてやんよ・・・ゴゴゴゴゴ
テンプレ