390. Elimination Game

发表于 | 分类于

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:

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

解法1： Recursion

观察可以发现，对于[1,2,3,4,5,6,7,8,9] 这个数组，第一遍从左到右去掉之后得到的是[2,4,6,8],这个时候需要从右往左。
那么她的结果也就是可以看成是两倍的right(1,2,3,4)。
同理，这个(1,2,3,4)又可以看成是从左到右的(1,2),不过这里要区分一下奇数和偶数的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lastRemaining(int n) {
        return left2Right(n);
    }
    private int left2Right(int n) {
        if (n <= 2) return n;
        return 2 * right2Left(n / 2);
    }
    private int right2Left(int n) {
        if (n <= 2) return 1;
        // differentiate between odd and even cases
        if (n % 2 == 1) {
            return 2 * left2Right(n / 2);
        } else {
            return 2 * left2Right(n / 2) - 1;
        }
    }
}

解法2： Iteration TLE

也可以用约瑟夫环的类似的解法取去模拟删除的过程。不过大数据的时候就TLE了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public int lastRemaining(int n) {
        if (n <= 2) return n;
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        ListIterator<Integer> iterator = list.listIterator();
        boolean left2Right = true;
        iterator.next();    // starting from the starting point
        while (list.size() > 1) {
            iterator.remove();
            if (left2Right) {
                if (iterator.hasNext()) {
                    iterator.next();
                    if (iterator.hasNext()) {
                        iterator.next();
                    } else {
                        left2Right = false;
                        iterator.previous();
                    }
                } else {
                    left2Right = false;
                    iterator.previous();
                }
            } else {
                if (iterator.hasPrevious()) {
                    iterator.previous();
                    if (iterator.hasPrevious()) {
                        iterator.previous();
                    } else {
                        left2Right = true;
                        iterator.next();
                    }
                } else {
                    left2Right = true;
                    iterator.next();
                }
            }
        }
        return list.get(0);
    }
}