季節の変わり目で必ず風邪を引くko_ya346です。
今日から少しずつleetcodeをやっていこうかと思います。
なんで？
この記事がきっかけです。
「つよつよのグローバル企業に転職する」という強い野望は特に持ち合わせていないのですが、
ソフトウェアエンジニアには実は少しだけ憧れがあります。。。
というのも、
- 競技プログラミングがきっかけでプログラミングにハマり、その経験が活かせそう
- 元々メーカー勤務でモノづくりは好き。ソフトウェアエンジニアはそれができそう
- IT業界のイメージがこの職種
という、（なんとも浅い理由ですが）そっち方面でも活躍出来たらなぁ、、というのは日々思っているところでした。
調べたところによると、atcoderよりも基礎教養的な問題が多いとのことで地固めにちょうどいいと思ったので、スキマ時間にチマチマ進めることにしました。
1. Two Sum
自力解法
- numsから要素を1つ選ぶ
- target - 選んだ数字を引く
- その値がnumsにあるか二部探索で探す
計算量はO(Nlog2N)かな？一応正解出来ました。
targetを構成する2つの数字が同じ場合の処理がやや面倒でした。
class Solution:
def twoSum(self, org_nums: List[int], target: int) -> List[int]:
if len(org_nums) == 2:
return 0, 1
nums = sorted(org_nums)
for i in range(len(nums)):
num = nums[i]
ret = self.binary_search(nums[i+1:], target - num)
# print(num, ret)
if ret is None:
continue
# print(org_nums[i+1:])
ans1 = org_nums.index(num)
if num == ret:
ans2 = org_nums[ans1+1:].index(num) + ans1 + 1
else:
ans2 = org_nums.index(ret)
return ans1, ans2
def binary_search(self, lst: List[int], val: int) -> Union[int, None]:
i_left = 0
i_right = len(lst) - 1
while i_left <= i_right:
i_middle = (i_left + i_right) // 2
val_middle = lst[i_middle]
if val < val_middle:
i_right = i_middle - 1
elif val > val_middle:
i_left = i_middle + 1
else:
return val_middle
return None
模範解答
普通に二重ループで解けます。ふええ
あとはhashmapを用意する方法が紹介されていました。
dictとsetはハッシュテーブルで実装しているため、高速で探索が可能です。
この方法だとO(N)で、自力解法よりも高速に処理出来ていました。すごごご
事前にtarget - nums[i]を計算しておき、その値をkey、iをvalueにもつ辞書を用意し、
そのあとに探索していきます。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hash_dict = {}
for i in range(len(nums)):
hash_dict[nums[i]] = i
for i in range(len(nums)):
diff_num = target - nums[i]
if diff_num in hash_dict and hash_dict[diff_num] != i:
return i, hash_dict[diff_num]
