一、204. Count Primes
Count the number of prime numbers less than a non-negative number, n.
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
1.数学原理：两个质数的乘积一定是合数。一个质数乘以任何数的积都一定不是质数。（除了1）
2.代码：需要注意的点：for (int j = 2; j * i < n; j++) notPremes[i * j] = true;
public int countPrimes(int n) {
boolean[] notPremes = new boolean[n];
int count = 0;
for (int i = 2; i < n; i++) {
if (!notPremes[i]) {
count ++;
for (int j = 2; j * i < n; j++) notPremes[i * j] = true;
}
}
return count;
}二、441. Arranging Coins
n = 5
The coins can form the following rows:
¤
¤ ¤
¤ ¤
Because the 3rd row is incomplete, we return 2. n = 8
The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
Because the 4th row is incomplete, we return 3.
1.数学原理：即求x满足：1+2+3+...+x <= n，即(1+x)*x<=n，解得x
2.代码：注意：如果使用8*n，可能会造成overflow，但是如果改成8.0*n，那么会自动转换成double类型的，就不会造成值大于Integer.Max_Value的情况。
public int arrangeCoins(int n) {
return (int) ((Math.sqrt(1 + 8.0 * n) - 1) / 2);
}三、258. Add Digits（不使用循环或者递归，并且在O(1)时间复杂度内解决这个问题。）
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
输入: 38
输出: 2
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。
1.思路：多写几个找出规律来：1 + (num - 1)%9【-1%9=-1】
输入：0，1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30...
输出：0,1,2,3,4,5,6,7,8,9, 1,2,3,4,5,6,7,8,9, 1,2,3,4,5,6,7,8,9, 1,2,3...
四、836. Rectangle Overlap
矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。
如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。
给出两个矩形，判断它们是否重叠并返回结果。
输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true
输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出：false
1.思路：两种方法：（1）按照点的位置考虑（2）按照重合的矩形的区域考虑
（1）按照点的位置考虑
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
return !(rec1[2] <= rec2[0] || // left
rec1[3] <= rec2[1] || // bottom
rec1[0] >= rec2[2] || // right
rec1[1] >= rec2[3]); // top
}（2）按照重合的矩形的区域考虑
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
return (Math.min(rec1[2], rec2[2]) > Math.max(rec1[0], rec2[0]) && // width > 0
Math.min(rec1[3], rec2[3]) > Math.max(rec1[1], rec2[1])); // height > 0
}五、326. Power of Three（TODO）
不使用循环或者递归来判断给定的整数是否是 3 的幂次方。
六、263. Ugly Number
丑数就是只包含质因数 2, 3, 5 的正整数。
1.遍历2,3,4,5，这里的4由于是和2重复，因此没有任何影响。注意表达：for (int i=2; i<6 && num>0; i++)
for (int i=2; i<6 && num>0; i++)
while (num % i == 0)
num /= i;
return num == 1;
2.直接方法，如果例如2 * 3 * 5 * 7这个数，
在第一个while之后，变为：1 * 3 * 5 * 7
在第二个while之后，变为：1 * 1 * 5 * 7
在第三个while之后，变为；1 * 1 * 1 * 7
public boolean isUgly(int num) {
if(num==1) return true;
if(num==0) return false;
while(num%2==0) num=num>>1;
while(num%3==0) num=num/3;
while(num%5==0) num=num/5;
return num==1;
}七、172. Factorial Trailing Zeroes（TODO）
给定一个整数 n，返回 n! 结果尾数中零的数量。
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
思路:
八、633. Sum of Square Numbers（TODO）
Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a2 + b2 = c.
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5
Input: 3
Output: False
思路：
九、400. Nth Digit（TODO）
在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 个数字。
n 是正数且在32为整形范围内 ( n < 231)。
输入:3
输出:3
输入:11
输出:0，第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0，它是10的一部分。