我们需要找出给定数组中两个数字之间的最大差值,即max(prices[j] - prices[i])
- # 此方法会超时
- class Solution:
- def maxProfit(self, prices: List[int]) -> int:
- ans = 0
- for i in range(len(prices)):
- for j in range(i + 1, len(prices)):
- ans = max(ans, prices[j] - prices[i])
- return ans
遍历价格数组一遍,记录历史最低点,然后在每一天考虑这么一个问题:如果我是在历史最低点买进的,那么我今天能赚多少钱
- # 此方法会超时
- class Solution:
- def maxProfit(self, prices: List[int]) -> int:
- inf = int(1e9)
- minprice = inf
- maxprofit = 0
- for price in prices:
- maxprofit = max(price - minprice,maxprofit)
- minprice = min(price,minprice)
-
- return maxprofit
这样一来,我们依次遍历数组中的每一个位置,并实时维护最远可以到达的距离。对于当前遍历到的位置x,,如果它是在最远可以到达的位置的范围内,那么我们就可以从起点通过若干次跳跃到达该位置,因此我们可以用x + nums[x]更新 最远可以到达的位置。
在遍历的过程中,如果最远可以到达的位置大于等于数组中的最后一个位置,那就说明最后一个位置可达,我们就可以直接返回True作为答案。反之,如果在遍历结束后,最后一个位置仍然不可达,我们就返回False作为答案。
- class Solution:
- def canJump(self, nums: List[int]) -> bool:
- n,rightmost = len(nums),0
- for i in range(n):
- if i <= rightmost:
- rightmost = max(rightmost,i + nums[i])
- if rightmost >= n -1:
- return True
- return False
1、如果某一个作为起跳点的格子可以跳跃的距离是3,那么表示后面3个格子都可以作为起跳点。
可以对每一个能作为起跳点的格子都尝试跳一次,把能跳到最远的距离不断更新。
2、如果从这个起跳点起跳叫做第1次跳跃,那么从后面3个格子起跳都可以叫做第2次跳跃。
3、所以,当一次跳跃结束时,从下一个格子开始,到现在能跳到最远距离,都是下一次跳跃的起跳点。
跳完一次之后,更新下一次起跳点的范围
在新的范围内跳,更新能跳到最远的距离
4、记录跳跃次数,如果跳到了终点,就得到了结果。
- class Solution:
- def jump(self, nums: List[int]) -> int:
- ans, start, end = 0,0,1
- while end < len(nums):
- maxPos = 0
- for i in range(start,end):
- maxPos = max(maxPos,i + nums[i])
- start = end
- end = maxPos + 1
- ans += 1
- return ans
- class Solution:
- def partitionLabels(self, s: str) -> List[int]:
- last = [0] * 26
- for i,ch in enumerate(s):
- last[ord(ch) - ord("a")] = i
-
- partition = list()
- start = end = 0
- print(last)
- for i, ch in enumerate(s):
- end = max(end,last[ord(ch) - ord("a")])
- if i == end:
- partition.append(end - start + 1)
- start = end + 1
- return partition