2022-01-08：数组中只有0和1，每过1代，0旁边只有1个1，当前0

原创

福大大架构师每日一题

发布于 2022-01-08 10:22:28

3250

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-01-08：数组中只有0和1，每过1代，0旁边只有1个1，当前0会变成1。每过1代，0旁边有2个1，当前0还是0。

比如10001，经过1代，会变成11011，再过1代，还是11011 。

求一个数组经过M代以后的数组。函数定义是void f(int[] arr,int m) 。

答案2022-01-08：

x里有有限个0。

1x1，中间0，x中有2m个0变成1，最中间的0不会变成1。

1x，右0，x中有m个0变成1。

x1，左0，x中有m个0变成1。

时间复杂度：O(N)。

空间复杂度：O(1)。

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

package main

import "fmt"

func main() {
    arr := []byte{0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0}
    f(arr, 2)
    fmt.Println(arr)
}

func f(arr []byte, m int) {
    //找中间0
    oneIndexList := make([]int, 0)
    for i, a := range arr {
        if len(oneIndexList) == 2 {
            oneIndexList = oneIndexList[1:]
        }
        if a == 1 {
            oneIndexList = append(oneIndexList, i)
        }
        if len(oneIndexList) == 2 {
            for j := oneIndexList[0] + 1; j <= oneIndexList[1]-1; j++ {
                if j-oneIndexList[0] != oneIndexList[1]-j &&
                    (j-oneIndexList[0] <= m ||
                        oneIndexList[1]-j <= m) {
                    arr[j] = 1
                }
            }
        }
    }

    //找左0
    oneLeftIndex := 0
    for i, a := range arr {
        if a == 1 {
            oneLeftIndex = i
            break
        }
    }
    if oneLeftIndex > 0 {
        left := oneLeftIndex - m
        right := oneLeftIndex - 1
        if left < 0 {
            left = 0
        }
        for i := left; i <= right; i++ {
            arr[i] = 1
        }
    }

    //找右0
    oneRightIndex := len(arr) - 1
    for i := oneRightIndex; i >= 0; i-- {
        a := arr[i]
        if a == 1 {
            oneRightIndex = i
            break
        }
    }
    if oneRightIndex < len(arr)-1 {
        left := oneRightIndex + 1
        right := oneRightIndex + m
        if right > len(arr)-1 {
            right = len(arr) - 1
        }
        for i := left; i <= right; i++ {
            arr[i] = 1
        }
    }
}