?? 面試必備：高頻算法題匯總「圖文解析 + 教學(xué)視頻 + 范例代碼」之字符串處理+動態(tài)規(guī)劃合集差购！

面試

Attention

秋招接近尾聲四瘫，我總結(jié)了牛客欲逃、WanAndroid 上找蜜，有關(guān)筆試面經(jīng)的帖子中出現(xiàn)的算法題，結(jié)合往年考題寫了這一系列文章稳析，所有文章均與 LeetCode 進(jìn)行核對洗做、測試。歡迎食用

本文將覆蓋「字符串處理」 + 「動態(tài)規(guī)劃」方面的面試算法題彰居，文中我將給出：

面試中的題目
解題的思路
特定問題的技巧和注意事項(xiàng)
考察的知識點(diǎn)及其概念
詳細(xì)的代碼和解析

開始之前诚纸，我們先看下會有哪些重點(diǎn)案例：

為了方便大家跟進(jìn)學(xué)習(xí)，我在 GitHub 建立了一個(gè)倉庫

倉庫地址：超級干貨陈惰！精心歸納視頻畦徘、歸類、總結(jié)抬闯，各位路過的老鐵支持一下井辆！給個(gè) Star ！

現(xiàn)在就讓我們開始吧溶握！

字符串處理

字符串廣泛應(yīng)用在 Java 編程中杯缺，在 Java 中字符串屬于對象，Java 提供了 String 類來創(chuàng)建和操作字符串睡榆。面試中的字符串處理問題夺谁，主要是對于字符串各種方法的靈活應(yīng)用。下面結(jié)合實(shí)例肉微，講講常見的考點(diǎn)：

參考方法

括號生成

給定 n，表示有 n 對括號, 請寫一個(gè)函數(shù)以將其生成所有的括號組合蜡塌，并返回組合結(jié)果碉纳。

例如

給出 n = 3，生成結(jié)果為：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

解題思路

使用回溯法

只有在我們知道序列仍然保持有效時(shí)才添加 '(' or ')'馏艾，而不是像方法一那樣每次添加劳曹。我們可以通過跟蹤到目前為止放置的左括號和右括號的數(shù)目來做到這一點(diǎn)奴愉，

如果我們還剩一個(gè)位置，我們可以開始放一個(gè)左括號铁孵。如果它不超過左括號的數(shù)量锭硼，我們可以放一個(gè)右括號。

視頻

視頻講解和源碼-生成括號

public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    helper(n, n, "", res);
    return res;
}

// DFS
private void helper(int nL, int nR, String parenthesis, List<String> res) {
    // nL 和 nR 分別代表左右括號剩余的數(shù)量
    if (nL < 0 || nR < 0) {
        return;
    }
    
    if (nL == 0 && nR == 0) {
        res.add(parenthesis);
        return;
    }
    helper(nL - 1, nR, parenthesis + "(", res);
    if (nL >= nR) {
        return;
    }
    helper(nL, nR - 1, parenthesis + ")", res);
}

復(fù)雜度

復(fù)雜度計(jì)算

Excel表列標(biāo)題

給定一個(gè)正整數(shù)蜕劝，返回相應(yīng)的列標(biāo)題檀头，如Excel表中所示。如:
1 -> A岖沛，
2 -> B
...
26 -> Z暑始，
27 -> AA

示例 :

輸入: 28
輸出: "AB"

解題思路

網(wǎng)上看了 n 多人的方法，感覺很多都做麻煩了婴削。大多數(shù)人都困在這個(gè) ‘A’ 或者說 n = 0 上
舉個(gè)例子廊镜，如果輸入 26，我們一般會直接把它 %26 這樣得到的就是一個(gè) 0
然而很多人得到字符的方式都是 %26 + 64唉俗，也就是 0 + ‘A’ = 'A' ,正確答案當(dāng)然是 ‘Z’嗤朴，于是加了一堆判斷
其實(shí)不用那么麻煩，一個(gè) n-- 就能搞定.

public String convertToTitle (int n) {
    StringBuilder str = new StringBuilder();

    while (n > 0) {
        n--;
        str.append ( (char) ( (n % 26) + 'A'));
        n /= 26;
    }
    return str.reverse().toString();
}

