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

执行结果如下:

图片


题目来自左神,代码是自己写的。