Leetcode之Math

Contents

1. 258 Add Digits
2. 202 Happy Number
3. 263 Ugly Number
4. 204 Count Primes

Leetcode之Math部分几题：258 Add Digits 各位求和，复杂度O(1)的就是有规律的，能推导出公式的；202 Happy Number 各位求平方和，终止条件会用上HashSet或Floyd（龟兔）判断状态循环；263 Ugly Number 主要涉及分解质约数；204 Count Primes 数素数个数，可巧用埃氏筛法的去除合数来优化。

258 Add Digits

https://leetcode.com/problems/add-digits/
标签： Math

题目：把一个数的各位数求和，循环这个过程，直到结果只有一个数字，返回这个数字。例如38->3+8=11->1+1=2。

容易想到的普通解法：

public class Solution {

    public int addDigits(int num) {
        while(num>=10){
            num=cal(num);
        }
        return num;

    }
    public int cal(int num){
        int sum=0;
        while(num>0){
            int x=num%10;
            num=num/10;
            sum=sum+x;
        }
        return sum;
    }

}

这个算法的效率至少也要$\Omega(n)$，$n$为数字的位数，而题目继续问 Could you do it without any loop/recursion in O(1) runtime?

一般，复杂度$O(1)$的就是有规律的，能推导出公式的。如11->2，12->3，规律来了！

其实这是著名的数根，用途包括：

数根可以计算模运算的同余，对于非常大的数字的情况下可以节省很多时间。如38的数根是2，38%9=2%9=2。（在此想起了小学时老师教判断一个数是否可被3正除，可把该数各位求和，和若可被3正除，则该数为3倍数，这应该也正是来源于数根的原理？）

数字根可作为一种检验计算正确性的方法。例如，两数字的和的数根等于两数字分别的数根的和。

另外，数根也可以用来判断数字的整除性，

总结一下，用$dr(n)$表示$n$的数根，则公式有：
$$
dr(n) =
\begin{cases}
0, & \text{if $n=0$} \\
9, & \text{if $n\neq 0$ and $n\equiv 0 \pmod 9$}\\
n\bmod 9, & \text{if $n\not\equiv 0 \pmod 9$}
\end{cases}
$$
其中 $n\equiv 0 \pmod 9$表示$n$和$0$对于模$9$同余，即$n\bmod 9=0\bmod 9=0$。则复杂度$O(1)$的算法代码如下：

public class Solution {

    public int addDigits(int num) {
	    if(num==0) return 0;
	    else if(num%9==0) return 9;
	    else return num%9;
    }
}

还可以继续归纳出
$$
\mbox{dr}(n) = 1\ +\ ((n-1)\ {\rm mod}\ 9)
$$
以及
$$
dr(n)=n-9\left\lfloor\frac{n-1}{9}\right\rfloor.
$$

202 Happy Number

https://leetcode.com/problems/happy-number/
标签：Math|HashTable

题目：把一个数的各位数求平方和，循环这个过程，直到结果为1返回true或无限循环返回false。
要注意循环终止条件与258 Add Digits不同，有两个终止条件。无限循环并不一定回到最初的数，注意挖掘循环的规则。

例如：

7->49->97->130->10->1，返回true
4->16->37->58->89->145->42->20->4，返回false
2->4->…->4，返回false

因此循环过程需要用上HashTable的数据结构，存储经历过的数。

public class Solution {
   public boolean isHappy(int n) {
		Set set = new HashSet();
		while (true) {
			System.out.println(n);
			if (set.contains(n)) //如果set中已有某数，表示陷入无限循环
				return false; 
			else {
				set.add(n);      //否则，将数加入set
				n = cal(n);      //求各位平方和
				if (n == 1)
					return true;
			}
		} 
	}

	public int cal(int num) {
		int squareSum = 0;
		while (num > 0) {
			int yushu = num % 10;
			num /= 10;
			squareSum += yushu * yushu;
		}
		return squareSum;
	}
}

