一、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.直接方法，如果例如22 * 32 * 52 * 7这个数，
在第一个while之后，变为：1 * 32 * 52 * 7
在第二个while之后，变为：1 * 1 * 52 * 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的一部分。