`
bcyy
  • 浏览: 1809852 次
文章分类
社区版块
存档分类
最新评论

Add Binary -- LeetCode

 
阅读更多
原题链接:http://oj.leetcode.com/problems/add-binary/

这道题跟Add Two Numbers很类似,代码结构很接近。从低位开始,一直相加并且维护进位。和Add Two Numbers的区别是这个题目低位在后面,所以要从string的尾部往前加。时间复杂度是O(m+n),m和n分别是两个字符串的长度,空间复杂度是结果的长度O(max(m,n))。代码如下:

public String addBinary(String a, String b) {
    if(a==null || a.length()==0)
        return b;
    if(b==null || b.length()==0)
        return a;
    int i=a.length()-1;
    int j=b.length()-1;
    int carry = 0;
    StringBuilder res = new StringBuilder();
    while(i>=0&&j>=0)
    {
        int digit = (int)(a.charAt(i)-'0'+b.charAt(j)-'0')+carry;
        carry = digit/2;
        digit %= 2;
        res.append(digit);
        i--;
        j--;
    }
    while(i>=0)
    {
        int digit = (int)(a.charAt(i)-'0')+carry;
        carry = digit/2;
        digit %= 2;
        res.append(digit);
        i--;
    }
    while(j>=0)
    {
        int digit = (int)(b.charAt(j)-'0')+carry;
        carry = digit/2;
        digit %= 2;
        res.append(digit);
        j--;
    }      
    if(carry>0)
    {
        res.append(carry);
    }
    return res.reverse().toString();
}
最后有一个小细节要注意一下,就是我们维护的res是把低位放在前面,为了满足结果最后要进行一次reverse。
分享到:
评论

相关推荐

    leetcode题库-LeetCode-Rust:听说刷题建repo是立flag一般的行为?

    LeetCode-Rust 听说 LeetCode 添加了 Rust 支持, 这岂不是双倍的快(fu)乐(za)? 于是来体验一下 用 Rust 写题真是酸爽无比啊! (各种意义上的) 刷了几天的感受 Rust 运行速度是真 TM 快 有了 NLL 以后与 borrow ...

    leetcode双人赛-leetcode-1:leetcode-1

    leetcode双人赛LeetCode ...AddBinary :简单的问题。 AddTwoNumbers :简单的问题。 Anagrams :简单的#hashtable问题。 BalancedBinaryTree :简单的#balance #tree问题。 BestTimetoBuyandSellStock :简单的问题。 ...

    lrucacheleetcode-leetcode:个人刷leetcode遇到的一些题汇总(golang)

    add-two-numbers find-peak-element longest-common-subsequence longest-consecutive-sequence max-area-of-island next-greater-element-ii serialize-and-deserialize-binary-tree subarray-sum-equals-k binary-...

    LeetCode最全代码

    401 | [Binary Watch](https://leetcode.com/problems/binary-watch/) | [C++](./C++/binary-watch.cpp) [Python](./Python/binary-watch.py) | _O(1)_ | _O(1)_ | Easy | | 411 | [Minimum Unique Word ...

    leetcode答案-LeetCode-Trip:LeetCode刷题代码,大佬勿入

    LeetCode-Trip LeetCode刷题代码,大佬勿入。 为一年后的研究生找工作准备 目标是BAT的算法岗哈哈哈哈哈 争取做到每日一更 嗯…… 19.10.22:鸽了这么久,我又回来了……主要在实验室天天没啥事,过于佛系,刷刷题吧...

    leetcode跳跃-Algorithm:算法学习,包括leetcode算法题,

    Add Two Numbers 328 odd-even-linked-list 无官方题解 94 binary-tree-inorder-traversal 无官方题解 104 maximum-depth-of-binary-tree 105 construct-binary-tree-from-preorder-and-inorder-traversal 无官方...

    leetcode卡-LeetCode:我的LeetCode解决方案

    Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡[LeetCode 3. Longest Substring Without Repeating Characters], N/A 2017.06.15 打卡[LeetCode 407. ...

    leetcode和oj-leetcode_downloader:用于您已接受的leetcodeoj提交的下载器

    add-binary │  └── Solution.665166.java ├── add-two-numbers │  └── Solution.666385.java ├── balanced-binary-tree │  └── Solution.660938.java ├── best-time-to-buy-and-sell-stock

    leetcode中文版-leetcode:leetcode

    leetcode中文版车鸟 一组用python编写的算法。 种类 冒泡排序 插入排序 归并排序 桶排序 计数排序 基数排序 选择排序 快速排序 堆排序 搜索 二分查找 深度优先搜索 广度优先搜索 递归 json 漂亮的打印 过滤中文文件 ...

    leetcode中国-leetcode:leetcode刷题

    addBinary longestPalindrome maximal rectangle :dp问题,较难 largestRectangleArea 求直方图的最大面积,左右两次扫面+剪枝优化 Valid Parentheses 用栈判断括号匹配 Regular Expression Matching 递归匹配 ...

    leetcodepython001-LeetCode:力码

    leetcode ...Binary Linked-list 002 Add Two Numbers Stack 020 Valid Parenthesis Hash Table 001 TwoSum Reference 完整的学习流程 How to be a softwair engineer: 其他人详解 Python的各式演算法

    lrucacheleetcode-LeetCode:LeetCode刷题

    两数相加(Add Two Numbers) 2018.9.25 翻转二叉树(Invert Binary Tree) 2018.9.25 环形链表(Linked List Cycle) 2018.9.25 环形链表 II(Linked List Cycle II) 2018.9.26 删除排序链表中的重复元素 II...

    Leetcode的ac是什么意思-LeetCodeInJava:leetcode-java

    Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate ...

    leetcode-js:算法和数据结构是一个程序员的灵魂,LeetCode JavaScript TypeScript 题解

    leetcode-js Leecode 经典题目 JavaScript TypeScript 题解。 Leetcode's answers by JavaScript and TypeScript. easy 66.加一 (Plus One) 67.二进制求和 (Add Binary) 69.x 的平方根 (Sqrt(x)) 70.爬楼梯 ...

    Leetcode-Algorithm-Exercise

    Leetcode算法练习 Leetcode算法练习 ...MaximumSubarray 58_LengthOfLastWord 66_PlusOne 67_AddBinary 69_Sqrt(x) 70_ClimbStairs 83_RemoveDuplicatesFromSortedList 88_MergeSortedArray 100_SameT

    leetcode中文版-LeetCode:LeetcodeC++/Java

    Add Two Numbers 两数相加 math 3 Longest Substring Without Repeating Characters 无重复字符的最长子串 string 4 LMedian of Two Sorted Arrays 两个排序数组的中位数 ary,binary search,dive and conquer 5 ...

    leetcode答案-ruby_leetcode:ruby_leetcode

    Programming),或是二分查找(Binary Search),或是回溯(Back tracing),或是分治法(Divide and Conquer),还有大量的对 树,数组、链表、字符串 和 hash 的操作。通过做这些题能让你对这些最基础的算法的思路...

    LeetCode-NoteBook:docsifyjs

    LeetCode笔记本docsifyjsLeetCode算法Java c / c ++ javascript的基本知识简单的1. Two Sum 704. Classical Binary Search2. 3 Sum206. Reverse Linked List中等的33. Search in Rotated Sorted Array74. Search a ...

    Leetcode回文串拼接-leetcode_note:用于记录leetcode题目的解析

    2.Add Two Numbers 3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring 6.ZigZag Conversion 7.Reverse Integer 8.String To Integer 9.Palindrome ...

    判断链表是否为回文链表leetcode-Algos_Practice:来自Leetcode、HackerRank等网站的练习题

    “add_binary.py” - 以字符串的形式将两个二进制数作为输入,并将它们的总和作为字符串的输出返回。 “add_digits.py” - 递归添加数字的所有数字的算法。 “contains_duplicate.py” - 检查整数列表是否包含任何...

Global site tag (gtag.js) - Google Analytics