LeetCode 66. Plus One & 67. Add Binary

Plus One

Description

给定一个用数组表示的十进制数，将数字加一。

Example 1:

1
2
3
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

1
2
3
Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func plusOne(digits []int) []int {
    for i := len(digits) - 1; i >= 0; i-- {
        if digits[i] != 9 {
            digits[i]++
            return digits
        }
        digits[i] = 0
    }

    return append([]int{1}, digits...)
}

Add Binary

Discription

Add Binary

将两个二进制字符串相加

Example 1:

1
2
Input: a = "11", b = "1"
Output: "100"

Example 2:

1
2
Input: a = "1010", b = "1011"
Output: "10101"

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func addBinary(a string, b string) string {
    aLen := len(a)
    bLen := len(b)

    limit := aLen
    if bLen > limit {
        limit = bLen
    }

    s := make([]byte, limit+1)

    var carry byte
    var idx int
    for i := 1; i <= limit; i++ {
        idx = aLen - i
        if idx >= 0 {
            carry += a[idx] - '0'
        }

        idx = bLen - i
        if idx >= 0 {
            carry += b[idx] - '0'
        }

        // 因为 s 长度为 limit+1，所以需要 limit-i+1
        s[limit-i+1] = carry&0x01 + '0'
        carry >>= 1
    }

    // 起初 s 申请的长度为 limit：make([]byte, limit)
    // 然后判断 carry 为 1 的时候 s = append([]byte{'1'}, s...)
    // 这样导致第二次申请内存，耗时增加
    // 所以直接申请 limit + 1 长度，返回时少返回一位
    if carry == 0 {
        return string(s[1:])
    }

    s[0] = '1'

    return string(s)
}