leetcode

https://leetcode.com/problems/linked-list-cycle/ Linked List が Cycle なのかを確認する。 Linked List が Cycle な場合、 2つのポインターを使う。 (1つめのポインターは 1つずつ進み、 2つめのポインターは 2つずつ進む。) Cycle な場合どこかの時点で2つ進むポインター が1つしか進まないポインターに追いつくので Cycle だとわかる。 Cycle ではない場合 いずれかの時点で ポインターが Null になる。 Time complexity: O(n) Mem complexity: O(1) # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ slow, fast = head, head while fast and fast....

https://leetcode.com/problems/reverse-linked-list/ 考え方としては、 1 → 2 → 3 → 4 → 5 1 ← 2 ← 3 ← 4 ← 5 とするように考える。 回答方法は iterative なやり方と recursive なやり方がある。 iterative なやり方は 2つの pointer を使う。 prev と curr まず prev に　None を設定する。 curr は head にする Null → 1 → 2 → 3 → 4 → 5 ↑ ↑ prev curr ループしている間 Linked List の 矢印の向き (curr.next) をずらしつつ、prev と next の pointer もずらしていく。...

https://leetcode.com/problems/valid-parentheses/ Prerequisite Hash Map Stack 最初にどのカッコがどの 括弧閉じ にマッチしているかわかるために HashMap を作る必要がある。 この際、括弧閉じ をキーにする。 for 文で list の中を確認し、 括弧開きは stack に入れる。 stack は 最後に入れたものから出すので、 括弧開き と 括弧閉じ がマッチしていれば、 stack から pop できる。 最後に stack に何も残らなければ、 全てがマッチして True を return する。 Time complexity: O(n) Mem complexity: O(n) class Solution(object): def isValid(self, s): """ :type s: str :rtype: bool """ stack = [] closeToOpen = { ')' : '(', ']' : '[', '}' : '{' } for c in s: if c in closeToOpen: if stack and stack[-1] == closeToOpen[c]: stack....

https://leetcode.com/problems/missing-number/ sum([0,1,2,3]) - sum([3,0,1]) = 2 2がない数字なので、2が残る。 最初に result に len(nums) を代入する。 nums が [3,0,1] の場合、 result に 3 が代入される。 これは for で回す時に range(len(nums)) だと 0, 1, 2 としかならないため。 result に len(nums) の代入が必要。 result += (i - nums[i]) をすることで、2 が return 出来る。 Time complexity: O(n) Mem complexity: O(1) class Solution(object): def missingNumber(self, nums): """ :type nums: List[int] :rtype: int """ result = len(nums) for i in range(len(nums)): result += (i - nums[i]) return result

https://leetcode.com/problems/maximum-subarray/ | -2 | 1 | -3 | 4 | -1 | 2 | 1 | -5 | 4 | 最初の3つの合計(-2 + 1 -3)はマイナスになるので、 そのため subarray のスタートは 4 もしくは 4以降の数字になる。 合計が正の数になる場合は保持しておく。 変数に0 を代入して、 iterate しながら数字を追加していく。 合計がマイナスになる場合は保持する必要がないので、0 にする。 Time complexity: O(n) Mem complexity: O(1) class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ max_subarray = nums[0] current_subarray = 0 for n in nums: if current_subarray < 0: current_subarray = 0 current_subarray += n max_subarray = max(max_subarray, current_subarray) return max_subarray