难度: Easy
给定一个32位整数 num，你可以将一个数位从0变为1。请编写一个程序，找出你能够获得的最长的一串1的长度。
示例 1：
输入: num = 1775(110111011112)
输出: 8
示例 2：
输入: num = 7(01112)
输出: 4
Submission
运行时间: 22 ms
内存: 16.1 MB
class Solution:
def reverseBits(self, num: int):
bi = [int(x) for x in (bin(num & 0xFFFFFFFF) if num < 0 else bin(num)).split('0b')[1]]
n = len(bi)
dp = [[0, 0, False] for x in range(n)]
dp[0] = [1 if bi[0] == 1 else 0, 1, False if bi[0] == 1 else True]
for i in range(1, n):
if bi[i] == 1:
dp[i][0] = dp[i-1][0] + 1
dp[i][1], dp[i][2] = dp[i-1][1] + 1, dp[i-1][2]
else:
dp[i][0] = 0
dp[i][1] = dp[i-1][0] + 1
dp[i][2] = not dp[i-1][2]
t1 = max([dp[i][0] for i in range(n)])
t2 = max([dp[i][1] for i in range(n)])
# add a zero at the first to reverse if num > 0
return max(t1+1, t2) if num >= 0 else max(t1, t2)
Explain
题解采用了动态规划的方式来处理问题。首先，将输入的整数 `num` 转换为二进制表示的列表 `bi`。每个元素 `bi[i]` 代表二进制位上的 0 或 1。动态规划表 `dp` 用于记录到当前位为止的无需翻转和翻转一次后的连续 1 的最大长度。 每个 `dp[i]` 包含三个元素：`dp[i][0]` 表示不翻转当前位时前 `i` 位的最长连续 1 的长度；`dp[i][1]` 表示翻转一次后前 `i` 位的最长连续 1 的长度，`dp[i][2]` 表示是否已经翻转过位值。初始状态和状态转移都针对当前位是否为 1 或 0 进行不同的处理。最后，从 `dp` 中找出最长的连续 1 的长度，并根据 `num` 的正负情况决定是否加一（针对全 1 的情况）。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def reverseBits(self, num: int):
# 将num转换为二进制列表，其中每个元素存储一个位的值
bi = [int(x) for x in (bin(num & 0xFFFFFFFF) if num < 0 else bin(num)).split('0b')[1]]
n = len(bi)
# 初始化动态规划表，每个元素包含三个值：不翻转时的长度、翻转一次后的长度、是否翻转过
dp = [[0, 0, False] for x in range(n)]
dp[0] = [1 if bi[0] == 1 else 0, 1, False if bi[0] == 1 else True]
# 遍历二进制位，填充动态规划表
for i in range(1, n):
if bi[i] == 1:
dp[i][0] = dp[i-1][0] + 1
dp[i][1], dp[i][2] = dp[i-1][1] + 1, dp[i-1][2]
else:
dp[i][0] = 0
dp[i][1] = dp[i-1][0] + 1
dp[i][2] = not dp[i-1][2]
# 计算最长连续1的长度
t1 = max([dp[i][0] for i in range(n)])
t2 = max([dp[i][1] for i in range(n)])
# 根据num的符号决定是否需要在结果上加一
return max(t1+1, t2) if num >= 0 else max(t1, t2)
Explore
`dp[i][0]`表示在第i位不进行翻转时，从开始到当前位的最长连续1的长度。`dp[i][1]`表示如果在第i位或之前的某一位进行了一次翻转，从开始到当前位的最长连续1的长度。`dp[i][2]`是一个布尔值，表示到当前位为止是否已经进行过翻转。如果`dp[i][2]`为True，表示在第i位或之前的某一位已经进行了翻转；如果为False，表示到第i位为止还没有进行翻转。这有助于决定在后续位是否还可以进行翻转。
初始化`dp[0]`时，如果`bi[0]`为0，则将`dp[0][1]`设为1，这代表我们选择翻转第一个位，从而使得从第一个位开始的连续1的长度为1。这确实意味着我们默认翻转了第一个位，以此来考虑最优解的情况，即使用一次翻转机会获得尽可能长的连续1序列。
对于`bi[i] == 0`的情况，`dp[i][1]`的值设置为`dp[i-1][0] + 1`表示我们选择在第i位进行翻转（将0翻转为1），并且在此之前的位没有进行过翻转。这样，我们使用了一次翻转机会，以将当前0位转变为1。这确实意味着我们在此处考虑的是从未翻转的状态转变到翻转的状态，以最大化利用单次翻转的优势。