p390

发表于 | 分类于 |

LeetCode p390 Elimination Game 题解

1.题目：

There is a list of sorted integers from 1 to n. 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 right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:

Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

Output:
6

题意：

一个循环删数操作，首先从左边开始每隔一个数删一次，然后从右边开始每隔一个数删一次。
重复以上操作，求最后留下来那个数。

2.解题思路:

先仰望各种大大一行AC的代码。。
然后。。理解无能TUT
最后采用这种方法：
假设头是被留下来的，每一次操作之后更新头部的位置。
具体就是判断头部是否会被删掉，如果会，头部更新到下一个位置。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
public class Solution {
    public int lastRemaining(int n) {
        boolean left = true;
		int head = 1;
		int r = n;
		int step = 1;
		while (r > 1) {
			if (left || r % 2 == 1) {
				head += step;
			}
			step = step * 2;
			left = !left;
			r = r / 2;
		}
		return head;
    }
}

4.一些总结：