题目:

给定一个整数len,求长度为len且仅为为字符’0′与’1′组成的所有可能的字符串中,有多少字符串满足:如果出现’0′的位置,它的左边必有’1′。
例如:
len = 1
所有可能的字符串:”1″和”0″,满足如果出现’0′的位置,它的左边必有’1′的字符串:”1″;
因为”0″字符串中,出现’0′的位置,左边就越界了;
所以返回1;

len = 2
所有可能的字符串:”00″、”01″、”10″和”11″,满足如果出现’0′的位置,它的左边必有’1′的字符串:”10″,”11″;
因为”01″字符串中,出现’0′的位置,左边就越界了;”00″中出现’0′的位置,左边要么越界,要么是’0′;
所以返回2;

len = 3
所有可能的字符串:”000″、”001″、”010″、”011″、”100″、”101″、”110″、”111″,满足如果出现’0′的位置,它的左边必有’1′的字符串:”101″、”110″、”111″;
所以返回3;

 

解答:

O(2^Len * len)方法难度:士
O(2^len)方法难度:尉
O(len)方法难度:尉
O(log(len))方法难度:校

O(2^Len * len)方法是一种直接根据题意来求解的方法。
首先长度为len且仅为为字符’0′与’1′组成的所有可能的字符串,其实就是范围为[0,(2^length)-1]的所有整数的二进制表达。
如len为4时,0用一个长度为4的char数组表示为{’0′,’0′,’0′,’0′},1为{’0′,’0′,’0′,’1′},…,15为{’1′,’1′,’1′,’1′},同时经过进一步分析我们知道,如果最左边的字符为’0′的数组,那么一定不满足出现’0′的位置左边必有’1′这个条件,所以我们从{’1′,’0′,’0′,’0′}开始检查即可;
接下来只要写一个函数,实现char数组可以像二进制数那样累加1,就可以依次得到所有可能的字符串了,例如:{’1′,’0′,’0′,’0′},累加1之后变为{’1′,’0′,’0′,’1′},具体请参看如下代码中的addOneToCharArr方法;
在依次累加的过程中,再实现一个检查char数组是否是满足条件的char数组,具体请参看如下代码中的isValid方法;
依次累加依次检查的过程中,发现一个符合条件的char数组出现,就将result++,最终result作为结果返回;
全部过程一共要检查2^(Len-1)个char数组,每一次检查要遍历数组的len-1个字符,所以最终的时间复杂度O(2^Len * len)。
整体过程就是如下代码中的getValidStatusNum1方法。

 

O(2^len)方法是一种利用朴素递归函数求解的方法。
递归函数 int computeProcess(int index, int length):
参数:
index:表示递归函数目前处理到index位置(最左侧为0位置)
length:表示我们题目中说的len的值
返回值:
表示在假设index-1位置一定是’1′的情况下,从index-1位置一直到length位置可以满足条件的字符串有多少

在假设index-1位置一定是’1′的情况下,当前的index位置可以是’1′也可以是’0′,
如果是’1′,满足条件的字符串数量就是computeProcess(index + 1, length)的值;
如果是’0′,说明index+1位置只能是’1′,这时满足条件的字符串数量就是computeProcess(index + 2, length)的值;
两者相加的值就是在假设index-1位置一定是’1′的情况下,从index-1位置一直到length位置可以满足条件的字符串有多少。
递归函数一共有len层,每一层两个递归分支,所以时间复杂度O(2^len),具体请参看如下代码中的getValidStatusNum2方法。
O(2^len)方法代码:

 

有了上一步的递归过程,我们发现computeProcess(index,length)的值,基本上就是computeProcess(index+1,length)与computeProcess(index+2,length)的累加,这让你想到什么?斐波那契数列。
先看一下在len分别为1,2,3,4,5,6,7,8的时候,结果是什么:1,2,3,5,8,13,21,34,…。没错,这个数列和斐波那契数列唯一的区别就是初始项不同,但是第i项的值就是i-1项和i-2项的累加。
所以O(len)方法特别容易可以得到,具体请参看如下代码中getValidStatusNum3方法。
O(len)方法代码: 

 

打开了斐波那契数列的这个天窗,我们知道类似斐波那契数列的过程,有一个时间复杂度O(logN)方法就是用矩阵乘法的办法求解。具体解释请参看精讲文章”脑客精讲(003):斐波那契数列的3种解法

 

O(log(len))方法代码:

欢迎留言