算法通关村第十三关—数字与数学高频问题(白银)

发布时间:2023年12月17日

??????数字与数学高频问题

一、数组实现加法专题

1.1 数组实现整数加法

?先看一个用数组实现逐个加一的问题。LeetCode66.具体要求是由整数组成的非空数组所表示的非负整数,在其基础上加一。这里最高位数字存放在数组的首位,数组中每个元素只存储单个数字。并且假设除了整数0之外,这个整数不会以零开头。例如:
image.png
?这个看似很简单是不?从后向前依次加就行了,如果有进位就标记一下,但是如果到头了要进位怎么办呢?
?例如如果digits=[9,9,9],从后向前加的时候,到了A[0]的位置计算为0,需要再次进位但是数组却不能保存了,该怎么办呢?
?这里的关键是A[0]什么时候出现进位的情况,我们知道此时一定是9,99,999这样的结构才会出现加1之后再次进位,而进位之后的结果一定是10,100,1000这样的结构,由于java中数组默认初始化为0,所以我们此时只要申请一个空间比A[]大一个单位的数组B[],然后将B[0]设置为1就行了。

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i] = (digits[i] + 1) % 10;
            //取余后不为0,不需要进位了
            if (digits[i] != 0) return digits;
        }
        //整个循环结束没返回,那就是100,1000这种类型的
        //除了第一位为1,其它位为0,创建时就默认了,不需要去赋值
        digits = new int[digits.length + 1]; 
        digits[0] = 1;
        return digits;
    }
}

1.2 字符串加法

?我们继续看将数字保存在字符串中的情况:字符串加法就是使用字符串来表示数字,然后计算他们的和。具体要求如下:给定两个字符串形式的非负整数num1和um2,计算它们的和并同样以字符串形式返回。你不能使用任何內建的用于处理大整数的库(比如BigInteger),也不能直接将输入的字符串转换为整数形式。
image.png
?先定义两个指针i和j分别指向num1和num2的未尾,即最低位,同时定义一个变量add维护当前是否有进位,然后从未尾到开头逐位相加。
?这里可能有个问题:两个数字位数不同该怎么处理?简单,补0即可。具体可以看下面的代码:

public String addStrings(String num1,String num2){
    int i = num1.length()-1, j = num2.length()-1, add = 0;
    StringBuffer ans = new StringBuffer();
    while(i >= 0 || j >= 0 || add != 0){
        int x = i >= 0 ? num1.charat(i) - '0' : 0;
        int y = j >= 0 ? num2.charAt(j) - '0' : 0;
        int result = x + y + add;
        ans.append(result % 10);
        add = result / 10;
        i--;
        j--;
    }
    //计算完以后的答案需要翻转过来
    ans.reverse()
    return ans.toString();
}

1.3 二进制加法

?这个题也是用字符串来表示数据的,也要先转换为字符数组。我们熟悉的十进制,是从各位开始,逐步向高位加,达到10就进位,而对于二进制则判断相加之后是否为二进制的10,是则进位。本题解中大致思路与上述一致,但由于字符串操作原因,不确定最后的结果是否会多出一位进位,下面2种处理方式都可以:
1.第一种,在进行计算时直接拼接字符串,得到一个反向字符,最后再翻转。
2.第二种,按照位置给结果字符赋值,最后如果有进位,则在前方进行字符串拼接添加进位
这里采用第二种实现。

class Solution {
    public String addBinary(String a, String b) {
        StringBuffer str = new StringBuffer();
        int alen = a.length() - 1, blen = b.length() - 1, add = 0;
        while(alen >= 0 || blen >= 0 || add != 0){
            int x = alen >= 0 ? a.charAt(alen) - '0': 0;
            int y = blen >= 0 ? b.charAt(blen) - '0': 0;
            int sum = x + y + add;
            str.append("" + sum % 2);
            add = sum / 2;

            alen--;
            blen--;
        }
        return str.reverse().toString();
    }
}

二、幂运算

?幂运算是常见的数学运算,其形式为ab,即a的b次方,其中a称为底数,b称为指数,ab为合法的运算(例如不会出现a=0且b≤0的情况)。幂运算满足底数和指数都是实数。根据具体问题,底数和指数的数据类型和取值范围也各不相同。例如,有的问题中,底数是正整数,指数是非负整数,有的问题中,底数是实数,指数是整数。
?力扣中,幂运算相关的问题主要是判断一个数是不是特定正整数的整数次幂,以及快速幂的处理。

2.1 求2的幂

?LeetCode:231.给你一个整数n,请你判断该整数是否是2的幂次方。如果是,返回true;否则,返回false。如果存在一个整数X使得n==2^×,则认为n是2的幂次方。
image.png
?解这道题其实挺简单的,首先排除负数。然后只要一直除以2,直至除不动为止,此时判断此数是否为1,1则为true

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

?也可以采用位运算,该方法与我们前面说的 统计数字转换成二进制数后:1的个数 思路一致。当n>0时,如果存在非负整数k使得n=2^k,则n的二进制表示为1后面跟k个0。由此可见,正整数n是2的幂,当且仅当n的二进制表示中只有最高位是1,其余位都是0,此时满足n&(n一1)=0(与运算)。因此代码就是:

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

2.2 求3的幂

?leetcode326给定一个整数,写一个函数来判断它是否是3的幂次方。如果是,返回true;否则,返回false。整数n是3的幂次方需满足:存在整数x使得n==3×

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

?这个题的问题和上面2的次幂一样,就是需要大量进行除法运算,我们能否优化一下呢?这里有个技巧。
v由于给定的输入n是int型,其最大值为2 ^ 31 - 1。因此在int型的数据范围内存在最大的3的幂,不超过2 ^ 31 -1 的最大的3的幂是3 ^ 19 = 1162261467。所以如果在1~2 ^ 31 -1内的数,如果是3的幂,则一定是1162261467的除数,所以这里可以通过一次除法就获得:

//仅作参考
public boolean isPowerofThree(int n){
	return n  >0 && 1162261467 % n = 0;
}

2.3 求4的幂

LeetCode:342给定一个整数,写一个函数来判断它是否是4的幂次方。如果是,返回true;否则,返回false。整数n是4的幂次方需满足:存在整数X使得n==4x。

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

总结

解决n次幂运算的通用方法
1.排除小于等于0的数
2.当该数取模n等于0时,循环除以n,直至除不了
3.返回判断该数是否等于1

文章来源:https://blog.csdn.net/m0_73709096/article/details/134973821
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。