【LeetCode】每日一题 2024_2_2 石子游戏 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 每个石子的价值，遍历的时候计算，最后再比较他们的大小即可