南京市玄武区建设局网站,高端的食品行业网站开发,免费算命,做外掛网站空间文章目录 LeetCode#xff1f;启动#xff01;#xff01;#xff01;题目#xff1a;石子游戏 VI题目描述代码与解题思路 LeetCode#xff1f;启动#xff01;#xff01;#xff01; 题目#xff1a;石子游戏 VI
题目链接#xff1a;1686. 石子游戏 VI
题目描述… 文章目录 LeetCode启动题目石子游戏 VI题目描述代码与解题思路 LeetCode启动 题目石子游戏 VI
题目链接1686. 石子游戏 VI
题目描述 代码与解题思路
func stoneGameVI(aliceValues []int, bobValues []int) int {type pair struct { x, y int }pairs : make([]pair, len(aliceValues))// 把 Alice 和 Bob 的石子计分保存下来for i : 0; i len(aliceValues); i {pairs[i] pair{aliceValues[i], bobValues[i]}}// 根据我们分析的性质进行排序slices.SortFunc(pairs, func(p, q pair) int { return (q.x q.y) - (p.x p.y) })// 根据最优解计算 Alice 和 Bob 的得分a, b : 0, 0for i, v : range pairs {if i % 2 0 {a v.x} else {b v.y}}// 比较最后谁赢了if a b {return 1} else if a b {return -1}return 0
}题目中 Alice 和 Bob 玩石子游戏游戏的规则是有一堆石子每次可以拿石子堆中任意一个石子拿过的石子不能再被拿
而 Alice 和 Bob 的计分方式是不同的Alice 先手如果要最优解那 Alice 每次必须拿给自己和 Bob 加分最多的石子这样自己加分多Bob 少了这个石子加分就少了也就是她拿的石子的 aliceValues[i] bobValues[i] 越大越好
而 Bob 也是同样的拿给自己和 Alice 加分最多的石子就行也就是说我们只需要按照这个规则升序排序 aliceValues[i] bobValues[i]然后就能通过最优解求出他们最后到底谁会赢了
这次还学习了 go 语言 slices 包的自己指定规则排序数组
slices.SortFunc(pairs, func(p, q pair) int { return (q.x q.y) - (p.x p.y) })
用后一个数 - 前一个数 升序排序
这里的排序规则就是我们前面提到的 aliceValues[i] bobValues[i]通过 pairs 数组保存住 Alice 和 Bob 每个石子的价值遍历的时候计算最后再比较他们的大小即可
