Leetcode题解 - 贪心算法部分简单题目代码+思路（860、944、1005、1029、1046、1217、1221）
2024-10-11 19:04:22
leetcode真的是一个学习阅读理解的好地方
860. 柠檬水找零
"""
因为用户支付的只会有5、10、20
对于10元的用户必须找一个5
对于20元的用户可以找（三个5）或者（一个10一个5），每次都从大的开始找起来
"""
class Solution:
def lemonadeChange(self, bills) -> bool:
five = 0
ten = 0
for i in bills:
if i == 5:
five += 1
if i == 10:
if five == 0:
return False
five -= 1
ten += 1
if i == 20:
if ten == 0:
if five < 3:
return False
five -= 3
else:
if not five:
return False
ten -= 1
five -= 1
return True
944. 删列造序
class Solution:
def minDeletionSize(self, A) -> int:
if len(A[0]) == 1 or not A[0]:
return 0
sequence = 0
minus = 0
while sequence < len(A[0]):
preTmp = 0
i = 1
# 判断该列是否应该被删除，即后一个是否大于等于前一个
while i != len(A):
if A[i][sequence] < A[preTmp][sequence]:
minus += 1
break
preTmp = i
i += 1
sequence += 1
return minus
1005. K 次取反后最大化的数组和
"""
因为可以对同一个进行多次处理，所以先把负的都变成正数，然后就一直对最小的进行取反操作
"""
class Solution:
def largestSumAfterKNegations(self, A, K: int) -> int:
A = sorted(A)
tmp = K
# 将负数先变成正数
for i in range(K):
if A[i] < 0:
A[i] = -A[i]
else:
tmp = i
break
A = sorted(A)
# 一直处理最小值
while tmp < K:
A[0] = -A[0]
tmp += 1
return sum(A)
1029. 两地调度
"""
先将所有人全部安排飞往B市，再选择N个人改变它们的行程，让它们飞往A市，那么每改变一个人就会额外付出priceA-priceB的费用，
谁的priceA-priceB最小（因为priceA-priceB是可正可负的），我们就让谁去。
"""
class Solution:
def twoCitySchedCost(self, costs) -> int:
costs = sorted(costs, key=lambda x:x[0] - x[1])
s = 0
n = len(costs)//2
for i in range(n):
s += costs[i][0] + costs[i + n][1]
return s
1046. 最后一块石头的重量
"""
每次都找最大的两块出来，然后进行粉碎操作，开始下一次操作前仍然需要重新排序
"""
class Solution:
def lastStoneWeight(self, stones) -> int:
if len(stones) == 1:
return stones[0]
while stones:
if len(stones) == 1:
return stones[0]
stones = sorted(stones, reverse=True)
a = stones.pop(0)
b = stones.pop(0)
if a != b:
stones.append(abs(a - b))
return 0
1217. 玩筹码
"""
已知单数筹码移至单数筹码所在位置，或双数筹码移至双数筹码所在位置上时， 将不用付出代价。
但如果是单数筹码移至双数筹码的位置上，或双->单， 将需要付出 1 的代价,成堆的筹码移动时，也需要付出对应筹码个数的代价。
那就先把奇数位置的全部移动到A，偶数位置的全部移动到B，然后比较A和B那个点的筹码多，再把筹码少的移动过去。
奇数移动到偶数（偶数移动到奇数）的代价为少的一个的数量
"""
class Solution:
def minCostToMoveChips(self, chips) -> int:
odd = 0
even = 0
for i in range(chips):
if chips[i] % 2 == 0:
even += 1
continue
odd += 1
return min(even, odd)
1221. 分割平衡字符串
"""
直观思路，为遇到的每一个R（L）找到配对的。
"""
class Solution:
def balancedStringSplit(self, s: str) -> int:
vis = set()
res = 0
for i in range(len(s)):
if i in vis:
continue
sign = 0
vis.add(i)
for j in range(i+1, len(s)):
# 如果遇到了同类，那么等下即使遇到了配对的，也不能立即配对
if s[j] == s[i]:
sign += 1
vis.add(j)
else:
sign -= 1
vis.add(j)
if sign == -1:
res += 1
break
return res
最新文章
- HDU 3033 分组背包变形（每种至少一个）
- jquery.form.js实现异步上传
- （二）Java对象与内存控制
- Android（java）学习笔记196：Android中Menu的使用（静态和动态）
- 为git配置ssh
- java中的IO流读取文件
- poj 1015 Jury Compromise_dp
- DrawerLayout、CoordinatorLayout、CollapsingToolbarLayout的使用--AndroidSupportDesign练手
- Java入门篇（三）——Java流程控制
- linux 常用命令及实例
- noj算法 装载问题 回溯法
- 虚拟主机、VPS、ECS云服务器 区别
- javascript 获取节点元素的封装
- 使用mui.js实现下拉刷新
- 在VMware中安装Mac OS
- update 中实现子查询
- 在CentOS上装Redis
- $.cookie is not a function;原因及解决办法
- SQL Server,MySQL,Oracle三者的区别
- 关于Cocos2d-x中定时器的使用总结