算法练习)二进制求和"/>
(算法练习)二进制求和
力扣上面的算法题目:(/)
给定两个二进制字符串,返回他们的和(用二进制表示)。
输入为非空字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:输入: a = "1010", b = "1011"
输出: "10101"来源:力扣(LeetCode)
链接:
主要考察的知识点:
1.当前字符的 ASCII 值减去 '0' 的 ASCII 值,相当于将这个字符转换成数值
2.StringBuilder
与 StringBuffer
的区别
3.字符翻转的方法 reverse();
4.时间复杂度的计算
实现思路:
整体思路是将两个字符串较短的用 00 补齐,使得两个字符串长度一致,然后从末尾进行遍历计算,得到最终结果。
本题解中大致思路与上述一致,但由于字符串操作原因,不确定最后的结果是否会多出一位进位,所以会有 2 种处理方式:
第一种,在进行计算时直接拼接字符串,会得到一个反向字符,需要最后再进行翻转
第二种,按照位置给结果字符赋值,最后如果有进位,则在前方进行字符串拼接添加进位
方案一:相关代码 (ps 由于Asscii 的知识点是盲点,我也是一句句敲的,一边写一边理解思路,加上备注)
class Solution {public String addBinary(String a, String b) {int aLen = a.length();int bLen = b.length();int maxLen = Math.max(aLen,bLen);//字符串进行翻转StringBuilder sbA = new StringBuilder(a).reverse();StringBuilder sbB = new StringBuilder(b).reverse();//让两个字符串补齐成一个长度,翻转过后前置位补0while(sbA.length() < maxLen){sbA.append("0");}while(sbB.length() < maxLen){sbB.append("0");}StringBuilder res = new StringBuilder();//进位的标志位, 默认是0int carry = 0;//知识点:当前字符的 ASCII 值减去 '0' 的 ASCII 值,相当于将这个字符转换成数值int num1;int num2;for(int i=0; i < maxLen; i++){num1 = sbA.charAt(i) - '0'; num2 = sbB.charAt(i) - '0';if(carry + num1 + num2 > 1){//1+1的情况,在二进制下 需要减去2res.append(carry + num1 + num2 - 2);//表示 需要进位,改变标志位carry = 1;}else{res.append(carry + num1 + num2);carry = 0; }}//对于最高位 需要增加位数,如果存在进位的情况if(carry == 1){res.append("1");}//最后再翻转一次,为开始补位的时候就是翻转后的return res.reverse().toString();}}
方案二:相关代码 (ps 我也是一句句敲的,一边写一边理解思路,加上备注)
上面的代码“翻转”了两次,显得有点啰嗦,我们可以使用两个指针,分别从字符串的末尾开始向前遍历,同时在借用 StringBuilder 对象的 insert 方法,从右向左依次得出计算结果,就真的非常接近我们手写“竖式加法”的过程了。下面是参考代码(摘录自题解)
private String doAddWithInsert(String a, String b){int i = a.length() - 1;int j = b.length() - 1;//这个是结果: 可变的字符序列对象StringBuilder res = new StringBuilder();int curSum;//进位的标志位int carry = 0;while(i >=0 || j >=0){curSum = carry;//当前位置的a的i位和 b 的j 位,都是末位进行相加if(i >= 0){curSum += a.charAt(i) - '0';i--;} if(j >= 0){curSum += b.charAt(j) - '0';j--;}//判断是否需要进位if(curSum > 1){//1+1的情况,在二进制下 需要减去2,有进位curSum -= 2;carry = 1;}else{carry = 0;} // 只写结果的值,进位作为下一轮的初始值res.insert(0, curSum);}if(carry == 1){res.insert(0, 1);}return res.toString();}
方案一可能好理解一些,但是方案二更加符合 竖加的 思路,主要点我觉得是 insert的使用.
更多推荐
(算法练习)二进制求和
发布评论