翻轉(zhuǎn)游戲

給定一個(gè)只包含兩種字符的字符串：+和-虫溜，你和你的小伙伴輪流翻轉(zhuǎn)"++"變成"--"雹姊。當(dāng)一個(gè)人無法采取行動時(shí)游戲結(jié)束，另一個(gè)人將是贏家吼渡。編寫一個(gè)函數(shù)容为，計(jì)算字符串在一次有效移動后的所有可能狀態(tài)。

示例 :

輸入：s = "++++"
[
  "--++",
  "+--+",
  "++--"
]

解題思路

我們從第二個(gè)字母開始遍歷
每次判斷當(dāng)前字母是否為+寺酪，和之前那個(gè)字母是否為+
如果都為加坎背，則將翻轉(zhuǎn)后的字符串存入結(jié)果中即可

public List<String> generatePossibleNextMoves (String s) {
    List list = new ArrayList();
    // indexOf 方法使用 看下方拓展
    for (int i = -1; (i = s.indexOf ("++", i + 1)) >= 0;) {
        list.add (s.substring (0, i) + "--" + s.substring (i + 2));
    }
    return list;
}

拓展：

Java中字符串中子串的查找共有四種方法，如下：

int indexOf(String str) ：返回第一次出現(xiàn)的指定子字符串在此字符串中的索引寄雀。
int indexOf(String str, int startIndex)：從指定的索引處開始得滤，返回第一次出現(xiàn)的指定子字符串在此字符串中的索引。
int lastIndexOf(String str) ：返回在此字符串中最右邊出現(xiàn)的指定子字符串的索引盒犹。
int lastIndexOf(String str, int startIndex) ：從指定的索引處開始向后搜索懂更，返回在此字符串中最后一次出現(xiàn)的指定子字符串的索引。

substring() 方法返回字符串的子字符串急膀。

public String substring(int beginIndex) 返回 beginIndex 后的字符串
public String substring(int beginIndex, int endIndex) 返回 beginIndex 到 endIndex 之間的字符串

翻轉(zhuǎn)字符串中的單詞

給定一個(gè)字符串沮协，逐個(gè)翻轉(zhuǎn)字符串中的每個(gè)單詞。

示例：

輸入: "a good   example"
輸出: "example good a"
解釋: 如果兩個(gè)單詞間有多余的空格卓嫂，將反轉(zhuǎn)后單詞間的空格減少到只含一個(gè)慷暂。

解題思路

通過 split 方法，以 “ ” 為標(biāo)識符為基準(zhǔn)拆分字符串
將拆分后的字符串倒序插入數(shù)組中即可

public String reverseWords(String s) {
    if(s.length() == 0 || s == null){
        return " ";
    }
    //按照空格將s切分
    String[] array = s.split(" ");
    StringBuilder sb = new StringBuilder();
    //從后往前遍歷array晨雳，在sb中插入單詞
    for(int i = array.length - 1; i >= 0; i--){
        if(!array[i].equals("")) {
            // 為防止字符串首多一個(gè) “ ” 判斷當(dāng)前是不是空字符串
            // 是字符串第一個(gè)就不輸出空格
            if (sb.length() > 0) {
                sb.append(" ");
            }
            
            sb.append(array[i]);
        }
    }
    return sb.toString();
}

字符串轉(zhuǎn)換整數(shù) (atoi)

實(shí)現(xiàn)atoi這個(gè)函數(shù)行瑞，將一個(gè)字符串轉(zhuǎn)換為整數(shù)奸腺。如果沒有合法的整數(shù)，返回0血久。如果整數(shù)超出了32位整數(shù)的范圍突照，返回 INT_MAX(2147483647) 如果是正整數(shù)，或者 INT_MIN(-2147483648) 如果是負(fù)整數(shù)氧吐。

示例 :

輸入: "4193 with words"
輸出: 4193
解釋: 轉(zhuǎn)換截止于數(shù)字 '3' 讹蘑，因?yàn)樗南乱粋€(gè)字符不為數(shù)字。
示例 4:

