LeetCode.1686. 石子游戏 VI

题目

题目链接

分析

本题采取贪心的策略
我们先假设只有两个石头a,b，
对于 Alice 价值分别为 a1,a2，
对于 Bob 价值而言价值分别是 b1,b2

1. 第一种方案是 Alice取第一个，Bob 取第二个，Alice与Bob的价值差是 c1 = a1 - b1；
2. 第一种方案是 Alice取第二个，Bob 取第一个，Alice与Bob的价值差是 c1 = a2 - b2；

那么这两种方案对于 Alice来说哪一种更优呢？？
取决于两种方案的价值差，记 c = c1 - c2 = (a1 - b2) - (a2 - b1) = (a1 + b1) - (a2 + b2);
如果 c > 0，那么方案一更优，如果 c == 0，则两种方案一样，如果 c < 0，则方案二更优。

那么比较两个方案的优劣其实就是比较 a1+b1 与 a2+b2 的优劣，也就是比较每个下标i的a[i]+b[i]的优劣。

所以贪心的策略：将两组石头的价值合并，每次取价值最大的那一组。

总结以上：先将两个数组的价值合并，并用下标去标记，对价值进行排序，
Alice取偶数下标，Bob取奇数下标，最后比较Alice和Bob的价值总和。

代码

class Solution {
    public int stoneGameVI(int[] aliceValues, int[] bobValues) {
        int n = aliceValues.length;
        Integer[] ids = new Integer[n];
        for (int i = 0; i < n; ++i) ids[i] = i;
        // 两个数组价值之和按照 大->小 排序，ids 记录下标
        // 例如： aliceValues = {1, 2, 3}; bobValues = {3, 1, 3};
        // 经过下面的代码：ids = {2,0,1}
        Arrays.sort(ids, (a, b) -> {
            int val1 = aliceValues[a] + bobValues[a];
            int val2 = aliceValues[b] + bobValues[b];
            return val2 - val1;
        });
        // Alice 价值总和
        int alisCount = 0;
        // Bob 价值总和
        int bobCount = 0;
        for(int i  =0;i < n;i ++) {
            // 偶数下标，Alice取值
            if(i % 2 == 0) {
                alisCount += aliceValues[ids[i]];
            }else {
                // 奇数下标，Bob取值
                bobCount += bobValues[ids[i]];
            }
        }
        if(alisCount - bobCount > 0) {
            return 1;
        }else if(alisCount == bobCount) {
            return 0;
        }else {
            return -1;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35