Skip to content

Latest commit

 

History

History
191 lines (152 loc) · 5.38 KB

README.md

File metadata and controls

191 lines (152 loc) · 5.38 KB
Raw

1686. 石子游戏 VI

English Version

题目描述

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.length
  • 1 <= n <= 105
  • 1 <= aliceValues[i], bobValues[i] <= 100

解法

方法一：贪心 + 排序

选取石头的最优化的策略是，让自己得分最高，同时让对手失分最多。因此，我们创建一个数组 arr，其中 arr[i] = aliceValues[i] + bobValues[i]，然后对 arr 进行降序排序。然后，我们从 arr 中取出石头，每次取出两个石头，分别给 Alice 和 Bob，直到 arr 中没有石头为止。最后，我们比较 Alice 和 Bob 的得分，得分高的人获胜。

时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 aliceValues 和 bobValues 的长度。

Python3

class Solution:
    def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
        arr = [(a + b, i)
               for i, (a, b) in enumerate(zip(aliceValues, bobValues))]
        arr.sort(reverse=True)
        a = sum(aliceValues[v[1]] for i, v in enumerate(arr) if i % 2 == 0)
        b = sum(bobValues[v[1]] for i, v in enumerate(arr) if i % 2 == 1)
        if a > b:
            return 1
        if a < b:
            return -1
        return 0

Java

class Solution {
    public int stoneGameVI(int[] aliceValues, int[] bobValues) {
        int n = aliceValues.length;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; ++i) {
            arr[i] = new int[] {aliceValues[i] + bobValues[i], i};
        }
        Arrays.sort(arr, (a, b) -> b[0] - a[0]);
        int a = 0, b = 0;
        for (int i = 0; i < n; ++i) {
            int j = arr[i][1];
            if (i % 2 == 0) {
                a += aliceValues[j];
            } else {
                b += bobValues[j];
            }
        }
        if (a == b) {
            return 0;
        }
        return a > b ? 1 : -1;
    }
}

C++

class Solution {
public:
    int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
        int n = aliceValues.size();
        vector<pair<int, int>> arr(n);
        for (int i = 0; i < n; ++i) {
            arr[i] = {aliceValues[i] + bobValues[i], i};
        }
        sort(arr.rbegin(), arr.rend());
        int a = 0, b = 0;
        for (int i = 0; i < n; ++i) {
            int j = arr[i].second;
            if (i % 2 == 0) {
                a += aliceValues[j];
            } else {
                b += bobValues[j];
            }
        }
        if (a == b) return 0;
        return a > b ? 1 : -1;
    }
};

Go

func stoneGameVI(aliceValues []int, bobValues []int) int {
	arr := make([][]int, len(aliceValues))
	for i, a := range aliceValues {
		b := bobValues[i]
		arr[i] = []int{a + b, i}
	}
	sort.Slice(arr, func(i, j int) bool { return arr[i][0] > arr[j][0] })
	a, b := 0, 0
	for i, v := range arr {
		if i%2 == 0 {
			a += aliceValues[v[1]]
		} else {
			b += bobValues[v[1]]
		}
	}
	if a == b {
		return 0
	}
	if a > b {
		return 1
	}
	return -1
}

...