2022/04/12

Leetcode Note: Go - Add Binary

Add Binary - LeetCode
https://leetcode.com/problems/add-binary/

  • Go 言語で取り組んだメモ

所感

  • パッと見た感じ、ただの文字列連携かと思ったが 2進数 としての加算が必要
  • 引数の string をパースして加算処理を行い、文字列にして return する必要がある
  • パース
    • for loop するしか無さそう
  • 加算処理
    • 桁上りを考慮する必要あり
  • 文字列にして return
    • itoa すれば OK

実装準備

func addBinary(a string, b string) string {
    return "Hello"
}

func main() { 
    a := "11"
    b := "1"
    fmt.Println(addBinary(a, b))
}

v1

func addBinary(a string, b string) string {

    // MAX_LENGTH := 5

    // convert to int array with zero fill
    intA := make([]int, len(a))
    intB := make([]int, len(b))

    for i := len(a) - 1; i >= 0; i-- {
    // for i := 0; i < len(a); i++ {
        if s, err := strconv.Atoi(string(a[i])); err == nil {
            intA[i] = s
            fmt.Println(s)
        }
    }
    
    for i := len(b) - 1; i >= 0; i-- {
        if s, err := strconv.Atoi(string(b[i])); err == nil {
            intB[i] = s
        }
    }

    // for len(intA) != 5 {
    //     intA = append(make([]int, 1), intA)
    // }
    // for len(intB) != 5 {
    //     intB = append([]int{0}, intB)
    // }

    // この計算でやるなら zero fill が必要
    maxLength := len(a)
    if len(a) < len(b) {
        maxLength = len(b)
    }

    fmt.Println(intA, intB, maxLength)
    
    // sum
    sum := make([]int, maxLength)
    carry := false // carry up flag
    for i := maxLength - 1; i >= 0; i-- {
        if len(intA) > i {
            sum[i] += intA[i]
        }
        if len(intB) > i {
            sum[i] += intB[i]
        }
        if sum[i] == 2 {
            sum[i] = 0
            carry = true
            
            // for j := i + 1; j < maxLength; j++ {
            //     if sum[j] == 0 {
            //         sum[j]++
            //     } else if sum[j] == 1 {
            //         sum[j] = 0
            //     }
            // }
        }
    }

    // carry up
    if carry {
        sum = append(sum, 1)
    }

    // convert string
    str := ""
    for i := len(sum) - 1; i >= 0; i-- {
        str += strconv.Itoa(sum[i])
    }

    fmt.Println(sum, carry, str)
    return str
}
  • 計算について考える
    • a = 1010
    • b = 1011
    • ans = 10101
  • 計算するときは逆順の方が都合が良さそう、そしてできればゼロ埋めしたい
    • 00101
    • 01101
    • 10101
  • 頭が働かず実装まで至らず・・・
    • そもそも for loop ありすぎでヤバい

回答

go simple 0ms - LeetCode Discuss
https://leetcode.com/problems/add-binary/discuss/1031983/go-simple-0ms

func addBinary(a string, b string) string {
        l1 := len(a) - 1
        l2 := len(b) - 1

        c := 0 // carry
        rs := 0
        var str strings.Builder

        for l1 >= 0 || l2 >= 0 {
                rs = c
                if l1 >= 0 {
                        rs += convBinary(a[l1])
                }

                if l2 >= 0 {
                        rs += convBinary(b[l2])
                }

                c = rs >> 1
                rs = rs & 1
                if rs == 1 {
                        str.WriteByte('1')
                } else {
                        str.WriteByte('0')
                }
                l1 -= 1
                l2 -= 1
        }

        if c == 1 {
                str.WriteByte('1')
        }


        var str2 strings.Builder
        t := str.String()
        // reverse str
        for i := len(t) - 1; i >= 0; i -= 1 {
                str2.WriteByte(t[i])
        }
        return str2.String()
}

func convBinary(c byte) int {
        if c == '1' {
                return 1
        }
        return 0
}
  • 同じようなアプローチの回答を読んだ
  • for loop のループで複数条件をつけるやり方があったか・・・
    • for l1 >= 0 || l2 >= 0 {
  • 2進数を扱う問題だったのでビット演算子の出番だったのも気がつけず
    • c = rs >> 1
  • strings.Builder で文字列の連結が行える
  • Atoi は error も return するのに Iota は error を return しないのは何でだろう？
    • 追記:
      • Itoa の場合、文字列変換に失敗する数値は存在しない
      • Aoti の場合、数値変換に失敗する文字列は存在する。例えば aaa とか
      • なので冷静に考えたら当たり前だった
  • アプローチは大きく間違っていなかったものの、標準ライブラリや演算子のボキャブラリーが不足していた。あと疲れであまり頭が働かなかった。
    • アルゴリズムの学習も必要だが、実際に必要となるコーディング力をつけるためには標準ライブラリなど組み込みの機能を色々把握しておくのが大事そう

See Also