明天重点看看动态规划问题
543. Diameter of Binary Tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
def diameterOfBinaryTree(self, root):
“””
:type root: TreeNode
:rtype: int
“””
self.ans = 0
def depth(node):
if not node: return 0
anL, anR = depth(node.right), depth(node.left)
self.ans = max(self.ans, anL+anR)
return 1+max(anL, anR)
depth(root)
return self.ans
|
540. Single Element in a Sorted Array
1
2
3
4
5
6
7
8
9
10
11
12
13
|
def singleNonDuplicate(self, nums):
“””
:type nums: List[int]
:rtype: int
“””
left, right = 0, len(nums)-1
while left < right:
mid = (left + right)/2
if nums[mid] == nums[mid+1]:
right = mid + 1
else:
left = mid
return nums[left]
|
然鹅超时了……不过先这样写着吧
198. House Robber
1
2
3
4
5
6
7
8
9
10
|
def rob(self, nums):
“””
:type nums: List[int]
:rtype: int
“””
i, j = 0, 0
for m in nums:
k, i = i, m + j
j = max(k, j)
return max(i, j)
|
f(0) = nums[0]
f(1) = max(num[0], num[1])
f(k) = max( f(k-2) + nums[k], f(k-1) )
104. Maximum Depth of Binary Tree
1
2
3
4
5
6
7
8
|
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))
|
近期评论