给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 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;
}
给定两个字符串形式的非负整数 num1
和num2
,计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库(比如 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
num1
和num2
都只包含数字 0-9
num1
和num2
都不包含任何前导零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();
}
给你两个二进制字符串 a
和 b
,以二进制字符串的形式返回它们的和。
示例 1:
输入:a = "11", b = "1"
输出:"100"
示例 2:
输入:a = "1010", b = "1011"
输出:"10101"
提示:
1 <= a.length, b.length <= 104
a
和 b
仅由字符 '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();
}
给你一个整数 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 的幂次方。如果是,返回 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 的幂次方。如果是,返回 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)
表示a
和b
除以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;
}