算法通关村-----数组实现加法专题问题解析

数组实现整数加法

问题描述

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 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();
}

总结与拓展

数组和字符串(本质上是字符数组)的加法其实只需要尽心遍历相加即可，但是数字是从低位到高位相加，而字符串是从高位到低位存储。所以需要反响遍历，并且注意进位，通过十进制与二进制的加法，可以拓展到任意进制的加法，只是在结果取模和判断进位时有所不同。