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;
}
