安徽建站之星,化妆品网站建设方案,个人备案经营网站备案,北京住房和建设部网站514. 自由之路
电子游戏“辐射4”中#xff0c;任务 “通向自由” 要求玩家到达名为 “Freedom Trail Ring” 的金属表盘#xff0c;并使用表盘拼写特定关键词才能开门。
给定一个字符串ring#xff0c;表示刻在外环上的编码#xff1b;给定另一个字符串key#xff0c;表…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 输入: ring “godding”, key “gd” 输出: 4 解释: 对于 key 的第一个字符 ‘g’已经在正确的位置, 我们只需要1步来拼写这个字符。 对于 key 的第二个字符 ‘d’我们需要逆时针旋转 ring “godding” 2步使它变成 “ddinggo”。 当然, 我们还需要1步进行拼写。 因此最终的输出是 4。 示例 2: 输入: ring “godding”, key “godding” 输出: 13 题目分析
经典动态规划问题更多案例可见 Leetcode 动态规划详解 我们可以使用动态规划解决本题解题思路
状态定义 dp[i][j] 表示 key 的第 i 个字符 ring 的第 j 个字符与 12:00 方向对齐的最少步数pos[i] 表示字符 i 在 ring 中出现的位置集合用来加速计算转移的过程 状态转移方程枚举上一次与12:00方向对齐的位置k此次需要从位置k旋转到位置j d p [ i ] [ j ] min k ∈ p o s [ k e y [ i − 1 ] ] d p [ i − 1 ] [ k ] m i n a b s ( j − k ) , n − a b s ( j − k ) 1 dp[i][j] \displaystyle\min_k∈pos[key[i−1]] {dp[i−1][k] min{abs(j − k), n − abs(j − k)} 1} dp[i][j]kmin∈pos[key[i−1]]dp[i−1][k]minabs(j−k),n−abs(j−k)1
min{abs(j − k), n − abs(j − k)} 1从位置k旋转到位置j的最少步数
初始状态dp[0][i] min{i, n - i} 1最终答案为 min i 0 n − 1 d p [ m − 1 ] [ i ] \displaystyle\min_i0^n-1 {dp[m-1][i]} imin0n−1dp[m−1][i] 动态规划一般用于求解具有重叠子问题和最优子结构的问题例如最长公共子序列、背包问题、最短路径等。重叠子问题指的是在求解问题的过程中多次用到相同的子问题最优子结构指的是问题的最优解可以通过子问题的最优解来构造 class Solution {public int findRotateSteps(String ring, String key) {int n ring.length(), m key.length();// 字符 i 在 ring 中出现的位置集合用来加速计算转移的过程ListInteger[] pos new List[26];for (int i 0; i 26; i) {pos[i] new ArrayListInteger();}for (int i 0; i n; i) {pos[ring.charAt(i) - a].add(i);}int[][] dp new int[m][n];for (int i 0; i m; i) {Arrays.fill(dp[i], Integer.MAX_VALUE);}for (int i : pos[key.charAt(0) - a]) {dp[0][i] Math.min(i, n - i) 1;}for (int i 1; i m; i) {for (int j : pos[key.charAt(i) - a]) {for (int k : pos[key.charAt(i - 1) - a]) {dp[i][j] Math.min(dp[i][j], dp[i - 1][k] Math.min(Math.abs(j - k), n - Math.abs(j - k)) 1);}}}return Arrays.stream(dp[m - 1]).min().getAsInt();}
}
