这是悦乐书的第 223 次更新, 第 236 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 90 题 (顺位题号是 415). 给定两个非负整数 num1 和 num2 表示为字符串, 返回 num1 和 num2 的总和.
注意:
num1 和 num2 的长度均 < 5100.
num1 和 num2 都只包含数字 0-9.
num1 和 num2 都不包含任何前导零.
您不能使用任何内置 BigInteger 库或直接将输入转换为整数.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
从后向前依次获取两个字符串的字符, 转成 int 类型, 然后做加法得到和, 利用对 10 取余将余数添加进字符串的第一位, 然后需要计算进位, 直接将和除以 10, 就是可能存在的进位.
在循环的判断条件中, 还需要判断进位是否等于 1, 因为有可能最高位会存在进位, 不然会存在误差.
两个字符串的长度不能保证相等, 所以索引从后往前递减时, 两索引大于等于 0 是或的关系.
在通过索引取对应位置的字符时, 也要判断是否大于等于 0, 不满足就取默认值 0.
- public String addStrings(String num1, String num2) {
- int len = num1.length()-1;
- int len2 = num2.length()-1;
- int count = 0;
- StringBuilder sb = new StringBuilder();
- for (int i=len, j=len2; i>=0 || j>=0 || count == 1; i--,j--) {
- int n = i>= 0 ? num1.charAt(i)-'0' : 0;
- int n2 = j>= 0 ? num2.charAt(j)-'0' : 0;
- int sum = n + n2 + count;
- sb.insert(0, sum%10);
- count = sum/10;
- }
- return sb.toString();
- }
03 第二种解法
和第一种解法的思路一样, 只是将 for 循环换成了 while 循环, 没有始终在第一位插入, 而是最后通过反转完成.
- public String addStrings2(String num1, String num2) {
- int i = num1.length()-1;
- int j = num2.length()-1;
- int carry = 0;
- StringBuilder sb = new StringBuilder();
- while (i>=0 || j>=0 || carry == 1) {
- int n = i>= 0 ? num1.charAt(i)-'0' : 0;
- int n2 = j>= 0 ? num2.charAt(j)-'0' : 0;
- int sum = n + n2 + carry;
- sb.append(sum%10);
- carry = sum/10;
- i--;
- j--;
- }
- return sb.reverse().toString();
- }
04 小结
算法专题目前已连续日更超过两个月, 算法题文章 90 + 篇, 公众号对话框回复 [数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/c786b69ca660