建设银行临江市支行网站,广州网络推广营销公司,ext做的网站有那些,wordpress域名无法访问题目
题目链接
分析
本题采取贪心的策略 我们先假设只有两个石头a,b#xff0c; 对于 Alice 价值分别为 a1,a2#xff0c; 对于 Bob 价值而言价值分别是 b1,b2
第一种方案是 Alice取第一个#xff0c;Bob 取第二个#xff0c;Alice与Bob的价值差是 c1 a1 - b1#xf…题目
题目链接
分析
本题采取贪心的策略 我们先假设只有两个石头a,b 对于 Alice 价值分别为 a1,a2 对于 Bob 价值而言价值分别是 b1,b2
第一种方案是 Alice取第一个Bob 取第二个Alice与Bob的价值差是 c1 a1 - b1第一种方案是 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则方案二更优。
那么比较两个方案的优劣其实就是比较 a1b1 与 a2b2 的优劣也就是比较每个下标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;}}
}
