回答のアプローチは Recursive DFS BFS Iterative DFS Base case root が empty children が Null Recursive DFS Time complexity: O(n) Mem complexity: O(n) class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right)) BFS BFS を使う場合は Queue を使う。 3 ／ ＼ 9 20 ／＼ 15 7 | 3 | 9 | 20 | 15 | 7 | 1 2 2 3 3 ← Level...
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/ この問題の回答方法としては Recursive と Iterative なアプローチがある。 Recursive Approach アルゴリズム ルートの Node から始める。 p と q が右の subtree にある場合、1から右のsubtreeを探すようにする。 p と q が左の subtree にある場合、1から左のsubtreeを探すようにする。 もし 2 と 3 のステップが not true の場合、p と q の共通の Node を見つけたこととなる。 Time complexity: O(n) Mem complexity: O(n) # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ parent_val = root....
https://leetcode.com/problems/climbing-stairs/ n = 5 0 ／ ＼ 1 2 ／＼ ／＼ 2 3 3 4 ／＼ ／＼ ／＼ ／＼ 3 4 4 5 4 5 5 6 ／＼ ／＼ ／＼ ／＼ 4 5 5 6 5 6 5 6 ／＼ 5 6 n が 5 steps の場合、 8通りの選択が出来る。 DFS でも出来るかが 2^n となる。 そのため Dynamic Programming を使う。 同じ計算をする値は memoize する | 8 | 5 | 3 | 2 | 1 | 1 | n に辿り着くまでの数 0 1 2 3 4 5(step) one two...
https://leetcode.com/problems/meeting-rooms/ 先ず始めに intervals のスタート時間でソートする。 intervals の時間がソートされたため、 ループで最初の会議の終わりの時間と次の会議の始まりの時間を比較し、 最初の会議の終わりの時間 が 次の会議の始まりの時間より大きい場合、 会議の時間が重なっているので、False を返す。 次の会議の開始時間 が 前の会議の終わり時間より小さい場合ループを続ける。 ループする際、次のリストと比較するため for の range で -1 をする。 ソートをするので Time complexity は O(n log n) となる。 Time complexity: O(n log n) Mem complexity: O(1) class Solution(object): def canAttendMeetings(self, intervals): """ :type intervals: List[List[int]] :rtype: bool """ intervals.sort() for i in range(len(intervals) -1): if intervals[i][1] > intervals[i + 1][0]: return False return True
https://leetcode.com/problems/merge-two-sorted-lists/ ダミー Node を作って edge case の 空の Linked List が挿入されても大丈夫なようにする。 その後はループで l1 と l2 の val を比べ、 小さい値を tail.next に入れる。 その後、 next をずらす。 ループ後 l1, l2 のどちらかのリストが empty の場合、 Linked List に追加する必要があるので、 リストが empty か確認し、値があれば Linked List に追加する。 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def mergeTwoLists(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ dummy = ListNode() tail = dummy while l1 and l2: if l1....