2022-01-03:比如arr = {3,1,2,4},
下标对应是:0 1 2 3,
你最开始选择一个下标进行 *** 作,一旦最开始确定了是哪个下标,以后都只能在这个下标上进行 *** 作。
比如你选定1下标,1下标上面的数字是1,你可以选择变化这个数字,比如你让这个数字变成2,
那么arr = {3,2,2,4}。
下标对应是:0 1 2 3,
因为你最开始确定了1这个下标,所以你以后都只能对这个下标进行 *** 作,
但是,和你此时下标上的数字一样的、且位置连成一片的数字,会跟着一起变。
比如你选择让此时下标1的数字2变成3,
那么arr = {3,3,3,4} 可以看到下标1和下标2的数字一起变成3,这是规则!一定会一起变。
下标对应是:0 1 2 3,
接下来,你还是只能对1下标进行 *** 作,那么数字一样的、且位置连成一片的数字(arr[0~2]这个范围)都会一起变,
决定变成4。
那么arr = {4,4,4,4},
下标对应是:0 1 2 3,
至此,所有数都成一样的了,你在下标1上做了3个决定(第一次变成2,第二次变成3,第三次变成4),
因为联动规则,arr全刷成一种数字了。
给定一个数组arr,最开始选择哪个下标,你随意,
你的目的是一定要让arr都成为一种数字,注意联动效果会一直生效,
返回最小的变化数。
arr长度 <= 200, arr中的值 <= 10^6。
来自腾讯。
答案2022-01-03:
递归。
代码用golang编写。代码如下:
package main import ( "fmt" "math" ) func main() { ret := process([]int{3, 1, 2, 4}, 2, 2, 2) fmt.Println(ret) } func process(arr []int, left, midV, right int) int { for left >= 0 && arr[left] == midV { left-- } for right < len(arr) && arr[right] == midV { right++ } if left == -1 && right == len(arr) { return 0 } p1 := math.MaxInt64 if left >= 0 { p1 = process(arr, left-1, arr[left], right) + 1 } p2 := math.MaxInt64 if right < len(arr) { p2 = process(arr, left, arr[right], right+1) + 1 } return getMin(p1, p2) } func getMin(a, b int) int { if a < b { return a } else { return b } }
执行结果如下:
左神java代码
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)