[数据结构与算法]LeetCode 390. 消除游戏

??????390. 消除游戏

给定一个从1 到 n 排序的整数列表。
首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。
第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。
我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
返回长度为 n 的列表中，最后剩下的数字。

1.模拟，其实写起来还好，但是TLE了，题目也没给取值范围啊，可能是默认的Int?这样的话，O(N^2)时间复杂度是肯定不可能的了，只能想别的办法

class Solution {
    public int lastRemaining(int n) {
        //将1～n存入到temp中
        ArrayList<Integer> temp = new ArrayList<>();
        for(int i = 1;i <= n;i++){
            temp.add(i);
        }
        int index = 0;
        //模拟删除
        while(true){
            //判断index的奇偶
            if(index % 2 == 0){
                //从左到右进行删除
                for(int i = 0;i < temp.size();i++){
                    //如果当前temp的大小为1 直接返回
                    if(temp.size() == 1){
                        return temp.get(0);
                    }
                    //移除
                    temp.remove(i);
                }
            }
            
            else{
                //从右到左删除
                for(int i = temp.size()-1;i>=0;i = i-2){
                    if(temp.size() == 1){
                        return temp.get(0);
                    }
                    temp.remove(i);
                }
            }
            index++;
        }
    }
}

2.等差数列?

这个算法的核心点在于，隔一个删一个始终能保证数据能构成等差数列，反复删除但等差数列的性质能保证，最后删除到只剩下一个数，也就是最后的的a1

a1是等差数列开头第一个数，step是公差，cnt是当前剩下数字总数，k是轮次

class Solution {
    public int lastRemaining(int n) {
        int a1 = 1;
        int k = 0, cnt = n, step = 1;
        while (cnt > 1) {
            if (k % 2 == 0) { // 正向
                a1 = a1 + step;
            } else { // 反向
                a1 = (cnt % 2 == 0) ? a1 : a1 + step;
            }
            k++;
            cnt = cnt >> 1;
            step = step << 1;
        }
        return a1;
    }
}