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

class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length ;
        for (int i = len - 1;i >= 0;i--){
            digits[i]++;
            digits[i] %= 10;
            if(digits[i] != 0){
                return digits;
            }
        }
        digits = new int[len + 1];
        digits[0] = 1;
        return digits;
    }
}

415.字符串相加

我们继续看将数字保存在字符串中的情况： 字符串加法就是使用字符串来表示数字，然后计算他们的和。具体要求如下：给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

我们先想一下小学里如何计算两个比较大的数相加的，经典的竖式加法是这样的：
从低到高逐位相加，如果当前位和超过 10，则向高位进一位。
因此我们只要将这个过程用代码写出来即可。先定义两个指针 i 和j 分别指向num1和num2的末尾，即最低位，同时定义一个变量 add 维护当前是否有进位，然后从末尾到开头逐位相加。
这里可能有个问题：两个数字位数不同该怎么处理？简单，补0即可。具体可以看下面的代码：

我们先想一下小学里如何计算两个比较大的数相加的，经典的竖式加法是这样的：

从低到高逐位相加，如果当前位和超过 10，则向高位进一位。

因此我们只要将这个过程用代码写出来即可。先定义两个指针 i 和j 分别指向num1和num2的末尾，即最低位，同时定义一个变量 add 维护当前是否有进位，然后从末尾到开头逐位相加。

这里可能有个问题：两个数字位数不同该怎么处理？简单，补0即可。具体可以看下面的代码：

class Solution {
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int 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. 二进制加法

我们继续看，如果这里是二进制该怎么处理呢？

详细要求：leetcode67.给你两个二进制字符串，这个字符串是用数组保存的，返回它们的和（用二进制表示）。其中输入为 非空 字符串且只包含数字 1 和 0。

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

示例2：
输入: a = "1010", b = "1011"
输出: "10101"

这个题也是用字符串来表示数据的，也要先转换为字符数组。我们熟悉的十进制，是从各位开始，逐步向高位加，达到10就进位，而对于二进制则判断相加之后是否为二进制的10，是则进位。本题解中大致思路与上述一致，但由于字符串操作原因，不确定最后的结果是否会多出一位进位，下面 2 种处理方式都可以：

● 第一种，在进行计算时直接拼接字符串，得到一个反向字符，最后再翻转。

● 第二种，按照位置给结果字符赋值，最后如果有进位，则在前方进行字符串拼接添加进位

我们这里采用第二种实现。

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();
    }
}

这里还有人会想，先将其转换成十进制，加完之后再转换成二进制可以吗？这么做实现非常容易，而且可以使用语言提供的方法直接转换，但是还是那句话，工程里可以这么干，稳定可靠，但是算法里不行，太简单了。

2. 幂运算

幂运算是常见的数学运算，其形式为 a^b ，即 a 的b次方，其中 a 称为底数，b 称为指数，a^b为合法的运算（例如不会出现 a=0且b≤0 的情况）。幂运算满足底数和指数都是实数。根据具体问题，底数和指数的数据类型和取值范围也各不相同。例如，有的问题中，底数是正整数，指数是非负整数，有的问题中，底数是实数，指数是整数。

力扣中，幂运算相关的问题主要是判断一个数是不是特定正整数的整数次幂，以及快速幂的处理。

2.1. 求 2 的幂

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

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

示例 1：

输入：n = 1
输出：true
解释：20 = 1

示例 2：
输入：n = 16
输出：true
解释：24 = 16

示例 3：
输入：n = 3
输出：false

示例 4：
输入：n = 4
输出：true

本题的解决思路还是比较简单的，我们可以用除的方法来逐步缩小n的值，另外一个就是使用位运算。

逐步缩小的方法就是如果 n 是 2 的幂，则 n>0，且存在非负整数 k 使得 n=2^k。

首先判断 n 是否是正整数，如果 n 是0 或负整数，则 n 一定不是 2 的幂。

当 n 是正整数时，为了判断 n 是否是 2 的幂，可以连续对 n 进行除以 2 的操作，直到 n 不能被 2 整除。此时如果 n=1，则 n 是 2 的幂，否则 n 不是 2 的幂。代码就是：

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

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

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

2.2. 求 3 的幂

leetcode 326 给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3^x

对于这个题，可以直接使用数学方法来处理，如果n是3 的幂，则 n>0，且存在非负整数 k 使得 n=3^k。

首先判断 n是否是正整数，如果 n是 0或负整数，则 n一定不是 3的幂。

当 n 是正整数时，为了判断 n 是否是 3 的幂，可以连续对 n 进行除以 3 的操作，直到 n 不能被 3 整除。此时如果n=1，则 n 是 3 的幂，否则 n 不是 3 的幂。

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

这个题的问题和上面2的次幂一样，就是需要大量进行除法运算，我们能否优化一下呢？这里有个技巧。

由于给定的输入 n 是int 型，其最大值为 2^31-1。因此在int 型的数据范围内存在最大的 3 的幂，不超过 2^31-1 的最大的 3 的幂是 3^19=1162261467。所以如果在1~ 2^31-1内的数，如果是3的幂，则一定是1162261467的除数，所以这里可以通过一次除法就获得：

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

当然这个解法只是拓展思路的，没必要记住1162261467这个数字。
思考 如果这里将3换成4 ，5，6，7，8，9可以吗？如果不可以，那如果只针对素数 3 、5、 7、 11、 13可以吗？

2.3. 求 4 的幂

LeetCode342 给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4^x。

第一种方法自然还是数学方法一直除，代码如下：

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

这个题可以利用2的次幂进行拓展来优化，感兴趣的同学自行查阅一下吧。

除了幂运算，指数计算的思路与之类似，感兴趣的同学可以研究一下LeetCode50，实现pow(x,n)这个题。

阅读量：1408

点赞量：0

收藏量:0