1. 6430找出转圈游戏输家
    image.png
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public static int[] circularGameLosers(int n, int k) {
        HashSet<Integer> acceptBallList = new HashSet<>();
        int ac = 1,idx = 1;
        while (true){
            if(acceptBallList.contains(ac)) break;
            acceptBallList.add(ac);
            ac += ((idx++)*k);
            if(ac>n) ac = (ac%n)==0?n:(ac%n);
        }
        idx = 0;
        int[] answer = new int[n-acceptBallList.size()<0?0:n-acceptBallList.size()];
        for(int i=1;i<=n;i++) {
            if(!acceptBallList.contains(i)) answer[idx++] = i;
        }
        Arrays.sort(answer);
        return answer;
    }
    image.png
    单纯的模拟，不过下标应该从0开始的.从1开始要额外判断%n==0的情况，搞的多了几次没必要的错误提交

2.相邻值的按位异或

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    private  boolean handler(int[] o,int[] d){
        for(int i=0;i<d.length-1;i++){
            o[i+1] = d[i]^o[i];
        }
        if((o[0]^o[o.length-1])!=d[d.length-1]) return false;
        return true;
    }

    public boolean doesValidArrayExist(int[] derived) {
        int[] o = new int[derived.length];
        int endBit = derived[derived.length-1];
        if(endBit == 0){
            o[0] = o[derived.length-1] = 0;
            return handler(o,derived);
        }else {
            o[0] = 1;
            o[derived.length-1] = 0;
            return handler(o,derived);
        }
    }
}

image.png
推公式递推即可。
题目中说了如果i = n-1,那么derived[i] = original[i] ^ original[0];
基于这一条件，可以根据原数组中第n-1个元素确定original数组的 original[0],original[n-1]
记 endBit = derived[n-1] ,如果endBit = 0，那么original[0] = original[n-1] = 0 (0^0 = 0,当然都为1也可以)
如果 endBit = 1,那么original[0] = 0,original[n-1] = 1

于是基于这两个初始状态，可以递推出original内剩下元素
i从0开始，对于每个original[i+1]
由于 derived[i] = original[i] ^ original[i+1]
于是 original[i+1] = derived[i] ^ original[i]

最后判断推出的original是不是合法的,这一步只需要判断头尾即可（因为其他元素都是合法推出来的）

第三题dfs出来样例了，不知道怎么剪枝超时了。下周再战