https://leetcode.com/problems/search-insert-position/ algorithm の runtime は O(log n) である必要があるため、 binary search で target の数の位置を調べる。 変数 left に 0、 right に len(nums) - 1 を設定する。 (left + right) // 2 で真ん中の値が取得出来るので、 真ん中の位置を mid とする。 nums の mid の値が target なら、mid の index の値を返す。 もし、target の値が mid より大きい場合、 left を mid + 1 にする。 target の値が mid より小さい場合、 right を mid - 1 にする。 [1, 3, 5, 6] で target = 2 の場合、...

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] !...