輸入: "words and 987"
輸出: 0
解釋: 第一個(gè)非空字符是 'w', 但它不是數(shù)字或正副砍、負(fù)號衔肢。
     因此無法執(zhí)行有效的轉(zhuǎn)換。

解題思路

首先我們要知道該數(shù)正負(fù)
根據(jù)題意調(diào)用 trim() 去掉空格
去完多余空格之后豁翎，首位有三種情況 ‘+’ ‘-’ 其他
設(shè)一個(gè) falg 叫做 sign 默認(rèn)值為一角骤，如果監(jiān)測到 ‘-’ 則設(shè)為 -1
這樣一來后面求出的結(jié)果乘以 sigh 就能帶上正負(fù)值
在定義一個(gè) num 值用于保存答案數(shù)值
for 循環(huán)從頭到尾訪問字符串
先判斷當(dāng)前位是否為數(shù)字，這時(shí)分兩種情況
如果字符串首位就不是數(shù)字和 -+ 號心剥，根據(jù)題意直接退出循環(huán)
如果為數(shù)字就將 sum 的值 *10 倍邦尊，再將其加入 sum 中
如果值超過 MAX_VALUE 跳出循環(huán)
對應(yīng) *sigh 輸出正負(fù)值，或者 MAX_VALUE 或 MIN_VALUE 即可

視頻

視頻講解和源碼-字符串轉(zhuǎn)換整數(shù)

public int myAtoi(String str) {
    if(str == null) {
        return 0;
    }
    str = str.trim();
    if (str.length() == 0) {
        return 0;
    }
        
    int sign = 1;
    int index = 0;

    if (str.charAt(index) == '+') {
        index++;
    } else if (str.charAt(index) == '-') {
        sign = -1;
        index++;
    }
    long num = 0;
    for (; index < str.length(); index++) {
        if (str.charAt(index) < '0' || str.charAt(index) > '9') {
            break;
        }
        num = num * 10 + (str.charAt(index) - '0');
        if (num > Integer.MAX_VALUE ) {
            break;
        }
    }   
    if (num * sign >= Integer.MAX_VALUE) {
        return Integer.MAX_VALUE;
    }
    if (num * sign <= Integer.MIN_VALUE) {
        return Integer.MIN_VALUE;
    }
    return (int)num * sign;
}

注：trim() 函數(shù)是去掉String字符串的首尾空格;

最長公共前綴

編寫一個(gè)函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴优烧。

如果不存在公共前綴蝉揍，返回空字符串 ""。

示例 :

輸入: ["flower","flow","flight"]
輸出: "fl"

解題思路

標(biāo)簽：鏈表
當(dāng)字符串?dāng)?shù)組長度為 0 時(shí)則公共前綴為空畦娄，直接返回
令最長公共前綴 ans 的值為第一個(gè)字符串又沾，進(jìn)行初始化
遍歷后面的字符串，依次將其與 ans 進(jìn)行比較熙卡，兩兩找出公共前綴杖刷，最終結(jié)果即為最長公共前綴
如果查找過程中出現(xiàn)了 ans 為空的情況，則公共前綴不存在直接返回
s 為所有字符串的長度之和

最大公共子串

視頻

最長公共前綴

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    String prefix = strs[0];
    for(int i = 1; i < strs.length; i++) {
        int j = 0;
        while (j < strs[i].length() && j < prefix.length() && strs[i].charAt(j) == prefix.charAt(j)) {
            j++;
        }
        if( j == 0) {
            return "";
        }
        prefix = prefix.substring(0, j);
    }
    return prefix;
}

時(shí)間復(fù)雜度：

$O(s)$

回文數(shù)

判斷一個(gè)正整數(shù)是不是回文數(shù)驳癌』迹回文數(shù)的定義是，將這個(gè)數(shù)反轉(zhuǎn)之后颓鲜，得到的數(shù)仍然是同一個(gè)數(shù)表窘。

示例 :

輸入: 121
輸出: true

解題思路

通過取整和取余操作獲取整數(shù)中對應(yīng)的數(shù)字進(jìn)行比較。

