当前位置:网站首页>情侣牵手[贪心 & 抽象]
情侣牵手[贪心 & 抽象]
2022-08-04 23:36:00 【REN_林森】
前言
贪心是考察分析能力的好题,尤其是带干扰性的,即需要我们将有用信息提取,去伪存真,将问题能够抽象出来。动态规划也是一样,如果没有抽象思维提取要害信息,则定义不出状态,自然也找不到状态如何转移。当然阅读理解题/脑筋急转弯,就更需要这种抽象有用信息的能力。
一、情侣牵手
二、贪心&抽象
package everyday.hard;
// 情侣牵手。
public class MinSwapsCouples {
/* 抽象思维:其实我们并不关心1/2/3...这些位置,我们只关心特殊的相邻关系<0,1><2,3>。 那么一对特殊位置<x,y>,有2种情况。一是情侣则不管;二不是情侣,可以换走1个人,也可换走2个人。 由于我们只关心相邻位置,即把两对情侣的男生换掉,换个角度看,其实也可看成把两个女生换掉,所以我们在乎的是相邻对,而不是特别的位置。 所以,根据贪心,换1人的做法是最好的,留下一个人,就少换一次。 */
public int minSwapsCouples(int[] row) {
int cnt = 0;
for (int i = 0; i < row.length; i += 2) {
int target = (row[i] & 1) == 0 ? row[i] + 1 : row[i] - 1;
if (target == row[i + 1]) continue;
findAndSwap(row, i + 1, target);
cnt++;
}
return cnt;
}
private void findAndSwap(int[] row, int begin, int target) {
int i = begin + 1;
while (i < row.length && target != row[i]) ++i;
row[i] = row[begin];
row[begin] = target;
}
}
总结
1)多练习贪心题,锻炼分析能力 & 信息加工能力 & 信息提取与转换能力。
参考文献
[1] LeetCode 情侣牵手
边栏推荐
猜你喜欢
一点点读懂thermal(一)
从单体架构迁移到 CQRS 后,我觉得 DDD 并不可怕
The market value of 360 has evaporated by 390 billion in four years. Can government and enterprise security save lives?
怎么将自己新文章自动推送给自己的粉丝(巨简单,学不会来打我)
Develop a SpaceX website based on the Appian low-code platform
Pytorch分布式训练/多卡/多GPU训练DDP的torch.distributed.launch和torchrun
PID控制器改进笔记之七:改进PID控制器之防超调设定
【无标题】线程三连鞭之“线程池”
大师教你3D实时角色制作流程,游戏建模流程分享
KT148A语音芯片怎么烧录语音进入芯片里面通过串口和电脑端的工具
随机推荐
Day118.尚医通:订单列表、详情、支付
Service Mesh landing path
当panic或者die被执行时,或者发生未定义指令时,如何被回调到
Service Mesh落地路径
建模师经验分享:模型学习方法
The market value of 360 has evaporated by 390 billion in four years. Can government and enterprise security save lives?
七牛云图片上传
未来我们还需要浏览器吗?(feat. 枫言枫语)
956. 最高的广告牌
PZK学C语言之字符串函数(一)
请你说一下final关键字以及static关键字
功耗控制之DVFS介绍
KT148A电子语音芯片ic方案适用的场景以及常见产品类型
【七夕情人节特效】-- canvas实现满屏爱心
Literature reading ten - Detect Rumors on Twitter by Promoting Information Campaigns with Generative Adversarial Learn
应用联合、体系化推进。集团型化工企业数字化转型路径
407. 接雨水 II
一点点读懂cpufreq(二)
使用代理对象执行实现类目标方法异常
Shell expect real cases