Leetcode --- 数学运算问题1

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 = (x²⁾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;
}