01 三除数

n 是三除数当且仅当它的除数为 1, n 和 sqrt(n)

class Solution {

    public boolean isThree(int n) {

        for (int i = 2; i * i <= n; i++) {

            if (n % i == 0) {

                return i * i == n;

            }

        }

        return false;

    }

}

02 你可以工作的最大周数

我们并不需要关心如何安排工作。只要工作量最大的任务不超过其他任务的总和，那么一定可以完成所有的任务，否则工作量最大的任务将会剩下一部分无法完成。

class Solution {

    public long numberOfWeeks(int[] milestones) {

        long sum = 0, max = 0;

        for (int i : milestones) {

            sum += i;

            max = Math.max(max, (long) i);

        }

        if (sum - max >= max) {

            return sum;

        }

        return sum - (max * 2 - sum - 1);

    }

}

03 收集足够苹果的最小花园周长

二分答案 + 数学推导。可以写出两层循环，然后数列求和，即可得到总的求和公式。

class Solution {

    public long minimumPerimeter(long neededApples) {

        long min = 1, max = (long) 100000;

        while (min + 1 < max) {

            long mid = (min + max) / 2;

            if (apples(mid) < neededApples) {

                min = mid;

            } else {

                max = mid;

            }

        }

        return (apples(min) >= neededApples ? min : max) * 8;

    }

​

    private long apples(long dis) {

        long result = 0;

//        for (long x = -dis; x <= dis; x++) {

//            for (long y = -dis; y <= dis; y++) {

//                result += Math.abs(x) + Math.abs(y);

//            }

//        }

        result += (1 + dis) dis (dis * 2 + 1);

        result += (1 + dis) dis (dis * 2 + 1);

        return result;

    }

}

​

04 统计特殊子序列的数目

递推即可。过程中记录 0 序列数量、01 序列数量、012 序列数量，令 dp[1] 表示 0 序列数量，dp[2] 表示 01 序列，dp[3] 表示 012 序列。

若当前位是 0，则可以增加 dp[1] + 1 个 0 序列

若当前位是 1，则可以增加 dp[2] + dp[1] 个 01 序列

若当前位是 2，则可以增加 dp[3] + dp[2] 个 012 序列

class Solution {

    public int countSpecialSubsequences(int[] nums) {

        long[] dp = {1, 0, 0, 0};

        for (int num : nums) {

            dp[num + 1] = (dp[num + 1] * 2 + dp[num]) % 1000000007L;

        }

        return (int) dp[3];

    }

}