lettcode刷题之贪心
leetcode刷题,使用python
1, 跳跃游戏 II —— 0045 贪心算法
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
from typing import List
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
maxPos, end, step = 0, 0, 0
for i in range(n-1):
if i<= maxPos:
maxPos = max(maxPos, i+nums[i])
if maxPos >= n-1:
return step+1
if i == end:
end = maxPos
step += 1
return step
S = Solution()
nums = [2,3,1,1,4]
#nums = [3,2,1,0,4]
print(S.jump(nums))
2, 加油站 —— 0134 贪心算法
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
示例 1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
from typing import List
# 贪心算法
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
# 总油量 < 总耗油量，一定无解
if sum(gas) < sum(cost):
return -1
# sum(gas) >= sum(cost)，一定有解【题目保证唯一解】
n = len(gas)
start = 0 # 记录出发点，从索引0开始
total = 0 # 记录汽车实际油量
for i in range(n):
total += gas[i] - cost[i] # 每个站点加油量相当于 gas[i] - cost[i]
if total < 0: # 在i处的油量<0，说明从之前站点出发的车均无法到达i
start = i+1 # 尝试从下一个站点i+1重新出发
total = 0 # 重新出发时油量置为0
return start
S = Solution()
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
print(S.canCompleteCircuit(gas, cost))
3, 最大数—— 0179 贪心算法
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例 1：
输入：nums = [10,2]
输出："210"
import functools
from typing import List
class Solution:
def largestNumber(self, nums: List[int]) -> str:
strs = map(str, nums) #将数字映射成为字符
def cmp(a, b):
if a+b == b+a:
return 0
elif a+b > b+a:
return 1
else:
return -1
strs = sorted(strs, key=functools.cmp_to_key(cmp), reverse=True)
return ''.join(strs) if strs[0] != '0' else '0'
S = Solution()
nums = [10,2]
print(S.largestNumber(nums))
4, 去重重复字母 —— 0316 贪心算法+单调栈
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：
输入：s = "bcabc"
输出："abc"
import collections
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
res = []
# freq[c] 表示之后时间里每个字符会出现的次数 初始化为每个字母的频数 遍历过程中减小
freq = collections.Counter(s)
for c in s:
#如果c不在res中, 再考虑是否添加
if c not in res:
while len(res)>0 and res[-1]>c and freq[res[-1]]>0:
res.pop()
res.append(c)
# 无论是否添加c 它之后出现的频数都-1
freq[c] -= 1
return ''.join(res)
S = Solution()
s = "bcabc"
print(S.removeDuplicateLetters(s))
5, 递增的三元子序列 —— 0334 贪心算法 或者 双向链表
给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意
from typing import List
#贪心算法 感觉自己肯定想不出来
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
n = len(nums)
if n<3:
return False
first, second = nums[0], float('inf')
for i in range(1, n):
num = nums[i]
if num > second:
return True
if num > first:
second = num
else:
first = num
return False
#双向链表
class Solution2:
def increasingTriplet(self, nums: List[int]) -> bool:
n = len(nums)
if n<3:
return False
leftMin = [0] * n # leftMin数组中 leftMin[i]表示 num[0]到nums[i]中的最小值
leftMin[0] = nums[0]
rightMax = [0] * n # rightMax数组中 rightMax[i]表示 num[i]到nums[n-1]中的最大值
rightMax[n-1] = nums[n-1]
for i in range(1, n):
leftMin[i] = min(leftMin[i-1], nums[i])
for i in range(n-2, -1, -1):
rightMax[i] = max(rightMax[i+1], nums[i])
for i in range(1, n-1):
if leftMin[i-1] < nums[i] < rightMax[i+1]:
return True
return False
nums = [1, 2, 3, 4, 5]
S = Solution()
S2 = Solution2()
print(S.increasingTriplet(nums))
print(S2.increasingTriplet(nums))
