脚本宝典收集整理的这篇文章主要介绍了leetcode每日一题390.消除游戏 暴力的数学之美一边就懂 由浅入深,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
📖本篇内容:leetcode每日一题390.消除游戏 暴力的数学之美一边就懂 由浅入深 📆 最近更新:2022年1月1日 leetcode每日一题2022. 将一维数组转变成二维数组 2022年从2022题开始 由1到2我相信咱们会更好 🙊个人简介:一只二本院校在读的大三程序猿,本着注重基础,打卡算法,分享技术作为个人的经验总结性的博文博主,虽然可能有时会犯懒,但是还是会坚持下去的,如果你很喜欢博文的话,建议看下面一行~(疯狂暗示QwQ) 🌇 点赞 👍 收藏 ⭐留言 📝 一键三连 关爱程序猿,从你我做起
小付在元旦节吃好喝好玩好,不知各位是如何度过这新年的第一天呢?到了第二天了,不要忘记打卡哦~,今天玩得是消除游戏,话不多说,打卡!
- 消除游戏
列表 arr 由在范围 [1, n] 中的所有整数组成,并按严格递增排序。请你对 arr 应用下述算法: 从左到右,删除第一个数字,然后每隔一个数字删除一个,直到到达列表末尾。 重复上面的步骤,但这次是从右到左。也就是,删除最右侧的数字,然后剩下的数字每隔一个删除一个。 不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。 给你整数 n ,返回 arr 最后剩下的数字。
示例1:
输入:n = 9
输出:6
解释:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]
示例2:
输入:n = 1
输出:1
小付刚看到这题的时候还是午觉睡醒的时候,整个脑子木的很,直接暴力遍历来模拟 但是我忘记了这种中等题一般还要考虑
超时
这个问题了,所以就出现了.
class Solution {
public int lastRemaining(int n) {
boolean left = true;
List<Integer> list = new ArrayList<>();
//初始化
for (int i = 1; i<=n; i++){
list.add(i);
}
while(true){
if (left){
//当从左往右开始消除的时候
for (int i = 0;i<list.size();i++){
if (list.size() == 1)return list.get(0);
list.remove(i);
}
}else{
//当从右往左开始消除的时候
for (int i = list.size()-1;i>=0;i-=2){
if(list.size() == 1)return list.get(0);
list.remove(i);
}
}
//更换方向
left = !left;
}
}
}
不出意外 你会得到一个
超时
的错误 ,但是 暴力真的无法解决么? 我们再来找找规律!
例题:咱们来手动模拟 如n = 20 时 如何解决呢? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 经过第一次消除! 还是用 left 来进行判读是为从左往右还是从右往左 第一次消除之后得到:(从左往右) 2 4 6 8 10 12 14 16 18 20 第二次消除之后得到:(从右往左) 2 6 10 14 18 第三次消除之后得到:(从左往右) 6 14 第四次消除之后得到:(从右往左) 6 所以返回 6 那么我们将返回的值作为 结果值 将其定为 变量
res
这个变量从一开始在 1 的位置 经过每次(从左往右)都在变化,但是从右往左并未变化(这道例题中没有变化,但实际的是如果此时从右向左遍历与2取模为1则需要向后移动)我们得到的 n 也在每次 减半 每次移动的值都是前一次移动的倍数。所以代码实现如下:
class Solution {
public int lastRemaining(int n) {
//需要返回结果值的位置
int res = 1;
//初始的移动长度
int step = 1;
//判断从左往右还是从右往左
boolean left = true;
while (n > 1){
//只有当从左边或者右边余数为1时才进行步长移动
if (left || n % 2 == 1){
res += step;
}
// n 数量减半
n = n >> 1;
// 步长加倍
step = step << 1;
// 方向转换
left = !left;
}
return res;
}
}
打卡2022 - 01 -02 !
加油!坚持每天打卡~
最后
每天进步点 每天收获点
愿诸君 事业有成 学有所获
如果觉得不错 别忘啦一键三连哦~
以上是脚本宝典为你收集整理的leetcode每日一题390.消除游戏 暴力的数学之美一边就懂 由浅入深全部内容,希望文章能够帮你解决leetcode每日一题390.消除游戏 暴力的数学之美一边就懂 由浅入深所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。