第 13 关 | 刷题模板之数学 ： 1.青铜挑战——数学与基础问题-灵析社区

1. 数字统计专题

统计一下特定场景下的符号，或者数字个数等是一类非常常见的问题。如果按照正常方式强行统计，可能会非常复杂，所以掌握一些技巧是非常重要的。

1.1. 符号统计

LeetCode1822 给定一个数组，求所有元素的乘积的符号，如果最终答案是负的返回-1，如果最终答案是正的返回1，如果答案是0返回0。

仔细分析一下这道题目，如果将所有数都乘起来，再判断正负，工作量真不少，而且还可能溢出。我们发现，一个数如果是 -100 和 -1，对符号位的贡献是完全一样的，所以只需要看有多少个负数，就能够判断最后乘积的符号了。

class Solution {
    public int arraySign(int[] nums) {
        int sign = 0;
        for(int i = 0;i < nums.length;i++){
            if(nums[i] == 0){
                return 0;
            }
            if(nums[i] < 0){
                sign++;
            }
        }
        if (sign % 2 == 1){
            return -1;
        }
        return 1;
    }
}

1.2 阶乘0的个数

很多数学相关算法的关键在于找到怎么通过最简洁的方式来解决问题，而不是硬算。例如：面试题16.05：设计一个算法，算出 n 阶乘有多少个尾随零。

这个题如果硬算，一定会超时，其实我们可以统计有多少个 0，实际上是统计 2 和 5 一起出现多少对，不过因为 2 出现的次数一定大于 5 出现的次数，因此我们只需要检查 5 出现的次数就好了，那么在统计过程中，我们只需要统计 5、10、15、 25、 ... 5^n 这样 5 的整数倍项就好了，最后累加起来，就是多少个 0。代码就是：

public int trailingZeroes(int n) {
    int cnt = 0;
    for (long num = 5; n / num > 0; num *= 5) {
        cnt += n / num;
    }
    return cnt;
}

数学不仅与算法难以区分 ，很多算法问题还与位运算密不可分，有些题目真不好说是该归类到数学中呢，还是位运算中。我们干脆就放在一起来看。

2. 溢出问题

溢出问题是一个极其重要的问题，只要涉及到输出一个数字，都可能遇到，典型的题目有三个：数字反转，将字符串转成数字和回文数。 不过溢出问题一般不会单独考察，甚至面试官都不会提醒你，但他就像捕捉猎物一样盯着你，看你会不会想到有溢出的问题，所以凡是涉及到输出结果为数字的问题，必须当心！

溢出处理的技巧都是一致的 ，接下来我们就看一下如何处理 。

2.1. 整数反转

LeetCode7 给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ，就返回 0。假设环境不允许存储 64 位整数（有符号或无符号）。

输入：x = 123  输出：321
输入：x = -123 输出：-321
输入：x = 120  输出：21
输入：x = 0    输出：0

这个题的关键有两点，一个是如何进行数字反转，另一个是如何判断溢出。反转好说，那为什么会有溢出问题呢？例如1147483649这个数字，它是小于最大的32位整数2147483647的，但是将这个数字反转过来后就变成了9463847411，这就比最大的32位整数还要大了，这样的数字是没法存到int里面的，所以就溢出了。

首先想一下，怎么去反转一个整数。用栈？或者把整数变成字符串再反转字符串？都可以但都不好。我们只要一边左移一边处理末尾数字就可以了。以12345为例，先拿到5，再拿到4，之后是3，2，1，然后就可以反向拼接出一个数字了。那如何获得末尾数字呢？好办，循环取模运算即可。例如：

1.将12345 % 10 得到5，之后将12345 / 10=1234
2.将1234 % 10 得到4，再将1234 / 10=123
3.将123 % 10 得到3，再将123 / 10=12
4.将12 % 10 得到2，再将12 / 10=1
5.将1 % 10 得到1，再将1 / 10=0

画成图就是：

这样的话，是不是将循环的判断条件设为x>0就可以了呢？不行！因为忽略了负数的问题，应该是while(x!=0)。去掉符号，剩下的数字，无论正数还是负数，按照上面不断的/10这样的操作，最后都会变成0，所以判断终止条件就是!=0。有了取模和除法操作，就可以轻松解决第一个问题，如何反转。

接下来看如何解决溢出的问题。我们知道32位最大整数是MAX=2147483647，如果一个整数num>MAX，那么应该有以下规律：

