算法通关村十三关 | 数组字符串加法专题

1. 数组实现整数加法

题目：LeetCode66，66. 加一 - 力扣（LeetCode）

思路

我们只需要从头到尾依次运算，用常量标记是否进位，需要考虑的特殊情况是digits = [9,9,9]的时候进位，我们组要创建长度加1的数组，首位添加为1即可。

代码

    /*** 数组实现整数加法* 需要考虑999+1变成1000，解决方法创建个新数组，首位补1*/public static int[] plusOne(int[] digits) {int len = digits.length;//从末尾向前计算for (int i = len - 1; i >= 0; i--) {digits[i]++;digits[i] %= 10;//加1之后对10取余不等于0则没有进位，直接返回//如果有进位，循环再次执行++，if (digits[i] != 0)return digits;}//三位数都有进位，999-1000,创建新数组，首位等于1digits = new int[len + 1];digits[0] = 1;return digits;}

2. 字符串实现加法

题目

        给定两个非负形式的字符串num1和num2，计算他们的和以字符串形式返回，不能使用Javaapi

思路

        还是竖式计算，从后往前，如果当前位置超过10，则发生进位，用两个指针分别从两数的末尾向前移动，遇到数字位数不同，只需补0继续和另一位数字运算。

代码

    /*** 字符串加法，竖式加法，需要判断是否进位。可以用变量来存储每次进位的值*/public static String addStrings(String num1, String num2) {int i = num1.length() - 1, j = num2.length() - 1, add = 0;StringBuilder sb = new StringBuilder();//位数不同，补0计算while (i >= 0 || j >= 0 || add != 0) {int x = i >= 0 ? num1.charAt(i) - '0' : 0;int y = j >= 0 ? num2.charAt(i) - '0' : 0;int result = x + y + add;//先拼接余数sb.append(result % 10);//再计算是否进位add = result / 10;i--;j--;}sb.reverse();return sb.toString();}

3. 二进制加法

题目

LeetCode67：67. 二进制求和 - 力扣（LeetCode）

思路

        二进制加法同上题一样，只不过进位变了，满2进1，同时也要处理出现首位继续向前进位的现象，可以用最后在前方拼接进位，不进位则不用拼接。

代码

    /*** 二进制的加法* 同字符串加法思想一样，是满2进1，换种形式写代码*/public static String addBinary(String a, String b) {StringBuilder sb = 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;sb.append(sum % 2);ca = sum / 2;}//处理最后一位sb.append(ca == 1 ? ca : "");return sb.reverse().toString();}

补充：

题目较为简单，记住模板即可。