https://leetcode.com/problems/house-robber/ 隣り合った家は訪れることが出来ないので、 変数 rob1 と rob2 を用意する。 for で全ての家を訪れ、 pointer のある位置＋rob1 と rob2 の大きい値を temp に入れる。 rob1 pointerのある位置の前の前の家 rob2 pointerのある位置のは前の家 rob2 が nums の最後の位置まで行くとループが終わるので return で rob2 を返す。 class Solution: def rob(self, num: List[int])-> int: rob1, rob2 = 0, 0 for n in num: temp = max(rob1 + n, rob2) rob1 = rob2 rob2 = temp return rob2
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/ この問題は pointer を2つ使い target になる数を探していく。 pointer を left と right に置き、 left と right の合計が target の値と同じかを計算する。 合計が大きい場合は right の pointer を左にずらし、 合計が小さい場合は left の pointer を右にずらしていく。 合計がtarget の値になるまでループして index の位置を返す。 target = 9 | 1 | 3 | 4 | 5 | 7 | 11 | ↑ ↑ 1 + 11 = 12 > 9 | 1 | 3 | 4 | 5 | 7 | 11 | ↑ ↑...
https://leetcode.com/problems/find-the-town-judge/ graphの問題で、trust のペア, [a, b] は a から b に向かう directed edge である。 例えば、 N = 5 で trust trust = [[1,3],[2,3],[4,3],[4,1],[5,3],[5,1],[5,4]] の場合下記のような graph になる。 3 は 1,2,4,5 から信頼されていて、 誰も信頼していない。 そのため、judge は 3 になる。 この graph theory の、 outdegree の辺は、 その人が他の人を信頼している数になる。 indegree の辺は他の人から信頼されている数になる。 そのため indegree と outdegree によって誰が judge か判断できる。 judge は outdegree が 0 で indegree が N - 1 となる。 trust をループして全員の indegree, outdegree の数を調査できる。 indegree = [0] * (N + 1) outdegree = [0] * (N + 1) for a, b in trust: outdegree[a] += 1 indegree[b] += 1 そして、1 ～ N 人全員をループして、チェックすれば、 judge がわかる。...
DFS Base Case root が Null は None を返す。 Tree を反転して値が同じなら True を返すので、 children node の値を swap して同じか確かめる。 Time complexity: O(n) Mem complexity: O(n) # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def invertTree(self, root): """ :type root: TreeNode :rtype: TreeNode """ if not root: return None tmp = root....
DFS recursive Base Case は p,q が Null の場合同じ Tree なので return する。 もし p,q のどちらかの値が違う場合、その Tree は同じではないので、 False を return する。 また、どちらかの値が Null の場合同じ Tree ではないので、この場合も False を return する。 Time complexity: O(n) Mem complexity: O(n) # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def isSameTree(self, p, q): """ :type p: TreeNode :type q: TreeNode :rtype: bool """ if not p and not q: return True if not p or not q or p....