问题

给定一个以二进制编码的数字,以字符串形式呈现。如果是偶数,做除2操作;奇数做减1操作。如此往复操作,直到最后变成0,统计操作的次数
例如28 :‘11100’
第1次操作 28/2=14 1110
第2次操作 14/2=7 111
第3次操作 7-1=6 110
第4次操作 6/2=3 11
第5次操作 3-1=2 10
第6次操作 2/2=1 1
第7次操作 1-1=0 0

分析与解答

本题目看起来是一个计算题目,实际上隐含了很多有关二进制的计算细节。最初,我的计算是按照给定计算规则进行的,

第1种,暴力直接解题方法如下

package solution

// you can also use imports, for example:
// import "fmt"
// import "os"
import (
	"strconv"
)

// Solution soultion
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
	var cnt int
	num, _ := strconv.ParseInt(S, 2, 0)
	for num > 0 {
		var tmp int64
		if num%2 == 0 {
			tmp = num / 2
		} else {
			tmp = num - 1
		}
		num = tmp
		cnt++
	}

	return cnt
}
这种解决方法存在无法解决超大数的问题,主要原因在于它依赖于strconv.ParseInt()方法提供的转换精度,对于像4000个1组成的二进制字符串,完全无法计算。

第2种方法,通过对字符比特化解决

其主要依赖于把传入字符串参数S转换为byte数组

bnums := []byte(S)

然后从字符串末端开始,逢1替换为0,逢0直接去掉最末的元素

// Solution soultion
// you can write to stdout for debugging purposes, e.g.
// fmt.Println("this is a debug message")
func Solution(S string) int {
    length := len(S)
    var cnt int
    bnums := []byte(S)
    length = len(bnums)
    var b0, b1 byte = 48, 49
    for i := 0; i < length; i++ {
        if bnums[i] == b0 {
            bnums = bnums[i+1:]
            length--
            i--
        } else {
            break
        }
    }
   
    for length > 0 {
        if bnums[length-1] == b1 {
            bnums[length-1] = b0
        } else {
            bnums = bnums[:length-1]
            length--
        }
        if len(bnums) == 0 {
            break
        }
        cnt++
    }
    return cnt
}

尽管byte化方法解决了超大数的问题,但是仍然存在对golang列表切片的操作,这样不免有额外的内存开销,所以只能算是勉强解决问题。

第3种方法,直接对字符串种的1计数来解决

通过对题目二进制缩减规则观察,我们可以找到一个规律:

  • 字符串长度大于2的情况下,对于末位是1的操作减少1位,其需要操作2次,譬如: 111(7)-> 110(6)->11(3)

  • 对于末位是0的操作减少1位,其操作需要1次,譬如 110(6)->11(3)

  • 对于最后一个1其变化位0截至操作,其操作次数为1

    总结该规律,我们可以通过对传入二进制参数的字符串长度,结合统计其中1的个数,就可以计算得知需要操作的次数。

//Solution imporved solution
func Solution(S string) int {
    S = regexp.MustCompile(`^[0]+`).ReplaceAllString(S, "")
 
    var cnt int
    for _, chr := range S {
        if chr == '1' {
            cnt++
        }
    }
    return len(S) + cnt - 1
}

总结

这是一家大厂的面试题目之一,尽管看起来简单,考察的知识点却很全面,临考时候本人也只想到了一和二,但是当时提供的方案二还存在瑕疵。对于文中提供的3种方法种,第一种最直接容易,第二种需要我们对ASCII码种0和1的计数有所了解,第三种方法使用了正则表达式,主要是为了防止传入二进制数字的字符串前面带有很多0,这样会使得最后的结果不准确。

参考