Skip to content

Latest commit

 

History

History

0390.Elimination-Game

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

题目

You have a list arr of all integers in the range [1, n] sorted in a strictly increasing order. Apply the following algorithm on arr:

  • Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
  • Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
  • Keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Given the integer n, return the last number that remains in arr.

Example 1:

Input: n = 9
Output: 6
Explanation:
arr = [1, 2,3, 4,5, 6,7, 8,9]
arr = [2,4, 6,8]
arr = [2, 6]
arr = [6]

Example 2:

Input: n = 1
Output: 1

Constraints:

  • 1 <= n <= 109

题目大意

列表 arr 由在范围 [1, n] 中的所有整数组成,并按严格递增排序。请你对 arr 应用下述算法:

  • 从左到右,删除第一个数字,然后每隔一个数字删除一个,直到到达列表末尾。
  • 重复上面的步骤,但这次是从右到左。也就是,删除最右侧的数字,然后剩下的数字每隔一个删除一个。
  • 不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。

给你整数 n ,返回 arr 最后剩下的数字。

解题思路

  • 模拟题。按照题意,第一轮从左往右删除数字,第二轮从右往左删除数字。题目要求最后剩下的数字,模拟过程中不需要真的删除元素。只需要标记起始元素,该轮步长和方向即可。最后总元素只剩下一个即为所求。

代码

package leetcode

func lastRemaining(n int) int {
	start, dir, step := 1, true, 1
	for n > 1 {
		if dir { // 正向
			start += step
		} else { // 反向
			if n%2 == 1 {
				start += step
			}
		}
		dir = !dir
		n >>= 1
		step <<= 1
	}
	return start
}