力扣1996. 游戏中弱角色的数量(#Day22)
2023-02-18 16:23:56 时间
力扣1996. 游戏中弱角色的数量
题目中对于弱角色的定义是:如果存在一个其他角色的攻击和防御均高于该角色,则这个角色是弱角色。我的想法是用哈希表的键来存储攻击力,哈希表的值用一个列表存放防御力,然后根据攻击力进行排序,并记录当前最高的防御力。由于攻击力已经按从大到小排好,那么找弱角色的逻辑就是只要这个角色的防御力比最大防御力小(伤害溢出),就满足弱角色,计数加一。
from typing import List
from collections import defaultdict
def numberOfWeakCharacters(properties: List[List[int]]) -> int:
res = 0
prop_map = defaultdict(list)
max_defence = 0
# {攻击力:[防御力,]}
for attack, defence in properties:
prop_map[attack].append(defence)
# 按攻击力对哈希表排序
for attack in sorted(prop_map, reverse=True):
for defence in prop_map[attack]:
if defence < max_defence:
res += 1
# 维护最大防御力
max_defence = max(max_defence, max(prop_map[attack]))
return res
properties = [[1, 5], [10, 4], [4, 3], [1, 2]]
print(numberOfWeakCharacters(properties)) # 2
还可以使用排序+双指针来实现,先给properties安排一波原地排序,按攻击力和防御力由大到小。一个指针用来遍历角色并维护当前遍历到的攻击力(之前最高的防御力),另一个指针维护与第一个指针攻击力相同的怪的防御力(当前攻击力下的防御力),统计弱角色的个数。
def double_pointer_solution(properties: List[List[int]]) -> int:
properties.sort(key=lambda x: (-x[0], -x[1])) # 按攻击力由大到小,按防御力由大到小
res = 0
max_defence = 0
i = 0
while i < len(properties): # i指针遍历角色的攻击力
j, cur_max, max_defence = i, max_defence, max(
max_defence, properties[i][1]) # 取当前最大防御力和该角色防御力间的最大值
# j指针在攻击力相等的情况维护当前攻击力下的防御力
while j < len(properties) and properties[j][0] == properties[i][0]:
if properties[j][1] < cur_max:
res += 1 # 满足伤害溢出
j += 1
i = j
return res
properties = [[1, 5], [10, 4], [4, 3], [1, 2]]
print(double_pointer_solution(properties)) # 2
END
相关文章
- 「虚拟员工」加速普及,小冰公司再融10亿元
- OceanBase社区版4.0正式上线,与企业版同等性能,一键安装两分钟跑通Demo
- 沉浸式体验飞鸟的快乐:从一张照片生成3D航拍视频
- 人脸神经辐射场的掩码编辑方法NeRFFaceEditing,不会三维建模也能编辑立体人脸
- 不能飞的风火轮!用AI造出世界最快的鞋子,时速最高11公里
- Diffusion预训练成本降低6.5倍,微调硬件成本降低7倍!Colossal-AI完整开源方案低成本加速AIGC产业落地
- NeurIPS 2022 | 如何正确定义测试阶段训练?顺序推理和域适应聚类方法
- 把Stable Diffusion模型塞进iPhone里,做成APP一分钟出图
- 国产手机芯二代标杆:vivo自研芯片V2出炉,将随X90月底发布
- 元宇宙的前世今生,业内大佬带你一遍过!
- 2022-12-15:寻找用户推荐人。写一个查询语句,返回一个客户列表,列表中客户的推荐人的编号都 不是 2。 对于示例数据,结果为: +------+ | n
- 2022RubyMine激活码(2022RubyMine最新激活码)2022RubyMine激活码
- Xilinx Zynq7035算力指标
- Hybrid模式下的热更新技术方案
- 电商收付通系统,可视化进件二级商户
- TKE/EKS集群通过logrotate切割nginx-ingress访问日志
- 给hash表分片:降低锁粒度,提高锁性能
- React渲染机制
- React源码之useState,useReducer
- React Context源码解读