2.数学（二）

题目汇总https://leetcode-cn.com/tag/math/

65. 有效数字困难（没做）

67. 二进制求和简单[✔]

69. x 的平方根简单[✔]

149. 直线上最多的点数困难（没做）

166. 分数到小数中等（没做）

168. Excel表列名称简单[✔]

171. Excel表列序号简单[✔]

172. 阶乘后的零简单

202. 快乐数简单[✔]

204. 计数质数简单（并不觉得简单）

67. 二进制求和简单

给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 **非空 **字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
提示：

• 每个字符串仅由字符 '0' 或 '1' 组成。
• 1 <= a.length, b.length <= 10^4
• 字符串如果不是 "0" ，就都不含前导零。

思路：

将两个字符串较短的用 0 补齐，使得两个字符串长度一致，然后从末尾进行遍历计算，得到最终结果。

class Solution {//执行用时：2 ms, 在所有 Java 提交中击败了98.60%的用户
    public String addBinary(String a, String b) {
        int carry = 0;  //是否进一位 
        StringBuilder res = new StringBuilder();
        for(int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--,j--){
            int valA = i >= 0 ? a.charAt(i) - '0': 0;
            int valB = j >= 0 ? b.charAt(j) - '0': 0;
            int sum = valA + valB + carry;
            res.append(sum % 2);  //如果二者都为1，那么 sum%2 应该刚好为0，否则为1
            carry = sum / 2;  //如果二者都为1，那么 carry 应该刚好为1，否则为0
        }
        //判断最后一次计算是否有进位，有则在最前面加上1 否则原样输出
        res.append(carry == 1 ? carry : "");
    //在进行计算时直接拼接字符串，会得到一个反向字符，需要最后再进行翻转
    return res.reverse().toString();
    }
}

69. x 的平方根简单

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 *x *是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。

思路：二分查找

二分查找的下界为 00，上界可以粗略地设定为 xx。在二分查找的每一步中，我们只需要比较中间元素 \textit{mid}mid 的平方与 xx 的大小关系，并通过比较的结果调整上下界的范围。

class Solution {//执行用时：2 ms, 在所有 Java 提交中击败了57.44%的用户
    public int mySqrt(int x) {
        int left = 0;
        int right = x ;
        int res = 0;
        while(left <= right){
            //int mid = (left + right) / 2
            //如果输入的left和right都接近2147483647，两个数相加就会溢出，变成一个负数。
            int mid = left + (right - left) / 2;
            //注意：有案例是 2147395599，求得 mid 平方会超过 int ，因此需要将平方结果转为 long 
            long square = (long)mid * mid;
            if(square > x){
                right = mid - 1;
            }else{
                res = mid;
                left = mid + 1;
            }
        }
    return res;
    }
}

168. Excel表列名称简单

给定一个正整数，返回它在 Excel 表中相对应的列名称。
例如，
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB
...
示例 1:
输入: 1，输出: "A"
示例 2:
输入: 28，输出: "AB"
示例 3:
输入: 701，输出: "ZY"

思路：

1-26处理为0-25，就是从0开始，0-25对应者'A'-'Z'，就是标准的26进制了

class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
    public String convertToTitle(int n) {
        if(n <= 0)
            return "";
        StringBuilder res = new StringBuilder();
        while(n > 0){
            n--;
            res.append((char)(n % 26 + 'A')); 
            n /= 26;
        }
    return res.reverse().toString();
    }
}

171. Excel表列序号简单

给定一个Excel表格中的列名称，返回其相应的列序号。
例如，
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...
示例 1:
输入: "A"，输出: 1
示例 2:
输入: "AB"，输出: 28
示例 3:
输入: "ZY"，输出: 701

思路：

与168. Excel表列名称是一样的

class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
    public int titleToNumber(String s) {
        int res = 0;
        for(int i = 0; i < s.length(); i++){
            //因为有26个字母，所以相当于26进制，每26个数则向前进一位
            res = res * 26 + (s.charAt(i) - 'A' + 1);
        }
    return res;
    }
}

172. 阶乘后的零简单

给定一个整数 n，返回 n! 结果尾数中零的数量。
示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n)。

思路：

要得到整数10 只能由 2×5 得到，问题转换成为 寻找<n 的所有数字中 的分解 因子中的 2 和 5 的个数。一个 2 和一个 5 就能构成10 。但是 2 的个数必然比 5 多，因此只需要统计 5 的个数就行了。不断除以 5，是因为每间隔 5 个数有一个数可以被 5 整除,，然后在这些可被 5 整除的数中，每间隔 5 个数又有一个可以被 25 整除,，故要再除一次， ... 直到结果为 0,，表示没有能继续被 5 整除的数了。

class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了99.79%的用户
    public int trailingZeroes(int n) {
        int count = 0;
        while (n > 0) {
            count += n / 5;
            n = n / 5;
        }
    return count;
    }
}

202. 快乐数简单

编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
示例：
输入：19
输出：true
解释： 1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

思路：双指针

SquareNum函数的作用是：每个数字根据各位的平方和指向另一个数字
使用两个指针，“快指针”每次走两步，“慢指针”每次走一步，当二者相等时，即为一个循环周期。此时，判断是不是因为1引起的循环，是的话就是快乐数，否则不是快乐数。

class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了99.98%的用户
    public boolean isHappy(int n) {
        int fast = n;
        int slow = n;
        do{
            slow = SquareNum(slow);
            fast = SquareNum(fast);
            fast = SquareNum(fast);
        }while(fast != slow);
        return slow == 1;
    }
    public int SquareNum(int n){
        int sum = 0;
        while(n != 0){
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }
}

204. 计数质数简单

统计所有小于非负整数 n的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

思路：排除法

需要看题解https://leetcode-cn.com/problems/count-primes/solution/ru-he-gao-xiao-pan-ding-shai-xuan-su-shu-by-labula/

class Solution {//执行用时：16 ms, 在所有 Java 提交中击败了78.80%的用户
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        for(int i = 2; i * i < n; i++){
            if(isPrime[i]){
                for(int j = i * i; j < n; j += i){
                    isPrime[j] = false;
                }
            }
        }

        int count = 0;
        for (int i = 2; i < n; i++){
            if (isPrime[i]) count++;
        }
        return count;
    }
}