数组实现整数加法
问题描述
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。详见leetcode66
问题分析
可以从数组的末尾，即length-1下标处开始向前遍历，末尾元素➕1，如果没有进位，直接返回该数组（例如 123+1->124），如果有进位，前一位继续加一，直至没有进位(例如 19+1->20)，如果循环结束，仍有进位，则需要创建一个比原数组长度增加1的数组，将首元素置为1，进行返回(例如 99+1->100)。
代码实现
public int[] plusOne(int[] digits) {
for(int i=digits.length-1;i>=0;i--){
digits[i]++;
digits[i]%=10;
if(digits[i]!=0){
return digits;
}
}
digits = new int[digits.length+1];
digits[0] = 1;
return digits;
}
字符串加法
问题描述
给定两个字符串形式的非负整数，计算他们的和并仍然以字符串的形式返回。
问题分析
从两个字符串末尾字符依次向前遍历，取对应位的字符进行加法，设置进位标识，结果可通过StringBuilder进行存储。最后反转即可。
代码实现
public static String plusString(String str1, String str2) {
int i = str1.length() - 1;
int j = str2.length() - 1;
int add = 0;
int x;
int y;
StringBuilder sb = new StringBuilder();
while (i >= 0 || j >= 0 || add != 0) {
if (i >= 0) {
x = str1.charAt(i) - '0';
} else {
x = 0;
}
if (j >= 0) {
y = str2.charAt(j) - '0';
}else {
y = 0;
}
int result = x + y + add;
sb.append(result%10);
if(result/10 == 1){
add = 1;
}else{
add = 0;
}
i--;
j--;
}
return sb.reverse().toString();
}
二进制加法
问题描述
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。详见leetcode67
问题分析
仍然是两个字符串末尾字符依次向前遍历，取对应位的字符进行加法，设置进位标识，结果可通过StringBuilder进行存储。最后反转即可。只是结果取模和判断进位与十进制有所不同，详见代码实现
代码实现
public String addBinary(String a, String b) {
int i = a.length() - 1;
int j = b.length() - 1;
int add = 0;
int x;
int y;
StringBuilder sb = new StringBuilder();
while(i>=0 || j>=0 || add!=0){
if(i>=0){
x = a.charAt(i)-'0';
}else{
x = 0;
}
if(j>=0){
y = b.charAt(j)-'0';
}else{
y = 0;
}
int sum = x + y + add;
sb.append(sum%2);
add = sum / 2;
i--;
j--;
}
if(add == 1){
sb.append(1);
}
return sb.reverse().toString();
}
总结与拓展
数组和字符串(本质上是字符数组)的加法其实只需要尽心遍历相加即可，但是数字是从低位到高位相加，而字符串是从高位到低位存储。所以需要反响遍历，并且注意进位，通过十进制与二进制的加法，可以拓展到任意进制的加法，只是在结果取模和判断进位时有所不同。
文章来源地址https://www.toymoban.com/news/detail-695891.html
文章来源：https://www.toymoban.com/news/detail-695891.html
到了这里，关于算法通关村-----数组实现加法专题问题解析的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
