leetcode390.Elimination Game

朱雀 2022-03-06 23:56 168阅读 0赞

## 题目要求 ##

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

假设有1-n一共n个数字，从左往右开始每隔一位删除一个数字，到达最右侧后，再从右往左每隔一位删除一个数字，如此反复，直到剩下最后一个数字。问最后剩下的数字是多少。

## 思路一：递归 ##

先从一个例子入手，当n等于7时，数字序列为1,2,3,4,5,6,7, 删除序列如下：

1 2 3 4 5 6 7
      2   4   6
          4

可以看到，第一轮删除后剩下的2，4，6就相当于是1，2，3的两倍，我们可以等价于从右往左删除1，2，3后剩余的结果乘2。由此可见，假如我们定义一个递归函数f(n, left),我们可以有f(n/2, right)来获取结果。

public int lastRemaining(int n) {
            return lastRemaining(n, true);
        }
        
        public int lastRemaining(int n, boolean left) {
            if(n == 1) {
                return 1;
            }
            if(n % 2 == 1) {
                return lastRemaining(n / 2, !left) * 2;
            }else{
                if( left ) {
                    return lastRemaining(n/2, !left) * 2;
                }else {
                    return lastRemaining(n/2, !left) * 2 -1;
                }
            }
        }

## 思路二 ##

这里其实存在一个镜像删除的问题，也就是说，对于任何一个1~n的序列来说，从左往右开始删除和从右往左开始删除剩余的结果的和一定为(n+1)，也就是所谓的镜像删除问题。  
举个例子：

从左往右开始删除
    1 2 3 4 5 6
      2   4   6
          4
          
    从右往左开始删除
    1 2 3 4 5 6
    1   3   5
        3

可以看到二者剩余的值加起来一定为n+1即7。  
根据这个原理，我们可以优化上面的递归，无需再利用left值来标记是从左往右删除还是从右往左删除，直接执行镜像删除即可。

public int lastRemaining2(int n) {
            return n == 1 ? 1 : (1 + n / 2 - lastRemaining2(n/2)) * 2;
        }