舉個(gè)例子：1221 這個(gè)數(shù)字甜滨。

通過計(jì)算 1221 / 1000乐严，得首位1
通過計(jì)算 1221 % 10，可得末位 1
進(jìn)行比較
再將 22 取出來繼續(xù)比較

解題思路

視頻

回文數(shù)

public boolean palindromeNumber(int num) {
    // Write your code here
    if(num < 0){
        return false;
    }
    int div = 1;
    while(num / div >= 10){
        div *= 10;
    }
    while(num > 0){
        if(num / div != num % 10){
            return false;
        }
        num = (num % div) / 10;
        div /= 100;
    }
    return true;
}

動態(tài)規(guī)劃

動態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題衣摩，動態(tài)規(guī)劃方法所耗時(shí)間往往遠(yuǎn)少于樸素解法麦备。其背后的基本思想非常簡單。大致上，若要解一個(gè)給定問題凛篙，我們需要解其不同部分（即子問題），再根據(jù)子問題的解以得出原問題的解栏渺。

通常許多子問題非常相似呛梆，為此動態(tài)規(guī)劃法試圖僅僅解決每個(gè)子問題一次，從而減少計(jì)算量：一旦某個(gè)給定子問題的解已經(jīng)算出磕诊，則將其記憶化存儲填物，以便下次需要同一個(gè)子問題解之時(shí)直接查表。這種做法在重復(fù)子問題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長時(shí)特別有用霎终。

單詞拆分

給定字符串 s 和單詞字典 dict滞磺，確定 s 是否可以分成一個(gè)或多個(gè)以空格分隔的子串，并且這些子串都在字典中存在莱褒。

示例：

輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因?yàn)?"applepenapple" 可以被拆分成 "apple pen apple"击困。
     注意你可以重復(fù)使用字典中的單詞。

解題思路

這個(gè)方法的想法是對于給定的字符串 s 可以被拆分成子問題 s1 和 s2 广凸。如果這些子問題都可以獨(dú)立地被拆分成符合要求的子問題阅茶，那么整個(gè)問題 s 也可以滿足。也就是谅海，如果 $catsanddog$ 可以拆分成兩個(gè)子字符串 " $catsand$ " 和 " $dog$ " 脸哀。子問題 " $catsand$ " 可以進(jìn)一步拆分成 " $cats$ " 和 " $and$ " ，這兩個(gè)獨(dú)立的部分都是字典的一部分扭吁，所以 " $catsand$ " 滿足題意條件撞蜂，再往前， " $catsand$ " 和 " $dog$ " 也分別滿足條件侥袜，所以整個(gè)字符串 " $catsanddog$ " 也滿足條件蝌诡。

現(xiàn)在，我們考慮 $dp$ 數(shù)組求解的過程:

我們使用 $n+1$ 大小數(shù)組的 $dp$ 系馆，其中 $n$ 是給定字符串的長度送漠。
我們也使用 2 個(gè)下標(biāo)指針 $i$ 和 $j$ ，其中 $i$ 是當(dāng)前字符串從頭開始的子字符串 $（s'）$ 的長度由蘑， $j$ 是當(dāng)前子字符串 $（s'）$ 的拆分位置闽寡，拆分成 $s'(0,j)$ 和 $s'(j+1,i)$ 。
為了求出 $dp$ 數(shù)組尼酿，我們初始化 $dp[0]$ 為 $true$ 爷狈，這是因?yàn)榭兆址偸亲值涞囊徊糠帧? $dp$ 數(shù)組剩余的元素都初始化為 $false$ 。
我們用下標(biāo) $i$ 來考慮所有從當(dāng)前字符串開始的可能的子字符串裳擎。對于每一個(gè)子字符串涎永，我們通過下標(biāo) $j$ 將它拆分成 s1' 和 s2'（注意 i 現(xiàn)在指向 s2' 的結(jié)尾）。
為了將 $dp[i]$ 數(shù)組求出來，我們依次檢查每個(gè) $dp[j]$ 是否為 $true$ 羡微，也就是子字符串 s1′ 是否滿足題目要求谷饿。如果滿足，我們接下來檢查 s2′ 是否在字典中妈倔。如果包含博投，我們接下來檢查 s2′ 是否在字典中，如果兩個(gè)字符串都滿足要求盯蝴，我們讓 $dp[i]$ 為 $true$ 毅哗，否則令其為 $false$ 窄赋。

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet=new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

