67. 二进制求和

PRE_ZHY · · 1268 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

给定两个二进制字符串,返回他们的和(用二进制表示)。
输入为非空字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"

碰到这个题目的第一个思路,转换为十进制求和,刚刚好熟悉一下 golang strconv 库

func addBinary(a string, b string) string {
    ai, err := strconv.ParseInt(a, 2, 64)
    if err != nil {
        fmt.Println(ai, err)
    }
    bi, err := strconv.ParseInt(b, 2, 64)
    return fmt.Sprintf("%b", ai+bi)
}

不出意外,提交不通过,不通过的测试为

c := "10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101"
d := "110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011"

这个测试的想法当然是让我们自己算了,ok,没有问题,计算二进制加法很简单,定义一个二进制加法函数(记得考虑进位)

func binadd(x, y, flag int) (sum, addflag int) {
    sum = (x + y + flag) % 2
    addflag = (x + y + flag) / 2
    return
}

好吧,为了配合输入输出是字符串,还需要转换一下

func binStr2Slice(BinStr string) []int {
    temp := make([]int, len(BinStr), len(BinStr))
    for i := 0; i < len(BinStr); i++ {
        if BinStr[i] == '0' {
            temp[i] = 0
        } else {
            temp[i] = 1
        }
    }
    return temp
}

func binSlice2str(b []int) string {
    s := ""
    for _, v := range b {
        s = s + fmt.Sprint(v)
    }
    return s
}

addBinary 需要一个遍历的过程

func addBinaryS(a string, b string) string {
    if len(a) < len(b) {
        a, b = b, a
    }
    maxL := len(a)
    aint := binStr2Slice(a)
    bint := binStr2Slice(b)

    addFlag := 0
    sum := make([]int, maxL, maxL)
    for i := 1; i <= maxL; i++ {
        if i <= len(b) {
            sum[len(sum)-i], addFlag = binadd(aint[len(aint)-i], bint[len(bint)-i], addFlag)
        } else {
            sum[len(sum)-i], addFlag = binadd(aint[len(aint)-i], 0, addFlag)
        }

    }
    if addFlag == 1 {
        sum = append([]int{1}, sum...)
    }
    return binSlice2str(sum)
}

PASS

附上0ms通过的代码,里面使用了字符加减的设计,个人感觉不是很好理解,所以不做分析

func addBinary(a string, b string) string {
    var carry, sum int
    i, j := len(a), len(b)
    if i < j {
        i, j = j, i
        a, b = b, a
    }

    res := make([]byte, i+1)

    for j > 0 {
        j--
        i--
        sum = int(a[i]-'0') + int(b[j]-'0') + carry
        carry = sum / 2
        sum = sum % 2
        res[i+1] = byte(sum + '0')
    }

    for i > 0 {
        i--
        sum = int(a[i]-'0') + carry
        carry = sum / 2
        sum = sum % 2
        res[i+1] = byte(sum + '0')
    }

    res[0] = byte(carry + '0')

    for i < len(res)-1 {
        if res[i] == '0' {
            i++
        } else {
            break
        }
    }
    return string(res[i:])
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:PRE_ZHY

查看原文:67. 二进制求和

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

1268 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传