lcp330

统计桌面上的不同数字

方法一: Queue + HashSet

class Solution {
    public int distinctIntegers(int n) {
        Set<Integer> set = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int k = 0; k < size; ++k) {
                int x = queue.poll();
                for (int i = 1; i <= n; ++i) {
                    if (!set.contains(i) && x % i == 1) {
                        queue.offer(i);
                        set.add(i);
                    }
                }
            }
        }
        return set.size() + 1;
    }
}

猴子碰撞的方法数

方法一: 快速幂

class Solution {
    int MOD = (int) 1e9 + 7;
    public int monkeyMove(int n) {
        // 只有所有猴子沿着顺时针或者逆时针走，才不会发生碰撞，所以猴子至少发生 一次碰撞 的移动方法数为 Math.pow(2,n) - 2，考察快速幂
        long res = 1, x = 2;
        while (n > 0) {
            if (n % 2 == 1)
                res = res * x % MOD;
            x = x * x % MOD;
            n /= 2;
        }

        return (int) ((res - 2 + MOD) % MOD);
    }
}