算法：数学问题

204 计数质数
快速计算小于n的质数个数的厄拉多塞筛法：
先将 2－N 的各数放入表中，然后在 2 的上面画一个圆圈，然后划去 2 的其他倍数；第一个既未画圈又没有被划去的数是 3，将它画圈，再划去 3 的其他倍数；现在既未画圈又没有被划去的第一个数是 5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于N的各数都画了圈或划去为止。

    public int countPrimes(int n){
        int i = 2;
        int num[] = new int[n];
        while (i < n){
            if (num[i] == 0) {
                num[i] = 1;
                for (int j = i + i; j < n; j += i) {
                    num[j] = -1;
                }
            }
            i++;
        }
        int count = 0;
        for (int j = 2; j<n; j++){
            if (num[j] == 1){
                count++;
            }
        }
        return count;
    }

326 3的幂
进制转换：将n转换为三进制数，然后判断其是否符合“100...0”的格式

    public boolean isPowerOfThree(int n) {
        return Integer.toString(n, 3).matches("^10*$");
    }

整数限制：int范围内，最大的3的幂是 $3^{19}$ ，因此所有的3的幂都是这个数的除数。

  public class Solution {
      public boolean isPowerOfThree(int n) {
          return n > 0 && 1162261467 % n == 0;
      }
  }

50 Pow(x, n)
快速幂算法：
$x^n = \begin{cases} x^{n/2}*x^{n/2}& {even}\\ x^{n/2}*x^{n/2}*x& {odd}\end{cases}$

private double fastPow(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        double half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        return fastPow(x, N);
    }

69 x 的平方根
牛顿迭代法：使用函数的切线来近似计算函数零值
本题中求 $y=x^2$ ，可令 $f(x) = x^2-y$ ，从 $x_0$ 点开始迭代，
$x_0$ 的切线函数为 $g(x) = f(x_0)+(x-x_0)f’(x_0)$ ，
取 $g(x)=0$ ，得 $x = \frac12(x_0+\frac{y}{x_0})$ ，令 $x = x_0$
迭代，直到x_0变化很小。

    def mySqrt(self, x):
        if x < 0:
            raise Exception('不能输入负数')
        if x == 0:
            return 0
        # 起始的时候在 1 ，这可以比较随意设置
        cur = 1
        while True:
            pre = cur
            cur = (cur + x / cur) / 2
            if abs(cur - pre) < 1e-6:
                return int(cur)

166 分数到小数
长除法：每次比对当前余数是否出现过，若出现，则得到循环节；否则，添加商，重置被除数。

        ...
        while (!rems.contains(num)){
            rems.add(num);
            num *= 10;
            quo = num / sor;
            num = num % sor;
            res += quo;
            if (num == 0) {
                if (numerator>0^denominator>0)
                    return "-" + res;
                else
                    return res;
            }
        }
        ...

最后编辑于：2019.08.13 14:28:28