https://leetcode-cn.com/problems/super-washing-machines/

由于思路不对,没写出来,参考官方题解,逆向分析解题思路。

运行case

这个case的结果为5,因为7,4,这两个位置,需要向右移动至少5次,所以至少要移动5次。

###caseItem.input:[7 4 0 0 1 6]
key:0,num:7,sum:0,ans:0
key:0,num:4,sum:4,ans:4

key:1,num:4,sum:4,ans:4
key:1,num:1,sum:5,ans:5

key:2,num:0,sum:5,ans:5
key:2,num:-3,sum:2,ans:5

key:3,num:0,sum:2,ans:5
key:3,num:-3,sum:-1,ans:5

key:4,num:1,sum:-1,ans:5
key:4,num:-2,sum:-3,ans:5

key:5,num:6,sum:-3,ans:5
key:5,num:3,sum:0,ans:5

###caseItem.ret:5

这个case由于最大值为18,所以最大值就为18这个节点,流出的数量15

###caseItem.input:[18 0 0 0 0 0]
key:0,num:18,sum:0,ans:0
key:0,num:15,sum:15,ans:15

key:1,num:0,sum:15,ans:15
key:1,num:-3,sum:12,ans:15

key:2,num:0,sum:12,ans:15
key:2,num:-3,sum:9,ans:15

key:3,num:0,sum:9,ans:15
key:3,num:-3,sum:6,ans:15

key:4,num:0,sum:6,ans:15
key:4,num:-3,sum:3,ans:15

key:5,num:0,sum:3,ans:15
key:5,num:-3,sum:0,ans:15

###caseItem.ret:15

解题

package main

import "fmt"

type testCase517 struct {
    want  int
    input []int
}

func main() {
    var inputList []testCase517
    inputList = []testCase517{
        //{0, []int{2}},
        //{-1, []int{0, 2, 0}},
        //{3, []int{1, 0, 5}},
        //{2, []int{0, 3, 0}},
        //{2, []int{4, 0, 0, 4}},
        //{4, []int{0, 4, 0, 0, 6}},
        //{3, []int{0, 4, 5, 2, 1, 6}},
        //{3, []int{9, 0, 9}},
        {5, []int{7, 4, 0, 0, 1, 6}}, //18 3
        //{15, []int{18, 0, 0, 0, 0, 0}},
    }
    for _, caseItem := range inputList {
        fmt.Printf("###caseItem.input:%+v\n", caseItem.input)
        ret := findMinMoves(caseItem.input)
        fmt.Printf("###caseItem.ret:%+v\n\n", ret)
        if ret != caseItem.want {
            fmt.Printf("!!!wrongCase:%+v,wrongRet:%d\n", caseItem, ret)
        }
    }
}

func findMinMoves(machines []int) (ans int) {
    n := len(machines)
    //衣服总数
    tot := 0
    for _, itemCount := range machines {
        tot += itemCount
    }
    //是否能均分
    if tot%n > 0 {
        return -1
    }
    //每个洗衣机里面的目标数量
    avg := tot / n
    //当前洗衣机需要移动的数量,>0为向右移动,<0为向左移动
    sum := 0
    for key, num := range machines {
        fmt.Printf("key:%v,num:%v,sum:%v,ans:%v\n", key, num, sum, ans)
        //计算当前与均值的差
        num -= avg
        //记录当前节点需要移动的数量
        sum += num
        //计算节点移动量 和 节点差值的max
        ans = max(ans, max(abs(sum), num))
        fmt.Printf("key:%v,num:%v,sum:%v,ans:%v\n\n", key, num, sum, ans)
    }
    return
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

最后修改:2021 年 09 月 30 日 11 : 27 AM
如果觉得我的文章对你有用,请随意赞赏