在Discuss中还有一种得票最高的空间复杂度$O(1)$的算法用的是Floyd判圈算法（Floyd Cycle detection），又称龟兔赛跑算法。

Floyd判圈算法的应用包括：

对于有限状态机与链表，可以判断从某个起点开始是否会返回到访问过运行过程中的某个状态和节点。
对于迭代函数，可以判断其是否存在周期，以及求出其最小正周期。

算法思想可以用龟兔赛跑的例子来解释，龟兔同时从$S$点出发，如果赛道有环，设环的长度为$l$，且环起始点为$C$，那么快的一方总能追上慢的一方，设相遇点为$P$。如果赛道没环，兔子将一路领先到达终点。

还可以进一步推导，龟兔相遇时（乌龟一旦进入环后一圈内就会相遇）有
$$
\begin{cases}
S_t=|\vec{SC}|+n×l+|\vec{CP}|\\
S_g=|\vec{SC}|+m×l+|\vec{CP}|\\
S_t=2×S_g\
m=0
\end{cases}
$$
得到$S_g=n×l$，相遇时乌龟总路程，即是兔子多跑的路的长度是兔子跑圈的总长度。

(1) 判断环的存在
假设在一个单位时间内，兔子跑2格，乌龟跑1格（两步或多步效果是等价的，只要一个比另一个快就行），同时出发，如果两者在之后的某一点相遇了，那么说明链表有环，否则，如果兔子到达了链表的结尾，那么说明没环。
以下图为例：

因为乌龟进入环后，在一圈之内肯定与兔子相遇，因此时间复杂度$O(|\vec{SC}|+l)$。空间复杂度为$O(1)$，是常数空间的算法。

(2) 求环的长度
确定有环后，再让乌龟从$P$点开始跑一圈，还会返回$P$点，这一次的推进的步数就是环的长度。

注：既不需要求环起始点（已知环起始点，那从起始点跑一圈回来的长度就是环长度），也不需要龟兔第二次追击相遇（龟兔从环内出发的追击相遇，兔子比乌龟只会多一圈）。

(3) 求环的起始点
从上图看，$|\vec{SC}|=|\vec{PC}|$，这并不是巧合。
之前推导得到了$S_g=n×l$。式子$S_g+|\vec{PC}|$表示乌龟从$P$继续走到$C$。式子$S_g+|\vec{SC}|=n×l+|\vec{SC}|$表示乌龟从$P$点再走$|\vec{SC}|$，该式交换后$|\vec{SC}|+n×l$又可视为从$S$直接到$C$点后环绕几圈，即乌龟从$P$点再走$|\vec{SC}|$也是到$C$。因此有$|\vec{SC}|=|\vec{PC}|$。
综上，求环起始点的算法只要令乌龟、兔子分别从$P$、$S$点都1格1格地前进，相遇的地方即是环起始点$C$。
参考

用Floyd判圈算法解此题的代码为：

public class Solution {
   public boolean isHappy(int n) {
		int slow, fast;
		slow = fast = n;
		do {
			slow = cal(slow);
			fast = cal(cal(fast));
		} while (slow != fast);
		return slow == 1;
	}

	public int cal(int num) {
		int squareSum = 0;
		while (num > 0) {
			int yushu = num % 10;
			num /= 10;
			squareSum += yushu * yushu;
		}
		return squareSum;
	}
}

263 Ugly Number

https://leetcode.com/problems/ugly-number/
标签：Math

如果一个数的质约数只有2、3和5，则返回true，否则返回false。如20为true，14为false。还要注意一些特殊值，如0为false，1为false。

这题的核心原理是分解质约数，方法是用短除法，从最小的质数除起，一直除到结果为质数为止。

分解质因数算法思想是，将数num，除尽从2到num的约数，即除尽2，除尽3，除尽4，……，除尽num。除尽4其实无意义，因为先除尽2，但这有效地避免了检验4是否为质数的步骤。另外要注意质数的质约数含有它本身，因此是小于等于。