nums/10 > MAX/10=214748364，也就是如果底数第二位大于4了，不管最后一位是什么都已经溢出了，如下：

所以我们要从到最大数的1/10时，就要开始判断，也即：

● 如果 num>214748364 那后面就不用再判断了，肯定溢出了。

● 如果num= 214748364，这对应到上图中第三、第四、第五排的数字，需要要跟最大数的末尾数字比较，如果这个数字比7还大，说明溢出了。

● 如果num<214748364，则没问题，继续处理。

这个结论对于负数也是一样的，所以实现代码就是：

class Solution {
    public int reverse(int x) {
        int res = 0;
        while(x!=0){
            // 获取末尾的数字
            int temp = x %10;
            // 判断是否大于最大 32 位整数，也可以使用 Integer.Max_Value /10 代替 214748364
            // 断是否 大于 最大32位整数
            if (res>214748364 || (res==214748364 && temp>7)) {
                return 0;
            }
            //判断是否 小于 最小32位整数
            if (res<-214748364 || (res==-214748364 && temp<-8)) {
                return 0;
            }
            res = res * 10 +temp;
            x /= 10;
        }
        return res;
    }
}

2.2. 字符串转整数

LeetCode8.意思就是字符串转整数(atoi函数)，题目比较长，解决过程中要涉及很多异常情况的处理，在《字符串》那一关进行了详细讲解，这里就不进行过多的赘述。

class Solution {
    public int myAtoi(String str) {
 int len = str.length();
        char[] charArray = str.toCharArray();

        // 1、去除前导空格
        int index = 0;
        while (index < len && charArray[index] == ' ') {
            index++;
        }

        // 2、如果已经遍历完成（针对极端用例 "      "）
        if (index == len) {
            return 0;
        }

        // 3、如果出现符号字符，仅第 1 个有效，并记录正负
        int sign = 1;
        char firstChar = charArray[index];
        if (firstChar == '+') {
            index++;
        } else if (firstChar == '-') {
            index++;
            sign = -1;
        }

        // 4、将后续出现的数字字符进行转换
        // 不能使用 long 类型，这是题目说的
        int res = 0;
        while (index < len) {
            char currChar = charArray[index];
            // 4.1 先判断不合法的情况
            if (currChar > '9' || currChar < '0') {
                break;
            }

            // 题目中说只能存储 32 位大小的有符号整数，下面两个if分别处理整数和负数的情况。
            // 提前判断乘以10以后是否越界,但res*11可能会越界，所以这里使用Integer.MAX_VALUE/10，这样一定不会越界。
            // 这是解决溢出问题的经典处理方式
            if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && (currChar - '0') > Integer.MAX_VALUE % 10)) {
                return Integer.MAX_VALUE;
            }
            if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && (currChar - '0') > -(Integer.MIN_VALUE % 10))) {
                return Integer.MIN_VALUE;
            }

            // 合法的情况下，才考虑转换，每一步都把符号位乘进去
            // 想想这里为什么要带着sign乘
            res = res * 10 + sign * (currChar - '0');
            index++;
        }
        return res;
    }
}

2.3. 回文数

LeetCode9 .给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。
思路解析：

映入脑海的第一个想法是将数字转换为字符串，并检查字符串是否为回文。但是，这需要额外的非常量空间来创建问题描述中所不允许的字符串。

第二个想法是将数字本身反转，然后将反转后的数字与原始数字进行比较，如果它们是相同的，那么这个数字就是回文。 但是，如果反转后的数字大于int.MAX，我们将遇到整数溢出问题。

按照第二个想法，为了避免数字反转可能导致的溢出问题，为什么不考虑只反转 int 数字的一半？毕竟，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。

例如，输入 1221，我们可以将数字 “1221” 的后半部分从 “21” 反转为 “12”，并将其与前半部分 “12” 进行比较，因为二者相同，我们得知数字 1221 是回文。

这个反转思路与链表的反转是一样的，不过要简单多了。

这里还不能忘的问题就是，反转之后数字可能会溢出，因此必须做防范，方法我们上面说了，这里我们可以进一步简化一下：

class Solution {
    public boolean isPalindrome(int x) {
         // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if(x < 0 || x % 10 == 0 && x != 0){
            return false;
        }
        int reverterNumber = 0 ;
        while(x > reverterNumber){
            reverterNumber = reverterNumber * 10 + x % 10;
            x/=10;
        }
        return x== reverterNumber || x == reverterNumber / 10;
    }
}

3. 进制专题

3.1. 七进制数