復(fù)雜度分析

時(shí)間復(fù)雜度： $O(n^2)$ 夸楣。求出 $dp$ 數(shù)組需要兩重循環(huán)朵锣。

空間復(fù)雜度： $O(n)$ 袜瞬。 $dp$ 數(shù)組的長度是 $n+1$ 纸淮。

爬樓梯

假設(shè)你正在爬樓梯遥皂。需要 n 階你才能到達(dá)樓頂捅僵。

每次你可以爬 1 或 2 個(gè)臺階足删。你有多少種不同的方法可以爬到樓頂呢鸣峭？

注意：給定 n 是一個(gè)正整數(shù)宏所。

示例 :

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
 1 階 + 1 階 + 1 階
 1 階 + 2 階
 2 階 + 1 階

解題思路

感覺這題類似斐波那契數(shù)列摊溶。不難發(fā)現(xiàn)爬骤，這個(gè)問題可以被分解為一些包含最優(yōu)子結(jié)構(gòu)的子問題，即它的最優(yōu)解可以從其子問題的最優(yōu)解來有效地構(gòu)建莫换，我們可以使用動態(tài)規(guī)劃來解決這一問題霞玄。

第 $i$ 階可以由以下兩種方法得到：

在第 $(i?1)$ 階后向上爬 1 階。

在第 $(i?2)$ 階后向上爬 2 階拉岁。

所以到達(dá)第 $i$ 階的方法總數(shù)就是到第 $(i?1)$ 階和第 $(i?2)$ 階的方法數(shù)之和坷剧。

令 $dp[i]$ 表示能到達(dá)第 $i$ 階的方法總數(shù)：

$dp[i]=dp[i-1]+dp[i-2]$
$dp[i]=dp[i?1]+dp[i?2]$

解題思路

public int climbStairs(int n) {
    if (n == 0) return 0;
    int[] array = new int[n + 1];
    array[0] = 1;
    if (array.length > 1) {
        array[1] = 1;
    }
    
    for(int i = 2; i < array.length; i++) {
        array[i] = array[i - 1] + array[i - 2];
    }
    return array[n];
}

打家劫舍

假設(shè)你是一個(gè)專業(yè)的竊賊，準(zhǔn)備沿著一條街打劫房屋喊暖。每個(gè)房子都存放著特定金額的錢惫企。你面臨的唯一約束條件是：相鄰的房子裝著相互聯(lián)系的防盜系統(tǒng)，且當(dāng)相鄰的兩個(gè)房子同一天被打劫時(shí)陵叽，該系統(tǒng)會自動報(bào)警狞尔。給定一個(gè)非負(fù)整數(shù)列表，表示每個(gè)房子中存放的錢巩掺，算一算偏序，如果今晚去打劫，在不觸動報(bào)警裝置的情況下, 你最多可以得到多少錢胖替。

示例 :

輸入: [2,7,9,3,1]
輸出: 12
解釋: 偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)研儒，接著偷竊 5 號房屋 (金額 = 1)豫缨。
     偷竊到的最高金額 = 2 + 9 + 1 = 12 。

解題思路

考慮所有可能的搶劫方案過于困難端朵。一個(gè)自然而然的想法是首先從最簡單的情況開始好芭。記：

$f(k) =$ 從前 k 個(gè)房屋中能搶劫到的最大數(shù)額， $A_i$ = 第 i 個(gè)房屋的錢數(shù)冲呢。

首先看 n = 1 的情況栓撞，顯然 f(1) = $A_1$ 。

再看 n = 2碗硬， $f(2) = max(A_1 , A_2 )$ 。

對于 n = 3瓢颅，有兩個(gè)選項(xiàng):

搶第三個(gè)房子恩尾，將數(shù)額與第一個(gè)房子相加。

