Flip Bit to Win: 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 ls you could create.
EXAMPLE
1
2
3
|
Input: 11001101111
^
Output: 7
|
Hints: #159, #226, #314,#352
解法1
暴力解法：
- 从右到左找
0在哪个位置
- 记住这个位置，在数字中数连续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
43
44
|
public int flipToWin(int num) {
int zeroIndex = zeroIndex(num, 0);
int maxLength = 0;
while (zeroIndex != -1) {
int length = maxContinousOne(num, zeroIndex);
if (length > maxLength) {
maxLength = length;
}
zeroIndex = zeroIndex(num, zeroIndex + 1);
}
return maxLength;
}
// 找0的下标
private int zeroIndex(int num, int start) {
for (int i = start; i < 32; i++) {
int bit = 1 << i;
if (num & bit == 0) {
return i;
}
}
return -1;
}
// 返回最大连续1的长度，当碰到zeroIndex的时候，当作是1
private int maxContinousOne(int num, int zeroIndex) {
int length = 0;
int maxLength = 0;
for (int i = 0; i < 32; i++) {
int bit = 1 << i;
if (num & bit != 0) {
length++;
} else if (i == zeroIndex) {
length++;
} else {
// 遇到0了
if (length > maxLength) {
maxLength = length;
}
length = 0;
}
}
return maxLength;
}
|
时间复杂度：O(d * b)，d代表0的数量，b代表num的比特数。
空间复杂度：O(d)，d代表0的数量
解法2
构建一个数组，里面记录连续0和连续1的长度，数组的构建是从低位到高位的，比如11001101111的数组是[0, 4, 1, 2, 2, 2, 21]，数组的第1个元素总是代表0的数量，后面每增加一个元素则反转代表0或1：
1
2
3
|
[0, 4, 1, 2, 2, 2, 21]
^ ^ ^ ^ ^ ^ ^
0 1111 0 11 00 11 000000000000000000000
|
因为第一个元素总是代表0，并且下一个元素反转为1，那么就意味着每隔两个元素就又是0。我们只需要看这个0的数量是否 == 1，如果是1则可以把左右两边的元素相加再加1（两边的1可以合并），如果 > 1则要么左边的加1，要么右边的加1（可以借用一个0），如果 == 0则等于右边的数，然后取最大值就行了。
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
|
public List<Integer> makeCount(int num) {
List<Integer> result = new ArrayList<>();
int count = 0;
int seek = 0;
for (int i = 0; i < 32; i++) {
if (num & 1 == seek) {
count++;
} else {
result.add(count);
seek = num & 1; // 翻转为0或1
count = 1;
}
num = num >>> 1;
}
result.add(count);
return result;
}
public int flipToWin(int num) {
if (~num == 0) {
// 已经全都是1了
return 32;
}
List<Integer> result = makeCount(num);
int maxLength = 0;
for (int i = 0; i < result.size(); i += 2) {
int zeros = result.get(i);
int leftOnes = i > 0 ? result.get(i - 1) : 0;
int rightOnes = i < result.size() - 1 ? result.get(i + 1) : 0;
int seq = 0;
if (zeros == 1) {
seq = leftOnes + 1 + rightOnes;
} else if (zeros > 1) {
seq = Math.max(leftOnes + 1, rightOnes + 1);
} else {
seq = rightOnes;
}
maxLength = Math.max(maxLength, seq);
}
return maxLength;
}
|
时间复杂度：makeCount=O(1)，实际上是循环了32次。flipToWin则是O(b)，b代表了数组的数量。
空间复杂度：O(b)，b代表数组的数量。
解法3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public int flipToWin(int num) {
if (~num == 0) {
return 32;
}
int currentLength = 0; // 记录当前连续1的数量
int previousLength = 0; // 记录上一次连续1的数量
int maxLength = 0;
while (a != 0) {
if ((a & 1) == 1) {
// 当前是1
currentLength++;
} else {
// 当前是0
// 看下一个bit是0还是1，如果是0，那么说明可以连接，否则不能连接
// 两段连续1可以连接时，previousLength和currentLength都不为0
previousLength = (a & 2) == 0 ? 0 : currentLength;
currentLength = 0;
}
maxLength = Math.max(previousLength + currentLength + 1, maxLength);
a >>>= 1;
}
}
|
时间复杂度：O(b)
空间复杂度：O(1)
评论