题目: 力扣514 ： 自由之路 . - 力扣（LeetCode）
题目的详细描述，直接打开力扣看就是了，下面说一下我对题目的理解:
事例1：
输入: ring = "godding", key = "gd"
输出: 4.
1. ring的第一个字符默认是指向12点方向的，这一点很重要
2. key的第一个字符为g，而ring中首字符和末尾字符都为g。因此，必然存在选择首字符的g还是末尾字符g的问题。
3. 即使ring中第一个字符为g，也还存在存在顺时针旋转和逆时针旋转的问题。(当然，当前案例比较极端，如果第一个字符不为g，理解起来更合适)
4. 这一题要求的是旋转的最小步数。因此，最终的值必然是获取最小值的。
5. 那么整体串起来分析：
ring = "godding", key = "gd"
字符godding下标0123456
a1. 如果ring的第一个g旋转，顺时针步数为0；逆时针步数为7；算上最终确认的1步，因此就 是在 1 和 8中选取最小值，选取1
a2. 接着a1继续分析，既然key的第一个字符已经确定了。那么key的第二个字符d又该选择 了。我们到底是用下标为2的d呢，还是使用下标为3的d呢？
选择1： 下标为2的d，从a1的g顺时针旋转只需要2步，逆时针旋转需要5步，。算上确认的1步，就是在3和6中选取最小值，选取3
选择2： 下标为3的d, 从a1的g顺时针旋转只需要3步，逆时针旋转需要4步。算上确认的1步，就是在4和5中选取最小值. 选取 4
如果g使用的是ring中第一个字符，针对以上2种选择，最好的选择就是使用下标为2的d，顺时针旋转2步，即3步。 那么，总的代价就是 1 + 3 = 4。
开头，我们就说过，ring中有开头和结尾都存在g，因此存在选择的问题。
b1. 如果我们使用ring中下标为6的g最为key的开头。顺时针旋转需要1步，逆时针旋转需要6步，算上最终确认的1步，就是2步和7步。选取最小值2.
b2. 接着b1继续分析，既然key的第一个字符已经确定了。那么key的第二个字符d又该选择 了。我们到底是用下标为2的d呢，还是使用下标为3的d呢？
选择1： 下标为2的d，从b1的g顺时针旋转只需要4步，逆时针旋转需要3步，。算上确认的1步，就是在5和4中选取最小值，选取4
选择2： 下标为3的d, 从b1的g顺时针旋转只需要3步，逆时针旋转需要4步。算上确认的1步，就是在4和5中选取最小值. 选取4
如果g使用的是ring中最后一个字符，针对以上2种选择，最好都为4。 那么，总的代价就是 2 + 4 = 6。
最终，如果以ring中第一个g作为旋转选择，最小的步数为4; 以ring中最后一个g作为旋转选择，那么最小步数为6； 因此，当前案例最小步数为 Math.min(4, 6).
递归代码：
package 刷题.第三天;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* 力扣514： 自由之路
* https://leetcode.cn/problems/freedom-trail/
*/
public class C2_FreeDomTtail_leet514_递归 {
//递归版本
public int findRotateSteps(String ring, String key) {
if (ring == null || ring.length() == 0 || key == null || key.length() == 0) {
return 0;
}
char[] source = ring.toCharArray();
char[] target = key.toCharArray();
//记录下每个字符的位置，有可能存在重复值的情况
HashMap
for (int i = 0; i < ring.length(); i++) {
if (map.containsKey(source[i])) {
//放入下标的位置
map.get(source[i]).add(i);
}
else {
List list = new ArrayList();
list.add(i);
map.put(source[i], list);
}
}
return process(map, source, 0, target, 0);
}
public int process (Map
char[] source, int sourceStartIndex,
char[] target, int targetIndex) {
if (targetIndex == target.length) {
return 0;
}
List
int minStep = Integer.MAX_VALUE;
for (int i = 0; i < ops.size(); i++) {
//从sourceStartIndex 到 ops.get(i) 最下步数; +1是确认按钮耗费的1步
int step = getMinSteps(sourceStartIndex, ops.get(i), source.length) + 1;
//深度优先遍历； 此时source的的开始位置为 ops.get(i)
minStep = Math.min(minStep, step + process(map, source, ops.get(i), target, targetIndex + 1));
}
return minStep;
}
//获取从最小长度
public int getMinSteps(int start, int end, int size)
{
//如果start < end, 则是顺时针; 反之， 逆时针
int step1 = Math.abs(start - end);
//如果step1是顺时针，那么step则是逆时针; 反之，顺时针
int step2 = size - step1;
return Math.min(step1, step2);
}
public static void main(String[] args) {
C2_FreeDomTtail_leet514_递归 ss = new C2_FreeDomTtail_leet514_递归();
String source = "godding";
String target = "gd";
System.out.println(ss.findRotateSteps(source, target));
}
}
测试结果：
超时是好事情，说明整体逻辑大概率是没有问题的。超时，说明递归计算的次数有问题。上方的分析过程中，a2和b2 都是针对d进行逻辑判断的，明显存在重复的过程。那么，就需要在递归的基础之上添加缓存了，俗称记忆化搜索。
我之前在说动态规划的时候就说过，如果表结构依赖不严格，或者说即使依赖严格表结构，但是没有优化的空间。 递归 + 缓存 == 动态规划。
递归+缓存版本：
package 刷题.第三天;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* 力扣514： 自由之路
* https://leetcode.cn/problems/freedom-trail/
*/
public class C2_FreeDomTtail_leet514_递归_缓存 {
//递归 + 缓存
public int findRotateSteps(String ring, String key) {
if (ring == null || ring.length() == 0 || key == null || key.length() == 0) {
return 0;
}
char[] source = ring.toCharArray();
char[] target = key.toCharArray();
//记录下每个字符的位置，有可能存在重复值的情况
HashMap
for (int i = 0; i < ring.length(); i++) {
if (map.containsKey(source[i])) {
//放入下标的位置
map.get(source[i]).add(i);
}
else {
List list = new ArrayList();
list.add(i);
map.put(source[i], list);
}
}
int[][] dp = new int[source.length][target.length];
for (int i = 0; i < source.length; i++) {
for (int j = 0; j < target.length; j++) {
//代表没算过
dp[i][j] = -1;
}
}
return process(map, source, 0, target, 0, dp);
}
public int process (Map
char[] source, int sourceStartIndex,
char[] target, int targetIndex,
int[][] dp) {
if (targetIndex == target.length) {
return 0;
}
//缓存
if (dp[sourceStartIndex][targetIndex] != -1) {
return dp[sourceStartIndex][targetIndex];
}
List
int minStep = Integer.MAX_VALUE;
for (int i = 0; i < ops.size(); i++) {
//从sourceStartIndex 到 ops.get(i) 最下步数; +1是确认按钮耗费的1步
int step = getMinSteps(sourceStartIndex, ops.get(i), source.length) + 1;
//深度优先遍历； 此时source的的开始位置为 ops.get(i)
minStep = Math.min(minStep, step + process(map, source, ops.get(i), target, targetIndex + 1, dp));
dp[sourceStartIndex][targetIndex] = minStep;
}
return minStep;
}
//获取从最小长度
public int getMinSteps(int start, int end, int size)
{
//如果start < end, 则是顺时针; 反之， 逆时针
int step1 = Math.abs(start - end);
//如果step1是顺时针，那么step则是逆时针; 反之，顺时针
int step2 = size - step1;
return Math.min(step1, step2);
}
public static void main(String[] args) {
C2_FreeDomTtail_leet514_递归_缓存 ss = new C2_FreeDomTtail_leet514_递归_缓存();
String source = "godding";
String target = "gd";
System.out.println(ss.findRotateSteps(source, target));
}
}
测试结果：
84%的胜率，8毫秒，已经相当优秀了。其实，这就是最优解
第三版本：纯动态规划
动态规划，那就需要分析递归的逻辑了。下面以ring作为行，以key作为列
第一步：
0 (g)1 (d)0 (g） 下标0的g: 顺时针：1步 逆时针：8步 选取1步 1 (o)2 (d) 3 (d) 4 (i)5 (n)6 (g) 下标6的g : 顺时针：2步 逆时针：7步 选取2步
第二步：
0 (g)1 (d)0 (g） 下标0的g: 1步 1 (o)2 (d) 下标为2的d： 从下标为0的g过来， 顺时针2步，逆时针5步， 算上确认的1步， 就是3步和6步，选取小值，即3步 从下标为6的g过来， 顺时针3步，逆时针4步， 算上确认的1步， 就是4步和5步，选取小值，即4步 最终值就是: 1+3 和 2 +4选取小的。即4步 1是下标为0的g耗费的1步 2是下标为6的g耗费的2步 3 (d) 下标为3的d： 从下标为0的g过来， 顺时针3步，逆时针4步， 算上确认的1步， 就是4步和5步，选取小值，即4步 从下标为6的g过来， 顺时针4步，逆时针3步， 算上确认的1步， 就是5步和4步，选取小值，即4步 最终值就是: 1+4 和 2 +4选取小的。即5步 1是下标为0的g耗费的1步 2是下标为6的g耗费的2步 4 (i)5 (n)6 (g)下标6的g : 2步
因此，最终最小的步数就是当key遍历完最后一个字符得到，即 1 + 3 = 4步；
纯动态规划
package 刷题.第三天;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* 力扣514： 自由之路
* https://leetcode.cn/problems/freedom-trail/
*/
public class C2_FreeDomTtail_leet514_动态规划 {
//纯动态规划
public int findRotateSteps(String ring, String key) {
if (ring == null || ring.length() == 0 || key == null || key.length() == 0) {
return 0;
}
char[] source = ring.toCharArray();
char[] target = key.toCharArray();
//记录下每个字符的位置，有可能存在重复值的情况
HashMap
for (int i = 0; i < ring.length(); i++) {
if (map.containsKey(source[i])) {
//放入下标的位置
map.get(source[i]).add(i);
}
else {
List list = new ArrayList();
list.add(i);
map.put(source[i], list);
}
}
int[][] dp = new int[source.length][target.length + 1];
//最终返回的最小值
int finalMinStep = Integer.MAX_VALUE;
//第一列
List
for (int index : ops) {
dp[index][0] = getMinSteps(0, index, source.length) + 1;
//如果要拼接的key只有一个字符，直接获取最小值即可
finalMinStep = Math.min(finalMinStep, dp[index][0]);
}
//如果要拼接的字符长度超过1，那么finalMinStep的值需要
//等到 target的最后一列才能确定
if (target.length > 1) {
finalMinStep = Integer.MAX_VALUE;
}
//列遍历，从第二列开始往后遍历
for (int i = 1; i < target.length ; i++)
{
//当前列对应的行信息
List
//当前列前一列对应的行信息
List
for (int j : ops2) //结束
{
//j行i列的默认最小值
int minStep = Integer.MAX_VALUE;
for(int m : ops3) //开始
{
//从m行到j行的步数
int curStep = getMinSteps(m, j, source.length) + 1;
//dp[m][i-1] : 从0到m累计步数
//dp[j][i-1] + curStep ： 代表从0行到j行累计步数
int steps = dp[m][i-1] + curStep;
//更新j行i列的最小值
minStep = Math.min(minStep, steps);
dp[j][i] = minStep;
}
//要拼接字符串的最后一个字符，也就是说可以
//已经全部拼接完了
if (i == target.length - 1) {
finalMinStep = Math.min(finalMinStep, dp[j][i]);
}
}
}
return finalMinStep;
}
//获取从最小长度
public int getMinSteps(int start, int end, int size)
{
//如果start < end, 则是顺时针; 反之， 逆时针
int step1 = Math.abs(start - end);
//如果step1是顺时针，那么step则是逆时针; 反之，顺时针
int step2 = size - step1;
return Math.min(step1, step2);
}
public static void main(String[] args) {
C2_FreeDomTtail_leet514_动态规划 ss = new C2_FreeDomTtail_leet514_动态规划();
/*String source = "godding";
String target = "gd";*/
String source = "eh";
String target = "h";
System.out.println(ss.findRotateSteps(source, target));
}
}
测试结果：
10毫秒，76%胜率，也还行。
第四种解法，即官方解法。因为胜率没有我写的两个版本的高，我就不说了。
官方代码胜率：
精彩文章
发表评论