[leetcode 1611][Go][位运算][记忆化搜索]使整数变为 0 的最少操作次数

题目链接

leetcode 1611 使整数变为 0 的最少操作次数

解题思路

递归(超时)

根据题目得知，要将数n变为0，那只能从左往右将所有为1的位数翻转。设i为下标从左往右遍历，若第i为为1则进行翻转，翻转时无论第i位为1还是0都需要分为以下三种情况处理:

  • 若i为0则直接翻转
  • 若i大于0且i-1为0则先递归处理将i-1翻转为1，翻转后再按照下面的情况处理
  • 若i大于0且i-1为1则设j = [i-2, 0]，遍历j，若第j位为1则先递归翻转第j位

根据以上子问题就可以初步构建递归函数:

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
//判断第i位是否为0
var isZero = func(n int, i int) bool {
	return 1<<i|n != n
}

//翻转第i位，返回操作次数和进行翻转后得到的数字
var reverse func(n int, i int) (int, int)
reverse = func(n, i int) (int, int) {
    //若i为0直接翻转
    if i == 0 && isZero(n, 0) {
        return 1, n + 1
    } else if i == 0 {
        return 1, n - 1
    }

    var ret int
    //若i-1位为0则递归处理将i-1位翻转为1
    if isZero(n, i-1) {
        d, m := reverse(n, i-1)
        ret += d
        n = m
    }
    //遍历并递归翻转[i-2,0]上所有1
    for j := i - 2; j >= 0; j-- {
        if !isZero(n, j) {
            d, m := reverse(n, j)
            ret += d
            n = m
        }
    }
    if isZero(n, i) {
        n = 1<<i | n
    } else {
        n = ((1<<bits.Len(uint(n)) - 1) - (1 << i)) & n
    }
    ret++
    return ret, n
}

然后在主函数中循环翻转最左侧的1直到n为0即可: 

1
2
3
4
5
6
7
var ret int
for n != 0 {
    d, m := reverse(n, bits.Len(uint(n))-1)
    ret += d
    n = m
}
return ret
但这段代码在就会超时

记忆化搜索

因为翻转i只会影响[i, 0]上的位数，那么就可以在每次递归时将[i, 0]上的数字和i记录下来，这样在之后的递归中遇到相同的情况就能在O(1)时间内拿到结果 

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
42
//key[0]表示[i, 0]位上的数, key[1]表示i
//value[0]表示翻转需要的操作数，value[1]表示翻转后[i, 0]位的数
var hash = make(map[[2]int][2]int)
var reverse func(n int, i int) (int, int)
reverse = func(n, i int) (int, int) {
    if i == 0 && isZero(n, 0) {
        return 1, n + 1
    } else if i == 0 {
        return 1, n - 1
    }
    //提取[i, 0]位并查询
    if m, ok := hash[[2]int{n & (1<<(i+1) - 1), i}]; ok {
        //若有记录，则将[i,0]重置为0再将m覆盖到[i,0]位
        n &= (1<<bits.Len(uint(n)) - 1) - (1<<(i+1) - 1)
        n |= m[1]
        return m[0], n
    }
    var ret int
    //因为后面的翻转操作会导致[i,0]位变化所以提前记录key
    var key = [2]int{n & (1<<(i+1) - 1), i}
    if isZero(n, i-1) {
        d, m := reverse(n, i-1)
        ret += d
        n = m
    }
    for j := i - 2; j >= 0; j-- {
        if !isZero(n, j) {
            d, m := reverse(n, j)
            ret += d
            n = m
        }
    }
    if isZero(n, i) {
        n = 1<<i | n
    } else {
        n = ((1<<bits.Len(uint(n)) - 1) - (1 << i)) & n
    }
    ret++
    //记录进哈希表
    hash[key] = [2]int{ret, n & (1<<(i+1) - 1)}
    return ret, n
}

完整代码

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
42
43
44
45
46
47
48
49
50
func isZero(n int, i int) bool {
	return 1<<i|n != n
}

func minimumOneBitOperations(n int) int {
	var hash = make(map[[2]int][2]int)
	var reverse func(n int, i int) (int, int)
	reverse = func(n, i int) (int, int) {
		if i == 0 && isZero(n, 0) {
			return 1, n + 1
		} else if i == 0 {
			return 1, n - 1
		}
		if m, ok := hash[[2]int{n & (1<<(i+1) - 1), i}]; ok {
			n &= (1<<bits.Len(uint(n)) - 1) - (1<<(i+1) - 1)
			n |= m[1]
			return m[0], n
		}
		var ret int
		var key = [2]int{n & (1<<(i+1) - 1), i}
		if isZero(n, i-1) {
			d, m := reverse(n, i-1)
			ret += d
			n = m
		}
		for j := i - 2; j >= 0; j-- {
			if !isZero(n, j) {
				d, m := reverse(n, j)
				ret += d
				n = m
			}
		}
		if isZero(n, i) {
			n = 1<<i | n
		} else {
			n = ((1<<bits.Len(uint(n)) - 1) - (1 << i)) & n
		}
		ret++
		hash[key] = [2]int{ret, n & (1<<(i+1) - 1)}
		return ret, n
	}

	var ret int
	for n != 0 {
		d, m := reverse(n, bits.Len(uint(n))-1)
		ret += d
		n = m
	}
	return ret
}