canvas案例网站,双鸭山网站开发,wordpress 主要,中国市政建设局网站本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 Alice 和 Bob 轮流玩一个游戏Alice 先手。
一堆石子里总共有 n 个石子轮到某个玩家时他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。
给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。
所有石子都被取完后得分较高的人为胜者。如果两个玩家得分相同那么为平局。两位玩家都会采用 最优策略 进行游戏。
请你推断游戏的结果用如下的方式表示
如果 Alice 赢返回 1 。如果 Bob 赢返回 -1 。如果游戏平局返回 0 。
示例 1
输入aliceValues [1,3], bobValues [2,1]
输出1
解释
如果 Alice 拿石子 1 下标从 0开始那么 Alice 可以得到 3 分。
Bob 只能选择石子 0 得到 2 分。
Alice 获胜。示例 2
输入aliceValues [1,2], bobValues [3,1]
输出0
解释
Alice 拿石子 0 Bob 拿石子 1 他们得分都为 1 分。
打平。示例 3
输入aliceValues [2,4,3], bobValues [1,6,7]
输出-1
解释
不管 Alice 怎么操作Bob 都可以得到比 Alice 更高的得分。
比方说Alice 拿石子 1 Bob 拿石子 2 Alice 拿石子 0 Alice 会得到 6 分而 Bob 得分为 7 分。
Bob 会获胜。提示
n aliceValues.length bobValues.length1 n 10^51 aliceValues[i], bobValues[i] 100 解法 排序贪心
设 Alice 选的数字之和为 A A ABob 选的数字之和为 B B B 。
如果 A − B 0 A−B0 A−B0 那么 Alice 赢如果 A − B 0 A−B0 A−B0 那么 Bob 赢如果 A − B 0 A-B0 A−B0 则平局。所以 Alice 需要最大化 A − B A−B A−B Bob 需要最小化 A − B A-B A−B 。
下文把数组 aliceValues \textit{aliceValues} aliceValues 记作 A A A把数组 bobValues \textit{bobValues} bobValues 记作 B B B。
以 a [ 2 , 4 , 3 , 5 ] , b [ 1 , 6 , 7 , 1 ] a[2,4,3,5], b[1,6,7,1] a[2,4,3,5],b[1,6,7,1] 为例说明。
假设 Bob 把所有石子都拿走则 A 0 , B 15 , A − B − 15 A0,\ B15,\ A−B−15 A0, B15, A−B−15 。
先来想一想如果 Alice 只能拿走一颗石子应该拿走哪颗呢
拿走第一颗那么 A 2 , B 14 , A − B − 12 A2,\ B14,\ A-B-12 A2, B14, A−B−12 。拿走第二颗那么 A 4 , B 9 , A − B − 5 A4,\ B9,\ A-B-5 A4, B9, A−B−5 。拿走第三颗那么 A 3 , B 8 , A − B − 5 A3,\ B8,\ A-B-5 A3, B8, A−B−5 。拿走第四颗那么 A 5 , B 14 , A − B − 9 A5,\ B14,\ A-B-9 A5, B14, A−B−9 。
对比 Bob 把所有石子都拿走的情况如果 Alice 拿走第二颗或者第三颗都可以让 − 15 -15 −15 增大为 − 5 -5 −5 增量为 10 10 10 。由于 A A A 增加了 a [ i ] a[i] a[i] B B B 减少了 b [ i ] b[i] b[i] 所以 A − B A−B A−B 的增量等于 a [ i ] − ( − b [ i ] ) a [ i ] b [ i ] a[i] - (-b[i]) a[i] b[i] a[i]−(−b[i])a[i]b[i] 所以 Alice 拿走 a [ i ] b [ i ] a[i]b[i] a[i]b[i] 最大的石子最优。
回到原题Alice 可以拿走两颗石子应该拿走哪两颗呢
我们从 Bob 把所有石子都拿走的情况出发也就是在 A 0 , B 15 A0,\ B15 A0, B15 的基础上思考Alice 拿走哪两颗石子可以让 A − B A-B A−B 增加的尽量多
定义 c [ i ] a [ i ] b [ i ] c[i]a[i]b[i] c[i]a[i]b[i] 那么 c [ 3 , 10 , 10 , 6 ] c[3,10,10,6] c[3,10,10,6] 。现在问题变成给定数组 c c c Alice 每回合拿走一个数Bob 每回合删除一个数Alice 拿走的数之和最大是多少注意 Bob 要让 Alice 拿走的数之和尽量小。
如此转换后贪心策略就很显然了Alice 从大到小拿走数字Bob 也从大到小删除数字。
所以把 c c c 从大到小排序为 [ 10 , 10 , 6 , 3 ] [10,10,6,3] [10,10,6,3] 两人从左往右交替取数那么 Alice 只能拿走下标为偶数的数字其余数字被 Bob 删除。所以 A − B A-B A−B 最大可以增加 c [ 0 ] c [ 2 ] 10 6 16 c[0]c[2]10616 c[0]c[2]10616 增加后 A − B 1 0 A-B10 A−B10 Alice 险胜
算法 把数组按照 a [ i ] b [ i ] a[i]b[i] a[i]b[i] 从大到小排序。可以创建一个 ( a [ i ] , b [ i ] ) (a[i],b[i]) (a[i],b[i]) 的 pair 数组对其排序也可以创建一个下标数组排序。
用 diff \textit{diff} diff 表示 A − B A-B A−B 初始化 diff 0 \textit{diff}0 diff0 。遍历数组把偶数下标的 a [ i ] a[i] a[i] 加到 A A A 中相当于 d i f f diff diff 增加了 a [ i ] a[i] a[i] 把奇数下标的 b [ i ] b[i] b[i] 加到 B B B 中相当于 diff \textit{diff} diff 减少了 b [ i ] b[i] b[i] 。
循环结束后如果 d i f f 0 diff0 diff0 返回 1 1 1 如果 d i f f 0 diff0 diff0 返回 − 1 −1 −1 如果 d i f f 0 diff0 diff0 返回 0 0 0 。 问从这个思路的本质是什么为什么这样转换一下问题就变得简单了许多 答转换前我们需要同时考虑 a [ i ] a[i] a[i] 和 b [ i ] b[i] b[i] 这两个变量不好处理。转换成 Bob 先把所有数字选了我们就只需要思考 Alice 如何选数字只有 c [ i ] c[i] c[i] 这一个变量更容易处理。从某种程度上来说这也可以算作一种「正难则反」。 问有没有其它的思考方式 答也可以这样思考对比两颗石子 ( a [ i ] , b [ i ] ) (a[i],b[i]) (a[i],b[i]) 和 ( a [ j ] , b [ j ] ) (a[j],b[j]) (a[j],b[j]) 。如果 Alice 选 i i i Bob 选 j j j 那么 A − B a [ i ] − b [ j ] A−Ba[i]−b[j] A−Ba[i]−b[j] 如果 Alice 选 j j j Bob 选 i i i 那么 A − B a [ j ] − b [ i ] A−Ba[j]−b[i] A−Ba[j]−b[i] 。如果 Alice 选 i i i 更优则有 a [ i ] − b [ j ] a [ j ] − b [ i ] a[i]−b[j]a[j]−b[i] a[i]−b[j]a[j]−b[i] 即 a [ i ] b [ i ] a [ j ] b [ j ] a[i]b[i]a[j]b[j] a[i]b[i]a[j]b[j] 说明 Alice 应当优先选 a [ i ] b [ i ] a[i]b[i] a[i]b[i] 更大的石子。 # python
class Solution:def stoneGameVI(self, a: List[int], b: List[int]) - int:pairs sorted(zip(a, b), key lambda p: -(p[0] p[1])) # a[i]b[i]越大排在前diff sum(x if i % 2 0 else -y for i, (x, y) in enumerate(pairs)) # 表示A-Breturn (diff 0) - (diff 0)class Solution:def stoneGameVI(self, a: List[int], b: List[int]) - int:s sorted((x y for x, y in zip(a, b)), reverse True)diff sum(s[::2]) - sum(b)return (diff 0) - (diff 0)func stoneGameVI(a []int, b []int) int {type pair struct { x, y int }pairs : make([]pair, len(a)) // pair数组for i, x : range a {pairs[i] pair{x, b[i]}}slices.SortFunc(pairs, func(p, q pair) int {return q.x q.y - (p.x p.y)})diff : 0for i, p : range pairs {if i % 2 0 {diff p.x} else {diff - p.y}}return cmp.Compare(diff, 0)
}复杂度分析
时间复杂度 O ( n log n ) \mathcal{O}(n\log n) O(nlogn) 其中 n n n 为 a a a 的长度。瓶颈在排序上。空间复杂度 O ( n ) \mathcal{O}(n) O(n) 。
