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 main import "fmt" func main() { for i := 1; i <= 10; i++ { ret := ff(i) fmt.Println(i, ret) } } //一个一个试,最直观思维 func ff(n int) int { ansval := 0 ans := &ansval arr := make([]int, n) //第0个位置,肯定是1 arr[0] = 1 process(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] = 0 process(arr, start+1, ans) } arr[start] = 1 process(arr, start+1, ans) }
代码结果如下: