2022-01-08：数组中只有0和1，每过1代，0旁边只有1个1，当前0
原创2022-01-08：数组中只有0和1，每过1代，0旁边只有1个1，当前0
原创
福大大架构师每日一题
发布于 2022-01-08 18:22:28
发布于 2022-01-08 18:22:28
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
}
}
}执行结果如下：
图片
题目来自左神，代码是自己写的。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读