【LeetCode】数学

等差数列 390. 消除游戏 - medium

【参考：390. 消除游戏 - 力扣（LeetCode）】

纯模拟会超时

class Solution {
    public int lastRemaining(int n) {
        List<Integer> list=new ArrayList<>();
        for(int i=0;i<n;i++){list.add(i+1);}
        int d=0;
        while(true){
            d++;
            if(d%2==1){
                for(int i=0;i<list.size();i++){
                    if(list.size()==1){return list.get(0);}
                    list.remove(i);
                }
            }
            else{
                for(int i=list.size()-1;i>=0;i-=2){
                    if(list.size()==1){return list.get(0);}
                    list.remove(i);
                }
            }
        }
    }
}

【参考：C++ 数学+找规律 - 消除游戏 - 力扣（LeetCode）】

class Solution {
    public int lastRemaining(int n) {
        int num=n; // 当前数组元素个数
        boolean left_to_right=true; // 判断此时是从左到右还是从右到左删除
        int a0=1; // 首项
        int d=1; // 公差
        while(num!=1){
            if(num%2==1){//num为奇数
                // a0=a0+d 是a0=a1=a0+d
                a0=a0+d;// 无论从左到右还是从右到左第一位都会被删，首项都会改变
            }
            else if(num%2==0){
               if(left_to_right)
                    a0=a0+d;//从左到右删首项会改变
               else
                    a0=a0;//从右到左删首项不变
            }
            left_to_right=!left_to_right;//每一轮改变删除方向
            d*=2; // 公差变大
            num/=2; // 个数向下取1/2
        }
        return a0;
    }
}