上接:【题解】—— 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.使循环数组所有元素相等的最少秒数
给你一个下标从 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−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] 必然是数组前 i 个元素的中位数, 有偶数个元素时 median[i] 则可以是排序后最中间两个数构成的区间内的任意一个值 (不理解这一点的可以画一个数轴感受一下), 所以我们可以利用 295. 数据流的中位数 中维护两个堆的方法快速求出 nums 数组前 i 个元素的中位数.
求得中位数后, 如果直接遍历 [0, i] 求需要的操作次数会超时, 所以我们将求中位数的算法稍加修改, 维护数据流较小的一半的和 maxSum (即小于中位数的所有数之和) 与较大的一半的和 minSum (即大于等于中位数的所有数之和), 即:
这样我们就不用数据流中每加入一个元素后重新求和, 从而以 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