1.x的平方根（69 - 易）
题目描述：实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 :
输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
思路：本题中x取值为非负整数，显然平方根介于0~x/2之间，那么我们可以使用二分去查找这个整数（题目要求返回值是整数）。
代码实现比较简单，但是这里注意几个细节：
- 循环退出条件l == r，这样我们最终不用纠结返回l还是r。
- 二分中mid = l + (r - l + 1) / 2，这里为什么加1，分析原因：在区间只有 2 个数的时候，根据 if、else 的逻辑区间的划分方式是：[left..mid - 1] 与 [mid..right]。如果 mid 下取整，在区间只有 22个数的时候有 mid = left，一旦进入分支 [mid..right] 区间不会再缩小，发生死循环。
解决办法：把取中间数的方式改成上取整。
代码实现：
public int mySqrt(int x) { if (x <= 1) return x; int l = 0, r = x / 2; while (l < r) { int mid = l + (r - l + 1) / 2; if (mid > x / mid) { r = mid - 1; } else { l = mid; } } return l; }
2.Excel表列名称（168 - 易）
题目描述：给定一个正整数，返回它在 Excel 表中相对应的列名称。
示例 :
1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB ...
思路：本题考察点进制转化：十进制转二十六进制
- 每确定一个字母（二十六位），十进制除以二十六。
- 怎么确定这个字母呢，十进制模二十六（控制在0~25）。
注意：
- 这里的拼接方式为前插（insert(索引，前插元素)）
- 模结果等于0需要特判，如果是0，证明字母是Z，根据循环条件（n > 0）, 所以n - 1的目的是保证得到Z后退出循环。比如n = 26，如果不减1，最后结果为AZ，而不是Z
代码实现：
public String convertToTitle(int n) { StringBuilder sb = new StringBuilder(); while (n > 0) { int c = n % 26; if (c == 0) { c = 26; n--; } sb.insert(0, (char)('A' + c - 1)); n /= 26; } return sb.toString(); }
3.分数转小数（166 - 中）
题目描述：给定两个整数（可正可负），分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。
- 如果小数部分为循环小数，则将循环的部分括在括号内。
- 如果存在多个答案，只需返回 任意一个 。
- 对于所有给定的输入，保证 答案字符串的长度小于 10^4 。
示例 :
输入：numerator = 1, denominator = 2 输出："0.5"
思路：本题也是细节题，主要需要解决三个问题：
- 负数情况：先判断结果的正负（异或，相同为0，不同为1）
- 整除情况：直接通过余数判断
- 循环如何判断？开始循环的时候，说明之前已经出现这个余数，我们只需要记录位置，插入括号即可。这里需要有长除法的基本知识，循环核心思想：当余数出现循环的时候，对应的商也会循环。这里使用hashmap记录余数和第一次出现的索引。
注意：需要将所有的数都转成long型，避免结果越界！
代码实现：
public String fractionToDecimal(int numerator, int denominator) { if (numerator == 0) return "0"; StringBuilder sb = new StringBuilder(); if (numerator < 0 ^ denominator < 0) { sb.append("-"); } // Convert to Long or else abs(-2147483648) overflows long dividend = Math.abs(Long.valueOf(numerator)); long divisor = Math.abs(Long.valueOf(denominator)); sb.append(dividend / divisor); long reminder = dividend % divisor; if (reminder == 0) { return sb.toString(); } sb.append("."); Map<Long, Integer> map = new HashMap<>(); while (reminder != 0) { if (map.containsKey(reminder)) { sb.insert(map.get(reminder), "("); sb.append(")"); break; } map.put(reminder, sb.length()); reminder *= 10; sb.append(String.valueOf(reminder / divisor)); reminder %= divisor; } return sb.toString(); }
4.2的幂（166 - 中）
题目描述：给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
示例 :
输入：n = 1 输出：true 解释：2^0 = 1
思路：朴素解很简单，看一下位运算，n为2的幂，必定满足下边两个条件：
- 恒有 n & (n - 1) == 0，这是因为：
- n 二进制最高位为 1，其余所有位为 0；
- n - 1二进制最高位为 0，其余所有位为 1；
- 一定满足 n > 0。
代码实现：
// 朴素解 public boolean isPowerOfTwo(int n) { if (n <= 0) return false; while (n % 2 == 0) { n /= 2; } return n == 1; } // 位运算 public boolean isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
5.快乐数（202 - 易）
题目描述：编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。
示例 :
输入：19 输出：true 解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
思路：本题是一种比较经典的快慢指针问题，类似的还有T287寻找重复元素。这种类型题目标就是找快慢指针相遇的点。对于本题：
- 如果两个指针相遇，此时检查相遇点，如果是1，找到欢乐数；如果不是1证明进入死循环。
代码实现：
public int squareSum(int n) { int sum = 0; while (n > 0) { int i = n % 10; sum += i * i; n /= 10; } return sum; } public boolean isHappy(int n) { int slow = n, fast = squareSum(n); while (fast != 1 && slow != fast) { slow = squareSum(slow); fast = squareSum(squareSum(fast)); } return fast == 1; }
6.第 n 位数字（400 - 中）
题目描述：在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 位数字。
注意：n 是正数且在 32 位整数范围内（n < 231）。
示例 :
输入：11 输出：0 解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。
思路：本题我们找第n位数的过程是什么？核心：通过索引定位元素
- 定位到n所属的区间（一位数、两位数...），用digit表示，1， 2...
- 定位到这个区间的具体一个数，用start表示该区间所有的起始点数，个位是1，十位是10...
- 定位到这个数的具体索引，用indexCount表示该区间一共有多少个索引，公式：indexCount = digit * 9 * start;
注意：while循环之后，n的值为从当前区间的第一个数start开始的第n个数（即第n - 1的索引），start + (n - 1) / digit定位到目标数，（n - 1）% digit就是原始n在这个数的第几位。
例如n循环一次值为4（原始n为13），那么10， 1【1】，12；
代码实现：
public int findNthDigit(int n) { int digit = 1; long start = 1, indexCount = digit * 9 * start; while (n > indexCount) { n -= indexCount; digit++; start *= 10; indexCount = digit * 9 * start; } long num = start + (n - 1) / digit; int remainder = (n - 1) % digit; String strNum = String.valueOf(num); return (int)(strNum.charAt(remainder) - '0'); }
7.Pow(x, n)（50 - 中）
题目描述：实现Pow(x, n)，x的n次幂。
示例 :
输入：x = 2.00000, n = 10 输出：1024.00000
思路：本题考查的核心是快速幂算法。类似x^4 = (x2)2，这时幂次N = N/2。对于奇数情况需要特殊判断依次，即幂次为奇数情况。注意：判断幂次N的正负。
代码实现：
public double myPow(double x, int n) { long N = n; return N >= 0 ? iterate(x, N) : 1.0 / iterate(x, -N); } private double iterate(double x, long N) { double ans = 1.0; // 初始贡献值 double c = x; while (N > 0) { if (N % 2 == 1) { ans *= c; } c *= c; N /= 2; } return ans; }
8.阶乘后0的数量（172 - 易）
题目描述：给定一个整数 n，返回 n! 结果尾数中零的数量。要求: 时间复杂度应为 O(log n) 。
示例 :
输入: 5 输出: 1 解释: 5! = 120, 尾数中有 1 个零.
思路：本题考查数学问题，转化一下，就是找2和5的对数（相乘结果为0），因为2的因数是每两个出现一次，5的因数是每5个出现一次，所以本题我们只需要找5的因数的个数即可。
注意：每隔5*5个数还会出现一个5的因数，每隔5*5*5个数也会出现一个5的因数...，这样5的因数的数量就变成了n / 5 + n / 25 + ...，为了避免分母溢出，我们可以在每次循环让n/5（同样的效果）。
代码实现：时间复杂度（logN）
public int trailingZeroes(int n) { int count = 0; while (n > 0) { count += n / 5; n /= 5; } return count; }
