【leetcode78-81贪心算法、技巧96-100】

贪心算法【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 = 0if len(nums) == 1: return Truefor i in range(len(nums)):if i <= cover:cover = max(i + nums[i], cover)if cover >= len(nums) - 1: return Truereturn False

45.跳跃游戏

class Solution:def jump(self, nums) -> int:if len(nums)==1:  # 如果数组只有一个元素，不需要跳跃，步数为0return 0i = 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:  # 如果当前能够覆盖的最远距离达到或超过数组的最后一个位置，直接返回步数+1return count+1count += 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] = 0for 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.划分字母区间

题目要求：划分尽可能多的片段，每个字母最多出现在一个片段里面

可以分为如下两步：

1. 统计每一个字符最后出现的位置
2. 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

class Solution:def partitionLabels(self, s: str) -> List[int]:last_occurrence = {}  # 存储每个字符最后出现的位置for index, ch in enumerate(s):last_occurrence[ch] = iresult = []start = 0end = 0for index, ch in enumerate(s):end = max(end, last_occurrence[ch])  # 找到当前字符出现的最远位置if index == end:  # 如果当前位置是最远位置，表示可以分割出一个区间result.append(end - start + 1)start = index + 1return result

技巧【96-100】

136.只出现一次的数字

空间常数，位运算

class Solution:def singleNumber(self, nums: List[int]) -> List[int]:x = 0for 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 = 0for i in nums:if vote == 0:x = i   #众数是iif i == x:vote += 1else : vote -= 1return 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 += 1elif nums[i] == 2:two -= 1nums[i], nums[two] = nums[two], nums[i]else:zero += 1nums[i], nums[zero] = nums[zero], nums[i]  #nums[zero]=1i += 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)returnself.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 += 1right -= 1

287.寻找重复数

环形链表

class Solution:def findDuplicate(self, nums: List[int]) -> int:def next(i):return nums[i]slow = fast = 0while True:slow = next(slow)fast = next(next(fast))if slow == fast:breakslow = 0while 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 numelse:hmap.add(num)return -1