翻转数位
难度:
标签:
题目描述
You have an integer and you can flip exactly one bit from a 0 to a 1. Write code to find the length of the longest sequence of 1s you could create.
Example 1:
Input: num = 1775(110111011112)
Output: 8
Example 2:
Input: num = 7(01112)
Output: 4
代码结果
运行时间: 22 ms, 内存: 16.1 MB
/*
* 思路：
* 与上述思路类似，但使用Java Stream API来处理数组的转换和计算。
*/
import java.util.Arrays;
public class Solution {
public int longestSequenceAfterFlip(int num) {
if (~num == 0) return Integer.BYTES * 8;
String binaryStr = Integer.toBinaryString(num);
String[] ones = binaryStr.split("0");
return Arrays.stream(ones)
.mapToInt(String::length)
.reduce((max, curr) -> Math.max(max, curr + 1 + (curr > 0 ? 1 : 0)))
.orElse(0);
}
}
解释
方法:
题解采用了动态规划的方式来处理问题。首先，将输入的整数 `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)
代码细节讲解
🦆
题解中的动态规划表`dp`三个元素分别代表什么？如何理解`dp[i][2]`表示的是否已翻转过位值？
▷🦆
为什么初始化`dp[0]`时，即使`bi[0]`为0，翻转后的长度也被设为1？这是否意味着我们默认翻转了第一个位？
▷🦆
在动态规划的状态转移方程中，对于`bi[i] == 0`的情况，为什么`dp[i][1]`的值是`dp[i-1][0] + 1`而不是`dp[i-1][1] + 1`？这是否意味着我们只考虑从未翻转到翻转的转变？
▷