class Solution {
public:
int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
}
};
1686. 石子游戏 VI
Alice 和 Bob 轮流玩一个游戏，Alice 先手。
一堆石子里总共有 n 个石子，轮到某个玩家时，他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。
给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。
所有石子都被取完后，得分较高的人为胜者。如果两个玩家得分相同，那么为平局。两位玩家都会采用 最优策略 进行游戏。
请你推断游戏的结果，用如下的方式表示：
1 。-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 <= 1051 <= aliceValues[i], bobValues[i] <= 100原站题解
rust 解法, 执行用时: 8 ms, 内存消耗: 4.1 MB, 提交时间: 2024-02-02 09:56:50
impl Solution {
pub fn stone_game_vi(a: Vec<i32>, b: Vec<i32>) -> i32 {
let mut pairs = a.into_iter().zip(b).collect::<Vec<_>>();
pairs.sort_unstable_by(|(px, py), (qx, qy)| (qx + qy).cmp(&(px + py)));
pairs.iter()
.enumerate()
.map(|(i, &(x, y))| if i % 2 == 0 { x } else { -y })
.sum::<i32>()
.signum()
}
}
javascript 解法, 执行用时: 309 ms, 内存消耗: 85.2 MB, 提交时间: 2024-02-02 09:56:39
/**
* @param {number[]} aliceValues
* @param {number[]} bobValues
* @return {number}
*/
var stoneGameVI = function(a, b) {
const pairs = _.zip(a, b).sort((p, q) => q[0] + q[1] - p[0] - p[1]);
let diff = 0;
for (let i = 0; i < pairs.length; i++) {
diff += i % 2 === 0 ? pairs[i][0] : -pairs[i][1];
}
return Math.sign(diff);
};
golang 解法, 执行用时: 136 ms, 内存消耗: 10.7 MB, 提交时间: 2024-02-02 09:56:22
func stoneGameVI(a, b []int) int {
type pair struct{ x, y int }
pairs := make([]pair, len(a))
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 := 0
for i, p := range pairs {
if i%2 == 0 {
diff += p.x
} else {
diff -= p.y
}
}
return cmp.Compare(diff, 0)
}
cpp 解法, 执行用时: 185 ms, 内存消耗: 106.3 MB, 提交时间: 2024-02-02 09:56:06
class Solution {
public:
int stoneGameVI(vector<int> &a, vector<int> &b) {
int n = a.size();
vector<int> ids(n);
iota(ids.begin(), ids.end(), 0);
ranges::sort(ids, [&](int i, int j) { return a[i] + b[i] > a[j] + b[j]; });
int diff = 0;
for (int i = 0; i < n; i++) {
diff += i % 2 == 0 ? a[ids[i]] : -b[ids[i]];
}
return (diff > 0) - (diff < 0);
}
};
java 解法, 执行用时: 85 ms, 内存消耗: 58.8 MB, 提交时间: 2024-02-02 09:55:47
class Solution {
public int stoneGameVI(int[] a, int[] b) {
int n = a.length;
Integer[] ids = new Integer[n];
for (int i = 0; i < n; i++) {
ids[i] = i;
}
Arrays.sort(ids, (i, j) -> a[j] + b[j] - a[i] - b[i]);
int diff = 0;
for (int i = 0; i < n; i++) {
diff += i % 2 == 0 ? a[ids[i]] : -b[ids[i]];
}
return Integer.compare(diff, 0);
}
}
python3 解法, 执行用时: 107 ms, 内存消耗: 21.8 MB, 提交时间: 2024-02-02 09:55:34
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)
python3 解法, 执行用时: 190 ms, 内存消耗: 32.4 MB, 提交时间: 2024-02-02 09:55:25
class Solution:
def stoneGameVI(self, a: List[int], b: List[int]) -> int:
pairs = sorted(zip(a, b), key=lambda p: -p[0] - p[1])
diff = sum(x if i % 2 == 0 else -y for i, (x, y) in enumerate(pairs))
return (diff > 0) - (diff < 0)
golang 解法, 执行用时: 164 ms, 内存消耗: 10.8 MB, 提交时间: 2023-08-18 15:08:08
type A struct {
Score int
Index int
}
func stoneGameVI(aliceValues []int, bobValues []int) int {
arr := make([]A, len(aliceValues))
for i := range aliceValues {
arr[i].Score = aliceValues[i] + bobValues[i]
arr[i].Index = i
}
sort.Slice(arr, func (i, j int) bool {
return arr[i].Score > arr[j].Score
})
AliceScore := 0
BobScore := 0
for i := 0; i < len(aliceValues); i++ {
if i % 2 == 0 {
AliceScore += aliceValues[arr[i].Index]
} else {
BobScore += bobValues[arr[i].Index]
}
}
if AliceScore > BobScore {
return 1
} else if AliceScore < BobScore {
return -1
} else {
return 0
}
}
python3 解法, 执行用时: 268 ms, 内存消耗: 32.3 MB, 提交时间: 2023-08-18 15:04:09
'''
将两组石头的价值合并，每次取价值最大的那一组
'''
class Solution:
def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
n = len(aliceValues)
newValues = [a+b for a, b in zip(aliceValues, bobValues)]
newValues = [(i, x) for i, x in enumerate(newValues)]
newValues.sort(key=lambda x: x[1], reverse=True)
s1, s2 = 0, 0
for i in range(n):
if i % 2 == 0:
# 偶数下标alice来取
s1 += aliceValues[newValues[i][0]]
else:
# 奇数下标bob来取
s2 += bobValues[newValues[i][0]]
if s1 > s2: return 1
elif s1 == s2: return 0
else: return -1