⭐️寒假新坑——代码之狐的每日做题笔记
1996. 游戏中弱角色的数量-Mid
题目描述:
你正在参加一个多角色游戏,每个角色都有两个主要属性:攻击 和 防御 。给你一个二维整数数组 properties
,其中 properties[i] = [attacki, defensei]
表示游戏中第 i
个角色的属性。
如果存在一个其他角色的攻击和防御等级 都严格高于 该角色的攻击和防御等级,则认为该角色为 弱角色 。更正式地,如果认为角色 i
弱于 存在的另一个角色 j
,那么 attackj > attacki
且 defensej > defensei
。
返回 弱角色 的数量。
解题思路:
按照攻击属性从大到小,若相同按照防御属性从小到大排序
排序后,标号为i的角色的攻击力总是小于等于前一个,因此只需要判断前面的角色防御力是否有比i高即可,并且由于相同攻击按防御值从小到达,因此前i个角色中,最高防御值(如果大于i的防御力)的角色其不可能和i攻击力相同,如果存在该角色,i可视为弱角色。
根据以上推断,我们每次判断缓存和更新当前最大防御力,每次判断角色i的防御力是否低于当前最大防御力,低于则弱角色个数++,否则更新最大防御力。
代码实现:
class Solution {
public int numberOfWeakCharacters(int[][] properties) {
//根据规则排序,自定义比较器见下
Arrays.sort(properties,new MyComparator());
//分别保存答案和当前最大防御力
int ans=0;
int max=0;
//循环判定
for(int i=0;i<properties.length;i++){
if(i==0){
max=properties[0][1];
}
if(i!=0&&(properties[i][1]<max)){
ans++;
}
else{
max=properties[i][1];
}
}
return ans;
}
//自定义比较器
class MyComparator implements Comparator<int[]>{
public int compare(int[] a, int[] b) {
//如果a的攻击力小,a后置,即按攻击力降序排列
if(a[0]<b[0]){
return 1;
}
else if(a[0]==b[0]){
//如果攻击力相同,a的防御力大,a后置,攻击力相同按防御力升序排列
if(a[1]>b[1]){
return 1;
}
}
return -1;
}
}
}
结尾
题目来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems
⭐️关注作者,带你刷题,从简单的算法题了解最常用的算法技能(寒假每日一题)
⭐️关注作者刷题——简单到进阶,让你不知不觉成为无情的刷题机器,有问题请私信