繼續挑戰自己的弱點~
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
想辦法獲取最大利益，除了不能在持有股票時再買以外，沒有其他限制
一開始寫的時候想得真的很多
tryit
class Solution:
#要做多次
#得到最大利益的總和
#如果right的下一個比現在這一個小，應該就可以跳車了
#還有絕對遞增的狀況需要考慮
def maxProfit(self, prices: List[int]) -> int:
ans = 0
left,right = 0,1
while right < len(prices):
if prices[right] > prices[right - 1]:
ans += prices[right] - prices[left]
left = right
elif prices[right] < prices[right-1]:
ans += (prices[right-1] - prices[left])
left = right
elif prices[right]<prices[left]:
left = right
right += 1
return ans
後來再仔細思考，發現真的想太多，其實可以很簡單解決
class Solution:
#但如果想更多一點這題馬上變白癡題
#啊我都有股票的趨勢圖可以看透未來了，當然一直低買高賣就好啦
#121. Best Time to Buy and Sell Stock，先做這一題可能會讓簡單的思考進入誤區，要注意
def maxProfit(self, prices: List[int]) -> int:
ans = 0
for i in range(1,len(prices)):
if prices[i] > prices[i-1]:
ans += prices[i] - prices[i-1]
return ans
You are given an integer array values where values[i] represents the value of the ith sightseeing spot. Two sightseeing spots i and j have a distance j - i between them.
The score of a pair (i < j) of sightseeing spots is values[i] + values[j] + i - j: the sum of the values of the sightseeing spots, minus the distance between them.
Return the maximum score of a pair of sightseeing spots.
有一公式values[i] + values[j] + i - j，找到兩個索引值 i 跟 j，然後獲取最大值。
一開始也是複雜化，無論是 values[i] + i 或者 values[j] - j都要越大越好，那這邊要怎麼挑選就是最大的難題，因此該開始想到values[i] + i由左至右保留最大值，然後建立hashmap，key用values[j] - j, value用 index，來去想辦法找到最大總和，不過越看越覺得寫過度複雜了，所以有第二方法。
class Solution:
#公式：values[i] + values[j] + i - j
#當成一個位置有兩種值存在
def maxScoreSightseeingPair(self, values: List[int]) -> int:
vPlusList = []
vMinus = {} #key = values[i] + i, value = index
ans = -1000
for i in range(len(values)):
vPlusList.append(values[i] + i)
vMinus[values[i] - i] = i
vPlusDp = [0] #一開始要留個0在這邊，因為 i < j，儲存前j個裡面的最大值
for i in vPlusList:
vPlusDp.append(max(vPlusDp[-1],i))
vMinusKeys = vMinus.keys() #抓值出來，順便獲取index值
ans = -1000
for i in vMinusKeys:
ans = max(ans,i+vPlusDp[vMinus[i]])
return ans
class Solution:
#慢慢簡化後
#整理後其實概念很簡單
#因為values[j]一定走在前面，values[i]一定在後面
#所以我們其實只需要把values[j]加上最大的values[i]就好
#想清楚後其實很簡單
def maxScoreSightseeingPair(self, values: List[int]) -> int:
ans = -1000
plus = 0
for i in range(1,len(values)):
plus = max(plus,values[i-1] + i-1)
ans = max(plus+values[i]-i,ans)
return ans
You are given the root of a full binary tree with the following properties:
Leaf nodes have either the value 0 or 1, where 0 represents False and 1 represents True.
Non-leaf nodes have either the value 2 or 3, where 2 represents the boolean OR and 3 represents the boolean AND.
The evaluation of a node is as follows:
If the node is a leaf node, the evaluation is the value of the node, i.e. True or False.
Otherwise, evaluate the node's two children and apply the boolean operation of its value with the children's evaluations.
Return the boolean result of evaluating the root node.
A full binary tree is a binary tree where each node has either 0 or 2 children.
A leaf node is a node that has zero children.
# 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:
#tree必為full binary tree，不會有獨立存在的節點
#簡單來說，葉節點必為True False
#其他的節點皆為 or(2) 跟 and(3)
#求最後的結果
#我怎覺得這比一些medium題目難==
#別人寫的，要重練
#看完之後覺得很簡單==
#preorder traversal
def evaluateTree(self, root: Optional[TreeNode]) -> bool:
def recur(node):
if not node.left and not node.right: #找到葉節點時
if node.val == 1:
return True
return False
left = recur(node.left)#先往左到底，抓到Bool時
right = recur(node.right)#往右走，找出上面的左節點可以配的右節點
if node.val == 2:
return left or right
if node.val == 3:
return left and right
return recur(root)
https://leetcode.com/problems/longest-subsequence-with-limited-sum/description/
Submission：https://leetcode.com/problems/longest-subsequence-with-limited-sum/submissions/859398893/
You are given an integer array nums of length n, and an integer array queries of length m.
Return an array answer of length m where answer[i] is the maximum size of a subsequence that you can take from nums such that the sum of its elements is less than or equal to queries[i].
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
from bisect import bisect
class Solution:
#有一串列queries
#找出合成queries[i]的最「大」數量是多少(從nums抓)
#這題要重寫
#看錯題目啦，是要最大數量，那我當然慢慢加就好啦，白癡喔
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
nums.sort()
prefix_sum = [0]
for n in nums:
prefix_sum.append(prefix_sum[-1] + n)
ans = []
for q in queries:
ans.append(bisect(prefix_sum, q) - 1)
return ans
iThome鐵人賽
看影片追技術