不搶第三個(gè)房子挽懦，保持現(xiàn)有最大數(shù)額翰意。

顯然，你想選擇數(shù)額更大的選項(xiàng)信柿。于是冀偶，可以總結(jié)出公式：

$f(k) = max(f(k – 2) + A_k , f(k – 1))$

我們選擇 $f(–1) = f(0) = 0$ 為初始情況，這將極大地簡化代碼渔嚷。

答案為 $f(n)$ 进鸠。可以用一個(gè)數(shù)組來存儲并計(jì)算結(jié)果形病。不過由于每一步你只需要前兩個(gè)最大值客年，兩個(gè)變量就足夠用了。

打劫房屋

public long houseRobber(int[] A) {
    if (A.length == 0) return 0;
    long[] res = new long[A.length + 1];
    res[0] = 0;
    res[1] = A[0];
    for (int i = 2; i < res.length; i++) {
        res[i] = Math.max(res[i - 2] + A[i - 1], res[i - 1]);
    }
    return res[A.length];
}

復(fù)雜度分析

時(shí)間復(fù)雜度： $O(n)$ 漠吻。其中 n 為房子的數(shù)量量瓜。
空間復(fù)雜度： $O(1)$ 。

編輯距離

給出兩個(gè)單詞word1和word2途乃，計(jì)算出將 word1 轉(zhuǎn)換為word2的最少操作次數(shù)绍傲。你總共三種操作方法：插入一個(gè)字符、刪除一個(gè)字符耍共、替換一個(gè)字符烫饼。

示例 :

輸入: word1 = "horse", word2 = "ros"
輸出: 3
解釋: 
horse -> rorse (將 'h' 替換為 'r')
rorse -> rose (刪除 'r')
rose -> ros (刪除 'e')


輸入: word1 = "intention", word2 = "execution"
輸出: 5
解釋: 
intention -> inention (刪除 't')
inention -> enention (將 'i' 替換為 'e')
enention -> exention (將 'n' 替換為 'x')
exention -> exection (將 'n' 替換為 'c')
exection -> execution (插入 'u')

解題思路

我們的目的是讓問題簡單化，比如說兩個(gè)單詞 horse 和 ros 計(jì)算他們之間的編輯距離 D划提，容易發(fā)現(xiàn)枫弟，如果把單詞變短會讓這個(gè)問題變得簡單，很自然的想到用 D[n][m] 表示輸入單詞長度為 n 和 m 的編輯距離鹏往。

具體來說淡诗，D[i][j] 表示 word1 的前 i 個(gè)字母和 word2 的前 j 個(gè)字母之間的編輯距離骇塘。

image

當(dāng)我們獲得 D[i-1][j]，D[i][j-1] 和 D[i-1][j-1] 的值之后就可以計(jì)算出 D[i][j]韩容。

每次只可以往單個(gè)或者兩個(gè)字符串中插入一個(gè)字符

那么遞推公式很顯然了

如果兩個(gè)子串的最后一個(gè)字母相同款违，word1[i] = word2[i] 的情況下：

$D[i][j] = 1 + \min(D[i - 1][j], D[i][j - 1], D[i - 1][j - 1] - 1)$
$D[i][j]=1+min(D[i?1][j],D[i][j?1],D[i?1][j?1]?1)$

否則，word1[i] != word2[i] 我們將考慮替換最后一個(gè)字符使得他們相同：

$D[i][j] = 1 + \min(D[i - 1][j], D[i][j - 1], D[i - 1][j - 1])$
$D[i][j]=1+min(D[i?1][j],D[i][j?1],D[i?1][j?1])$

所以每一步結(jié)果都將基于上一步的計(jì)算結(jié)果群凶，示意如下：

image

同時(shí)插爹，對于邊界情況，一個(gè)空串和一個(gè)非空串的編輯距離為 D[i][0] = i 和 D[0][j] = j请梢。

綜上我們得到了算法的全部流程赠尾。

image

溫馨提示，如果思維不好理解的話毅弧，把解題思路記清楚就行

