|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
题目描述:
- 给你两个二进制字符串,返回它们的和(用二进制表示)。
- 输入为 非空 字符串且只包含数字 1 和 0。
-  
- 示例 1:
- 输入: a = "11", b = "1"
- 输出: "100"
- 示例 2:
- 输入: a = "1010", b = "1011"
- 输出: "10101"
-  
- 提示:
- 每个字符串仅由字符 '0' 或 '1' 组成。
- 1 <= a.length, b.length <= 10^4
- 字符串如果不是 "0" ,就都不含前导零。
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/add-binary
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
- class Solution {
- public:
- void dfs(string & a, string & b, string& res, int cura, int curb, int store){
- if(cura < 0 && curb < 0){
- if(store != 0) res += '1';
- return;
- }
- if(cura < 0){
- int temp = b[curb] - '0' + store;
- if(temp >= 2){
- store = 1;
- if(temp == 2)res += '0';
- else res += '1';
- }
- else if(temp < 2){
- char temp2 = temp + '0';
- res += temp2;
- store = 0;
- }
- dfs(a, b, res, -1, curb - 1, store);
- }
- else if(curb < 0){
- int temp = a[cura] - '0' + store;
- if(temp >= 2){
- store = 1;
- if(temp == 2)res += '0';
- else res += '1';
- }
- else if(temp < 2){
- char temp2 = temp + '0';
- res += temp2;
- store = 0;
- }
- dfs(a, b, res, cura-1, -1, store);
- }
- else{
- int temp = a[cura] - '0' + b[curb] - '0' + store;
- if (temp >= 2){
- store = 1;
- if(temp == 2)res += '0';
- else res += '1';
- }else if(temp < 2){
- char temp2 = temp + '0';
- res += temp2;
- store = 0;
- }
- dfs(a, b, res, cura-1, curb-1, store);
- }
- }
- string addBinary(string a, string b) {
- string res;
- dfs(a, b, res, a.size()-1, b.size() - 1, 0);
- reverse(res.begin(), res.end());
- return res;
- }
- };
复制代码 |
|