数字与数学

数字统计专题

L1822 数组元素积的符号

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

  • 如果 x 是正数,返回 1
  • 如果 x 是负数,返回 -1
  • 如果 x 是等于 0 ,返回 0

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

返回 signFunc(product)

示例 1:

输入:nums = [-1,-2,-3,-4,3,2,1]
输出:1
解释:数组中所有值的乘积是 144 ,且 signFunc(144) = 1

示例 2:

输入:nums = [1,5,0,2,-3]
输出:0
解释:数组中所有值的乘积是 0 ,且 signFunc(0) = 0

示例 3:

输入:nums = [-1,1,-1,1,-1]
输出:-1
解释:数组中所有值的乘积是 -1 ,且 signFunc(-1) = -1

这道题时间复杂度最少为O(n), 假设有一个0直接返回0即可,解题:

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

面试题16.05 阶乘0的个数

设计一个算法,算出 n 阶乘有多少个尾随零。

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

说明: 你算法的时间复杂度应为 O(log n) 。

这道题很难想到,一般只会想到直接乘出来硬数,但是那样便南辕北辙了

这里一个LeetCode社区的解释:

/**

  • 解题思路:
  • 1、那么 n 过大时,从 1 遍历到 n, 那么会超时,因此我们修改下规律
  • n! = 1 * 2 * 3 * 4 * (1 * 5) * ... * (2 * 5) * ... * (3 * 5) ...
  • 我们发现,
  • 每隔 5 个数就会出现 一个 5,因此我们只需要通过 n / 5 来计算存在存在多少个 5 个数,那么就对应的存在多少个 5
  • 但是,我们也会发现
  • 每隔 25 个数会出现 一个 25, 而 25 存在 两个 5,我们上面只计算了 25 的一个 5,因此我们需要 n / 25 来计算存在多少个 25,加上它遗漏的 5
  • 同时,我们还会发现
  • 每隔 125 个数会出现一个 125,而 125 存在 三个 5,我们上面只计算了 125 的两个 5,因此我们需要 n / 125 来计算存在多少个 125,加上它遗漏的 5
  • ...
    *
  • 因此我们 count = n / 5 + n / 25 + n / 125 + ...
  • 最终分母可能过大溢出,上面的式子可以进行转换
    *
  • count = n / 5 + n / 5 / 5 + n / 5 / 5 / 5 + ...
  • 因此,我们这样进行循环
  • n /= 5;
  • count += n;
  • 这样,第一次加上的就是 每隔 5 个数的 5 的个数,第二次加上的就是 每隔 25 个数的 5 的个数 ...

作者:刘宇
链接:https://leetcode.cn/problems/factorial-zeros-lcci/solutions/294787/zhai-zi-ping-lun-qu-suan-tou-wang-bazuo-zhe-de-dai/

很容易得到代码

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

这里的 res+=n可能有点难理解,其实就是下面的简化

  • count = n / 5 + n / 25 + n / 125 + ...

溢出问题

L7 整数反转

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

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

假设环境不允许存储 64 位整数(有符号或无符号)。

示例 1:

输入:x = 123
输出:321

示例 2:

输入:x = -123
输出:-321

示例 3:

输入:x = 120
输出:21

示例 4:

输入:x = 0
输出:0

这里反转很好解决,参考以前做过的数字反转方法,溢出则更好解决了,可以回忆字符串章节部分的溢出操作;这里第二遍遇见自己写的时候发现这种处理溢出的思路是解决溢出部分即可,

底下的解决方式就是处理了两种情况:

  • 位数相同溢出
  • 位数大于溢出

代码如下:

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

L8 字符串转整数

这道也有溢出问题的情况,可以参考上面的溢出解决思路,字符串已解决

L9 回文数字

这道题见了很多遍,直接看代码:

class Solution {
    public boolean isPalindrome(int x) {
         if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        return x == revertedNumber || x == revertedNumber / 10;
    }
}

另一种

class Solution {
    public boolean isPalindrome(int x) {
        if(x<0|| (x % 10 == 0 && x != 0))return false;
        int res = 0;
        int num =x;
        while (x != 0) {
            int end = x % 10;
            x /= 10;
            res = res * 10 + end;
        }
        return res==num;
    }
}

进制专题

L504 七进制数

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

示例 1:

输入: num = 100
输出: "202"

示例 2:

输入: num = -7
输出: "-10"

提示:

  • -107 <= num <= 107

这里可以先回忆十进制转换二进制的辗除法,但是需要注意两点:

  • 最后要求是字符串,可以直接用字符串拼接结果即可
  • 考虑负数和0的情况

然后可以很容易按照过程得到代码:

class Solution {
    public String convertToBase7(int num) {
        if (num == 0)
            return "0";
        StringBuilder sb = new StringBuilder();
        // 先拿到正负号
        boolean sign = num < 0;
        num = sign?-num:num;
        while (num != 0) {
            sb.append(num % 7);
            num /= 7;
        }
        return sign?sb.append("-").reverse().toString():sb.reverse().toString();
    }
}

N进制

给定一个十进制数M,以及需要转换的进制数N,将十进制数M转化为N进制数。M是32位整数,2<=N<=16。

代码很好实现,需要注意的只有一点,因为会有十六进制,所以我们可以使用一个字典法,定义数组

public static String convertToBaseN(int num, int N) {
        if (num == 0)
            return "0";
         final String[] F = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F"};
        StringBuilder sb = new StringBuilder();
        boolean sign = num < 0;
        num = sign?-num:num;
        while (num != 0) {
            sb.append(F[num % N]);
            num /= N;
        }
        return sign?sb.append("-").reverse().toString():sb.reverse().toString();
    }

数组实现加法专题

数组实现整数除法

给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。

最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外,这个整数不会以零开头。

示例 1:

输入:digits = [1,2,3]
输出:[1,2,4]
解释:输入数组表示数字 123。

示例 2:

输入:digits = [4,3,2,1]
输出:[4,3,2,2]
解释:输入数组表示数字 4321。

示例 3:

输入:digits = [0]
输出:[1]

提示:

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9

这道题拿到后只需要考虑两种情况:

  • 进位: 这里需要考虑两种情况:
    • 原位数不变
    • 位数改变需要扩容数组
  • 不进位

很容易得到代码:

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (++digits[i] == 10) {
                digits[i] = 0;
            } else {
                break;
            }
        }
        if (digits[0] == 0) {
            int[] newarr = new int[digits.length + 1];
            System.arraycopy(digits, 0, newarr, 1, digits.length);
            newarr[0] = 1;
            return newarr;
        }
        return digits;
    }
}

这里的代码其实可以优化:

  1. 首先是条件,当我们处理需要扩容数组的时候,其实这个时候不需要复制原有的数字,因为这个时候原数组都是0,所以我们只需要创建新数组并第一个赋值1即可
  2. 既然要执行的创建新数组条件是基于循环执行完毕,那么我们也可以将条件改为!=10,这样执行到下面的时候也就不需要判断了
class Solution {
    public int[] plusOne(int[] digits) {
        boolean sign = false;
        for (int i = digits.length - 1; i >= 0; i--) {
            if (++digits[i] != 10) {
                return digits;
            }
            digits[i] = 0;
        }
        int[] newarr = new int[digits.length + 1];
        newarr[0] = 1;
        return newarr;

    }
}

字符串相加

给定两个字符串形式的非负整数 num1num2 ,计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库(比如 BigInteger), 也不能直接将输入的字符串转换为整数形式。

示例 1:

输入:num1 = "11", num2 = "123"
输出:"134"

示例 2:

输入:num1 = "456", num2 = "77"
输出:"533"

示例 3:

输入:num1 = "0", num2 = "0"
输出:"0"

提示:

  • 1 <= num1.length, num2.length <= 104
  • num1num2 都只包含数字 0-9
  • num1num2 都不包含任何前导零

做题心得记录:

本来这道题的思维是先处理位数相同的情况,之后处理多余位数的情况,但是这种情况仍然需要处理进位,所以很不方便

因此有了以下解法:

  1. 思路还是一位一位计算,多余的位数可以看错为0,只需要循环的时候判断即可
  2. 但是这里需要加上**extra!=0**,原因是,当两个位数相同的时候还需要进位,这时候还需要执行一次,所以加入该条件
class Solution {
    public String addStrings(String num1, String num2) {
        int num1Index = num1.length() - 1;
        int num2Index = num2.length() - 1;
        int extra = 0;
        StringBuilder sb = new StringBuilder();
        while (num1Index >= 0 || num2Index >= 0||extra!=0) {
            int x = num1Index >= 0 ? num1.charAt(num1Index--) - '0' : 0;
            int y = num2Index >= 0 ? num2.charAt(num2Index--) - '0' : 0;
            int sum = x + y + extra;
            extra = sum >= 10 ? 1 : 0;
            int num = sum >= 10 ? sum - 10 : sum;
            sb.append(num);
        }

        return sb.reverse().toString();
    }
}

二进制求和

给你两个二进制字符串 ab ,以二进制字符串的形式返回它们的和。

示例 1:

输入:a = "11", b = "1"
输出:"100"

示例 2:

输入:a = "1010", b = "1011"
输出:"10101" 

提示:

  • 1 <= a.length, b.length <= 104
  • ab 仅由字符 '0''1' 组成
  • 字符串如果不是 "0" ,就不含前导零

这里我们回顾一个位运算方法,先转换为Long类型的二进制:

因为^是不进位二进制加法,&后在<<1,可以得到进位结果

class Solution {
   public String addBinary(String a, String b) {
        long x = Long.parseLong(a, 2);
        long y = Long.parseLong(b, 2);
        while (y!=0){
            long sign =(x&y)<<1;
            x = x^y;
            y=sign;
        }
        return Long.toBinaryString(x);
    }
}

这里在Java如果超过Long最大范围会报,但是使用大数也会无法通过,因此这里说明其他方法

这里也可以像上一道一样做法,但是这里做法是如果有进位单独加入一个1即可;
思路依然是得到每一位的sum,sum和对应的二进制数相加后,最终拼接结果

class Solution {
   public String addBinary(String a, String b) {
        StringBuilder ans = new StringBuilder();
        int ca = 0;
        for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--) {
            int sum = ca;
            sum += i >= 0 ? a.charAt(i) - '0' : 0;
            sum += j >= 0 ? b.charAt(j) - '0' : 0;
            ans.append(sum%2);
            ca = sum/2;
        }
        ans.append(ca==1?ca:"");
        return ans.reverse().toString();
    }
}

幂运算

L231 2的幂

给你一个整数 n,请你判断该整数是否是 2 的幂次方。如果是,返回 true ;否则,返回 false

如果存在一个整数 x 使得 n == 2x ,则认为 n 是 2 的幂次方。

示例 1:

输入:n = 1
输出:true
解释:2^0 = 1

示例 2:

输入:n = 16
输出:true
解释:2^4 = 16

示例 3:

输入:n = 3
输出:false

提示:

  • -231 <= n <= 231 - 1

**进阶:**你能够不使用循环/递归解决此问题吗?

这道题不难,可以直接计算是否最终能被2整除即可,不断将n/2

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        while (n % 2 == 0) {
            n /= 2;
        }
        return n == 1;
    }
}

进阶: 不使用循环计算呢?

我们知道,2的幂次方二进制是1,10,100 ………

class Solution {
    public boolean isPowerOfTwo(int n) {
      return n>0&&(n&(n-1))==0;
    }
}

这里是借助了n&(n-1)这个位运算公式,它可以去除二进制最后一个0;

官方:

除了使用二进制表示判断之外,还有一种较为取巧的做法。

除了使用二进制表示判断之外,还有一种较为取巧的做法。在题目给定的 32 位有符号整数的范围内,最大的2的幂为 2^30=1073741824。我们只需要判断 n是否是 2^30的约数即可。

class Solution {
    static final int BIG = 1 << 30;

    public boolean isPowerOfTwo(int n) {
        return n > 0 && BIG % n == 0;
    }
}

L326 3的幂

给定一个整数,写一个函数来判断它是否是 3 的幂次方。如果是,返回 true ;否则,返回 false

整数 n 是 3 的幂次方需满足:存在整数 x 使得 n == 3x

示例 1:

输入:n = 27
输出:true

示例 2:

输入:n = 0
输出:false

示例 3:

输入:n = 9
输出:true

示例 4:

输入:n = 45
输出:false

提示:

  • -231 <= n <= 231 - 1

推荐方法:

一样的取巧方法: 算出范围的最大公约数,直接除即可

最大的 3的幂为 3^19 = 1162261467

class Solution {
    public boolean isPowerOfThree(int n) {
        return n>0&&1162261467%n==0;
    }
}

使用正常解法:

class Solution {
    public boolean isPowerOfThree(int n) {
        if (n <= 0) {
            return false;
        }
        while (n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
}

L342 4的幂

给定一个整数,写一个函数来判断它是否是 4 的幂次方。如果是,返回 true ;否则,返回 false

整数 n 是 4 的幂次方需满足:存在整数 x 使得 n == 4x

示例 1:

输入:n = 16
输出:true

示例 2:

输入:n = 5
输出:false

示例 3:

输入:n = 1
输出:true

提示:

  • -231 <= n <= 231 - 1

**进阶:**你能不使用循环或者递归来完成本题吗?

这里正常解法:

class Solution {
     public boolean isPowerOfFour(int n) {
        if (n <= 0) {
            return false;
        }
        while (n % 4 == 0) {
            n /= 4;
        }
        return n == 1;
    }
}

这里,使用位运算:我们继续观察4的幂次方,分别是:1,100,10000等

我们发现,1总是在奇数位置上,而且一个数如果是4的幂,他也一定是2的幂,所以我们先判断他是不是2的幂基础上判断:

他的1是否都在奇数位上;怎么实现呢?那就是直接判断偶数位上有没有1就行了;代码如下:

class Solution {
    public boolean isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
}

取模:

解析:

如果 n是 2的幂却不是 4 的幂,那么它可以表示成 4^ x 2 的形式,此时它除以 3 的余数一定为2,

如果是4的幂,那么余数为1

class Solution {
    public boolean isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
    }
}

一道关于数学和分治法的题

实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn )。

示例 1:

输入:x = 2.00000, n = 10
输出:1024.00000

示例 2:

输入:x = 2.10000, n = 3
输出:9.26100

示例 3:

输入:x = 2.00000, n = -2
输出:0.25000
解释:2-2 = 1/22 = 1/4 = 0.25

提示:

  • -100.0 < x < 100.0
  • -231 <= n <= 231-1
  • n 是一个整数
  • 要么 x 不为零,要么 n > 0
  • -104 <= xn <= 104

看这道题前,首先了解一下快速幂算法:

快速幂算法的本质是分治算法。举个例子,如果我们要计算 x^64,我们可以按照:

x -> x^2 -> x^4 -> x^8 -> x^16 …… x^64

的顺序,从:开始,每次直接把上一次的结果进行平方,计算6次就可以得到x^64的值,而不需要对 x乘 63 次 x。

递归

知道了原理,下面进行代码实现:

class Solution {
    public double myPow(double x, int n) {
        long N =n;
        return N>=0?quickMul(x,N):1.0/quickMul(x,-N);
    }


    public double quickMul(double x, long N) {
        //当为0返回1.0
        if (N==0){
            return 1.0;
        }
        double y = quickMul(x,N/2);
        return N%2==0?y*y:y*y*x;
    }
}

注意点:

  1. 使用N是为了防止溢出
  2. 后面的—N没有必要,正负没有区别

迭代

代码如下:

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        double ans = 1.0;
        // 贡献的初始值为 x
        double x_contribute = x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N > 0) {
            if (N % 2 == 1) {
                // 如果 N 二进制表示的最低位为 1,那么需要计入贡献
                ans *= x_contribute;
            }
            // 将贡献不断地平方
            x_contribute *= x_contribute;
            // 舍弃 N 二进制表示的最低位,这样我们每次只要判断最低位即可
            N /= 2;
        }
        return ans;
    }
}