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

发布时间:2024年01月24日

数组实现加法专题

数组实现整数加法

66. 加一 - 力扣(LeetCode)

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

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

你可以假设除了整数 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
解一
public int[] plusOne(int[] digits)
{
    for (int i = digits.length - 1; i >= 0 ; i--)
    {
        //若某一位加一后不会产生进位,则该位加一后直接返回
        if(digits[i] != 9)
        {
            digits[i]++;
            return digits;
        }

        //发生进位,低位归零
        digits[i] = 0;
    }

    //进位发生在最高位:99999999
    int[] ans = new int[digits.length + 1];
    ans[0] = 1;
    return ans;
}
解二
public int[] plusOne(int[] digits)
{
    for (int i = digits.length - 1; i >= 0 ; i--)
    {
        digits[i]++;
        //计算低位
        digits[i] = digits[i] % 10;
        //加一后不出现进位,直接返回
        if(digits[i] != 0)
            return digits;
    }

    //进位发生在最高位:99999999
    int[] ans = new int[digits.length + 1];
    ans[0] = 1;
    return ans;
}

字符串相加

415. 字符串相加 - 力扣(LeetCode)

给定两个字符串形式的非负整数 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 都不包含任何前导零
StringBuilder + 位数不同就补零
public String addStrings(String num1, String num2)
{
    int i = num1.length() - 1;
    int j = num2.length() - 1;
    int carry = 0;  //进位
    StringBuilder ans = new StringBuilder();

    while (i >= 0 || j >= 0 || carry == 1)
    {
        int x = i >= 0 ? num1.charAt(i) - '0' : 0;
        int y = j >= 0 ? num2.charAt(j) - '0' : 0;

        int curSum = x + y + carry;
        ans.append(curSum % 10);    //先把低位相加的结果放在前面
        carry = curSum / 10;

        i--;
        j--;
    }

    //反转:高位在前,低位在后。然后StringBuilder类型转为字符串类型再返回
    return ans.reverse().toString();
}

二进制求和

67. 二进制求和 - 力扣(LeetCode)

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

示例 1:

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

示例 2:

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

提示:

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

把求余和整除换成2即可

public String addBinary(String a, String b)
{
    int i = a.length() - 1;
    int j = b.length() - 1;
    int carry = 0;  //进位
    StringBuilder ans = new StringBuilder();

    while (i >= 0 || j >= 0 || carry == 1)
    {
        int x = i >= 0 ? a.charAt(i) - '0' : 0;
        int y = j >= 0 ? b.charAt(j) - '0' : 0;

        int curSum = x + y + carry;
        ans.append(curSum % 2);    //先把低位相加的结果放在前面
        carry = curSum / 2;

        i--;
        j--;
    }

    //反转:高位在前,低位在后。然后StringBuilder类型转为字符串类型再返回
    return ans.reverse().toString();
}

幂运算

2 的幂

231. 2 的幂 - 力扣(LeetCode)

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

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

提示:

  • -2^31 <= n <= 2^31 - 1

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

循环一
public boolean isPowerOfTwo(int n)
{
    //负数和0不可能是2的幂次方
    if (n <= 0)
        return false;

    for (int i = 0; Math.pow(2, i) < Integer.MAX_VALUE; i++)
    {
        if(n == Math.pow(2, i))
            return true;
    }

    return false;
}
循环二

2的幂次方的特点:整除2后是偶数,不断整除2的结果是1

这个方法比循环一要高效

public boolean isPowerOfTwo_3(int n)
{
    if (n <= 0)
        return false;

    while (n % 2 == 0)
        n = n / 2;

    return n == 1;
}
位运算

正整数 n 是 2 的幂,当且仅当 n 的二进制表示中只有最高位是 1,其余位都是 0

public boolean isPowerOfTwo(int n)
{
    //n & (n - 1)的作用是消除 n 的二进制表示中最低位的1
    //如果 n 是2的幂次方,那 n 的二进制表示中只有最高位为1
    //除去1后,结果应该为零,否则就不是2的幂次方
    return n > 0 && ((n & (n - 1)) == 0);
}

3 的幂

326. 3 的幂 - 力扣(LeetCode)

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

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

循环
public boolean isPowerOfThree(int n)
{
    if (n <= 0)
        return false;

    while (n % 3 == 0)
        n = n / 3;

    return n == 1;
}
一步到位

如果n是3的幂次方,则整型范围内n一定是最大的3的幂次方的除数

public boolean isPowerOfThree(int n)
{
    // 1162261467 is the largest power of 3
    return (n > 0) && (1162261467 % n == 0);
}

4的幂

342. 4的幂 - 力扣(LeetCode)

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

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

循环
public boolean isPowerOfThree(int n)
{
    if (n <= 0)
        return false;

    while (n % 4 == 0)
        n = n / 4;

    return n == 1;
}
位运算

在这里插入图片描述

同余符号 ≡:在数论中使用,表示两个整数除以同一个数后余数相等。例如,a ≡ b (mod m)表示ab除以m后有相同的余数。

由于

4 ≡ 1 ( mod 3)

4^2 ≡ 1^2 ≡ 1 ( mod 3)

4^3 ≡ 1^3 ≡ 1 ( mod 3)

以此类推,可以得出对于任何整数4^x ≡ 1 ( mod 3)

public boolean isPowerOfFour(int n)
{
    //若n是4的幂次方,则n一定是2的幂次方
    return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
}

更多题目

50. Pow(x, n) - 力扣(LeetCode)

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