数字统计专题

符号统计

问题描述

已知函数 signFunc(x) 将会根据 x 的正负返回特定值：

如果 x 是正数，返回 1 。

如果 x 是负数，返回 -1 。

如果 x 是等于 0 ，返回 0 。

给你一个整数数组 nums 。令 product 为数组 nums 中所有元素值的乘积。

返回 signFunc(product) 。

详见leetcode1822

问题分析

最直接的方式是遍历nums数组，计算各个数的乘积，判断结果的正负。这样做计算量很大，而且很可能会发生溢出问题。根据乘法同号为正，异号为负的规则，只需统计数组中负数的个数，就能判断最终结果的正负，最后，只要数组中存在一个0，则最终结果为0

代码实现

public int arraySign(int[] nums) {
    int result = 1;
    for(int i=0;i<nums.length;i++){
        if(nums[i]==0){
            return 0;
        }else if(nums[i]<0){
            result = -result;
        }
    }
    return result;
}

统计阶乘尾数中的0

问题描述

设计一个算法，算出 n 阶乘有多少个尾随零。详见leetcode16.05

问题分析

直接计算阶乘结果，在统计结果中0的个数计算复杂，且可能会产生溢出问题。通过分析阶乘中的尾随0是由2(2的倍数)和5(5的倍数)运算产生的，而2(2的倍数出现的次数)总是大于5(5的倍数)出现的次数。所以，我们只需统计5(5的倍数出现的次数)，就能统计阶乘结果的尾随0。

代码实现

public int trailingZeroes(int n) {
    int count = 0;
    while(n!=0){
        n /= 5;
        count += n;
    }
    return count;
}

溢出问题专题

整数反转

问题描述

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

问题分析

如果不考虑溢出，我们可以直接先将x对10取余，得到尾数，将x/10去掉尾数，尾数不断✖️10加上新的尾数，可以实现反转效果。代码如下

public int reverse(int x) {
    int result = 0;
    while(x!=0){
        int temp = x%10;
        result = result*10 + temp;
        x = x/10;
    }
    return result;
}

很明显，反转后会出现数字溢出的问题。但是我们无法直接判断result>Integer.MAX_VALUE或者result<Integer.MIN_VALUE，因为此时result已经溢出了，我们可以判断result/10与最大值或者最小值除以10的关系，以最大值为例，当result/10>Integer.MAX_VALUE/10时，一定会溢出。当result/10<Integer.MAX_VALUE/10，此时下一轮不溢出，可以继续运算，当result/10==Integer.MAX_VALUE/10时，需要比较余数与Integer.MAX_VALUE%10的关系，余数>Integer.MAX_VALUE%10会溢出，否则不会溢出

代码实现

public int reverse(int x) {
    int result = 0;
    while(x!=0){
        int temp = x%10;
        if(result>Integer.MAX_VALUE/10 || (result==Integer.MAX_VALUE/10&& temp>Integer.MAX_VALUE%10)){
            return 0;
        }
        if(result<Integer.MIN_VALUE/10 || (result==Integer.MIN_VALUE/10&&temp<Integer.MIN_VALUE%10)){
            return 0;
        }
        result = result*10 + temp;
        x = x/10;
    }
    return result;
}

字符串转整数

在字符串专题已经详细分析实现，详见不简单的字符串转换

回文数的判断

问题描述

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

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

问题分析

如果直接将整数x反转比较，运算复杂，而且可能产生溢出问题，可以反转x的一半，如果x中的个数是奇数个，最中间的一个也可以反转，判断时不算在内即可。另外特殊情况，如x是负数，x的尾数为0的情况可以单独判断。

代码实现

public boolean isPalindrome(int x) {
    if(x<0){
        return false;
    }
    if(x%10==0 && x!=0){
        return false;
    }
    int reverse = 0;
    while(x>reverse){
        reverse = reverse*10 +x%10;
        x = x/10;
    }
    return reverse==x || reverse/10==x;
}

禁止专题

七进制数

问题描述

给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。

问题分析

十进制转7禁止，可以对整数num进行不断对7取余，得到的余数反转，拼接得到最终结果，题目要求最终返回的结果是字符串，那么我们可以直接用字符转拼接。

代码实现

public String convertToBase7(int num) {
        if(num==0){
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        boolean flag = true;
        if(num<0){
            flag = false;
            num *= -1;
        }
        while(num!=0){
            int temp = num%7;
            sb.append(temp);
            num = num/7;
        }
        if(!flag){
            sb.append("-");
        }
        return sb.reverse().toString();
    }

拓展：十进制转任意进制

问题描述

给定一个整数 num和一个数字n，将num转化为 n进制，并以字符串形式输出。

问题分析

思路和转换方式和上面是一样的，可自行体会代码实现

代码实现

public static String base10ToBaseN(int num, int n) {
    String[] numbers = new String[]{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F"};
    boolean flag = true;
    StringBuilder sb = new StringBuilder();
    if (num < 0) {
        flag = false;
        num *= -1;
    }
    while (num != 0) {
        int temp = num % n;
        sb.append(numbers[temp]);
        num /= n;
    }
    if(!flag){
        sb.append("-");
    }
    return sb.reverse().toString();
}

总结

数字与数学问题要灵活运用取整，取余等操作获取数字，同时要注意溢出问题。