2021-02-05：给定一个数N，想象只由0和1两种字符，组成的所有长度为N的字符串。如果某个字符串,任何0字符的左边都有1紧挨着,认为这个字符串达标。请问有多少达标的字符串？

2021-02-05：给定一个数N，想象只由0和1两种字符，组成的所有长度为N的字符串。如果某个字符串,任何0字符的左边都有1紧挨着,认为这个字符串达标。请问有多少达标的字符串？

福哥答案2021-02-05：
举例：
N=6
[1 0 1 0 1 0]
[1 0 1 0 1 1]
[1 0 1 1 0 1]
[1 0 1 1 1 0]
[1 0 1 1 1 1]
[1 1 0 1 0 1]
[1 1 0 1 1 0]
[1 1 0 1 1 1]
[1 1 1 0 1 0]
[1 1 1 0 1 1]
[1 1 1 1 0 1]
[1 1 1 1 1 0]
[1 1 1 1 1 1]
总共13种。

这道题是斐波那契数列。代码不用斐波那契数列，用递归最直观。

代码用golang编写，代码如下：

package mainimport "fmt"func main() {for i := 1; i <= 10; i++ {ret := ff(i)fmt.Println(i, ret)}
}//一个一个试，最直观思维
func ff(n int) int {ansval := 0ans := &ansvalarr := make([]int, n)//第0个位置，肯定是1arr[0] = 1process(arr, 1, ans)return *ans
}//递归
func process(arr []int, start int, ans *int) {if start == len(arr) {*ans++return}if arr[start-1] == 1 {arr[start] = 0process(arr, start+1, ans)}arr[start] = 1process(arr, start+1, ans)
}

代码结果如下：

左神java代码
评论