【Leetcode】600. Non-negative Integers without Consecutive Ones 解题报告
【Leetcode】600. Non-negative Integers without Consecutive Ones 解题报告
题目:求小于等于n的数中,其二进制中不含相邻两个1的数的个数。
解题思路:
首先考虑类似的问题:一个长度小于等于n的二进制数中,满足上述条件(无连续1)的数有多少个。这个问题怎么解?
首先我们做一下推演,挖掘一下规律是什么?
先摸索一下:
1)长度为1时:
0和1
2)长度为2时:
此时的组合是不是,取决于第一位?
如果第一位是0,那么,第二位就既可以是0也可以是1,即10,00;
如果第一位是1,我们第二位只能是0(不能有连续的1)即01,(11不符合条件)。
3)分段(条件):
简单摸索之后,我们发现,整体上需要分两种情况讨论,当结尾为0时,和结尾为1时,那么最后的总数,就是二者之和。
OK!!!那么我们正式开始推演一下:
首先,我们初始化,两个数组(列表)来存储,每个位置的符合要求的情况个数:
# a[i]表示以0结尾长度为i的数的个数
# b[i]表示以1结尾长度为i的数的个数
a = [0]*n
b = [0]*n
此处假设n=4:
第一步:n=1时:
以0结尾,只有一种情况:0
以1结尾,只有一种情况:1
# a[i]表示以0结尾长度为i的数的个数
# b[i]表示以1结尾长度为i的数的个数
a = [1,0,0,0]
b = [1,0,0,0]
第二步:n=2时:
1)以0结尾情况,第二位,可以是0也可以是1,
a)当我们第二位固定是0时,当前符合条件的数字个数,取决于之前的位有几种情况,他就有多少种情况,因为0不和任何数字冲突,此时他前面有一位,也就是0,所以有1个符合条件的数字;
b)当我们第二位固定1时候,第一位也是0,所以符合条件的个数也未1;
所以两种情况之和就是n=2时,结尾为0情况下,符合条件的数字个数2;
2)以1结尾情况,第二位只能固定为0,不能是1,所以当前次数,取决于前一位情况的个数,还是1中情况;
# a[i]表示以0结尾长度为i的数的个数
# b[i]表示以1结尾长度为i的数的个数
a = [1,2,0,0]
b = [1,1,0,0]
第三步:n=3时:
1)以0结尾情况,第3位,可以是0也可以是1,
a)当我们第三位固定是0时,当前符合条件的数字个数,取决于之前的位有几种情况,他就有多少种情况,因为0不和任何数字冲突,此时他前面有2位时候,结尾为0的情况下,符合条件的个数为2,所以有2个符合条件的数字(010,000);
b)当我们第二位固定1时候,为了避免冲突:它的下一位必须是0(如:10*),所以,相当于前两位是固定的,那么当前条件下,符合条件的数字个数取决于标*的位置时候,有多少个符合条件的,也就是第一位,只能是0,所以有一种情况(100);
所以两种情况之和就是n=3时,结尾为0情况下,符合条件的数字个数3;
2)以1结尾情况,第3位可以是0,也可以是1:
a)当我们第三位固定是0时,它的前一位既可以是0也可以是1,所以,就是n=2时候的,以1结尾情况下,的符合条件的个数1(001);
b)当我们第二位固定是1时,为了避免冲突:它的下一位必须是0(如:10*),所以,相当于前两位是固定的,那么当前条件下,符合条件的数字个数取决于标*的位置时候,有多少个符合条件的,也就是第一位,只能是0,所以有一种情况(101);
所以两种情况之和就是n=3时,结尾为1情况下,符合条件的数字个数2;
# a[i]表示以0结尾长度为i的数的个数
# b[i]表示以1结尾长度为i的数的个数
a = [1,2,3,0]
b = [1,1,2,0]
第四步:n=4时:
1)以0结尾情况,第4位,可以是0也可以是1,
a)当我们第三位固定是0时,当前符合条件的数字个数,取决于之前的位有几种情况,他就有多少种情况,因为0不和任何数字冲突,此时他前面有3位,结尾为0的情况下,符合条件的个数为3,所以有3个符合条件的数字(0 100,0 010,0 000);
b)当我们第二位固定1时候,为了避免冲突:它的下一位必须是0(如:10**),所以,相当于前两位是固定的,那么当前条件下,符合条件的数字个数取决于标*的位置时候,有多少个符合条件的,也就是第2位,a[1]位置的值,2,所以有2种情况(1000, 1010);
所以两种情况之和就是n=4时,结尾为0情况下,符合条件的数字个数3+2=5;
2)以1结尾情况,第4位可以是0,也可以是1:
a)当我们第4位固定是0时,它的前一位既可以是0也可以是1,所以,就是n=3时候的,以1结尾情况下,的符合条件的个数2(0001, 0101);
b)当我们第二位固定是1时,为了避免冲突:它的下一位必须是0(如:10**),所以,相当于前两位是固定的,那么当前条件下,符合条件的数字个数取决于标**的位置时候,有多少个符合条件的,也就是第二位,只能是0,所以有一种情况(1001);
所以两种情况之和就是n=4时,结尾为1情况下,符合条件的数字个数1+2=3;
# a[i]表示以0结尾长度为i的数的个数
# b[i]表示以1结尾长度为i的数的个数
a = [1,2,3,5]
b = [1,1,2,3]
通过以上的推演,似乎我们找到了规律“斐波数列”,没错就是斐波数列。因此我们获得如下,递推公式:
for i in range(1,n):
a[i] = a[i-1] + b[i-1]
b[i] = a[i-1]
res = a[-1] + b[-1]
对于a[i],他的上一位既可以是0也可以是1,即以0或1结尾长度为i-1的数的个数,所以有
a[i] = a[i-1] + b[i-1]
对于b[i],他的上一位只能是0,即以1结尾的长度为i-1的数的个数,所以有
b[i] = a[i-1]
这样我们就能求得长度为n的二进制满足条件的个数。
下面我们对比一下,“长度小于等于n的二进制数,不存在连续1的情况下,的数字个数”这个问题与我们实际的题干的差异是什么?
举例说明:假设,我们题干要考虑的整数位 num= 9(二进制为1001),对应到上边的问题是 n= 4,我们可以轻松的求n=4时:
a = [1,2,3,5]
b = [1,1,2,3]
res = 8
但 n = 4的时候对应的十进制数是15(1111),我们要求的是小于等于9的满足条件的数,怎么办?
1)那么什么时候,可能出现比整数本身大的情况?
例如:num=9;二进制为:1001,如果我们把两个连续的零在符合条件的情况下,其中一个变为1就会比本身大,例如,1010;
我们可以从左往右遍历:
每次找到有相邻的两个0(index 分别为i和i+1),那么我们就将res 减去b[length-i-2](length-i-1对应的是i+1到末尾的字符串的长度),因为res是第一个0后面既可以跟1又可以跟0的情况下求的结果,现在后面只有0没有1,所以我们要把对应的1产生的满足条件的数给减掉。
2)其实还有一种情况,就是连续1,例如,如果二进制数1101,如果,因为11连续了,不符合条件,所以,符合条件的数字中,11中,至少有一个会变为0,所以,任何一位变为零,都会比本身小。所以,遍历的过程中,如果遇到两个1就直接退出,以为不会出现两个1的情况,出现两个1肯定后面覆盖了10开头的所有情况。
AC代码 (耗时:32ms)
class Solution(object):
def findIntegers(self, num):
"""
:type num: int
:rtype: int
"""
num = bin(num)[2:]
length = len(num)
a = [1]*length
b = [1]*length
for i in range(1,length):
a[i] = a[i-1] + b[i-1]
b[i] = a[i-1]
result = a[-1] + b[-1]
for i in range(length-1):
if num[i] == "0" and num[i+1] == "0":
result -= b[length - i -2]
if num[i] == "1" and num[i+1] == "1":
break
return result