质数与快速幂

埃氏筛（LeetCode 204）

public int countPrimes(int n) {
    boolean[] notPrime = new boolean[n];
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (!notPrime[i]) {
            count++;
            for (long j = (long)i*i; j < n; j += i)
                notPrime[(int)j] = true;
        }
    }
    return count;
}

快速幂（LeetCode 50）

public double myPow(double x, int n) {
    long N = n;
    if (N < 0) { x = 1 / x; N = -N; }
    double result = 1;
    while (N > 0) {
        if ((N & 1) == 1) result *= x;
        x *= x; N >>= 1;
    }
    return result;
}

丑数（LeetCode 264）

三路归并维护三个指针：

public int nthUglyNumber(int n) {
    int[] ugly = new int[n];
    ugly[0] = 1;
    int p2 = 0, p3 = 0, p5 = 0;
    for (int i = 1; i < n; i++) {
        int next = Math.min(ugly[p2]*2, Math.min(ugly[p3]*3, ugly[p5]*5));
        ugly[i] = next;
        if (next == ugly[p2]*2) p2++;
        if (next == ugly[p3]*3) p3++;
        if (next == ugly[p5]*5) p5++;
    }
    return ugly[n-1];
}

快乐数（LeetCode 202）

快慢指针检测循环：

public boolean isHappy(int n) {
    int slow = n, fast = next(n);
    while (fast != 1 && slow != fast) {
        slow = next(slow); fast = next(next(fast));
    }
    return fast == 1;
}
private int next(int n) {
    int s = 0;
    while (n > 0) { int d = n % 10; s += d*d; n /= 10; }
    return s;
}