題目: 力扣514 ： 自由之路??. - 力扣（LeetCode）
題目的詳細描述，直接打開力扣看就是了，下面說一下我對題目的理解:
事例1：
輸入: ring = "godding", key = "gd" 輸出: 4.
1. ring的第一個字符默認是指向12點方向的，這一點很重要
2. key的第一個字符為g，而ring中首字符和末尾字符都為g。因此，必然存在選擇首字符的g還是末尾字符g的問題。
3. 即使ring中第一個字符為g，也還存在存在順時針旋轉和逆時針旋轉的問題。(當然，當前案例比較極端，如果第一個字符不為g，理解起來更合適)
4. 這一題要求的是旋轉的最小步數(shù)。因此，最終的值必然是獲取最小值的。
5. 那么整體串起來分析：
????????ring = "godding", key = "gd"
? ? ? ?
| 字符 | g | o | d | d | i | n | g |
| 下標 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
a1. 如果ring的第一個g旋轉，順時針步數(shù)為0；逆時針步數(shù)為7；算上最終確認的1步，因此就? ? ? ? ? ? ? ?是在 1 和 8中選取最小值，選取1
a2. 接著a1繼續(xù)分析，既然key的第一個字符已經(jīng)確定了。那么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繼續(xù)分析，既然key的第一個字符已經(jīng)確定了。那么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作為旋轉選擇，最小的步數(shù)為4;? 以ring中最后一個g作為旋轉選擇，那么最小步數(shù)為6；? 因此，當前案例最小步數(shù)為 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<Character, List> map = new HashMap<Character, List>();
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<Character, List> map,
char[] source, int sourceStartIndex,
char[] target, int targetIndex) {
if (targetIndex == target.length) {
return 0;
}
List<Integer> ops = map.get(target[targetIndex]);
int minStep = Integer.MAX_VALUE;
for (int i = 0; i < ops.size(); i++) {
//從sourceStartIndex 到 ops.get(i) 最下步數(shù); +1是確認按鈕耗費的1步
int step = getMinSteps(sourceStartIndex, ops.get(i), source.length) + 1;
//深度優(yōu)先遍歷； 此時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));
}
}
測試結果：
超時是好事情，說明整體邏輯大概率是沒有問題的。超時，說明遞歸計算的次數(shù)有問題。上方的分析過程中，a2和b2 都是針對d進行邏輯判斷的，明顯存在重復的過程。那么，就需要在遞歸的基礎之上添加緩存了，俗稱記憶化搜索。
我之前在說動態(tài)規(guī)劃的時候就說過，如果表結構依賴不嚴格，或者說即使依賴嚴格表結構，但是沒有優(yōu)化的空間。? 遞歸 + 緩存 ==?動態(tài)規(guī)劃。
遞歸+緩存版本：
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<Character, List> map = new HashMap<Character, List>();
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<Character, List> 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<Integer> ops = map.get(target[targetIndex]);
int minStep = Integer.MAX_VALUE;
for (int i = 0; i < ops.size(); i++) {
//從sourceStartIndex 到 ops.get(i) 最下步數(shù); +1是確認按鈕耗費的1步
int step = getMinSteps(sourceStartIndex, ops.get(i), source.length) + 1;
//深度優(yōu)先遍歷； 此時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毫秒，已經(jīng)相當優(yōu)秀了。其實，這就是最優(yōu)解
第三版本：純動態(tài)規(guī)劃
動態(tài)規(guī)劃，那就需要分析遞歸的邏輯了。下面以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步 |
因此，最終最小的步數(shù)就是當key遍歷完最后一個字符得到，即 1 + 3 = 4步；
純動態(tài)規(guī)劃
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_動態(tài)規(guī)劃 {
//純動態(tài)規(guī)劃
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<Character, List> map = new HashMap<Character, List>();
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<Integer> ops = map.get(target[0]);
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<Integer> ops2 = map.get(target[i]);
//當前列前一列對應的行信息
List<Integer> ops3 = map.get(target[i-1]);
for (int j : ops2) //結束
{
//j行i列的默認最小值
int minStep = Integer.MAX_VALUE;
for(int m : ops3) //開始
{
//從m行到j行的步數(shù)
int curStep = getMinSteps(m, j, source.length) + 1;
//dp[m][i-1] : 從0到m累計步數(shù)
//dp[j][i-1] + curStep ： 代表從0行到j行累計步數(shù)
int steps = dp[m][i-1] + curStep;
//更新j行i列的最小值
minStep = Math.min(minStep, steps);
dp[j][i] = minStep;
}
//要拼接字符串的最后一個字符，也就是說可以
//已經(jīng)全部拼接完了
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_動態(tài)規(guī)劃 ss = new C2_FreeDomTtail_leet514_動態(tài)規(guī)劃();
/*String source = "godding";
String target = "gd";*/
String source = "eh";
String target = "h";
System.out.println(ss.findRotateSteps(source, target));
}
}
測試結果：
10毫秒，76%勝率，也還行。
第四種解法，即官方解法。因為勝率沒有我寫的兩個版本的高，我就不說了。
官方代碼勝率：文章來源：http://www.zghlxwxcb.cn/news/detail-852469.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-852469.html
到了這里，關于算法50：動態(tài)規(guī)劃專練(力扣514題：自由之路-----4種寫法)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
