leetcode

nums = [0,0,1,1,1,2,2,3,3,4] の重複をなくすようにするので、下記のようになる。 nums = [0,1,2,3,4,,,,,_] pointer を 2つ使う。 最初の数字は必ずユニークになるので、 left = 1　とする。 right は for でループさせながら icrement していく。 non-decreasing order なので、 right の値と right - 1　を比較して、 違う値なら一番初めに現れるユニークの数字だとわかる。 そのためその数字を left pointer がある位置に入れる。 その後、 left pointer をicrementする。 最終的に left pointer の位置がユニークな数の出現回数となるので、 その値を return する。 class Solution: def removeDuplicates(self, nums: List[int]) -> int: left = 1 for right in range(1, len(nums)): if nums[right] != nums[right - 1]: nums[left] = nums[right] left += 1 return left

sentinel ノードは Linked List を空にせず、ヘッドレスにしないようにする。 アルゴリズムは sentinel ノードをセットする。 curr と prev のポインターを設定する。 curr が null でない場合、ループする。 curr.val が 削除する値の場合、 class Solution: def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: sentinel = ListNode(next=head) prev, curr = sentinel, head while curr: if curr.val == val: prev.next = curr.next else: prev = curr curr = curr.next return sentinel.next

https://leetcode.com/problems/path-sum/solution/ ノードがリーフでない場合は、子に対してhasPathSumメソッドを再帰的に呼び出し、合計を現在のノードの値だけ減らす。 ノードがリーフの場合、現在の合計がゼロであるかどうか、つまり最初の合計が検出されたかどうかを確認します。 Base case は、root が none ということはリーフの下の node を確認してるので、sum が 0 になっていないので False を返す。 class Solution: def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: if not root: return False targetSum -= root.val if not root.left and not root.right: # if reach a leaf return targetSum == 0 return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)

https://leetcode.com/problems/isomorphic-strings/ s と t をマッピングして考える。 この際、同じ文字なのに違う文字がマッピングされる場合 isomorphic にならない。 ex. foo bar | f → b | | o → a | | o → r | | b → f | | a → o | | r → o | o が a と r にマッピングされているので、 isomorphic にならず、false になる。 class Solution: def isIsomorphic(self, s: str, t: str) -> bool: mapST, mapTS = {}, {} for c1, c2 in zip(s, t): if((c1 in mapST and mapST[c1] !...

https://leetcode.com/problems/min-stack/solution/ 2つの stack を使う。 1つ目の stack は普通のstackを使うように扱う。(Stack) 2つ目の stack は現在の minimum をトラックするのに使う。(MinStack) MinStack の pushメソッドは現在の値が stack の top より小さい場合、 push される。 popメソッドは Stack のみからpopすると MinStack と合わなくなるので、 If top of main_stack == top of min_tracker_stack: min_tracker_stack.pop() の処理が必要になる。 class MinStack: def __init__(self): self.stack = [] self.min_stack = [] def push(self, x: int) -> None: self.stack.append(x) if not self.min_stack or x <= self.min_stack[-1]: self.min_stack.append(x) def pop(self) -> None: if self.min_stack[-1] == self.stack[-1]: self.min_stack.pop() self....