目录1.水壶问题2. 石子游戏 VIII3. 单面值组合的第 K 小金额1.水壶问题有两个水壶容量分别为x和y升。水的供应是无限的。确定是否有可能使用这两个壶准确得到target升。你可以装满任意一个水壶清空任意一个水壶将水从一个水壶倒入另一个水壶直到接水壶已满或倒水壶已空。**示例 1: **输入: x 3,y 5,target 4输出: true解释按照以下步骤操作以达到总共 4 升水装满 5 升的水壶(0, 5)。把 5 升的水壶倒进 3 升的水壶留下 2 升(3, 2)。倒空 3 升的水壶(0, 2)。把 2 升水从 5 升的水壶转移到 3 升的水壶(2, 0)。再次加满 5 升的水壶(2, 5)。从 5 升的水壶向 3 升的水壶倒水直到 3 升的水壶倒满。5 升的水壶里留下了 4 升水(3, 4)。倒空 3 升的水壶。现在5 升的水壶里正好有 4 升水(0, 4)。参考来自著名的 “Die Hard”示例 2:输入: x 2, y 6, target 5输出: false示例 3:输入: x 1, y 2, target 3输出: true解释同时倒满两个水壶。现在两个水壶中水的总量等于 3。提示:1 x , y , t a r g e t 10 3 1 x, y, target 10^31x,y,target103思路方法一深度(或广度)优先搜索将当前水壶的状态看做图中的节点倒水的行为看成路径根据当前状态每次可以采取以下6种行为x中水倒满y中水倒满x中水倒空y中水倒空x中水倒入y中x空或者y满y中水倒入x中有空或者x满有可能会出现重复状态此时用Set集合保存已经出现过的状态这里x,y的取值在[0,1000]因此可以自定义哈希保存当前状态classSolution{publicbooleancanMeasureWater(intx,inty,inttarget){SetIntegerseennewHashSet();Dequeint[]stacknewArrayDeque();stack.push(newint[]{0,0});while(!stack.isEmpty()){if(seen.contains(hash(stack.peek()))){stack.pop();continue;}seen.add(hash(stack.peek()));int[]statestack.pop();intrxstate[0],rystate[1];if(rxtarget||rytarget||rxrytarget){returntrue;}//根据xy的状态进行操作//x中水倒入y中stack.push(newint[]{rx-Math.min(rx,y-ry),ryMath.min(rx,y-ry)});//y中水倒入x中stack.push(newint[]{rxMath.min(x-rx,ry),ry-Math.min(ry,x-rx)});//x灌满stack.push(newint[]{x,ry});//y灌满stack.push(newint[]{rx,y});//x倒空stack.push(newint[]{0,ry});//y倒空stack.push(newint[]{rx,0});}returnfalse;}//自定义哈希privateinthash(int[]state){returnstate[0]*10000state[1];}}方法二把两个水壶看做一个整体每次倒水整体总量的变化是±x或者±y。说明如下若两个壶同时空或者同时满则显然符合要求若一个空一个满也符合要求若一个满另一个不满则不满的壶倒空或者倒满没任何意义因此此操作无效若一个空另一个不满则不满的倒满同样无意义若一个空另一个不满先倒满空的再倒入另一个壶中则这两个动作总的水量变化是x或者y并且一般是两个动作组合在一起有可能得出答案因此说明每次倒水整体水量变化是±x或者±y。故x,y,z(target)满足方程axbyz其中a,b是整数。由贝祖定理可知只要z是x和y的最大公约数的倍数则a,b有解classSolution{publicbooleancanMeasureWater(intx,inty,inttarget){if(xytarget){returnfalse;}intgcgcd(x,y);returntarget%gc0;}privateintgcd(intx,inty){returny0?x:gcd(y,x%y);}2. 石子游戏 VIIIAlice 和 Bob 玩一个游戏两人轮流操作 Alice 先手 。总共有 n 个石子排成一行。轮到某个玩家的回合时如果石子的数目 大于 1 他将执行以下操作选择一个整数 x 1 并且 移除 最左边的 x 个石子。将 移除 的石子价值之 和 累加到该玩家的分数中。将一个 新的石子 放在最左边且新石子的值为被移除石子值之和。当只剩下 一个 石子时游戏结束。Alice 和 Bob 的 分数之差 为 (Alice 的分数 - Bob 的分数) 。 Alice 的目标是 最大化 分数差Bob 的目标是 最小化 分数差。给你一个长度为 n 的整数数组 stones 其中 stones[i] 是 从左边起 第 i 个石子的价值。请你返回在双方都采用 最优 策略的情况下Alice 和 Bob 的 分数之差 。示例 1输入stones [-1,2,-3,4,-5]输出5解释Alice 移除最左边的 4 个石子得分增加 (-1) 2 (-3) 4 2 并且将一个价值为 2 的石子放在最左边。stones [2,-5] 。Bob 移除最左边的 2 个石子得分增加 2 (-5) -3 并且将一个价值为 -3 的石子放在最左边。stones [-3] 。两者分数之差为 2 - (-3) 5 。示例 2输入stones [7,-6,5,10,5,-2,-6]输出13解释Alice 移除所有石子得分增加 7 (-6) 5 10 5 (-2) (-6) 13 并且将一个价值为 13 的石子放在最左边。stones [13] 。两者分数之差为 13 - 0 13 。示例 3输入stones [-10,-12]输出-22解释Alice 只有一种操作就是移除所有石子。得分增加 (-10) (-12) -22 并且将一个价值为 -22 的石子放在最左边。stones [-22] 。两者分数之差为 (-22) - 0 -22 。提示n s t o n e s . l e n g t h n stones.lengthnstones.length2 n 10 5 2 n 10^52n105− 10 4 s t o n e s [ i ] 10 4 -10^4 stones[i] 10^4−104stones[i]104思路动态规划这里的移除石子后再添加移除总和的石子有迷惑性实质上是前缀和如A移除[0,5]则A当前操作利益是前缀和pre[5],添加的石子也是前缀和pre[5],然后B再移除[5,9]则B当前操作利益是前缀和pre[9]添加的石子是前缀和pre[9],因此无论移除的多少当前操作获得利益都是前缀和用dp[i]来保存当前玩家从[i,n)中选择石子得到的最大收益故当前玩家从[i,n)中选择石子总的收益自己的收益减对手的收益是d p [ i ] M a t h . m a x ( p r e [ i ] − d p [ i 1 ] , d p [ i 1 ] ) dp[i] Math.max(pre[i]-dp[i1],dp[i1])dp[i]Math.max(pre[i]−dp[i1],dp[i1])当前玩家有两种可选操作一是选择i石子则另一名玩家是可以选择范围是[i1,n) 因为当前玩家选择后会添加一枚石子由于都采用最优策略由dp定义可知另一名玩家的收益是dp[i1]故此时当前玩家收益是pre[i]-dp[i1]二是不选择i石子则当前玩家选择方位是[i1,n)此时当前玩家收益是dp[i1]两者取最大值符合最优策略classSolution{publicintstoneGameVIII(int[]stones){intnstones.length;int[]prenewint[n];pre[0]stones[0];for(inti1;in;i){pre[i]pre[i-1]stones[i];}int[]dpnewint[n];dp[n-1]pre[n-1];for(intin-2;i1;i--){dp[i]Math.max(dp[i1],pre[i]-dp[i1]);}returndp[1];}}时间复杂度O ( n ) O(n)O(n)空间复杂度O ( n ) O(n)O(n)3. 单面值组合的第 K 小金额给你一个整数数组 coins 表示不同面额的硬币另给你一个整数 k 。你有无限量的每种面额的硬币。但是你 不能 组合使用不同面额的硬币。示例 1输入 coins [3,6,9], k 3输出 9解释给定的硬币可以制造以下金额3元硬币产生3的倍数3, 6, 9, 12, 15等。6元硬币产生6的倍数6, 12, 18, 24等。9元硬币产生9的倍数9, 18, 27, 36等。所有硬币合起来可以产生3, 6, 9, 12, 15等。示例 2输入coins [5,2], k 7输出12解释给定的硬币可以制造以下金额5元硬币产生5的倍数5, 10, 15, 20等。2元硬币产生2的倍数2, 4, 6, 8, 10, 12等。所有硬币合起来可以产生2, 4, 5, 6, 8, 10, 12, 14, 15等。提示1 c o i n s . l e n g t h 15 1 coins.length 151coins.length151 c o i n s [ i ] 25 1 coins[i] 251coins[i]251 k 2 ∗ 10 9 1 k 2 * 10^91k2∗109coins包含两两不同的整数。返回使用这些硬币能制造的 第kth小金额。思路二分容斥原理classSolution{publiclongfindKthSmallest(int[]coins,intk){Arrays.sort(coins);intncoins.length;intm1n;int[]bitCountnewint[m];//用来统计子集的最小公倍数long[]lcmsnewlong[m];longlk;longr(long)coins[0]*k1;//计算所有子集的最小公倍数for(intmask1;maskm;mask){longcurLcm1;for(inti0;in;i){if((maski1)1){//最大公约数bitCount[mask];if(curLcmr){continue;}longggcd(curLcm,coins[i]);longtempcurLcm/g;if(tempr/coins[i]){curLcmr1;break;}else{curLcmtemp*coins[i];}}}lcms[mask]curLcm;}while(lr){longmidl(r-l)/2;longcountscount(lcms,bitCount,mid);if(countsk){lmid1;}else{//countskrmid;}}returnl;}privatelongcount(long[]lcms,int[]bitCount,longmid){longcount0;intmlcms.length;for(inti1;im;i){if(lcms[i]mid){continue;}if((bitCount[i]1)0){//偶数count-mid/lcms[i];}else{countmid/lcms[i];}}returncount;}privatelonggcd(longa,longb){returnb0?a:gcd(b,a%b);}}时间复杂度O ( n 2 2 n × ( l o g ( m a x { c o i n s } ) l o g ( k × m i n { c o i n s } ) ) ) O(n^22^n×(log(max\{coins\})log(k×min\{coins\})))O(n22n×(log(max{coins})log(k×min{coins})))其中n nn为coins的长度。预处理阶段每个子集的最小公倍数计算时间为 O(log(maxKaTeX parse error: Expected }, got EOF at end of input: {coins}))共有O ( 2 n ) O(2^n)O(2n)个子集需要处理。二分枚举x时需枚举l o g ( k × m i n { c o i n s } ) log(k×min\{coins\})log(k×min{coins})次计算count[x]的时间复杂度为O ( 2 n ) O(2^n)O(2n)空间复杂度O ( 2 n ) O(2^n)O(2n)