public List decomposePrimeFactors(int num) {
	List list=new ArrayList();
	for (int i = 2; i <= num; i++) {
		while (num % i == 0) {  //除尽i
			list.add(i);
			num = num / i;
		}
	}
	return list;
}

对本题，可以求出所有质因数，再检查质约数是否只有2、3和5。也可以改造分解质约数的过程，在除尽2、3和5后，如果num为1，则不可能有其他质约数，否则还有其他质约数。代码如下参考：

public boolean isUgly(int num) {
	if (num == 0)    //避免陷入死循环
		return false;
	for (int i = 2; i < 6; i++) {
		while (num % i == 0) {
			num = num / i;
		}
	}
	return num == 1;
}

拓展：求两数的公约数、公倍数。参考

204 Count Primes

https://leetcode.com/problems/count-primes/
标签：HashTable|Math

题目：数出小于非负数n的素数个数并返回。例如，小于12的素数有2、3、5、7、11，共5个。

容易想到的一种算法是用函数isPrime判断每一个小于n的数是否为素数。isPrime(n)要考虑num是否满足“除了1和它本身外，不能被其他自然数整除”的素质性质。如果“其他自然数”要从$2$考虑到$n-1$，复杂度就是$O(n)$；进一步省去对称的乘式，就只需要从2考虑到$\sqrt{n}$，复杂度将为$O(n^{0.5})$。

public boolean isPrime(int num){
	if(num <= 1) return false;
	for(int i = 2; i * i <= num; i++){
		if(num % i == 0) return false;
	}
	return true;
}

终止条件用的是i * i <= num而不是i <= sqrt(num)，可以比较有效加快速度。将isPrime用于判断每一个小于n的数，这种算法总的时间复杂度是$O(n^{1.5})$。

埃拉托斯特尼筛法（sieve of Eratosthenes），一种更快的简单检定素数的算法。基本思想是筛除掉各个数的倍数，也就是合数，那剩下的就必然都是素数了。

例如找出30以内的素数。先考虑2，倍数4、6、8、10、12等都不是素数，划去；考虑3，倍数有6、9、12等，划去；考虑4，倍数有8、12等……；考虑29，但倍数都大于30。最后剩下的未被划去的就是30以内的素数。

代码如下所示：

1
2
3

for(int i = 2; i < n; i++)
	for(int j = 2; i * j < n; j++)
		primeArr[i * j] = false;

空间复杂度$O(n)$，时间复杂度是$O(\frac{n}{2}-1+\frac{n}{3}-1+\ldots+\frac{n}{n-1}-1)$，化简得到$O\big(n(1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{n-1})-2n+2\big)$，由欧拉公式得$O\big(n(\ln(n-1)+C)-2n+2\big)$，$C$是欧拉常数，化简后是$O(n\ln{n})$。

进一步优化：

2的3倍和3的2倍都是6，没有必要两次划去6。因此考虑数$x$时，$x×2,x×3$等可能都被划去，只需要划去倍数$x×x,x×(x+1)$等就可以了。
4的倍数实际被2的倍数覆盖，且在考虑2时划去。因此被划去的数就直接跳过。
由优化1产生的，对$x×x$大于30，无需考虑，此时剩下的未被划去的就是30以内的素数。

数素数

埃氏筛法的Java代码如下：

public class Solution {
    public int countPrimes(int n) {
        boolean[] primeArr = new boolean[n];
        Arrays.fill(primeArr, true);
        
		for(int i = 2; i * i < n; i++){         //优化3
			if(!primeArr[i]) continue;    //优化2
			for(int j = i; i * j < n; j++)      //优化1
				primeArr[i * j] = false;
		}
		
		//数素数个数，也可以放到筛选过程中
        int count = 0;
        for (int i = 2; i < n; i++) 
			if (primeArr[i]) count++;
        return count;
	}
}

优化后时间复杂度降到$O(n \ln \ln n)$。

Stackess

在互联网世界做只小透明

Leetcode之Math

258 Add Digits

202 Happy Number

263 Ugly Number

204 Count Primes