LeetCode笔记:67. Add Binary
2023-03-15 23:22:25 时间
问题:
Given two binary strings, return their sum (also a binary string). For example, a = "11" b = "1" Return "100".
大意:
给出两个二进制字符串,返回它们的和(同样是二进制字符串)。 例子: a = "11" b = "1" 返回 "100".
思路:
这其实就是一个模拟二进制加法的问题。如果某一位两个数都是0,结果的这一位也为0,有一个1就是1,如果都是1,这一位是0,还有进一位,所以上面三种情况还要考虑低位有没有进位。
因为两个二进制数的长度可能不同,所以我们先要在一个循环中去加两个数的和,当任一个数处理完之后,再看剩下哪个,将其加到结果中去。
这种做法速度还是很快的,只是代码比较多,也可以直接将短的那个加到长的那个上面去,但最后还是要根据进位遍历一遍长的剩余部分,节省不了太多东西。
代码(Java):
public class Solution {
public String addBinary(String a, String b) {
int flag = 0;
char[] result = new char[a.length() > b.length() ? a.length() : b.length()];
int k = result.length - 1;
int i = a.length() - 1;
int j = b.length() - 1;
for (; i >= 0 && j >= 0; i--, j--, k--) {
if (a.charAt(i) == '1' && b.charAt(j) == '1') {
result[k] = flag == 1 ? '1' : '0';
flag = 1;
} else if (a.charAt(i) == '1' || b.charAt(j) == '1') {
result[k] = flag == 1 ? '0' : '1';
flag = flag == 1 ? 1 : 0;
} else {
result[k] = flag == 1 ? '1' : '0';
flag = 0;
}
}
if (i >= 0) {
for (; i >=0; i--, k--) {
if (a.charAt(i) == '1' && flag == 1) {
result[k] = '0';
flag = 1;
} else if (a.charAt(i) == '1' || flag == 1) {
result[k] = '1';
flag = 0;
} else {
result[k] = '0';
flag = 0;
}
}
}
if (j >= 0) {
for (; j >=0; j--, k--) {
if (b.charAt(j) == '1' && flag == 1) {
result[k] = '0';
flag = 1;
} else if (b.charAt(j) == '1' || flag == 1) {
result[k] = '1';
flag = 0;
} else {
result[k] = '0';
flag = 0;
}
}
}
return flag == 1 ? "1" + String.valueOf(result) : String.valueOf(result);
}
}
相关文章
- CentOS 上最佳的第三方仓库
- 如何在 Linux 上用 SQL 语句来查询 Apache 日志
- 《HttpClient官方文档》2.6 连接维持存活策略
- Python For Data Analysis -- IPython
- 非常规网络安全报告 —— 黑客报告2017
- Python For Data Analysis -- NumPy
- 反射是否真的会让你的程序性能降低?
- Python For Data Analysis -- Pandas
- 如何在Linux上构建 RAID 10阵列
- 京东白条爆严重BUG!不法分子POS机疯狂套利
- 《HttpClient官方文档》第六章 HTTP 缓存
- 《云数据管理:挑战与机遇》2.1 向量时钟
- 带着问题学 Spring MVC 源码: 一、概述
- 影子经纪人再次归来,公开密码解密更多NSA黑客工具!连中国运营商都被入侵过?
- 浅析 Linux 初始化 init 系统: sysvinit
- 《HttpClient官方文档》2.5 连接驱逐策略
- 浅析 Linux 初始化 init 系统: UpStart
- 《云数据管理:挑战与机遇》2.1.3 互斥和仲裁集
- 《云数据管理:挑战与机遇》2.1.4 领导者选举
- Linux有问必答——如何在Linux命令行中剪裁图像