身體不太舒服的日子
然後又開啟一個自己比較爛區域的study plan寫起來真是痛苦QQ
後來就挑些比較簡單的寫了~當作偷懶XD
https://leetcode.com/problems/minimum-distance-between-bst-nodes/
Submission：https://leetcode.com/problems/minimum-distance-between-bst-nodes/submissions/857323464/
Given the root of a Binary Search Tree (BST), return the minimum difference between the values of any two different nodes in the tree.
從BST裡面找出兩個點相差的最小值
tryit
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
#找到任意兩節點相差的最小值
#有點忘記stack的traversal怎麼寫，想了一下
def minDiffInBST(self, root: Optional[TreeNode]) -> int:
recL = []
ans = float("inf")
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
recL.append(root.val)
if len(recL) > 1:
ans = min(ans,recL[-1] - recL[-2])
root = root.right
# print(recL)
return ans
https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/
Submission：https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/submissions/857313938/
Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node's value is the smaller value among its two sub-nodes. More formally, the property root.val = min(root.left.val, root.right.val) always holds.
Given such a binary tree, you need to output the second minimum value in the set made of all the nodes' value in the whole tree.
If no such second minimum value exists, output -1 instead.
找到binary tree裡面的第二小的值，要注意不是binary search tree
這題直接寫懶人法XD
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
#找到第二小的值
#幹，不是BST
def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
ansL = set()
queue = [root]
while queue:
temp = queue.pop(0)
if temp:
queue.append(temp.left)
ansL.add(temp.val)
queue.append(temp.right)
if len(ansL)>1:
ansL.remove(min(ansL))
return min(ansL)
return -1
https://leetcode.com/problems/closest-binary-search-tree-value/
Submission：https://leetcode.com/problems/closest-binary-search-tree-value/submissions/857312198/
Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target.
找到最靠近target的node點，要注意target是float，所以要處理小數問題
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
#找到最靠近target的值
#動腦
#參考別人
def closestValue(self, root, target):
r = root.val #紀錄最一開始的root.val
while root:
if abs(root.val - target) < abs(r - target):#每到一層比較一次，直到走完這條路為止
r = root.val
root = root.left if target < root.val else root.right
return r
#不想動腦就中序後binarySearch
def closestValue(self, root: Optional[TreeNode], target: float) -> int:
rec = []
def inorder(root):
if root:
inorder(root.left)
rec.append(root.val)
inorder(root.right)
def bSearch(numList,target):
left,right = 0,len(numList)-1
while left<right:
mid = (left+right)//2
if target>numList[mid]:
left = mid + 1
else:
right = mid
return left-1 #因為left會出現在target右邊
inorder(root)
if target<=rec[0]:
return rec[0]
elif target>=rec[-1]:
return rec[-1]
left = bSearch(rec,target)
return rec[left+1] if target > (rec[left] + rec[left+1])/2 else rec[left]
https://leetcode.com/problems/house-robber-ii/
Submission：https://leetcode.com/problems/house-robber-ii/submissions/857296989/
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
搶房子，但不可以搶已經搶過的隔壁房，重點是他是環，這點讓我思考很久，我完全沒碰過這樣的題目QQ。
有些類型沒做過但想得出來，可惜這題不是，或許是想得不夠久。
但要花很多很多時間去想，還是節省時間參考答案？這大概是我的難題之一吧
class Solution:
#現在是頭尾相連，大致理解
#也就是說，某方面來說沒有頭尾
#沒做過類似的題目，有點難倒我==
#從最大開始找？
#從0找一次，再從1找一次？
#有點接近了，稍微一點偏差，我想應該是經驗不夠的緣故，之後還要練習
#別人寫的之一
#做house robber兩次
#假設說有十家房屋 0,1,2,3,4,5,6,7,8,9
#強制搶劫 0，那1跟9就不能搶，所以可以搶2~8
#強制不搶劫 0， 所以可以搶1~9。
def rob(self, nums):
def rob_helper(nums):
dp1, dp2 = 0, 0
for num in nums:
dp1, dp2 = dp2, max(dp1 + num, dp2)
return dp2
return max(nums[0] + rob_helper(nums[2:-1]), rob_helper(nums[1:]))
#別人寫的之二
#也是做兩次
def rob(self, nums):
def simple_rob(nums, i, j):
rob, not_rob = 0, 0
for idx in range(i, j):
num = nums[idx]
rob, not_rob = not_rob + num, max(rob, not_rob)
return max(rob, not_rob)
if not nums:
return 0
elif len(nums) == 1:
return nums[0]
else:
n = len(nums)
return max(simple_rob(nums, 1, n), simple_rob(nums, 0, n-1))
#別人寫的之三
#也是做兩次
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
dp = [0 for _ in range(len(nums)-1)]
dp2 = [0 for _ in range(len(nums))]
for i in range(len(nums)-1):
prev2 = dp[i-2] if i - 2 >= 0 else 0
prev1 = dp[i-1] if i - 1 >= 0 else 0
dp[i] = max(prev2 + nums[i], prev1)
for i in range(1, len(nums)):
prev2 = dp2[i-2] if i - 2 >= 0 else 0
prev1 = dp2[i-1] if i - 1 >= 0 else 0
dp2[i] = max( prev2 + nums[i], prev1)
return max(dp2[-1], dp[-1]) if dp else dp2[-1]
iThome鐵人賽
看影片追技術