数字游戏"/>
用Java实现消除数字游戏
用Java实现消除数字游戏
1.题目描述:
数字消除游戏(Leetcode第390题)
列表 arr 由在范围 [1, n] 中的所有整数组成,并按严格递增排序。请你对 arr 应用下述算法:
从左到右,删除第一个数字,然后每隔一个数字删除一个,直到到达列表末尾。
重复上面的步骤,但这次是从右到左。也就是,删除最右侧的数字,然后剩下的数字每隔一个删除一个。
不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。
给你整数 n ,返回 arr 最后剩下的数字
2.题目解读:
-
首先数列为严格递增排序,无论从左向右删还是从右向左删,都是隔一个删一个,故每次删除后的数列都是等差数列。
-
思路:最后只剩下一个数字,假设我们每次追踪新数列的首元素,当数列只剩下一个数字时,该数字也是该数列的首元素
-
每删除一次,公差+1,数列长度变为原来一半
-
当删除次数为偶数时,从左向右删,必然首元素被删(其中当数列为奇数个时,首元素尾元素都会被删除,当数列为偶数个数时,只删除首元素,故只要是从左向右删)
-
当删除次数为奇数时,从右向左删,当数列为奇数个时,首尾元素都被删除,当数列为偶数个数时,首元素不变,只删除尾元素
3.Java代码
public class Leetcode_T390 {public int lastRemaining(int n) {
// a为每次删除后的第一个元素,n为元素个数,step为公差,k为删除次数int a = 1, count = n, step = 1, k = 0;while(count > 1){if(k % 2 == 0) {
// 从左向右删,如果为奇数个,首尾都删,偶数个只删头,故首元素必然会变为它的下下一个a = a + step;}else{
// 从右向左删,如果为奇数个,首尾都删,偶数个只删尾节点不删头节点a = count % 2 == 1 ? a+step : a;}k++;count = count >> 1;step = step << 1;}return a;}}
更多推荐
用Java实现消除数字游戏
发布评论