【题解】—— 每日一道题目栏
上接:【题解】—— LeetCode一周小结4
29.自由之路
题目链接:514. 自由之路
电子游戏“辐射4”中,任务 “通向自由” 要求玩家到达名为 “Freedom Trail Ring” 的金属表盘,并使用表盘拼写特定关键词才能开门。
给定一个字符串 ring ,表示刻在外环上的编码;给定另一个字符串 key ,表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。
最初,ring 的第一个字符与 12:00 方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐,然后按下中心按钮,以此逐个拼写完 key 中的所有字符。
旋转 ring 拼出 key 字符 key[i] 的阶段中:
- 您可以将 ring 顺时针或逆时针旋转 一个位置 ,计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐,并且这个字符必须等于字符 key[i] 。
- 如果字符 key[i] 已经对齐到12:00方向,您需要按下中心按钮进行拼写,这也将算作 1 步。按完之后,您可以开始拼写 key 的下一个字符(下一阶段), 直至完成所有拼写。
示例 1:
解释:
对于 key 的第一个字符 ‘g’,已经在正确的位置, 我们只需要1步来拼写这个字符。
对于 key 的第二个字符’d’,我们需要逆时针旋转 ring “godding” 2步使它变成 “ddinggo”。
当然, 我们还需要1步进行拼写。
因此最终的输出是 4。
示例 2:
输入: ring = “godding”, key = “godding”
输出: 13
提示:
1 <= ring.length, key.length <= 100
ring 和 key 只包含小写英文字母
保证 字符串 key 一定可以由字符串 ring 旋转拼出
题解
方法:动态规划
我们用 dp[i][j] 表示从游戏开始到拼接完成 key[0:i] 在 ring[j]==key[i] 的时候最小步数,所以 dp 的最大长度是 dp[key.length][ring.length]
什么是:在 ring[j]==key[i] 的时候最小步数?
这是本题的难点所在,因为存在重复字符串,所以我们把所有重复的位置都考虑到。
比如一下情况:
ring=“ababac”
key=“ab”
第一步 我们先开始拼接 a,我们要把 ring 中每一个a都计算到
计算的结果是:
dp[0][0]=1
dp[0][2]=3
dp[0][4]=4
为什么出现上面三个结果,因为 ring 中总共有三个 a,比如 dp[0][4] 的第二维度 4 表示 a 在 ring 中的下标。
第二步 我们开始算 b,上一步指针停留的位置必然是某个 a 的位置,我们无法知道哪个 a 的位置更优,所以都考虑到,也就是说我们对于上个每一个 a 得位置和现在每一个 b 得位置 都要计算。
比如对于在位置 1 的 b,我们要算 dp[1][1]=min(dp[0][0]+m+1,dp[0][2]+m+1,dp[0][4]+m+1)
其中 m 是两个位置的距离
比如对于在位置 2 的 b,我们要算 dp[1][3]=min(dp[0][0]+m+1,dp[0][2]+m+1,dp[0][4]+m+1)
下图是上述的所以搜索路径
最后答案是所有的 dp[1][index(a)] 的最小值。
我们可以开始用和哈希表来保存每一个字符在 ring 中所有出现位置,来节约时间
class Solution {
Map<Character,List<Integer>> mp;
int[][] dp;
public int findRotateSteps(String ring, String key) {
int rl=ring.length();
int kl=key.length();
if(kl==0) return 0;
char[] r=ring.toCharArray();
char[] k=key.toCharArray();
mp = new HashMap<>();
for(int i=0;i<rl;i++){//保存字符出现的位置
if(mp.containsKey(r[i])){
mp.get(r[i]).add(i);
}
else{
List<Integer> next= new ArrayList<>();
next.add(i);
mp.put(r[i],next);
}
}
dp = new int[kl][rl];
List<Integer> next2 = mp.get(k[0]);
Iterator<Integer> it2 = next2.iterator();
while(it2.hasNext()){
int c = it2.next();
int m = Math.min(c,rl-c);//找到每个位置
dp[0][c]=m+1;
}
for(int i=1;i<kl;i++){
List<Integer> next = mp.get(k[i]);
Iterator<Integer> it = next.iterator();
while(it.hasNext()){
int c = it.next();//找到本次的所有位置
int min=Integer.MAX_VALUE;
List<Integer> next1 = mp.get(k[i-1]);
Iterator<Integer> it1 = next1.iterator();
while(it1.hasNext()){
int d = it1.next();//找到上个字符所有的位置来计算
int m = Math.min(rl-c+d,rl-d+c);
m = Math.min(m,Math.abs(c-d));
min=Math.min(min,dp[i-1][d]+m+1);
}
dp[i][c]=min;
}
}
int ans=Integer.MAX_VALUE;
List<Integer> next = mp.get(k[kl-1]);
Iterator<Integer> it = next.iterator();
while(it.hasNext()){
ans=Math.min(ans,dp[kl-1][it.next()]);
}
return ans;
}
}
30.使循环数组所有元素相等的最少秒数
题目链接:2808. 使循环数组所有元素相等的最少秒数
给你一个下标从 0 开始长度为 n 的数组 nums 。
每一秒,你可以对数组执行以下操作:
对于范围在 [0, n - 1] 内的每一个下标 i ,将 nums[i] 替换成 nums[i] ,nums[(i - 1 + n) % n] 或者 nums[(i + 1) % n] 三者之一。
注意,所有元素会被同时替换。
请你返回将数组 nums 中所有元素变成相等元素所需要的 最少 秒数。
示例 1:
输入:nums = [1,2,1,2]
输出:1
解释:我们可以在 1 秒内将数组变成相等元素:
- 第 1 秒,将每个位置的元素分别变为 [nums[3],nums[1],nums[3],nums[3]] 。变化后,nums = [2,2,2,2] 。
1 秒是将数组变成相等元素所需要的最少秒数。
示例 2:
输入:nums = [2,1,3,3,2]
输出:2
解释:我们可以在 2 秒内将数组变成相等元素:
- 第 1 秒,将每个位置的元素分别变为 [nums[0],nums[2],nums[2],nums[2],nums[3]] 。变化后,nums = [2,3,3,3,3] 。
- 第 2 秒,将每个位置的元素分别变为 [nums[1],nums[1],nums[2],nums[3],nums[4]] 。变化后,nums = [3,3,3,3,3] 。
2 秒是将数组变成相等元素所需要的最少秒数。
示例 3:
输入:nums = [5,5,5,5]
输出:0
解释:不需要执行任何操作,因为一开始数组中的元素已经全部相等。
提示:
1 <= n == nums.length <= 105
1 <= nums[i] <= 109
题解
方法:把问题看成是【扩散】元素
提示 1
最终所有元素一定变成了一个在 nums 中的数。
枚举这个数。
提示 2
考虑把数字 x 扩散到其它位置,那么每一秒 x 都可以向左右扩散一位。
多个相同数字 x 同时扩散,那么扩散完整个数组的耗时,就取决于相距最远的两个相邻的 x。
假设这两个 x 的下标分别为 i 和 j,且 i<j,那么耗时为:
⌊(j−i)/2⌋不同的 x,计算相应的耗时,更新答案的最小值。
提示 3
统计所有相同数字的下标,记到一个哈希表 pos 中。
本题数组可以视作是环形的,假设最左边的 x 的下标是 i,只需要在 pos[x] 列表末尾添加一个 i+n,就可以转换成非环形数组处理了。
public class Solution {
public int minimumSeconds(List<Integer> nums) {
int n = nums.size();
Map<Integer, List<Integer>> pos = new HashMap<>();
for (int i = 0; i < n; i++) {
pos.computeIfAbsent(nums.get(i), k -> new ArrayList<>()).add(i);
}
int ans = n;
for (List<Integer> a : pos.values()) {
a.add(a.get(0) + n);
int mx = 0;
for (int i = 1; i < a.size(); ++i) {
mx = Math.max(mx, (a.get(i) - a.get(i - 1)) / 2);
}
ans = Math.min(ans, mx);
}
return ans;
}
}
31.找出不同元素数目差数组
题目链接:2670. 找出不同元素数目差数组
给你一个下标从 0 开始的数组 nums ,数组长度为 n 。
nums 的 不同元素数目差 数组可以用一个长度为 n 的数组 diff 表示,其中 diff[i] 等于前缀 nums[0, …, i] 中不同元素的数目 减去 后缀 nums[i + 1, …, n - 1] 中不同元素的数目。
返回 nums 的 不同元素数目差 数组。
注意 nums[i, …, j] 表示 nums 的一个从下标 i 开始到下标 j 结束的子数组(包含下标 i 和 j 对应元素)。特别需要说明的是,如果 i > j ,则 nums[i, …, j] 表示一个空子数组。
示例 1:
输入:nums = [1,2,3,4,5]
输出:[-3,-1,1,3,5]
解释:
对于 i = 0,前缀中有 1 个不同的元素,而在后缀中有 4 个不同的元素。因此,diff[0] = 1 - 4 = -3 。
对于 i = 1,前缀中有 2 个不同的元素,而在后缀中有 3 个不同的元素。因此,diff[1] = 2 - 3 = -1 。
对于 i = 2,前缀中有 3 个不同的元素,而在后缀中有 2 个不同的元素。因此,diff[2] = 3 - 2 = 1 。
对于 i = 3,前缀中有 4 个不同的元素,而在后缀中有 1 个不同的元素。因此,diff[3] = 4 - 1 = 3 。
对于 i = 4,前缀中有 5 个不同的元素,而在后缀中有 0 个不同的元素。因此,diff[4] = 5 - 0 = 5 。
示例 2:
输入:nums = [3,2,3,4,2]
输出:[-2,-1,0,2,3]
解释:
对于 i = 0,前缀中有 1 个不同的元素,而在后缀中有 3 个不同的元素。因此,diff[0] = 1 - 3 = -2 。
对于 i = 1,前缀中有 2 个不同的元素,而在后缀中有 3 个不同的元素。因此,diff[1] = 2 - 3 = -1 。
对于 i = 2,前缀中有 2 个不同的元素,而在后缀中有 2 个不同的元素。因此,diff[2] = 2 - 2 = 0 。
对于 i = 3,前缀中有 3 个不同的元素,而在后缀中有 1 个不同的元素。因此,diff[3] = 3 - 1 = 2 。
对于 i = 4,前缀中有 3 个不同的元素,而在后缀中有 0 个不同的元素。因此,diff[4] = 3 - 0 = 3 。
提示:
1 <= n == nums.length <= 50
1 <= nums[i] <= 50
题解
方法:O(n) 前后缀分解
先倒序枚举 nums,并记录每个后缀的不同元素个数到 suf 数组中,这可以用哈希表做到。
然后正序枚举 nums[i],同样地,记录每个前缀的不同元素个数,减去 suf[i+1],即为答案。
class Solution {
public int[] distinctDifferenceArray(int[] nums) {
int n = nums.length;
var suf = new int[n + 1];
var s = new HashSet<Integer>();
for (int i = n - 1; i > 0; i--) {
s.add(nums[i]);
suf[i] = s.size();
}
s.clear();
var ans = new int[n];
for (int i = 0; i < n; i++) {
s.add(nums[i]);
ans[i] = s.size() - suf[i + 1];
}
return ans;
}
}
2024.2
1.数字游戏
题目链接:LCP 24. 数字游戏
小扣在秋日市集入口处发现了一个数字游戏。主办方共有 N 个计数器,计数器编号为 0 ~ N-1。每个计数器上分别显示了一个数字,小扣按计数器编号升序将所显示的数字记于数组 nums。每个计数器上有两个按钮,分别可以实现将显示数字加一或减一。小扣每一次操作可以选择一个计数器,按下加一或减一按钮。
主办方请小扣回答出一个长度为 N 的数组,第 i 个元素(0 <= i < N)表示将 0~i 号计数器 初始 所示数字操作成满足所有条件 nums[a]+1 == nums[a+1],(0 <= a < i) 的最小操作数。回答正确方可进入秋日市集。
由于答案可能很大,请将每个最小操作数对 1,000,000,007 取余。
示例 1:
输入:nums = [3,4,5,1,6,7]
输出:[0,0,0,5,6,7]
解释: i = 0,[3] 无需操作 i = 1,[3,4] 无需操作; i = 2,[3,4,5] 无需操作; i = 3,将
[3,4,5,1] 操作成 [3,4,5,6], 最少 5 次操作; i = 4,将 [3,4,5,1,6] 操作成
[3,4,5,6,7], 最少 6 次操作; i = 5,将 [3,4,5,1,6,7] 操作成 [3,4,5,6,7,8],最少 7
次操作; 返回 [0,0,0,5,6,7]。
示例 2:
输入:nums = [1,2,3,4,5]
输出:[0,0,0,0,0]
解释:对于任意计数器编号 i 都无需操作。
示例 3:
输入:nums = [1,1,1,2,3,4]
输出:[0,1,2,3,3,3]
解释:
i = 0,无需操作; i = 1,将 [1,1] 操作成 [1,2] 或 [0,1] 最少 1 次操作; i = 2,将
[1,1,1] 操作成 [1,2,3] 或 [0,1,2],最少 2 次操作; i = 3,将 [1,1,1,2] 操作成
[1,2,3,4] 或 [0,1,2,3],最少 3 次操作; i = 4,将 [1,1,1,2,3] 操作成
[-1,0,1,2,3],最少 3 次操作; i = 5,将 [1,1,1,2,3,4] 操作成 [-1,0,1,2,3,4],最少 3
次操作; 返回 [0,1,2,3,3,3]。
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 103
题解
方法:求数据流的中位数
下文中所有 “数组 nums 的前 i 个元素” 均指 nums[0] 到 nums[i] 的 i + 1 个元素
题目中要求满足 nums[a] + 1 == nums[a + 1]
, 等价于满足 nums[a] - a == nums[a + 1] - (a + 1),
所以我们可以先对数组进行预处理, 将每个nums[i] 替换为 nums[i] - i, 问题就变成寻找最小的操作次数使得数组的前 i 个元素相等, 假设操作后得到的这个相等的元素为 median[i], 即:
median[i]={argmin_x} ∑ j − 0 i ∣ n u m s [ j ] − x ∣ \sum\limits_{j-0}^i\lvert nums[j]−x\rvert j−0∑i∣nums[j]−x∣
那么当前有奇数个元素时, median[i] 必然是数组前 i 个元素的中位数, 有偶数个元素时 median[i] 则可以是排序后最中间两个数构成的区间内的任意一个值 (不理解这一点的可以画一个数轴感受一下), 所以我们可以利用 295. 数据流的中位数 中维护两个堆的方法快速求出 nums 数组前 i 个元素的中位数.
求得中位数后, 如果直接遍历 [0, i] 求需要的操作次数会超时, 所以我们将求中位数的算法稍加修改, 维护数据流较小的一半的和 maxSum (即小于中位数的所有数之和) 与较大的一半的和 minSum (即大于等于中位数的所有数之和), 即:
minSum = ∑ j = 0 ⋯ i , n u m s [ j ] ≥ m e d i a n [ i ] n u m s [ j ] \sum\limits_{j=0⋯i,nums[j]≥median[i]}\ {nums[j]} j=0⋯i,nums[j]≥median[i]∑ nums[j]
maxSum= ∑ j = 0 ⋯ i , n u m s [ j ] < m e d i a n [ i ] n u m s [ j ] \sum\limits_{j=0⋯i,nums[j]<median[i]}\ {nums[j]} j=0⋯i,nums[j]<median[i]∑ nums[j]
所以:
∑ j − 0 i ∣ n u m s [ j ] − m e d i a n [ i ] ∣ \sum\limits_{j-0}^i\lvert nums[j]−median[i]\rvert j−0∑i∣nums[j]−median[i]∣ = minSum − card({j∣nums[j]≥median[i],0≤j≤i})×median[i]+(card({j∣nums[j]<median[i],0≤j≤i})×median[i]−maxSum)
这样我们就不用数据流中每加入一个元素后重新求和, 从而以 O(nlogn) 复杂度解决问题.
注意代码中 minHeap 代表的小顶堆维护的是数据流较大的一半, 而 maxHeap 则是较小的一半.
class Solution {
public int[] numsGame(int[] nums) {
int n = nums.length;
int[] result = new int[n];
for (int i = 0; i < n; i++)
nums[i] -= i;
result[0] = 0;
MedianFinder finder = new MedianFinder();
finder.addNum(nums[0]);
for (int i = 1; i < n; i++) {
finder.addNum(nums[i]);
int median = finder.findMedian();
long value = finder.minSum - (long) (finder.minHeap.size() - 1) * (long) median
+ ((long) (finder.maxHeap.size() - 1) * (long) median - finder.maxSum);
result[i] = (int) (value % 1000000007);
}
return result;
}
}
class MedianFinder {
PriorityQueue<Integer> minHeap, maxHeap;
long minSum = 0, maxSum = 0;
public MedianFinder() {
minHeap = new PriorityQueue<>();
maxHeap = new PriorityQueue<>(1, (x, y) -> {
long result = (long) y - (long) x;
if (result > 0)
return 1;
if (result < 0)
return -1;
return 0;
});
minHeap.add(Integer.MAX_VALUE);
maxHeap.add(Integer.MIN_VALUE);
}
private void adjust() {
int maxSize = maxHeap.size(), minSize = minHeap.size();
if (maxSize - minSize >= 2) {
int num = maxHeap.poll();
maxSum -= num;
minHeap.add(num);
minSum += num;
} else if (minSize - maxSize >= 2) {
int num = minHeap.poll();
minSum -= num;
maxHeap.add(num);
maxSum += num;
}
}
public void addNum(int num) {
int lowerMax = maxHeap.peek();
if (num <= lowerMax) {
maxHeap.add(num);
maxSum += num;
} else {
minHeap.add(num);
minSum += num;
}
adjust();
}
public int findMedian() {
if (maxHeap.size() > minHeap.size())
return maxHeap.peek();
else
return minHeap.peek();
}
}
2.石子游戏 VI
题目链接:1686. 石子游戏 VI
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
题解
方法:博弈
在游戏进行的过程中,想要本轮自己的得分最优化,要同时考虑自己能够获得尽可能多得分,并且可以让对手损失尽可能多的得分。令 values[i]=aliceValues[i]+bobValues[i],values[x] 大,意味着自己可以获得对二者而言均比较大的石头,正好可以满足目标:自己的收益和让对方的损失权衡下来最大化。先对 values 逆序排序,两人轮流顺序取当前得分和对应的石头即可(对二者而言这么取都是最有利于自己的)。
class Solution {
public int stoneGameVI(int[] aliceValues, int[] bobValues) {
int n = aliceValues.length;
List<int[]> value = new ArrayList<>();
for (int i = 0; i < n; i++)
value.add(new int[] {i, aliceValues[i] + bobValues[i]});
value.sort((x, y) -> y[1] - x[1]);
int total = 0;
for (int i = 0; i < n; i++)
total += i % 2 == 0 ? aliceValues[value.get(i)[0]] : -bobValues[value.get(i)[0]];
return Integer.compare(total, 0);
}
}
3.石子游戏 VII
题目链接:1690. 石子游戏 VII
石子游戏中,爱丽丝和鲍勃轮流进行自己的回合,爱丽丝先开始 。
有 n 块石子排成一排。每个玩家的回合中,可以从行中 移除 最左边的石头或最右边的石头,并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时,得分较高者获胜。
鲍勃发现他总是输掉游戏(可怜的鲍勃,他总是输),所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。
给你一个整数数组 stones ,其中 stones[i] 表示 从左边开始 的第 i 个石头的值,如果爱丽丝和鲍勃都 发挥出最佳水平 ,请返回他们 得分的差值 。
示例 1:
输入:stones = [5,3,1,4,2]
输出:6
解释:
- 爱丽丝移除 2 ,得分 5 + 3 + 1 + 4 = 13 。游戏情况:爱丽丝 = 13 ,鲍勃 = 0 ,石子 = [5,3,1,4] 。
- 鲍勃移除 5 ,得分 3 + 1 + 4 = 8 。游戏情况:爱丽丝 = 13 ,鲍勃 = 8 ,石子 = [3,1,4] 。
- 爱丽丝移除 3 ,得分 1 + 4 = 5 。游戏情况:爱丽丝 = 18 ,鲍勃 = 8 ,石子 = [1,4] 。
- 鲍勃移除 1 ,得分 4 。游戏情况:爱丽丝 = 18 ,鲍勃 = 12 ,石子 = [4] 。
- 爱丽丝移除 4 ,得分 0 。游戏情况:爱丽丝 = 18 ,鲍勃 = 12 ,石子 = [] 。
得分的差值 18 - 12 = 6 。
示例 2:
输入:stones = [7,90,5,1,100,10,10,2]
输出:122
提示:
n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000
题解
方法:递归 记忆化搜索 动态规划 前缀和
灵神教你一步步思考动态规划:从记忆化搜索到递推
方法:动态规划
public int stoneGameVII(int[] stones) {
int n = stones.length;
int[][] dp = new int[n][n];
//通过动态方程,发现i和 >=i的有关系,j和<=j的有关系.
//所以计算需要i从大到小,j从小到大,这样才能正确.
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (i + 1 == j) {
dp[i][j] = Math.max(stones[i], stones[j]);
} else {
//如果Alice先选i,那么bobo只能选i+1和j,这时候差就是stones[i+1]或者stones[j]
//当然,还需要加上子区间dp的差值,才是最终的差值.
//left和right就相当于是bobo选择后的差值,这个要尽可能小.所以是min
//dp是Alice的差值,要尽可能大,所以是max
int left = Math.min(stones[i + 1] + dp[i + 2][j], stones[j] + dp[i + 1][j - 1]);
int right = Math.min(stones[i] + dp[i + 1][j - 1], stones[j - 1] + dp[i][j - 2]);
dp[i][j] = Math.max(left, right);
}
}
}
return dp[0][n - 1];
}
4.Nim 游戏
题目链接:292. Nim 游戏
你和你的朋友,两个人一起玩 Nim 游戏:
- 桌子上有一堆石头。
- 你们轮流进行自己的回合, 你作为先手 。
- 每一回合,轮到的人拿掉 1 - 3 块石头。
- 拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数,来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢,返回 true;否则,返回 false 。
示例 1:
输入:n = 4
输出:false
解释:以下是可能的结果:
- 移除1颗石头。你的朋友移走了3块石头,包括最后一块。你的朋友赢了。
- 移除2个石子。你的朋友移走2块石头,包括最后一块。你的朋友赢了。
- 你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
在所有结果中,你的朋友是赢家。
示例 2:
输入:n = 1
输出:true
示例 3:
输入:n = 2
输出:true
提示:
1 <= n <= 231 - 1
题解
方法:博弈论
class Solution {
public boolean canWinNim(int n) {
return n % 4 != 0;
}
}
巴什博弈:只有一堆n个物品,两个人轮流从这堆物品中取物, 规定每次至少取一个,最多取m个。最后取光者得胜。 只要 n 不能整除 m+1 ,那么必然是先手取胜,否则后手取胜
下接:【题解】—— LeetCode一周小结6