public int minDistance(String word1, String word2) {
    // write your code here
    int n = word1.length();
    int m = word2.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 0; i < n + 1; i++){
        dp[i][0] = i;
    }
    for (int j = 0; j < m + 1; j++){
        dp[0][j] = j;
    }
    for (int i = 1; i< n + 1; i++){
        for (int j = 1; j < m + 1; j++){
            if (word1.charAt(i - 1) == word2.charAt(j - 1)){
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
            }
        }
    }
    return  dp[n][m];
}

復(fù)雜度分析

時(shí)間復(fù)雜度： $O(m n)$ 气嫁，兩層循環(huán)顯而易見。
空間復(fù)雜度： $O(m n)$ 够坐，循環(huán)的每一步都要記錄結(jié)果寸宵。

乘積最大子序列

給定一個(gè)整數(shù)數(shù)組 nums ，找出一個(gè)序列中乘積最大的連續(xù)子序列（該序列至少包含一個(gè)數(shù)）元咙。

示例 :

輸入: [-2,0,-1]
輸出: 0
解釋: 結(jié)果不能為 2, 因?yàn)?[-2,-1] 不是子數(shù)組梯影。

解題思路

遍歷數(shù)組時(shí)計(jì)算當(dāng)前最大值，不斷更新
令imax為當(dāng)前最大值庶香，則當(dāng)前最大值為 imax = max(imax * nums[i], nums[i])
由于存在負(fù)數(shù)甲棍，那么會導(dǎo)致最大的變最小的，最小的變最大的脉课。因此還需要維護(hù)當(dāng)前最小值imin救军，imin = min(imin * nums[i], nums[i])
當(dāng)負(fù)數(shù)出現(xiàn)時(shí)則imax與imin進(jìn)行交換再進(jìn)行下一步計(jì)算

乘積最大子序列

    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE, imax = 1, imin = 1;
        for(int i=0; i<nums.length; i++){
            if(nums[i] < 0){ 
              int tmp = imax;
              imax = imin;
              imin = tmp;
            }
            imax = Math.max(imax*nums[i], nums[i]);
            imin = Math.min(imin*nums[i], nums[i]);
            
            max = Math.max(max, imax);
        }
        return max;
    }

時(shí)間復(fù)雜度：

O(n)

Attention

為了提高文章質(zhì)量，防止冗長乏味

下一部分算法題

本片文章篇幅總結(jié)越長倘零。我一直覺得唱遭，一片過長的文章，就像一堂超長的會議/課堂呈驶，體驗(yàn)很不好拷泽，所以我打算再開一篇文章
在后續(xù)文章中，我將繼續(xù)針對鏈表 棧 隊(duì)列 堆 動態(tài)規(guī)劃 矩陣 位運(yùn)算 等近百種袖瞻，面試高頻算法題司致，及其圖文解析 + 教學(xué)視頻 + 范例代碼，進(jìn)行深入剖析有興趣可以繼續(xù)關(guān)注 _yuanhao 的編程世界
不求快聋迎，只求優(yōu)質(zhì)脂矫，每篇文章將以 2 ～ 3 天的周期進(jìn)行更新，力求保持高質(zhì)量輸出

歡迎關(guān)注_yuanhao的簡書拄轻！

請點(diǎn)贊颅围！因?yàn)槟愕墓膭?lì)是我寫作的最大動力！

學(xué)Android

為了方便大家跟進(jìn)學(xué)習(xí)恨搓，我在 GitHub 建立了一個(gè)倉庫

