力扣第 252 场周赛解题报告

NO1. 三除数

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;
    }
}

NO.2 你能够工作的最大周数

咱们并不需要关怀如何安顿工作。只有工作量最大的工作不超过其余工作的总和，那么肯定能够实现所有的工作，否则工作量最大的工作将会剩下一部分无奈实现。

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);
    }
}

NO.3 收集足够苹果的最小花园周长

二分答案 + 数学推导。能够写出两层循环，而后数列求和，即可失去总的求和公式。

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;
    }
}

NO.4 统计非凡子序列的数目

递推即可。过程中记录 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];
    }
}