【数据结构与算法】二进制字符串的划分

发表于 更新于 分类于 阅读次数：
本文字数： 2.8k 阅读时长 ≈ 3 分钟

问题说明

给定一个长度为 \(n\) 的二进制字符串。

判断是否可以将字符串分割为 \(i\) 个部分，其中 \(i \in \left\{0,2,\cdots,n \right\}\)，使得每个部分的十进制为 \(7\) 的整数次幂。返回最小的分割的部分的数目。

  • If \(x= 111110001\), then the following partition gives powers of \(7\): \(111 \mid 110001\). (\(111_2 = 7, 110001_2 = 49\)). In this case, the answer is \(2\) and this is the best way to divide \(x\) into powers of \(7\).
  • If \(x=11111\), then it is possible to divide \(x\) such that every part is a power of \(7\) as follows \(1\mid 1 \mid 1 1 1\). Hence, in this case, the answer is \(3\).
  • If \(x=011111\), then it is not possible to divide \(x\) such that every part is a power of \(7\). Hence, in this case, the answer is \(-1\). (Recall, leading zeros are not allowed.)
  • If \(x=111111\), then it is possible to divide \(x\) such that every part is a power of \(7\) in two ways. \(1\mid 1 \mid 1\mid 1\mid 1\mid 1\) has \(6\) parts and \(111\mid 111\) has \(2\) parts. Hence, in this case, the answer is \(2\).

For simplicity, leading zeros are not allowed in our definition of the powers of \(7\). \(111\) is a power of \(7\) but \(0111\) is not a power of \(7\).

代码部分

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import sys
import math
import re

# global
bestSplitNum = sys.maxsize # Assumed minimum number of divisions
powers = list() # store all the powers

def split(strTemp, start, depth):
    """
    use bfs method to find the shortest path
    """
    global bestSplitNum
    global powers

    if depth >= bestSplitNum:
        return

    if start == len(strTemp):
        bestSplitNum = depth
        return
    
    for power in powers:
        # print(power)
        if strTemp.startswith(power, start):
            split(strTemp, start + len(power), depth + 1)


def calNumSplit(strTemp):
    """
    the smallest positive integer
    """
    global bestSplitNum
    global powers

    # calc all powers of 7 that fits in given string
    pow = 1
    powers.append('1')
    while pow:
        binaryPowStr = str(bin(int(math.pow(7,pow))))[2:] # get the binary string
        if (len(binaryPowStr) <= len(strTemp)):
            powers.append(binaryPowStr)
        else:
            break
        pow += 1

    powers.sort(reverse=False) # Sort binary strings in descending order
    # print(powers)

    # do recursive split
    split(strTemp, 0, -1)

    if bestSplitNum == sys.maxsize:
        print(-1)
    else:
        print(bestSplitNum + 1)
    
def reset():
    """
    reset the global variable
    """
    global bestSplitNum
    global powers
    bestSplitNum = sys.maxsize # Assumed minimum number of divisions
    powers = list() # store all the powers


if __name__ == "__main__":

    strTest1 = "111110001"
    strTest2 = "11111"
    strTest3 = "011111"
    strTest4 = "111111"

    print("If the string is '111110001', the answer is: ", sep='')
    calNumSplit(strTest1) # 2
    reset()
    print("If the string is '11111', the answer is: ", sep='')
    calNumSplit(strTest2) # 3
    reset()
    print("If the string is '011111', the answer is: ", sep='')
    calNumSplit(strTest3) # -1
    reset()
    print("If the string is '111111', the answer is: ", sep='')
    calNumSplit(strTest4) # 2
    reset()

参考