倉庫地址：超級干貨院促！精心歸納視頻、歸類斧抱、總結(jié)常拓，各位路過的老鐵支持一下！給個(gè) Star 辉浦！

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末墩邀，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子盏浙，更是在濱河造成了極大的恐慌，老刑警劉巖荔茬，帶你破解...
沈念sama閱讀 207,113評論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件废膘，死亡現(xiàn)場離奇詭異，居然都是意外死亡慕蔚，警方通過查閱死者的電腦和手機(jī)丐黄，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,644評論 2贊 381
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來孔飒，“玉大人灌闺，你說我怎么就攤上這事』得椋” “怎么了桂对？”我有些...
開封第一講書人閱讀 153,340評論 0贊 344
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長鸠匀。經(jīng)常有香客問我蕉斜，道長，這世上最難降的妖魔是什么缀棍？我笑而不...
開封第一講書人閱讀 55,449評論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任宅此，我火速辦了婚禮，結(jié)果婚禮上爬范，老公的妹妹穿的比我還像新娘父腕。我一直安慰自己，他們只是感情好青瀑，可當(dāng)我...
茶點(diǎn)故事閱讀 64,445評論 5贊 374
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布璧亮。她就那樣靜靜地躺著萧诫，像睡著了一般。火紅的嫁衣襯著肌膚如雪杜顺。梳的紋絲不亂的頭發(fā)上财搁，一...
開封第一講書人閱讀 49,166評論 1贊 284
城市分裂傳說
那天，我揣著相機(jī)與錄音躬络，去河邊找鬼尖奔。笑死，一個(gè)胖子當(dāng)著我的面吹牛穷当，可吹牛的內(nèi)容都是我干的提茁。我是一名探鬼主播，決...
沈念sama閱讀 38,442評論 3贊 401
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼馁菜，長吁一口氣：“原來是場噩夢啊……” “哼茴扁！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起汪疮，我...
開封第一講書人閱讀 37,105評論 0贊 261
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤峭火，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后智嚷，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體卖丸，經(jīng)...
沈念sama閱讀 43,601評論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,066評論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年盏道，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了稍浆。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,161評論 1贊 334
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡猜嘱，死狀恐怖衅枫，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情朗伶，我是刑警寧澤弦撩，帶...
沈念sama閱讀 33,792評論 4贊 323
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站论皆，受9級特大地震影響孤钦，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜纯丸，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,351評論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一偏形、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧觉鼻，春花似錦俊扭、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,352評論 0贊 19
一樁弒父案萨惑，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽捐康。三九已至，卻和暖如春庸蔼，著一層夾襖步出監(jiān)牢的瞬間解总，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 31,584評論 1贊 261
情欲美人皮
我被黑心中介騙來泰國打工姐仅，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留花枫，地道東北人。一個(gè)月前我還...
沈念sama閱讀 45,618評論 2贊 355
代替公主和親
正文我出身青樓掏膏，卻偏偏與公主長得像劳翰，于是被迫代替她去往敵國和親。傳聞我的和親對象是個(gè)殘疾皇子馒疹，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,916評論 2贊 344

?? 面試必備：高頻算法題匯總「圖文解析 + 教學(xué)視頻 + 范例代碼」之 字符串處理+動態(tài)規(guī)劃 合集差购！

Attention

開始之前诚纸，我們先看下會有哪些重點(diǎn)案例：

為了方便大家跟進(jìn)學(xué)習(xí)，我在 GitHub 建立了一個(gè)倉庫

字符串處理

括號生成

解題思路

視頻

復(fù)雜度

Excel表列標(biāo)題

解題思路

翻轉(zhuǎn)游戲

解題思路

拓展：

翻轉(zhuǎn)字符串中的單詞

解題思路

字符串轉(zhuǎn)換整數(shù) (atoi)

解題思路

視頻

最長公共前綴

解題思路

視頻

時(shí)間復(fù)雜度：

回文數(shù)

解題思路

視頻

動態(tài)規(guī)劃

單詞拆分

解題思路

復(fù)雜度分析

爬樓梯

解題思路

打家劫舍

解題思路

復(fù)雜度分析

編輯距離

解題思路

復(fù)雜度分析

乘積最大子序列

解題思路

時(shí)間復(fù)雜度：

Attention

下一部分算法題

相關(guān)文章

歡迎關(guān)注_yuanhao的簡書拄轻！

請點(diǎn)贊颅围！因?yàn)槟愕墓膭?lì)是我寫作的最大動力！

為了方便大家跟進(jìn)學(xué)習(xí)恨搓，我在 GitHub 建立了一個(gè)倉庫

推薦閱讀更多精彩內(nèi)容

?? 面試必備：高頻算法題匯總「圖文解析 + 教學(xué)視頻 + 范例代碼」之字符串處理+動態(tài)規(guī)劃合集差购！