贪心算法【78-81】
121.买卖股票的最佳时机
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp=[[0,0] for _ in range(len(prices))] #dp[i][0]第i天持有股票，dp[i][1]第i天不持有股票
dp[0][0] = -prices[0]
for i in range(1, len(prices)):
dp[i][0] = max(dp[i-1][0], -prices[i])
dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])
return dp[-1][1]
55.跳跃游戏
## for循环
class Solution:
def canJump(self, nums: List[int]) -> bool:
cover = 0
if len(nums) == 1: return True
for i in range(len(nums)):
if i <= cover:
cover = max(i + nums[i], cover)
if cover >= len(nums) - 1: return True
return False
45.跳跃游戏
class Solution:
def jump(self, nums) -> int:
if len(nums)==1: # 如果数组只有一个元素，不需要跳跃，步数为0
return 0
i = 0 # 当前位置
count = 0 # 步数计数器
cover = 0 # 当前能够覆盖的最远距离
while i <= cover: # 当前位置小于等于当前能够覆盖的最远距离时循环
for i in range(i, cover+1): # 遍历从当前位置到当前能够覆盖的最远距离之间的所有位置
cover = max(nums[i]+i, cover) # 更新当前能够覆盖的最远距离
if cover >= len(nums)-1: # 如果当前能够覆盖的最远距离达到或超过数组的最后一个位置，直接返回步数+1
return count+1
count += 1 # 每一轮遍历结束后，步数+1
'''动态规划
1. dp[i]: 到nums[i]的最小跳跃次数
2. j<= nums[i]; dp[i+j] = min(dp[i+j], dp[i]+1)
3.dp[0] = 0,其他初始化为最大值
'''
class Solution:
def jump(self, nums: List[int]) -> int:
dp = [float('inf')] * len(nums)
dp[0] = 0
for i in range(len(nums)):
for j in range(nums[i]+1):
if i+j < len(nums):
dp[i+j] = min(dp[i+j], dp[i]+1)
return dp[-1]
763.划分字母区间
题目要求：划分尽可能多的片段，每个字母最多出现在一个片段里面
可以分为如下两步：
- 统计每一个字符最后出现的位置
- 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
class Solution:
def partitionLabels(self, s: str) -> List[int]:
last_occurrence = {} # 存储每个字符最后出现的位置
for index, ch in enumerate(s):
last_occurrence[ch] = i
result = []
start = 0
end = 0
for index, ch in enumerate(s):
end = max(end, last_occurrence[ch]) # 找到当前字符出现的最远位置
if index == end: # 如果当前位置是最远位置，表示可以分割出一个区间
result.append(end - start + 1)
start = index + 1
return result
技巧【96-100】
136.只出现一次的数字
空间常数，位运算
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
x = 0
for num in nums: # 1. 遍历 nums 执行异或运算
x ^= num
return x # 2. 返回出现一次的数字 x
169.多数元素
'''
======当发生 票数和 =0 时，剩余数组的众数一定不变 =====
如果vote为0，当前元素为临时众数
如果临时众数是全局众数，抵消的数字里面，一半是众数；没抵消的数组里面，众数肯定不变
如果临时众数不是全局众数，vito会变成0
'''
class Solution:
def majorityElement(self, nums: List[int]) -> int:
vote = 0
for i in nums:
if vote == 0:
x = i #众数是i
if i == x:
vote += 1
else :
vote -= 1
return x
75.颜色分类
 |
三路快排：nums[0…zero] = 0 ；nums[zero+1…i-1] = 1 ；nums[two…n-1] = 2 |
|---|---|
 |
 |
'''
nums[0…zero] = 0 ；
nums[zero+1…i-1] = 1 ；
nums[two…n-1] = 2
'''
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
i, zero, two = 0,-1, len(nums)
while i < two:
if nums[i] == 1:
i += 1
elif nums[i] == 2:
two -= 1
nums[i], nums[two] = nums[two], nums[i]
else:
zero += 1
nums[i], nums[zero] = nums[zero], nums[i] #nums[zero]=1
i += 1
31.下一个排列
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
length = len(nums)
for i in range(length-2,-1,-1):
if nums[i] >= nums[i+1]:
continue #剪枝
for j in range(length-1,i,-1):
if nums[j] > nums[i]:
nums[j], nums[i] = nums[i], nums[j]
self.reverse(nums, i+1, length-1)
return
self.reverse(nums, 0, length-1) #代表是，降序排列
#翻转nums[left...... right]
def reverse(self, nums, left, right):
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
287.寻找重复数
环形链表
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
def next(i):
return nums[i]
slow = fast = 0
while True:
slow = next(slow)
fast = next(next(fast))
if slow == fast:
break
slow = 0
while slow != fast:
slow = next(slow)
fast = next(fast)
return slow #入环的地方
哈希表
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
hmap = set()
for num in nums:
if num in hmap:
return num
else:
hmap.add(num)
return -1
