2021-11-19:0,4,7 : 0表示这里石头没有颜色,如果变红代价是4,如果变蓝代价是7,1,X,X : 1表示这里石头已经是红,而且不能改颜色,所以后两个数X无意义,2,X,X : 2表示这里石头已经是蓝,而且不能改颜色,所以后两个数X无意义,颜色只可能是0、1、2,代价一定>=0,给你一批这样的小数组,要求最后必须所有石头都有颜色,且红色和蓝色一样多,返回最小代价。如果怎么都无法做到所有石头都有颜色、且红色和蓝色一样多,返回-1。来自小红书。
答案2021-11-19:
(资料图片)
1.排序。具体见代码。
2.统计无色,红色,蓝色个数。
3.如果红色或者蓝色过半,直接返回-1。
4.遍历,计算最小代价。具体见代码。
时间复杂度:排序的。
空间复杂度:排序的。
代码用golang编写。代码如下:
package mainimport ( "fmt" "sort")func main() { stones := [][]int{{0, 2, 4}, {0, 4, 1}} ret := minCost(stones) fmt.Println(ret)}func minCost(stones [][]int) int { n := len(stones) if (n & 1) != 0 { return -1 } sort.Slice(stones, func(i, j int) bool { a := stones[i] b := stones[j] if a[0] == 0 && b[0] == 0 { return b[1]-b[2]-a[1]+a[2] < 0 } else { return a[0]-b[0] < 0 } }) zero := 0 red := 0 blue := 0 cost := 0 for i := 0; i < n; i++ { if stones[i][0] == 0 { zero++ cost += stones[i][1] } else if stones[i][0] == 1 { red++ } else { blue++ } } if red > (n>>1) || blue > (n>>1) { return -1 } blue = zero - ((n >> 1) - red) for i := 0; i < blue; i++ { cost += stones[i][2] - stones[i][1] } return cost}
执行结果如下:
左神java代码
X 关闭