算法通关村第十三关—数学与数学基础问题(青铜)

??????数学与数学基础问题

一、统计专题

1.1 符号统计

?LeetCode1822给定一个数组，求所有元素的乘积的符号，如果最终答案是负的返回-1，如果最终答案是正的返回1，如果答案是0返回0。
?题目比较简单，正数对结果完全没影响，只需判断有多少个负数和是否有0即可

class Solution {
    public int arraySign(int[] nums) {
        int judge = 1;
        for(int num: nums){
            if(num == 0) return 0;
            if(num < 0) judge *= -1;
        }
        return judge == 1 ? 1 : -1;
    }
}

1.2 阶乘0的个数

?Leetcode 172 给定一个整数n，返回 n!结果中尾随零的数量。
?这道题需要统计尾数有多少个0，那其实可以想成有多少对5和2，而5的数量是一定是少于2的，所以统计出5的个数即可得出结果

class Solution {
    public int trailingZeroes(int n) {
        int sum = 0;
        //求出所有5的倍数
        for(int i = 5; i <= n; i += 5){
            //这些数可以拆出多少个5
            for(int k = i; k % 5 == 0; k /= 5) sum++;
        }
        return sum;
    }
}

?当然,这道题还可以进行优化，例如：当某个数x是5的倍数时，当5^1 <= x < 5^2 时，它只含有一个5，像5，10，15，20；而当5^2 <= x< 5^3 时它包含两个5。所以，我们可以利用上述例子来计算0的个数。sum = n/5+n/(5^2)+…

lass Solution {
    public int trailingZeroes(int n) {
        int sum = 0;
       
        for(int i = 5; n / i > 0; i *= 5){
            sum += n / i;
        }
        return sum;
    }
}

二、溢出问题

2.1 整数反转

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

?这道题要解决两个关键问题：1.如何进行整数反转；2.如何判断溢出
?对于整数反转，只需要创建另外一个变量rev来反转即可，不需要复杂的数据结构

例：123
123 % 10 = 3, 123 / 10 = 12 
rev = 0 * 10 + 3 = 3

12 % 10 = 2, 12 / 10 = 1
rev = 3 * 10 + 2 = 32

1 % 10 = 1, 1 / 10 = 0
rev = 32 * 10 + 1 = 321

?对于溢出问题，当int溢出时，会无法得到你正常运算结果的数，这里有两种解决方法。一种是讲义中对溢出的前一位就进行判断，另外一种我是用long类型变量来保存反转结果，这样可以在反转完一次性判断是否溢出。两种写法代码如下：

//第一种 讲义
class Solution {
    public int reverse(int x) {
        int rev = 0;
        while(x != 0){
            int max = Integer.MAX_VALUE;
            int min = Integer.MIN_VALUE;
            if(rev > max / 10 || (rev == max / 10 && x % 10 > max % 10)) return 0;
            if(rev < min / 10 || (rev == min / 10 && x % 10 < min % 10)) return 0;
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        return rev;
    }
}

//第二种 自己发现的，时间复杂度也是击败100%
class Solution {
    public int reverse(int x) {
        long rev = 0;
        while(x != 0){
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        if(rev > Integer.MAX_VALUE || rev < Integer.MIN_VALUE) return 0;
        return (int)rev;
    }
}

2.2 字符串转整数

Leetcode 8 ：在字符串一关中

2.3 回文数

?LeetCode9 给你一个整数x,如果x是一个回文整数，返回true;否则，返回false
?根据题目要求，我们可以对整数x进行反转后与原数进行比较，若相等则为回文数，但这样要考虑溢出问题。所以，可以考虑反转一半的数，然后前后两部分进行比较。（注意考虑整数位数的奇偶）
代码如下：

public boolean isPalindrome(int x){
//特殊情况：
//如上所述，当x<0时，x不是回文数。
//同样地，如果数字的最后一位是0，为了使该数字为回文，
//则其第一位数字也应该是0
//只有0满足这一属性
if(x < 0 || (x % 10 = 0 && × != 0)) return false;
int revertedNumber 0;
while (x > revertedNumber){
revertedNumber = revertedNumber 10 + x % 10;
x /= 10;
}
//当数字长度为奇数时，我们可以通过revertedNumber/10去除处于中位的数字。
//例如，当输入为12321时，在while循环的末尾我们可以得到x=12,revertedNumber=123
//由于处于中位的数字不影响回文（它总是与自己相等)，所以我们可以简单地将其去除。
return x == revertedNumber || x == revertedNumber / 10;
}

巧妙地化字符串，利用reverse()方法求解

class Solution {
    public boolean isPalindrome(int x) {
        String reversedStr = (new StringBuilder(x + "")).reverse().toString();
        return (x + "").equals(reversedStr);
    }
}

三、进制专题

3.1 七进制数

?LeetCode504.给定一个整数num,将其转化为7进制，并以字符串形式输出。其中-10^7<=num<=107。
?给定一个整数将其转换成7进制的主要过程是循环取余和整除，最后将所有的余数反过来即可。例如，将十进制数101转成七进制：

示例：101
101÷7=14 余 3
14÷7=2 余 0
2÷7=0 余 2
结果：203

注意如果是负数，要先把负号取出来再计算。

class Solution {
    public String convertToBase7(int num) {
        StringBuffer str = new StringBuffer();
        if(num == 0) return "0";
        int judge = 1;
        if(num < 0){
            judge = -1;
            num = -1 * num;
        }
        while(num != 0){
            str.append("" + num % 7);
            num /= 7;
        }
        if(judge == -1) str.append("-");
        return str.reverse().toString();
    }
}

3.2 进制转换

?给定一个十进制数M,以及需要转换的进制数N,将十进制数M转化为N进制数。M是32位整数，2<=N<=16。
?这个题目的思路不复杂，但是想写正确却很不容易，本题有好几个需要处理的问题：
1.超过进制最大范围之后如何准确映射到其他进制，特别是ABCDEF这种情况。简单的方式是大量采用if判断，但是这样写代码太多了
2.需要对结果进行一次转置。
3.需要判断负号。
?下面这个是讲义总结出的最精简，最容易理解的实现方案。注意采取三个措施来方便处理：
1.定义大小为16的数组F,保存的是2到16的各个进制的值对应的标记，这样赋值时只计算下标，不必考虑不同进制的转换关系了。（绝妙）
2.使用StringBuffer的reverse()完成数组转置等功能，如果不记得这个方法，工作量直接飙升。
3.通过一个flag来判断正数还是负数，最后才处理。

//要考虑到余数>9的情况，2<=N<=16.
public static final String[] F = {"0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"};
//将十进制数M转化为N进制数
public String convert(int M,int N){
    Boolean flag = false;
    if(M < 0){
        flag = true;
        M *= -1;
    }
    StringBuffer sb = new StringBuffer();
    int temp;
    while(M != 0){
        temp = M % N;
        //技巧一：通过数组F[]解决了大量繁琐的不同进制之间映射的问题
        sb.append(F[temp]);
        M = M / N;
    }
    //技巧二：使用StringBuffer的reverse()方法，让原本麻烦的转置瞬间美好
    sb.reverse();
    //技巧三：最后处理正负，不要从一开始就揉在一起。
    return (flag ? "-" : "") + sb.toString();
}