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)
}

代码结果如下:

图片

左神java代码
评论