2019.12-2020.02后端面試材料分享队魏，算法篇公般。

拿到了字節(jié)offer，走完了Hello單車和達(dá)達(dá)的面試流程（沒給offer）胡桨，螞蟻的前三輪（接了字節(jié)Offer官帘，放棄后續(xù)流程）。

按照九章歸納的算法題出現(xiàn)的頻率準(zhǔn)備的：

紅(高頻)到灰(低頻)

但后來發(fā)現(xiàn)九章主要是針對硅谷系的公司昧谊，算法要求普遍比較高刽虹。國內(nèi)的即使是大公司，難度也低很多呢诬，把經(jīng)典的數(shù)據(jù)結(jié)構(gòu)涌哲、經(jīng)典的算法搞清楚胖缤，10-20分鐘內(nèi)能搞定leetcode上簡單難度的題，即可阀圾。

掌握套路是很重要的哪廓，因?yàn)閷こ處煹囊笫鞘煜ぁ皯?yīng)用”，而不是“發(fā)明”初烘，套路沒get情況下涡真，硬啃會(huì)浪費(fèi)大量時(shí)間。我的方式是肾筐，最開始把leetcod上簡單級(jí)別的題目哆料，全看一遍，只看不寫吗铐，沒想法的东亦、思路不優(yōu)化的，說明對背后的套路尚不熟悉抓歼，應(yīng)該先熟悉一遍讥此，然后再上手寫代碼，提高算法落低和bug-free能力谣妻。推薦多看看別人的總結(jié)萄喳，比如：

• 二分法套路
• 動(dòng)態(tài)規(guī)范套路
• 回溯算法套路

以下清單是當(dāng)時(shí)看完后沒有立刻來思路的題目(來自leetcode)。思路的掌握涉及記憶蹋半，我希望根據(jù)遺忘曲線來安排學(xué)習(xí)進(jìn)度和復(fù)習(xí)計(jì)劃他巨。于是便有了這個(gè)類anki的小程序：一進(jìn)制。默認(rèn)隱藏答案减江，思考后再點(diǎn)開對照染突；根據(jù)你反饋的難度，安排復(fù)習(xí)時(shí)間辈灼。

“一進(jìn)制”份企，算法篇

-問題1: 最長公共前綴

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

如果不存在公共前綴巡莹，返回空字符串 ""司志。

示例 1:
輸入:["flower","flow","flight"] 輸出: "fl"
示例 2:
輸入:["dog","racecar","car"] 輸出: "" 解釋: 輸入不存在公共前綴。
說明:

所有輸入只包含小寫字母 a-z 降宅。

-tags: 字符串,算法

-解答:

方法一：水平掃描

首先骂远，我們將描述一種查找一組字符串的最長公共前綴 LCP(S_1 ... S_n) 的簡單方法。
我們將會(huì)用到這樣的結(jié)論：

LCP(S_1 ... S_n) = LCP(LCP(LCP(S_1, S_2),S_3), ... S_n)

為了運(yùn)用這種思想腰根，算法要依次遍歷字符串 [S_1 ... S_n]激才，當(dāng)遍歷到第i個(gè)字符串的時(shí)候，找到最長公共前綴 LCP(S_1 ... S_i)。當(dāng)它是一個(gè)空串的時(shí)候瘸恼，算法就結(jié)束了劣挫。 否則，在執(zhí)行了n次遍歷之后钞脂，算法就會(huì)返回最終答案揣云。

public String longestCommonPrefix(String[] strs) {
   if (strs.length == 0) return "";
   String prefix = strs[0];
   for (int i = 1; i < strs.length; i++)
       while (strs[i].indexOf(prefix) != 0) {
           prefix = prefix.substring(0, prefix.length() - 1);
           if (prefix.isEmpty()) return "";
       }        
   return prefix;
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(S)，S 是所有字符串中字符數(shù)量的總和冰啃。

• 最壞的情況下邓夕，n個(gè)字符串都是相同的。算法會(huì)將 S1 與其他字符串 [S_2 .._n] 都做一次比較阎毅。這樣就會(huì)進(jìn)行 S次字符比較焚刚，其中 S 是輸入數(shù)據(jù)中所有字符數(shù)量。

• 空間復(fù)雜度：O(1)扇调，我們只需要使用常數(shù)級(jí)別的額外空間矿咕。

算法二：水平掃描2

想象數(shù)組的末尾有一個(gè)非常短的字符串，使用上述方法依舊會(huì)進(jìn)行 `S? 次比較狼钮。優(yōu)化這類情況的一種方法碳柱，我們從前往后枚舉字符串的每一列，先比較每個(gè)字符串相同列上的字符（即不同字符串相同下標(biāo)的字符）然后再比較下一列熬芜。

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

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(S)莲镣，S 是所有字符串中字符數(shù)量的總和。

  • 最壞情況下涎拉，輸入數(shù)據(jù)為 n個(gè)長度為 m 的相同字符串瑞侮，算法會(huì)進(jìn)行 S = mn 次比較」呐。可以看到最壞情況下半火，本算法的效率與算法一相同，但是最好的情況下季俩，算法只需要進(jìn)行 nminLen 次比較钮糖，其中 minLen 是數(shù)組中最短字符串的長度。

• 空間復(fù)雜度：O(1)酌住，我們只需要使用常數(shù)級(jí)別的額外空間店归。

算法三：分治

這個(gè)算法的思路來自于LCP操作的結(jié)合律。 我們可以發(fā)現(xiàn)：
LCP(S_1 ... S_n) = LCP(LCP(S_1 ... S_k), LCP (S_{k+1} ... S_n))
赂韵，其中 LCP(S_1 ... S_n) 是字符串 [S_1 ... S_n] 的最長公共前綴娱节，1 < k < n挠蛉。

為了應(yīng)用上述的結(jié)論祭示，我們使用分治的技巧，將原問題分成兩個(gè)子問題 LCP(S_i, S_{mid}) 與 LCP(S_{mid+1}, S_j) ，其中 mid = (i + j) / 2质涛。 我們用子問題的解 lcpLeft 與 lcpRight 構(gòu)造原問題的解 LCP(S_i ... S_j)稠歉。 從頭到尾挨個(gè)比較 lcpLeft 與 lcpRight 中的字符，直到不能再匹配為止汇陆。 計(jì)算所得的 lcpLeft 與 lcpRight 最長公共前綴就是原問題的解怒炸。

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";    
        return longestCommonPrefix(strs, 0 , strs.length - 1);
}

private String longestCommonPrefix(String[] strs, int l, int r) {
    if (l == r) {
        return strs[l];
    }
    else {
        int mid = (l + r)/2;
        String lcpLeft =   longestCommonPrefix(strs, l , mid);
        String lcpRight =  longestCommonPrefix(strs, mid + 1,r);
        return commonPrefix(lcpLeft, lcpRight);
   }
}

String commonPrefix(String left,String right) {
    int min = Math.min(left.length(), right.length());       
    for (int i = 0; i < min; i++) {
        if ( left.charAt(i) != right.charAt(i) )
            return left.substring(0, i);
    }
    return left.substring(0, min);
}

復(fù)雜度分析

最壞情況下，我們有 n 個(gè)長度為 m的相同字符串毡代。

• 時(shí)間復(fù)雜度：O(S)阅羹，S 是所有字符串中字符數(shù)量的總和，S=mn*教寂。最好情況下捏鱼，算法會(huì)進(jìn)行 次比較，其中 是數(shù)組中最短字符串的長度酪耕。

• 空間復(fù)雜度：O(m * log(n))
  內(nèi)存開支主要是遞歸過程中使用的椀及穑空間所消耗的。 一共會(huì)進(jìn)行 log(n) 次遞歸迂烁，每次需要 m 的空間存儲(chǔ)返回結(jié)果看尼，所以空間復(fù)雜度為 O(m * log(n))。

方法四：二分查找法

這個(gè)想法是應(yīng)用二分查找法找到所有字符串的公共前綴的最大長度 L盟步。 算法的查找區(qū)間是 (0 ... minLen)藏斩，其中 minLen 是輸入數(shù)據(jù)中最短的字符串的長度，同時(shí)也是答案的最長可能長度址芯。 每一次將查找區(qū)間一分為二灾茁，然后丟棄一定不包含最終答案的那一個(gè)。算法進(jìn)行的過程中一共會(huì)出現(xiàn)兩種可能情況：

• S[1...mid] 不是所有串的公共前綴谷炸。 這表明對于所有的 j > i S[1..j] 也不是公共前綴北专，于是我們就可以丟棄后半個(gè)查找區(qū)間啦粹。

• S[1...mid] 是所有串的公共前綴恰响。 這表示對于所有的 i < j S[1..i] 都是可行的公共前綴，因?yàn)槲覀円易铋L的公共前綴关筒，所以我們可以把前半個(gè)查找區(qū)間丟棄描孟。

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0)
        return "";
    int minLen = Integer.MAX_VALUE;
    for (String str : strs)
        minLen = Math.min(minLen, str.length());
    int low = 1;
    int high = minLen;
    while (low <= high) {
        int middle = (low + high) / 2;
        if (isCommonPrefix(strs, middle))
            low = middle + 1;
        else
            high = middle - 1;
    }
    return strs[0].substring(0, (low + high) / 2);
}

private boolean isCommonPrefix(String[] strs, int len){
    String str1 = strs[0].substring(0,len);
    for (int i = 1; i < strs.length; i++)
        if (!strs[i].startsWith(str1))
            return false;
    return true;
}

復(fù)雜度分析
最壞情況下驶睦，我們有 n 個(gè)長度為 m 的相同字符串。

• 時(shí)間復(fù)雜度：O(S * log(n))匿醒，其中 S所有字符串中字符數(shù)量的總和场航。

算法一共會(huì)進(jìn)行 log(n) 次迭代，每次一都會(huì)進(jìn)行 S = mn* 次比較廉羔，所以總時(shí)間復(fù)雜度為 O(S * log(n))溉痢。

• 空間復(fù)雜度：`O(1)，我們只需要使用常數(shù)級(jí)別的額外空間。

-問題2: x 的平方根

實(shí)現(xiàn) int sqrt(int x) 函數(shù)孩饼。

計(jì)算并返回 x 的平方根髓削，其中 x是非負(fù)整數(shù)。

由于返回類型是整數(shù)镀娶，結(jié)果只保留整數(shù)的部分立膛，小數(shù)部分將被舍去。

示例 1:
輸入: 4 輸出: 2
示例 2:
輸入: 8 輸出: 2 說明: 8 的平方根是 2.82842..., 由于返回類型是整數(shù)梯码，小數(shù)部分將被舍去宝泵。

-tags: 二分查找,算法,數(shù)學(xué)

-解答:

方法一：二分法

使用二分法搜索平方根的思想很簡單，高了就往低了猜轩娶，低了就往高了猜鲁猩，范圍越來越小。因此罢坝，使用二分法猜算術(shù)平方根就很自然廓握。

需要觀察到的關(guān)鍵點(diǎn)是：一個(gè)數(shù)的平方根不會(huì)超過它的一半，因此一半可當(dāng)做右值嘁酿。

class Solution:
    def mySqrt(self, x: int) -> int:
        # 為了照顧到 0 把左邊界設(shè)置為 0
        left = 0
        # 為了照顧到 1 把右邊界設(shè)置為 x // 2 + 1
        right = x // 2 + 1
        while left < right:
            # 注意：這里一定取右中位數(shù)隙券，如果取左中位數(shù)，代碼可能會(huì)進(jìn)入死循環(huán)
            # mid = left + (right - left + 1) // 2
            mid = (left + right + 1) >> 1
            square = mid * mid

            if square > x:
                right = mid - 1
            else:
                left = mid
        # 因?yàn)橐欢ù嬖谀炙荆虼藷o需后處理
        return left

方法二：牛頓法

使用牛頓法可以得到一個(gè)正實(shí)數(shù)的算術(shù)平方根娱仔，因?yàn)轭}目中說“結(jié)果只保留整數(shù)部分”，因此游桩，我們把使用牛頓法得到的浮點(diǎn)數(shù)轉(zhuǎn)換為整數(shù)即可牲迫。

這里給出牛頓法的思想：

在迭代過程中，以直線代替曲線借卧，用一階泰勒展式（即在當(dāng)前點(diǎn)的切線）代替原曲線盹憎，求直線與 x 軸的交點(diǎn)，重復(fù)這個(gè)過程直到收斂铐刘。

class Solution:

    def mySqrt(self, x):
        if x < 0:
            raise Exception('不能輸入負(fù)數(shù)')
        if x == 0:
            return 0
        # 起始的時(shí)候在 1 陪每，這可以比較隨意設(shè)置
        cur = 1
        while True:
            pre = cur
            cur = (cur + x / cur) / 2
            if abs(cur - pre) < 1e-6:
                return int(cur)

-問題3: 二叉樹的層次遍歷 II

給定一個(gè)二叉樹，返回其節(jié)點(diǎn)值自底向上的層次遍歷镰吵。 （即按從葉子節(jié)點(diǎn)所在層到根節(jié)點(diǎn)所在的層檩禾，逐層從左向右遍歷）

例如：
給定二叉樹 [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
返回其自底向上的層次遍歷為：
[ [15,7], [9,20], [3] ]

-tags: 廣度優(yōu)先搜索,算法,樹

-解答:
先從頂部遍歷

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        levelorder(root,0,res);
        return vector<vector<int>>(res.rbegin(),res.rend());
    }
        
    void levelorder(TreeNode* node, int level, vector<vector<int>>& res) 
    {
        if(!node) return ;
        if(res.size()==level) res.push_back({});
        res[level].push_back(node->val);
        if(node->left) levelorder(node->left,level+1, res);
        if(node->right) levelorder(node->right,level+1,res);
    }
};

-問題4: 買賣股票的最佳時(shí)機(jī)

給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格疤祭。

如果你最多只允許完成一筆交易（即買入和賣出一支股票）盼产，設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。

注意你不能在買入股票前賣出股票勺馆。

示例 1:
輸入: [7,1,5,3,6,4] 輸出: 5 解釋:在第 2 天（股票價(jià)格 = 1）的時(shí)候買入戏售，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出啦辐，最大利潤 = 6-1 = 5 。 注意利潤不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格蜈项。
示例 2:
輸入: [7,6,4,3,1] 輸出: 0 解釋:在這種情況下, 沒有交易完成, 所以最大利潤為 0。

-tags: 數(shù)組,動(dòng)態(tài)規(guī)劃,算法

-解答:

解決方案

我們需要找出給定數(shù)組中兩個(gè)數(shù)字之間的最大差值（即续挟，最大利潤）紧卒。此外，第二個(gè)數(shù)字（賣出價(jià)格）必須大于第一個(gè)數(shù)字（買入價(jià)格）诗祸。

形式上跑芳，對于每組 和 （其中 ）我們需要找出 。

方法一：暴力法

public class Solution {
    public int maxProfit(int prices[]) {
        int maxprofit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxprofit)
                    maxprofit = profit;
            }
        }
        return maxprofit;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：直颅。循環(huán)運(yùn)行 次博个。
• 空間復(fù)雜度：。只使用了兩個(gè)變量 —— 和 功偿。

方法二：一次遍歷

算法

假設(shè)給定的數(shù)組為：

[7, 1, 5, 3, 6, 4]

如果我們在圖表上繪制給定數(shù)組中的數(shù)字盆佣，我們將會(huì)得到：

Profit Graph

{:width="400px"}
{:align="center"}

使我們感興趣的點(diǎn)是上圖中的峰和谷。我們需要找到最小的谷之后的最大的峰械荷。
我們可以維持兩個(gè)變量——minprice 和 maxprofit共耍，它們分別對應(yīng)迄今為止所得到的最小的谷值和最大的利潤（賣出價(jià)格與最低價(jià)格之間的最大差值）。

public class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice)
                minprice = prices[i];
            else if (prices[i] - minprice > maxprofit)
                maxprofit = prices[i] - minprice;
        }
        return maxprofit;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：吨瞎，只需要遍歷一次痹兜。
• 空間復(fù)雜度：，只使用了兩個(gè)變量颤诀。

-問題5: 買賣股票的最佳時(shí)機(jī) II

給定一個(gè)數(shù)組字旭，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。

設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤崖叫。你可以盡可能地完成更多的交易（多次買賣一支股票）遗淳。

注意：你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1:
輸入: [7,1,5,3,6,4] 輸出: 7 解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入心傀，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 洲脂。 隨后，在第 4 天（股票價(jià)格 = 3）的時(shí)候買入剧包，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 恐锦。
示例 2:
輸入: [1,2,3,4,5] 輸出: 4 解釋: 在第 1 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 疆液。 注意你不能在第 1 天和第 2 天接連購買股票一铅，之后再將它們賣出。 因?yàn)檫@樣屬于同時(shí)參與了多筆交易堕油，你必須在再次購買前出售掉之前的股票潘飘。
示例 3:
輸入: [7,6,4,3,1] 輸出: 0 解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0肮之。

-tags: 數(shù)組,算法,貪心算法

-解答:

方法一：暴力法

這種情況下，我們只需要計(jì)算與所有可能的交易組合相對應(yīng)的利潤卜录，并找出它們中的最大利潤戈擒。

class Solution {
    public int maxProfit(int[] prices) {
        return calculate(prices, 0);
    }

    public int calculate(int prices[], int s) {
        if (s >= prices.length)
            return 0;
        int max = 0;
        for (int start = s; start < prices.length; start++) {
            int maxprofit = 0;
            for (int i = start + 1; i < prices.length; i++) {
                if (prices[start] < prices[i]) {
                    int profit = calculate(prices, i + 1) + prices[i] - prices[start];
                    if (profit > maxprofit)
                        maxprofit = profit;
                }
            }
            if (maxprofit > max)
                max = maxprofit;
        }
        return max;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n^n)，調(diào)用遞歸函數(shù) n^n次艰毒。
• 空間復(fù)雜度：O(n)筐高，遞歸的深度為 n。

方法二：峰谷法

假設(shè)給定的數(shù)組為：

[7, 1, 5, 3, 6, 4]丑瞧，想象成高低不平的群山柑土，那么我們的興趣點(diǎn)是連續(xù)的峰和谷。

用數(shù)學(xué)語言描述為：

Total Profit= sum_{i}(height(peak_i)-height(valley_i))

關(guān)鍵是我們需要考慮到緊跟谷的每一個(gè)峰值以最大化利潤绊汹。如果我們試圖跳過其中一個(gè)峰值來獲取更多利潤稽屏，那么我們最終將失去其中一筆交易中獲得的利潤，從而導(dǎo)致總利潤的降低西乖。

class Solution {
    public int maxProfit(int[] prices) {
        int i = 0;
        int valley = prices[0];
        int peak = prices[0];
        int maxprofit = 0;
        while (i < prices.length - 1) {
            while (i < prices.length - 1 && prices[i] >= prices[i + 1])
                i++;
            valley = prices[i];
            while (i < prices.length - 1 && prices[i] <= prices[i + 1])
                i++;
            peak = prices[i];
            maxprofit += peak - valley;
        }
        return maxprofit;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)狐榔。遍歷一次。

• 空間復(fù)雜度：O(1)获雕。需要常量的空間荒叼。

方法三：簡單的一次遍歷

該解決方案遵循 方法二 的本身使用的邏輯，但有一些輕微的變化典鸡。在這種情況下被廓，我們可以簡單地繼續(xù)在斜坡上爬升并持續(xù)增加從連續(xù)交易中獲得的利潤，而不是在谷之后尋找每個(gè)峰值萝玷。最后嫁乘，我們將有效地使用峰值和谷值，但我們不需要跟蹤峰值和谷值對應(yīng)的成本以及最大利潤球碉，但我們可以直接繼續(xù)增加加數(shù)組的連續(xù)數(shù)字之間的差值蜓斧，如果第二個(gè)數(shù)字大于第一個(gè)數(shù)字，我們獲得的總和將是最大利潤睁冬。這種方法將簡化解決方案挎春。
這個(gè)例子可以更清楚地展現(xiàn)上述情況：

[1, 7, 2, 3, 6, 7, 6, 7]

class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1])
                maxprofit += prices[i] - prices[i - 1];
        }
        return maxprofit;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)$，遍歷一次豆拨。
• 空間復(fù)雜度：O(1)直奋，需要常量的空間。

-問題6: 只出現(xiàn)一次的數(shù)字

給定一個(gè)非空整數(shù)數(shù)組施禾，除了某個(gè)元素只出現(xiàn)一次以外脚线，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素弥搞。

說明：

你的算法應(yīng)該具有線性時(shí)間復(fù)雜度邮绿。 你可以不使用額外空間來實(shí)現(xiàn)嗎渠旁？

示例 1:
輸入: [2,2,1] 輸出: 1
示例 2:
輸入: [4,1,2,1,2] 輸出: 4

-tags: 算法,位運(yùn)算,哈希表

-解答:

方法 1：列表操作

1. 遍歷 nums 中的每一個(gè)元素
2. 如果某個(gè) nums 中的數(shù)字是新出現(xiàn)的，則將它添加到列表中
3. 如果某個(gè)數(shù)字已經(jīng)在列表中船逮，刪除它

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        no_duplicate_list = []
        for i in nums:
            if i not in no_duplicate_list:
                no_duplicate_list.append(i)
            else:
                no_duplicate_list.remove(i)
        return no_duplicate_list.pop()

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n^2) 顾腊。遍歷 nums花費(fèi) O(n) 的時(shí)間。還要在列表中遍歷判斷是否存在這個(gè)數(shù)字挖胃，花費(fèi) O(n) 的時(shí)間杂靶，所以總循環(huán)時(shí)間為 O(n^2)。
• 空間復(fù)雜度：O(n) 冠骄。我們需要一個(gè)大小為n的列表保存所有元素。

方法 2：哈希表

我們用哈希表避免每次查找元素是否存在需要的 O(n) 時(shí)間加袋。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        hash_table = {}
        for i in nums:
            try:
                hash_table.pop(i)
            except:
                hash_table[i] = 1
        return hash_table.popitem()[0]

方法 3：數(shù)學(xué)

觀察得到以下等式：
2 * (a + b + c) - (a + a + b + b + c) = c

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return 2 * sum(set(nums)) - sum(nums)

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n + n) = O(n) 凛辣。sum 會(huì)調(diào)用 next 將 nums 中的元素遍歷一遍。我們可以把上述代碼看成 sum(list(i, for i in nums)) 职烧，這意味著時(shí)間復(fù)雜度為 O(n) 扁誓。
• 空間復(fù)雜度： O(n + n) = O(n) 。 set 需要的空間跟 nums 中元素個(gè)數(shù)相等蚀之。

方法 4：位操作

• 如果我們對 0 和二進(jìn)制位做 XOR 運(yùn)算蝗敢，得到的仍然是這個(gè)二進(jìn)制位
• 如果我們對相同的二進(jìn)制位做 XOR 運(yùn)算，返回的結(jié)果是 0
• XOR 滿足交換律和結(jié)合律： a xor a xor b = (a xor a) xor b = 0 xor b = b

所以我們只需要將所有的數(shù)進(jìn)行 XOR 操作足删，得到那個(gè)唯一的數(shù)字寿谴。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        a = 0
        for i in nums:
            a ^= i
        return a

-問題7: 只出現(xiàn)一次的數(shù)字 II

給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外失受，其余每個(gè)元素均出現(xiàn)了三次讶泰。找出那個(gè)只出現(xiàn)了一次的元素。

說明：

你的算法應(yīng)該具有線性時(shí)間復(fù)雜度拂到。 你可以不使用額外空間來實(shí)現(xiàn)嗎痪署？

示例 1:
輸入: [2,2,3,2] 輸出: 3
示例 2:
輸入: [0,1,0,1,0,1,99] 輸出: 99

-tags: 算法,位運(yùn)算

-解答:

解題思路：

• 二進(jìn)制下不考慮進(jìn)位的加法：異或運(yùn)算的含義是二進(jìn)制下不考慮進(jìn)位的加法，即：0 xor 0=0+0=0, 0 xor 1=0+1=1, 1 xor 0=1+0=1, 1 xor 1=1+1=0（不進(jìn)位）兄旬。
• 三進(jìn)制下不考慮進(jìn)位的加法：通過定義某種運(yùn)算 #狼犯，使得 0 # 1 = 1，1 # 1 = 2领铐，2 # 1 = 0悯森。在此運(yùn)算規(guī)則下，出現(xiàn)了 3 次的數(shù)字的二進(jìn)制所有位全部抵消為 0绪撵，而留下只出現(xiàn) 1 次的數(shù)字二進(jìn)制對應(yīng)位為 1呐馆。因此，在此運(yùn)算規(guī)則下將整個(gè) arr 中數(shù)字遍歷加和莲兢，留下來的結(jié)果則為只出現(xiàn) 1 次的數(shù)字汹来。

class Solution:

    def singleNumber(self, nums: [int]) -> int:

        ones, twos, threes = 0, 0, 0

        for num in nums:

            twos |= ones & num # 二進(jìn)制某位出現(xiàn)1次時(shí)twos = 0续膳，出現(xiàn)2, 3次時(shí)twos = 1；

            ones ^= num  # 二進(jìn)制某位出現(xiàn)2次時(shí)ones = 0收班，出現(xiàn)1, 3次時(shí)ones = 1坟岔；

            threes = ones & twos # 二進(jìn)制某位出現(xiàn)3次時(shí)（即twos = ones = 1時(shí)）three = 1，其余即出現(xiàn)1, 2次時(shí)three = 0摔桦；

            ones &= ~threes # 將二進(jìn)制下出現(xiàn)3次的位置零社付，實(shí)現(xiàn)`三進(jìn)制下不考慮進(jìn)位的加法`；

            twos &= ~threes

        return ones

代碼分析：

• ones ^= num：記錄至目前元素num邻耕，二進(jìn)制某位出現(xiàn) 1 次（當(dāng)某位出現(xiàn) 3 次時(shí)有 ones = 1 鸥咖，與 twos = 1 共同表示“出現(xiàn) 3 次”）；
• twos |= ones & num：記錄至目前元素num兄世，二進(jìn)制某位出現(xiàn)2 次 （當(dāng)某位出現(xiàn) 2 次時(shí)啼辣，twos = 1 且 ones = 0 ）；
• threes = ones & twos：記錄至目前元素num御滩，二進(jìn)制某位出現(xiàn) 3 次（即當(dāng) ones 和 twos 對應(yīng)位同時(shí)為 1 時(shí) three = 1 ）鸥拧。
• one &= ~threes, two &= ~threes：將 ones, twos 中出現(xiàn)了 3 次的對應(yīng)位清零，實(shí)現(xiàn) “不考慮進(jìn)位的三進(jìn)制加法” 削解。

復(fù)雜度分析：

• 時(shí)間復(fù)雜度 O(N)：遍歷一遍 nums 需要線性時(shí)間復(fù)雜度富弦；
• 空間復(fù)雜度 O(1)：使用常數(shù)額外空間。

進(jìn)一步簡化：

• 以上過程本質(zhì)上是通過構(gòu)建 3 個(gè)變量的狀態(tài)轉(zhuǎn)換表來表示對應(yīng)位的出現(xiàn)次數(shù)：使所有數(shù)字“相加”后出現(xiàn) 3N+1 次的位 ones = 1氛驮，出現(xiàn) 3N腕柜，3N+2次的位為 ones = 0。由于 three 其實(shí)是 ones & twos 的結(jié)果矫废，因此我們可以舍棄 threes媳握，僅使用 ones 和 twos 來記錄出現(xiàn)次數(shù)。

class Solution:

    def singleNumber(self, nums: [int]) -> int:

        ones, twos = 0, 0

        for num in nums:

            ones = ones ^ num & ~twos

            twos = twos ^ num & ~ones

        return ones

代碼分析：

• ones = ones ^ num & ~twos：
  • 當(dāng) num = 1 時(shí)磷脯，只當(dāng) ones = twos = 0 時(shí)將 ones 置 1蛾找，代表出現(xiàn) 3N+1 次；其余置 0赵誓，根據(jù) twos 值分別代表出現(xiàn) 3N 次和 3N+2 次打毛；
  • 當(dāng) num = 0 時(shí)，ones 不變俩功；
• twos = twos ^ num & ~ones：
  • 當(dāng) num = 1 時(shí)幻枉，只當(dāng) ones = twos = 0 時(shí)將 twos 置 1，代表出現(xiàn) 3N+2 次诡蜓；其余置 0熬甫，根據(jù) ones 值分別代表出現(xiàn) 3N 次和 3N+1 次。
  • 當(dāng) num = 0 時(shí)蔓罚，twos 不變椿肩。

-問題8: 二叉搜索樹的最近公共祖先

給定一個(gè)二叉搜索樹, 找到該樹中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先瞻颂。

最近公共祖先的定義為：“對于有根樹 T 的兩個(gè)結(jié)點(diǎn) p、q郑象，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x贡这，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）厂榛「墙茫”

例如，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

輸出: 6

解釋:節(jié)點(diǎn) 2 和節(jié)點(diǎn) 8 的最近公共祖先是 6击奶。

示例 2:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4

輸出: 2

解釋:節(jié)點(diǎn) 2 和節(jié)點(diǎn) 4 的最近公共祖先是 2, 因?yàn)楦鶕?jù)定義最近公共祖先節(jié)點(diǎn)可以為節(jié)點(diǎn)本身辈双。

說明:

• 所有節(jié)點(diǎn)的值都是唯一的。
• p柜砾、q 為不同節(jié)點(diǎn)且均存在于給定的二叉搜索樹中湃望。

-tags: 算法,樹

-解答:

題解

我們來復(fù)習(xí)一下二叉搜索樹（BST）的性質(zhì)：

1. 節(jié)點(diǎn) N左子樹上的所有節(jié)點(diǎn)的值都小于等于節(jié)點(diǎn) N的值
2. 節(jié)點(diǎn) N右子樹上的所有節(jié)點(diǎn)的值都大于等于節(jié)點(diǎn) N 的值
3. 左子樹和右子樹也都是 BST

方法一 （遞歸）

節(jié)點(diǎn) p，q 的最近公共祖先（LCA）是距離這兩個(gè)節(jié)點(diǎn)最近的公共祖先節(jié)點(diǎn)局义。在這里 最近 考慮的是節(jié)點(diǎn)的深度喜爷。

算法

1. 從根節(jié)點(diǎn)開始遍歷樹
2. 如果節(jié)點(diǎn) p和節(jié)點(diǎn) q 都在右子樹上冗疮，那么以右孩子為根節(jié)點(diǎn)繼續(xù) 1 的操作
3. 如果節(jié)點(diǎn) p 和節(jié)點(diǎn) q 都在左子樹上萄唇，那么以左孩子為根節(jié)點(diǎn)繼續(xù) 1 的操作
4. 如果條件 2 和條件 3 都不成立，這就意味著我們已經(jīng)找到節(jié) p 和節(jié)點(diǎn) q 的 LCA 了

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        // Value of current node or parent node.
        int parentVal = root.val;

        // Value of p
        int pVal = p.val;

        // Value of q;
        int qVal = q.val;

        if (pVal > parentVal && qVal > parentVal) {
            // If both p and q are greater than parent
            return lowestCommonAncestor(root.right, p, q);
        } else if (pVal < parentVal && qVal < parentVal) {
            // If both p and q are lesser than parent
            return lowestCommonAncestor(root.left, p, q);
        } else {
            // We have found the split point, i.e. the LCA node.
            return root;
        }
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(N)，在最壞的情況下我們可能需要訪問 BST 中所有的節(jié)點(diǎn)。

• 空間復(fù)雜度：O(N)
  所需開辟的額外空間主要是遞歸棧產(chǎn)生的舆吮，而BST的高度為 N始赎。

方法二 （迭代）

這個(gè)方法跟方法一很接近。唯一的不同是移剪，我們用迭代的方式替代了遞歸來遍歷整棵樹。由于我們不需要回溯來找到 LCA 節(jié)點(diǎn)，所以我們是完全可以不利用椃尬＃或者是遞歸的。實(shí)際上這個(gè)問題本身就是可以迭代的没龙，我們只需要找到分割點(diǎn)就可以了铺厨。這個(gè)分割點(diǎn)就是能讓節(jié)點(diǎn) p和節(jié)點(diǎn) q 不能在同一顆子樹上的那個(gè)節(jié)點(diǎn)，或者是節(jié)點(diǎn) p 和節(jié)點(diǎn) q 中的一個(gè)硬纤，這種情況下其中一個(gè)節(jié)點(diǎn)是另一個(gè)節(jié)點(diǎn)的父親節(jié)點(diǎn)解滓。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        // Value of p
        int pVal = p.val;

        // Value of q;
        int qVal = q.val;

        // Start from the root node of the tree
        TreeNode node = root;

        // Traverse the tree
        while (node != null) {

            // Value of ancestor/parent node.
            int parentVal = node.val;

            if (pVal > parentVal && qVal > parentVal) {
                // If both p and q are greater than parent
                node = node.right;
            } else if (pVal < parentVal && qVal < parentVal) {
                // If both p and q are lesser than parent
                node = node.left;
            } else {
                // We have found the split point, i.e. the LCA node.
                return node;
            }
        }
        return null;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(N)，在最壞的情況下我們可能需要遍歷 BST 中所有的節(jié)點(diǎn)筝家。

• 空間復(fù)雜度：O(1)

-問題9: Nim 游戲

你和你的朋友洼裤，兩個(gè)人一起玩 Nim 游戲：桌子上有一堆石頭，每次你們輪流拿掉 1 - 3 塊石頭溪王。 拿掉最后一塊石頭的人就是獲勝者腮鞍。你作為先手值骇。

你們是聰明人，每一步都是最優(yōu)解缕减。 編寫一個(gè)函數(shù)雷客，來判斷你是否可以在給定石頭數(shù)量的情況下贏得游戲。

示例:
輸入: 4 輸出: false 解釋:如果堆中有 4 塊石頭桥狡，那么你永遠(yuǎn)不會(huì)贏得比賽搅裙； 因?yàn)闊o論你拿走 1 塊、2 塊 還是 3 塊石頭裹芝，最后一塊石頭總是會(huì)被你的朋友拿走部逮。

-tags: 算法,極小化極大,腦筋急轉(zhuǎn)彎

-解答:
如果堆中石頭的數(shù)量 n不能被 4整除，那么你總是可以贏得 Nim 游戲的勝利嫂易。

推理

讓我們考慮一些小例子兄朋。顯而易見的是，如果石頭堆中只有一塊怜械、兩塊颅和、或是三塊石頭，那么在你的回合缕允，你就可以把全部石子拿走峡扩，從而在游戲中取勝。而如果就像題目描述那樣障本，堆中恰好有四塊石頭教届，你就會(huì)失敗。因?yàn)樵谶@種情況下不管你取走多少石頭驾霜，總會(huì)為你的對手留下幾塊案训，使得他可以在游戲中打敗你。因此粪糙，要想獲勝强霎，在你的回合中，必須避免石頭堆中的石子數(shù)為 4 的情況蓉冈。

同樣地城舞，如果有五塊、六塊洒擦、或是七塊石頭椿争，你可以控制自己拿取的石頭數(shù)，總是恰好給你的對手留下四塊石頭熟嫩，使他輸?shù)暨@場比賽秦踪。但是如果石頭堆里有八塊石頭，你就不可避免地會(huì)輸?shù)簦驗(yàn)椴还苣銖囊欢咽^中挑出一塊椅邓、兩塊還是三塊柠逞，你的對手都可以選擇三塊、兩塊或一塊景馁，以確保在再一次輪到你的時(shí)候板壮，你會(huì)面對四塊石頭。

顯然合住，它以相同的模式不斷重復(fù) n=4,8,12,16...绰精，基本可以看出是 4 的倍數(shù)。

public boolean canWinNim(int n) {
    return (n % 4 != 0);
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(1)透葛，只進(jìn)行了一次檢查笨使。
• 空間復(fù)雜度：O(1)，沒有使用額外的空間僚害。

-問題10: 路徑總和 III

給定一個(gè)二叉樹硫椰，它的每個(gè)結(jié)點(diǎn)都存放著一個(gè)整數(shù)值。

找出路徑和等于給定數(shù)值的路徑總數(shù)萨蚕。

路徑不需要從根節(jié)點(diǎn)開始靶草，也不需要在葉子節(jié)點(diǎn)結(jié)束，但是路徑方向必須是向下的（只能從父節(jié)點(diǎn)到子節(jié)點(diǎn)）岳遥。

二叉樹不超過1000個(gè)節(jié)點(diǎn)奕翔，且節(jié)點(diǎn)數(shù)值范圍是 [-1000000,1000000] 的整數(shù)。

示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

返回 3寒随。和等于 8 的路徑有: 1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11

-tags: 樹,算法

-解答:
利用棧對二叉樹進(jìn)行遍歷糠悯，用一個(gè)額外的數(shù)組保存所有二叉樹路徑的節(jié)點(diǎn)和帮坚，判斷每個(gè)保存節(jié)點(diǎn)和的數(shù)組里有多少個(gè)和sum相等的數(shù)即可妻往。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        if not root:
            return 0
        
        stack = [(root,[root.val])]
        res = 0

        while stack:
            node,temp = stack.pop()
            res += temp.count(sum)
            temp += [0]
            if node.left:
                arr = [i+node.left.val for i in temp]
                stack.append((node.left,arr))
            
            if node.right:
                arr = [i+node.right.val for i in temp]
                stack.append((node.right,arr))
        
        return res

-問題11: 找到字符串中所有字母異位詞

給定一個(gè)字符串 s和一個(gè)非空字符串 p，找到 s中所有是 p的字母異位詞的子串试和，返回這些子串的起始索引讯泣。

字符串只包含小寫英文字母，并且字符串 s和 p的長度都不超過 20100阅悍。

說明：

• 字母異位詞指字母相同好渠，但排列不同的字符串。
• 不考慮答案輸出的順序节视。

示例 1:

輸入: s: "cbaebabacd" p: "abc" 輸出: [0, 6]

解釋: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母異位詞拳锚。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母異位詞。

示例 2:

輸入: s: "abab" p: "ab" 輸出: [0, 1, 2]

解釋: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母異位詞寻行。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母異位詞霍掺。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母異位詞。

-tags: 算法,哈希表

-解答:

滑動(dòng)窗口

思路

1、我們在字符串 S 中使用雙指針中的左右指針技巧杆烁，初始化 left = right = 0牙丽，把索引閉區(qū)間 [left, right] 稱為一個(gè)「窗口」。

2兔魂、我們先不斷地增加 right 指針擴(kuò)大窗口 [left, right]烤芦，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

3析校、此時(shí)构罗，我們停止增加 right，轉(zhuǎn)而不斷增加 left 指針縮小窗口 [left, right]智玻，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）绰播。同時(shí)，每次增加 left尚困，我們都要更新一輪結(jié)果蠢箩。

4、重復(fù)第 2 和第 3 步事甜，直到 right 到達(dá)字符串 S 的盡頭谬泌。

這個(gè)思路其實(shí)也不難，第 2 步相當(dāng)于在尋找一個(gè)「可行解」逻谦，然后第 3 步在優(yōu)化這個(gè)「可行解」掌实，最終找到最優(yōu)解。左右指針輪流前進(jìn)邦马，窗口大小增增減減贱鼻，窗口不斷向右滑動(dòng)。

那么滋将，如何判斷 window 即子串 s[left...right] 是否符合要求邻悬，是否包含 t 的所有字符呢？

可以用兩個(gè)哈希表當(dāng)作計(jì)數(shù)器解決随闽。用一個(gè)哈希表 needs 記錄字符串 t 中包含的字符及出現(xiàn)次數(shù)父丰，用另一個(gè)哈希表 window 記錄當(dāng)前「窗口」中包含的字符及出現(xiàn)的次數(shù)，如果 window 包含所有 needs 中的鍵掘宪，且這些鍵對應(yīng)的值都大于等于 needs 中的值蛾扇，那么就可以知道當(dāng)前「窗口」符合要求了，可以開始移動(dòng) left 指針了魏滚。

string s, t;
// 在 s 中尋找 t 的「最小覆蓋子串」
int left = 0, right = 0;
string res = s;

// 相當(dāng)于兩個(gè)計(jì)數(shù)器
unordered_map<char, int> window;
unordered_map<char, int> needs;
for (char c : t) needs[c]++;

// 記錄 window 中已經(jīng)有多少字符符合要求了
int match = 0; 

while (right < s.size()) {
    char c1 = s[right];
    if (needs.count(c1)) {
        window[c1]++; // 加入 window
        if (window[c1] == needs[c1])
            // 字符 c1 的出現(xiàn)次數(shù)符合要求了
            match++;
    }
    right++;

    // window 中的字符串已符合 needs 的要求了
    while (match == needs.size()) {
        // 更新結(jié)果 res
        res = minLen(res, window);
        char c2 = s[left];
        if (needs.count(c2)) {
            window[c2]--; // 移出 window
            if (window[c2] < needs[c2])
                // 字符 c2 出現(xiàn)次數(shù)不再符合要求
                match--;
        }
        left++;
    }
}
return res;

這個(gè)算法的時(shí)間復(fù)雜度是 O(M + N)镀首，M 和 N 分別是字符串 S 和 T 的長度。因?yàn)槲覀兿扔?for 循環(huán)遍歷了字符串 T 來初始化 needs鼠次，時(shí)間 O(N)更哄，之后的兩個(gè) while 循環(huán)最多執(zhí)行 2M 次靖秩，時(shí)間 O(M)。

讀者也許認(rèn)為嵌套的 while 循環(huán)復(fù)雜度應(yīng)該是平方級(jí)竖瘾，但是你這樣想沟突，while 執(zhí)行的次數(shù)就是雙指針 left 和 right 走的總路程，最多是 2M 嘛捕传。

具體應(yīng)用到這道題上：

vector<int> findAnagrams(string s, string t) {
    // 用數(shù)組記錄答案
    vector<int> res;
    int left = 0, right = 0;
    unordered_map<char, int> needs;
    unordered_map<char, int> window;
    for (char c : t) needs[c]++;
    int match = 0;
    
    while (right < s.size()) {
        char c1 = s[right];
        if (needs.count(c1)) {
            window[c1]++;
            if (window[c1] == needs[c1])
                match++;
        }
        right++;

        while (match == needs.size()) {
            // 如果 window 的大小合適
            // 就把起始索引 left 加入結(jié)果
            if (right - left == t.size()) {
                res.push_back(left);
            }
            char c2 = s[left];
            if (needs.count(c2)) {
                window[c2]--;
                if (window[c2] < needs[c2])
                    match--;
            }
            left++;
        }
    }
    return res;
}

-問題12: 找到所有數(shù)組中消失的數(shù)字

給定一個(gè)范圍在 1 ≤ a[i] ≤ n ( n = 數(shù)組大小 ) 的 整型數(shù)組惠拭，數(shù)組中的元素一些出現(xiàn)了兩次，另一些只出現(xiàn)一次庸论。

找到所有在 [1, n] 范圍之間沒有出現(xiàn)在數(shù)組中的數(shù)字职辅。

您能在不使用額外空間且時(shí)間復(fù)雜度為O(n)的情況下完成這個(gè)任務(wù)嗎? 你可以假定返回的數(shù)組不算在額外空間內(nèi)。

示例:
輸入: [4,3,2,7,8,2,3,1] 輸出: [5,6]

-tags: 算法,數(shù)組

-解答:
關(guān)鍵是用好條件： 1 ≤ a[i] ≤ n （n為數(shù)組長度） 聂示。

a[1]-1在[0,n-1]中域携。將a[i]放在位置a[i]-1是可行的。

遍歷元素時(shí)鱼喉，當(dāng) a[i] != i+1的秀鞭，就將其交換到正確的位置a[i]-1。

此時(shí)扛禽，當(dāng) a[i] == a[a[i]-1]時(shí)锋边，表示a[i]有重復(fù)。

遍歷完后编曼，再遍歷一次豆巨。所有 a[i] != i+1 的i+1就是結(jié)果。

i=0;
while(i < n){
    while(i < n 且 a[i] != i+1){
        if(a[i] == a[a[i]-1]){
            ++i;
            下一個(gè);
        }
        交換a[i],a[a[i]-1];
    }
}
i=0;
while(i < n){
    if(a[i] == a[a[i]-1]){
        i+1是結(jié)果;
    }
    ++i;
}

代碼:

    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> ans;
        int i=0;
        while(i < nums.size()){
            while(i < nums.size() && nums[i] != i+1){
                if(nums[i] == nums[nums[i]-1]){
                    i++;
                    continue;
                }
                swap(nums[i],nums[nums[i]-1]);
            }
            ++i;
        }
        i=0;
        while(i < nums.size()){
            if(nums[i] != i+1){
                ans.push_back(i+1);
            }        
            ++i;
        }
        
        return ans;
    }

-問題13: 最小移動(dòng)次數(shù)使數(shù)組元素相等

給定一個(gè)長度為 n 的非空整數(shù)數(shù)組掐场，找到讓數(shù)組所有元素相等的最小移動(dòng)次數(shù)往扔。每次移動(dòng)可以使 n - 1 個(gè)元素增加 1。

示例:
輸入: [1,2,3] 輸出: 3 解釋: 只需要3次移動(dòng)（注意每次移動(dòng)會(huì)增加兩個(gè)元素的值）： [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

-tags: 數(shù)學(xué),算法

-解答:

利用排序

算法

如果對數(shù)組進(jìn)行排序得到有序數(shù)列 a熊户，可以有效地簡化問題萍膛。類似于方法二，我們用 diff=max-min 更新數(shù)列敏弃。但不同的是卦羡，我們不需要每次都遍歷整個(gè)數(shù)組來得到最大和最小值噪馏，而是可以利用數(shù)組的有序性在 O(1) 時(shí)間內(nèi)找到更新后的最大值和最小值麦到。此外，我們也不需要真的更新數(shù)組的值欠肾。

為了便于理解瓶颠，下面逐步講解該算法。

首先刺桃，假設(shè)我們在每一步計(jì)算 diff 之后正在更新有序數(shù)組的元素粹淋。下面展示如何在不遍歷數(shù)組的情況下找到最大最小值。在第一步中，最后的元素即為最大值桃移，因此 diff=a[n-1]-a[0]屋匕。我們對除了最后一個(gè)元素以外所有元素增加 diff。

現(xiàn)在借杰，更新后的數(shù)組開頭元素 a'[0] 變成了 a[0]+diff=a[n-1]过吻。因此，a'[0] 等于上一步中最大的元素 a[n-1]蔗衡。由于數(shù)組排過序纤虽，直到 i-2 的元素都滿足 a[j]>=a[j-1]。因此绞惦，更新之后逼纸，a'[n-2] 即為最大元素。而 a[0] 依然是最小元素济蝉。

于是杰刽，在第二次更新時(shí)，diff=a[n-2]-a[0]王滤。更新后 a''[0] 會(huì)成為 a'[n-2]专缠，與上一次迭代類似。

然后淑仆，由于 a'[0] 和 a'[n-1] 相等涝婉，在第二次更新后，a''[0]=a''[n-1]=a'[n-2]蔗怠。于是墩弯，最大的元素為 a[n-3]。

于是寞射，我們可以繼續(xù)這樣渔工，在每一步用最大最小值差更新數(shù)組。

下面進(jìn)入第二步桥温。第一步中引矩，我們假設(shè)每一步會(huì)更新數(shù)組 a 中的元素。但事實(shí)上侵浸，我們不需要這么做旺韭。這是因?yàn)椋词故窃诟略刂筇途酰覀円怯浀?diff 差值也不變区端，因?yàn)?max 和 min 增加的數(shù)字相同。

于是澳腹，我們可以簡單的將數(shù)組排序一次织盼， moves=sum_{i=1}^{n-1} (a[i]-a[0])杨何。

public class Solution {
    public int minMoves(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            count += nums[i] - nums[0];
        }
        return count;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n log(n) )。 排序需要 的時(shí)間沥邻。

• 空間復(fù)雜度：O(1)危虱。不需要額外空間。

動(dòng)態(tài)規(guī)劃

算法

如果對數(shù)組進(jìn)行排序得到有序數(shù)列 a唐全，可以有效地簡化問題槽地。考慮有序數(shù)組 a芦瘾，我們不考慮整個(gè)問題捌蚊，而是將問題分解。假設(shè)近弟，**直到 i-1位置的元素都已經(jīng)相等缅糟，我們只需要考慮 i 位的元素，將差值 diff=a[i]-a[i-1] 加到總移動(dòng)次數(shù)上**祷愉，使得第i` 位也相等窗宦。

moves=moves+diff。

但當(dāng)我們想要繼續(xù)這一步時(shí)二鳄，a[i] 之后的元素也會(huì)被增加 diff赴涵，亦即 a[j]=a[j]+diff，其中 j>i订讼。

但當(dāng)實(shí)現(xiàn)本方法時(shí)髓窜，我們不需要對這樣的 a[j] 進(jìn)行增加。相反欺殿，我們把 moves 的數(shù)量增加到當(dāng)前元素（a[i]）中寄纵，a'[i]=a[i]+moves。

簡而言之脖苏，我們對數(shù)列進(jìn)行排序程拭，一直更新 moves 以使得直到當(dāng)前的元素相等，而不改變除了當(dāng)前元素之外的元素棍潘。在整個(gè)數(shù)組掃描完畢后恃鞋，moves 即為答案。

public class Solution {
    public int minMoves(int[] nums) {
        Arrays.sort(nums);
        int moves = 0;
        for (int i = 1; i < nums.length; i++) {
            int diff = (moves + nums[i]) - nums[i - 1];
            nums[i] += moves;
            moves += diff;
        }
        return moves;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n log(n) )亦歉。 排序需要 的時(shí)間恤浪。

• 空間復(fù)雜度：O(1)。只使用了一個(gè)變量鳍徽。

數(shù)學(xué)法

算法

該方法基于以下思路：將除了一個(gè)元素之外的全部元素+1资锰，等價(jià)于將該元素-1，因?yàn)槲覀冎粚υ氐南鄬Υ笮「信d趣阶祭。因此绷杜，該問題簡化為需要進(jìn)行的減法次數(shù)。

顯然濒募，我們只需要將所有的數(shù)都減到最小的數(shù)即可。為了找到答案，我們不需要真的操作這些元素鸭轮。

public class Solution {
    public int minMoves(int[] nums) {
        int moves = 0, min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            moves += nums[i];
            min = Math.min(min, nums[i]);
        }
        return moves - min * nums.length;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)竣蹦。對數(shù)組進(jìn)行了一次遍歷。

• 空間復(fù)雜度：O(1)晌姚。不需要額外空間粤剧。

改進(jìn)的數(shù)學(xué)法

算法

上一個(gè)方法可能存在整數(shù)越界，改進(jìn)如下挥唠。

public class Solution {
    public int minMoves(int[] nums) {
        int moves = 0, min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            min = Math.min(min, nums[i]);
        }
        for (int i = 0; i < nums.length; i++) {
            moves += nums[i] - min;
        }
        return moves;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)抵恋。一次遍歷尋找最小值，一次遍歷計(jì)算次數(shù)宝磨。

• 空間復(fù)雜度：O(1)弧关。不需要額外空間。

-問題14: 重復(fù)的子字符串

給定一個(gè)非空的字符串唤锉，判斷它是否可以由它的一個(gè)子串重復(fù)多次構(gòu)成世囊。給定的字符串只含有小寫英文字母，并且長度不超過10000窿祥。

示例 1:
輸入: "abab" 輸出: True 解釋: 可由子字符串 "ab" 重復(fù)兩次構(gòu)成株憾。
示例 2:
輸入: "aba" 輸出: False
示例 3:
輸入: "abcabcabcabc" 輸出: True 解釋: 可由子字符串 "abc" 重復(fù)四次構(gòu)成。 (或者子字符串 "abcabc" 重復(fù)兩次構(gòu)成晒衩。)

-tags: 算法,字符串

-解答:
1.將原字符串給出拷貝一遍組成新字符串号胚；
2.掐頭去尾留中間；
3.如果還包含原字符串浸遗，則滿足題意猫胁。

public boolean repeatedSubstringPattern(String s) {
\t\t
\tString str = s + s;
\treturn str.substring(1, str.length() - 1).contains(s);;
\t}

-問題15: 最大回文數(shù)乘積

你需要找到由兩個(gè) n 位數(shù)的乘積組成的最大回文數(shù)。

由于結(jié)果會(huì)很大跛锌，你只需返回最大回文數(shù) mod 1337得到的結(jié)果弃秆。

示例:

輸入: 2

輸出: 987

解釋: 99 x 91 = 9009, 9009 % 1337 = 987

說明:

n 的取值范圍為 [1,8]。

-tags: 算法

-解答:

object Solution {
    def largestPalindrome(n: Int): Int = {
         Array(9, 987, 123, 597, 677, 1218, 877, 475)(n-1)
    }
}

-問題16: 下一個(gè)更大元素 I

給定兩個(gè)沒有重復(fù)元素的數(shù)組 nums1 和 nums2 髓帽，其中nums1 是 nums2 的子集菠赚。找到 nums1 中每個(gè)元素在 nums2 中的下一個(gè)比其大的值。

nums1 中數(shù)字 x 的下一個(gè)更大元素是指 x 在 nums2 中對應(yīng)位置的右邊的第一個(gè)比 x大的元素郑藏。如果不存在衡查，對應(yīng)位置輸出-1。

示例 1:

輸入: nums1 = [4,1,2], nums2 = [1,3,4,2]. 輸出: [-1,3,-1]

解釋: 對于num1中的數(shù)字4必盖，你無法在第二個(gè)數(shù)組中找到下一個(gè)更大的數(shù)字拌牲，因此輸出 -1俱饿。 對于num1中的數(shù)字1，第二個(gè)數(shù)組中數(shù)字1右邊的下一個(gè)較大數(shù)字是 3塌忽。 對于num1中的數(shù)字2拍埠，第二個(gè)數(shù)組中沒有下一個(gè)更大的數(shù)字，因此輸出 -1土居。

示例 2:

輸入: nums1 = [2,4], nums2 = [1,2,3,4]. 輸出: [3,-1]

解釋: 對于num1中的數(shù)字2枣购，第二個(gè)數(shù)組中的下一個(gè)較大數(shù)字是3。 對于num1中的數(shù)字4擦耀，第二個(gè)數(shù)組中沒有下一個(gè)更大的數(shù)字棉圈，因此輸出 -1。

注意:

2. nums1和nums2中所有元素是唯一的眷蜓。
3. nums1和nums2 的數(shù)組大小都不超過1000分瘾。

-tags: 算法,棧

-解答:

方法一：單調(diào)棧

我們可以忽略數(shù)組 nums1，先對將 nums2 中的每一個(gè)元素账磺，求出其下一個(gè)更大的元素芹敌。隨后對于將這些答案放入哈希映射（HashMap）中，再遍歷數(shù)組 nums1垮抗，并直接找出答案氏捞。對于 nums2，我們可以使用單調(diào)棧來解決這個(gè)問題冒版。

我們首先把第一個(gè)元素 nums2[1] 放入棧液茎，隨后對于第二個(gè)元素 nums2[2]，

• 如果 nums2[2] > nums2[1]辞嗡，那么我們就找到了nums2[1] 的下一個(gè)更大元素 nums2[2]捆等，此時(shí)就可以把 nums2[1] 出棧并把 nums2[2] 入棧；
• 如果 nums2[2] <= nums2[1]续室，我們就僅把 nums2[2] 入棧栋烤。對于第三個(gè)元素 nums2[3]，此時(shí)棧中有若干個(gè)元素挺狰，那么所有比nums2[3]小的元素都找到了下一個(gè)更大元素（即 nums2[3]）明郭，因此可以出棧，在這之后丰泊，我們將 nums2[3] 入棧薯定，以此類推。

可以發(fā)現(xiàn)瞳购，我們維護(hù)了一個(gè)單調(diào)棧话侄，棧中的元素從棧頂?shù)綏５资菃握{(diào)不降的。當(dāng)我們遇到一個(gè)新的元素 nums2[i] 時(shí)，我們判斷棧頂元素是否小于 nums2[i]年堆，如果是吞杭，那么棧頂元素的下一個(gè)更大元素即為 nums2[i]，我們將棧頂元素出棧嘀韧。重復(fù)這一操作篇亭，直到棧為空或者棧頂元素大于 nums2[i]缠捌。此時(shí)我們將 nums2[i] 入棧锄贷，保持棧的單調(diào)性，并對接下來的 nums2[i + 1], nums2[i + 2] ... 執(zhí)行同樣的操作曼月。

public class Solution {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        Stack < Integer > stack = new Stack < > ();
        HashMap < Integer, Integer > map = new HashMap < > ();
        int[] res = new int[findNums.length];
        for (int i = 0; i < nums.length; i++) {
            while (!stack.empty() && nums[i] > stack.peek())
                map.put(stack.pop(), nums[i]);
            stack.push(nums[i]);
        }
        while (!stack.empty())
            map.put(stack.pop(), -1);
        for (int i = 0; i < findNums.length; i++) {
            res[i] = map.get(findNums[i]);
        }
        return res;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(M+N)谊却，其中 M 和 N 分別是數(shù)組 nums1 和 nums2 的長度。

• 空間復(fù)雜度：O(N)哑芹。我們在遍歷 nums2 時(shí)炎辨，需要使用棧，以及哈希映射用來臨時(shí)存儲(chǔ)答案聪姿。

-問題17: 二叉樹的直徑

給定一棵二叉樹碴萧，你需要計(jì)算它的直徑長度。一棵二叉樹的直徑長度是任意兩個(gè)結(jié)點(diǎn)路徑長度中的最大值末购。這條路徑可能穿過根結(jié)點(diǎn)破喻。

示例 :
給定二叉樹
1 / \ 2 3 / \ 4 5
返回 3, 它的長度是路徑 [4,2,1,3] 或者 [5,2,1,3]。

注意：兩結(jié)點(diǎn)之間的路徑長度是以它們之間邊的數(shù)目表示盟榴。

-tags: 樹,算法

-解答:

方法 1：深度優(yōu)先搜索

任意一條路徑可以被寫成兩個(gè) 箭頭（不同方向）曹质，每個(gè)箭頭代表一條從某些點(diǎn)向下遍歷到孩子節(jié)點(diǎn)的路徑。

假設(shè)我們知道對于每個(gè)節(jié)點(diǎn)最長箭頭距離分別為 L, R擎场，那么最優(yōu)路徑經(jīng)過 L + R + 1 個(gè)節(jié)點(diǎn)羽德。

算法

按照常用方法計(jì)算一個(gè)節(jié)點(diǎn)的深度：

max(depth of node.left, depth of node.right) + 1。

在計(jì)算的同時(shí)迅办，經(jīng)過這個(gè)節(jié)點(diǎn)的路徑長度為 1 + (depth of node.left) + (depth of node.right) 宅静。搜索每個(gè)節(jié)點(diǎn)并記錄這些路徑經(jīng)過的點(diǎn)數(shù)最大值，期望長度是結(jié)果 - 1站欺。

class Solution(object):
    def diameterOfBinaryTree(self, root):
        self.ans = 1
        def depth(node):
            if not node: return 0
            L = depth(node.left)
            R = depth(node.right)
            self.ans = max(self.ans, L+R+1)
            return max(L, R) + 1

        depth(root)
        return self.ans - 1

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(N)姨夹，每個(gè)節(jié)點(diǎn)只訪問一次。
• 空間復(fù)雜度：O(N)镊绪，深度優(yōu)先搜索的棧開銷匀伏。

-問題18: 最短無序連續(xù)子數(shù)組

給定一個(gè)整數(shù)數(shù)組，你需要尋找一個(gè)連續(xù)的子數(shù)組蝴韭，如果對這個(gè)子數(shù)組進(jìn)行升序排序够颠，那么整個(gè)數(shù)組都會(huì)變?yōu)樯蚺判颉?/p>

你找到的子數(shù)組應(yīng)是最短的，請輸出它的長度榄鉴。

示例 1:
輸入: [2, 6, 4, 8, 10, 9, 15] 輸出: 5 解釋: 你只需要對 [6, 4, 8, 10, 9] 進(jìn)行升序排序履磨，那么整個(gè)表都會(huì)變?yōu)樯蚺判颉?br> 說明 :

2. 輸入的數(shù)組長度范圍在 [1, 10,000]蛉抓。
3. 輸入的數(shù)組可能包含重復(fù)元素 ，所以升序的意思是<=剃诅。

-tags: 算法,數(shù)組

-解答:

方法 1：暴力

算法

在暴力方法中巷送，我們考慮 nums 數(shù)組中每一個(gè)可能的子序列。對于每一個(gè)子序列 nums[i:j] 矛辕，我們檢查它是否是最小的無序子序列笑跛。因此對于每一個(gè)子序列，我們求出這個(gè)子序列中的最大和最小值聊品，并分別用 max 和 min 表示飞蹂。

如果子序列 nums[0:i-1] 和 nums[j:n-1] 是升序的，那么僅有 nums[i:j] 是可能的子序列翻屈。更進(jìn)一步陈哑， nums[0:i-1] 中所有的元素都要比 min 小且 nums[j:n-1] 中所有的元素都要比 max 大。我們對于枚舉的每一對 i 和 j 都做這樣的檢查伸眶。

接下來惊窖，我們需要檢查 nums[0:i-1] 和 nums[j:n-1] 是否是升序的。如果上述所有條件都滿足厘贼，我們通過枚舉所有的 i 和 j 并計(jì)算 j-i 來找到最短的無序子數(shù)組界酒。

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int res = nums.length;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j <= nums.length; j++) {
                int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE, prev = Integer.MIN_VALUE;
                for (int k = i; k < j; k++) {
                    min = Math.min(min, nums[k]);
                    max = Math.max(max, nums[k]);
                }
                if ((i > 0 && nums[i - 1] > min) || (j < nums.length && nums[j] < max))
                    continue;
                int k = 0;
                while (k < i && prev <= nums[k]) {
                    prev = nums[k];
                    k++;
                }
                if (k != i)
                    continue;
                k = j;
                while (k < nums.length && prev <= nums[k]) {
                    prev = nums[k];
                    k++;
                }
                if (k == nums.length) {
                    res = Math.min(res, j - i);

                }
            }
        }
        return res;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n^3) 。使用了三重循環(huán)涂臣。

• 空間復(fù)雜度：O(1) 盾计。只使用了常數(shù)空間。

方法 2：更好的暴力

算法

在這種方法中赁遗，我們基于選擇排序使用如下想法：我們遍歷 nums 數(shù)組中的每一個(gè)元素 nums[i] 署辉。對于每一個(gè)元素，我們嘗試找到它在正確順序數(shù)組中的位置岩四，即將它與每一個(gè)滿足 i < j < n 的 nums[j] 做比較哭尝，這里 n 是 nums 數(shù)組的長度。

如果存在 nums[j] 比 nums[i] 小剖煌，這意味著 nums[i] 和 nums[j] 都不在排序后數(shù)組中的正確位置材鹦。因此我們需要交換這兩個(gè)元素使它們到正確的位置上。但這里我們并不需要真的交換兩個(gè)元素耕姊，我們只需要標(biāo)記兩個(gè)元素在原數(shù)組中的位置 i 和 j 桶唐。這兩個(gè)元素標(biāo)記著目前無序數(shù)組的邊界。

因此茉兰，在所有的 nums[i] 中尤泽，我們找到最左邊不在正確位置的 nums[i] ，這標(biāo)記了最短無序子數(shù)組的左邊界（l）。類似的坯约，我們找到最右邊不在正確位置的邊界 nums[j] 熊咽，它標(biāo)記了最短無序子數(shù)組的右邊界 (r) 。

因此闹丐，我們可以求得最短無序子數(shù)組的長度為 r - l + 1 横殴。

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int l = nums.length, r = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[i]) {
                    r = Math.max(r, j);
                    l = Math.min(l, i);
                }
            }
        }
        return r - l < 0 ? 0 : r - l + 1;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n^2) 。使用了兩重循環(huán)卿拴。

• 空間復(fù)雜度：O(1) 衫仑。只使用了常數(shù)空間。

方法 3：排序

算法

另一個(gè)簡單的想法是：我們將數(shù)組 nums 進(jìn)行排序巍棱，記為 nums_sorted 惑畴。然后我們比較 nums 和 nums_sorted 的元素來決定最左邊和最右邊不匹配的元素蛋欣。它們之間的子數(shù)組就是要求的最短無序子數(shù)組航徙。

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] snums = nums.clone();
        Arrays.sort(snums);
        int start = snums.length, end = 0;
        for (int i = 0; i < snums.length; i++) {
            if (snums[i] != nums[i]) {
                start = Math.min(start, i);
                end = Math.max(end, i);
            }
        }
        return (end - start >= 0 ? end - start + 1 : 0);
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n log n) 。排序消耗 n log n 的時(shí)間陷虎。

• 空間復(fù)雜度：O(n) 到踏。我們拷貝了一份原數(shù)組來進(jìn)行排序。

方法 4：使用棧

算法

這個(gè)方法背后的想法仍然是選擇排序尚猿。我們需要找到無序子數(shù)組中最小元素和最大元素分別對應(yīng)的正確位置窝稿，來求得我們想要的無序子數(shù)組的邊界。

為了達(dá)到這一目的凿掂，此方法中伴榔，我們使用 棧 。我們從頭遍歷 nums 數(shù)組庄萎，如果遇到的數(shù)字大小一直是升序的踪少，我們就不斷把對應(yīng)的下標(biāo)壓入棧中，這么做的目的是因?yàn)檫@些元素在目前都是處于正確的位置上糠涛。一旦我們遇到前面的數(shù)比后面的數(shù)大援奢，也就是 nums[j] 比棧頂元素小，我們可以知道 nums[j] 一定不在正確的位置上忍捡。

為了找到 nums[j] 的正確位置集漾，我們不斷將棧頂元素彈出，直到棧頂元素比 nums[j] 小砸脊，我們假設(shè)棧頂元素對應(yīng)的下標(biāo)為 k 具篇，那么我們知道 nums[j] 的正確位置下標(biāo)應(yīng)該是 k + 1 。

我們重復(fù)這一過程并遍歷完整個(gè)數(shù)組凌埂，這樣我們可以找到最小的 k驱显， 它也是無序子數(shù)組的左邊界。

類似的，我們逆序遍歷一遍 nums 數(shù)組來找到無序子數(shù)組的右邊界秒紧。這一次我們將降序的元素壓入棧中绢陌，如果遇到一個(gè)升序的元素，我們像上面所述的方法一樣不斷將棧頂元素彈出熔恢，直到找到一個(gè)更大的元素脐湾，以此找到無序子數(shù)組的右邊界。

我們可以看下圖作為參考叙淌。我們觀察到上升還是下降決定了相對順序秤掌，我們還可以觀察到指針 b 在下標(biāo) 0 后面標(biāo)記著無序子數(shù)組的左邊界，指針 a 在下標(biāo) 7 前面標(biāo)記著無序子數(shù)組的右邊界鹰霍。

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        Stack < Integer > stack = new Stack < Integer > ();
        int l = nums.length, r = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i])
                l = Math.min(l, stack.pop());
            stack.push(i);
        }
        stack.clear();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i])
                r = Math.max(r, stack.pop());
            stack.push(i);
        }
        return r - l > 0 ? r - l + 1 : 0;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)闻鉴。需要遍歷數(shù)組一遍，棧的時(shí)間復(fù)雜度也為 O(n)茂洒。

• 空間復(fù)雜度：O(n)孟岛。棧的大小最大達(dá)到 n。

方法 5：不使用額外空間

算法

這個(gè)算法背后的思想是無序子數(shù)組中最小元素的正確位置可以決定左邊界督勺，最大元素的正確位置可以決定右邊界渠羞。

因此，首先我們需要找到原數(shù)組在哪個(gè)位置開始不是升序的智哀。我們從頭開始遍歷數(shù)組次询，一旦遇到降序的元素，我們記錄最小元素為 min 瓷叫。

類似的屯吊，我們逆序掃描數(shù)組 nums，當(dāng)數(shù)組出現(xiàn)升序的時(shí)候摹菠，我們記錄最大元素為 max盒卸。

然后，我們再次遍歷 nums 數(shù)組并通過與其他元素進(jìn)行比較辨嗽，來找到 min 和 max 在原數(shù)組中的正確位置世落。我們只需要從頭開始找到第一個(gè)大于 min 的元素，從尾開始找到第一個(gè)小于 max 的元素糟需，它們之間就是最短無序子數(shù)組屉佳。

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        boolean flag = false;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1])
                flag = true;
            if (flag)
                min = Math.min(min, nums[i]);
        }
        flag = false;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] > nums[i + 1])
                flag = true;
            if (flag)
                max = Math.max(max, nums[i]);
        }
        int l, r;
        for (l = 0; l < nums.length; l++) {
            if (min < nums[l])
                break;
        }
        for (r = nums.length - 1; r >= 0; r--) {
            if (max > nums[r])
                break;
        }
        return r - l < 0 ? 0 : r - l + 1;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)。使用了4個(gè) O(n) 的循環(huán)洲押。

• 空間復(fù)雜度：O(1)武花。使用了常數(shù)空間。

-問題19: 兩數(shù)之和 IV - 輸入 BST

給定一個(gè)二叉搜索樹和一個(gè)目標(biāo)結(jié)果杈帐，如果 BST 中存在兩個(gè)元素且它們的和等于給定的目標(biāo)結(jié)果体箕，則返回 true专钉。

案例 1:
輸入: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 輸出: True
案例 2:
輸入: 5 / \ 3 6 / \ \ 2 4 7 Target = 28 輸出: False

-tags: 樹,算法

-解答:

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        def inorder(root):
            if not root:
                return []
            return inorder(root.left)+[root.val]+inorder(root.right)
        numbers = sorted(inorder(root))
        n = len(numbers)
           
        i = 0
        j = n-1
        while i < j:
             if numbers[i] + numbers[j] > k:
                j -= 1
             elif numbers[i] + numbers[j] < k:
                i +=1
             else:
                return True
        return False

-問題20: 最長同值路徑

給定一個(gè)二叉樹，找到最長的路徑累铅，這個(gè)路徑中的每個(gè)節(jié)點(diǎn)具有相同值跃须。 這條路徑可以經(jīng)過也可以不經(jīng)過根節(jié)點(diǎn)。

注意：兩個(gè)節(jié)點(diǎn)之間的路徑長度由它們之間的邊數(shù)表示娃兽。

示例 1:

輸入:
5 / \ 4 5 / \ \ 1 1 5
輸出:
2
示例 2:

輸入:
1 / \ 4 5 / \ \ 4 4 5
輸出:
2
注意: 給定的二叉樹不超過10000個(gè)結(jié)點(diǎn)菇民。 樹的高度不超過1000。

-tags: 樹,遞歸,算法

-解答:

方法：遞歸

思路

我們可以將任何路徑（具有相同值的節(jié)點(diǎn)）看作是最多兩個(gè)從其根延伸出的箭頭投储。

具體地說第练，路徑的根將是唯一節(jié)點(diǎn)，因此該節(jié)點(diǎn)的父節(jié)點(diǎn)不會(huì)出現(xiàn)在該路徑中玛荞，而箭頭將是根在該路徑中只有一個(gè)子節(jié)點(diǎn)的路徑娇掏。

然后，對于每個(gè)節(jié)點(diǎn)勋眯，我們想知道向左延伸的最長箭頭和向右延伸的最長箭頭是什么婴梧？我們可以用遞歸來解決這個(gè)問題。

算法

令 arrow_length(node) 為從節(jié)點(diǎn) node 延伸出的最長箭頭的長度凡恍。如果 node.Left 存在且與節(jié)點(diǎn) node 具有相同的值志秃，則該值就會(huì)是 1 + arrow_length(node.left)。在 node.right 存在的情況下也是一樣嚼酝。

當(dāng)我們計(jì)算箭頭長度時(shí)，候選答案將是該節(jié)點(diǎn)在兩個(gè)方向上的箭頭之和竟坛。我們將這些候選答案記錄下來闽巩，并返回最佳答案。

class Solution {
    int ans;
    public int longestUnivaluePath(TreeNode root) {
        ans = 0;
        arrowLength(root);
        return ans;
    }
    public int arrowLength(TreeNode node) {
        if (node == null) return 0;
        int left = arrowLength(node.left);
        int right = arrowLength(node.right);
        int arrowLeft = 0, arrowRight = 0;
        if (node.left != null && node.left.val == node.val) {
            arrowLeft += left + 1;
        }
        if (node.right != null && node.right.val == node.val) {
            arrowRight += right + 1;
        }
        ans = Math.max(ans, arrowLeft + arrowRight);
        return Math.max(arrowLeft, arrowRight);
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(N)担汤，其中 N 是樹中節(jié)點(diǎn)數(shù)涎跨。我們處理每個(gè)節(jié)點(diǎn)一次。

• 空間復(fù)雜度：O(H)崭歧，其中 H 是樹的高度隅很。我們的遞歸調(diào)用棧可以達(dá)到 H 層的深度率碾。

-問題21: 計(jì)數(shù)二進(jìn)制子串

給定一個(gè)字符串 s叔营，計(jì)算具有相同數(shù)量0和1的非空(連續(xù))子字符串的數(shù)量，并且這些子字符串中的所有0和所有1都是組合在一起的所宰。

重復(fù)出現(xiàn)的子串要計(jì)算它們出現(xiàn)的次數(shù)绒尊。

示例 1 :
輸入: "00110011" 輸出: 6 解釋: 有6個(gè)子串具有相同數(shù)量的連續(xù)1和0：“0011”，“01”仔粥，“1100”婴谱，“10”蟹但，“0011” 和 “01”。 請注意谭羔，一些重復(fù)出現(xiàn)的子串要計(jì)算它們出現(xiàn)的次數(shù)华糖。 另外，“00110011”不是有效的子串瘟裸，因?yàn)樗械?（和1）沒有組合在一起缅阳。
示例 2 :
輸入: "10101" 輸出: 4 解釋: 有4個(gè)子串：“10”，“01”景描，“10”掐暮，“01”，它們具有相同數(shù)量的連續(xù)1和0抡秆。
注意：

• s.length 在1到50,000之間搀继。
• s 只包含“0”或“1”字符。

-tags: 算法,字符串

-解答:

方法一：按字符分組

我們可以將字符串 s 轉(zhuǎn)換為 groups 數(shù)組表示字符串中相同字符連續(xù)塊的長度棠绘。例如件相，如果 s=“11000111000000”，則 groups=[2氧苍，3夜矗，4，6]让虐。

對于 '0' * k + '1' * k 或 '1' * k + '0' * k 形式的每個(gè)二進(jìn)制字符串紊撕，此字符串的中間部分必須出現(xiàn)在兩個(gè)組之間。

讓我們嘗試計(jì)算 groups[i] 和 groups[i+1] 之間的有效二進(jìn)制字符串?dāng)?shù)赡突。如果我們有 groups[i] = 2, groups[i+1] = 3对扶，那么它表示 “00111” 或 “11000”。顯然惭缰，我們可以在此字符串中生成 min(groups[i], groups[i+1]) 有效的二進(jìn)制字符串浪南。

算法：

• 讓我們創(chuàng)建上面定義的 groups。s 的第一個(gè)元素屬于它自己的組漱受。每個(gè)元素要么與前一個(gè)元素不匹配络凿，從而開始一個(gè)大小為 1 的新組；要么匹配昂羡，從而使最近一個(gè)組的大小增加 1絮记。
• 然后，我們將取 min(groups[i-1], groups[i]) 的和紧憾。

class Solution(object):
    def countBinarySubstrings(self, s):
        groups = [1]
        for i in xrange(1, len(s)):
            if s[i-1] != s[i]:
                groups.append(1)
            else:
                groups[-1] += 1

        ans = 0
        for i in xrange(1, len(groups)):
            ans += min(groups[i-1], groups[i])
        return ans

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(N)到千。其中 N 是 s 的長度。每個(gè)循環(huán)都是 O(N)赴穗。
• 空間復(fù)雜度：O(N)憔四，groups 使用的空間膀息。

方法二：線性掃描

我們可以修改我們的方法 1 來實(shí)時(shí)計(jì)算答案。我們將只記住 prev = groups[-2] 和 cur=groups[-1] 來代替 groups了赵。然后潜支，答案是我們看到的每個(gè)不同的 (prev, cur) 的 min(prev, cur) 之和。

class Solution(object):
    def countBinarySubstrings(self, s):
        ans, prev, cur = 0, 0, 1
        for i in xrange(1, len(s)):
            if s[i-1] != s[i]:
                ans += min(prev, cur)
                prev, cur = cur, 1
            else:
                cur += 1

        return ans + min(prev, cur)

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(N)柿汛。其中 N 是 s 的長度冗酿。每個(gè)循環(huán)都是 O(N)。
• 空間復(fù)雜度：O(1)络断。

-問題22: 1比特與2比特字符

有兩種特殊字符裁替。第一種字符可以用一比特0來表示。第二種字符可以用兩比特(10 或 11)來表示貌笨。

現(xiàn)給一個(gè)由若干比特組成的字符串弱判。問最后一個(gè)字符是否必定為一個(gè)一比特字符。給定的字符串總是由0結(jié)束锥惋。

示例 1:
輸入: bits = [1, 0, 0] 輸出: True 解釋: 唯一的編碼方式是一個(gè)兩比特字符和一個(gè)一比特字符昌腰。所以最后一個(gè)字符是一比特字符。
示例 2:
輸入: bits = [1, 1, 1, 0] 輸出: False 解釋: 唯一的編碼方式是兩比特字符和兩比特字符膀跌。所以最后一個(gè)字符不是一比特字符遭商。
注意:

• 1 <= len(bits) <= 1000.
• bits[i] 總是0 或 1.

-tags: 算法,數(shù)組

-解答:

方法一：線性掃描

我們可以對 bits 數(shù)組從左到右掃描來判斷最后一位是否為一比特字符。當(dāng)掃描到第 i 位時(shí)捅伤，如果 bits[i]=1劫流，那么說明這是一個(gè)兩比特字符，將 i 的值增加 2暑认。如果 bits[i]=0困介，那么說明這是一個(gè)一比特字符，將 i 的值增加 1蘸际。

如果 i 最終落在了 bits[length-1] 的位置，那么說明最后一位一定是一比特字符徒扶。

class Solution(object):
    def isOneBitCharacter(self, bits):
        i = 0
        while i < len(bits) - 1:
            i += bits[i] + 1
        return i == len(bits) - 1

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)粮彤，其中 n 是 bits 數(shù)組的長度。
• 空間復(fù)雜度：O(1)姜骡。

方法二：貪心

三種字符分別為 0导坟，10 和 11，那么 bits 數(shù)組中出現(xiàn)的所有 0 都表示一個(gè)字符的結(jié)束位置（無論其為一比特還是兩比特）圈澈。因此最后一位是否為一比特字符惫周，只和他左側(cè)出現(xiàn)的連續(xù)的 1 的個(gè)數(shù)（即它與倒數(shù)第二個(gè) 0 出現(xiàn)的位置之間的 1 的個(gè)數(shù)，如果bits數(shù)組中只有 1 個(gè) 0康栈，那么就是整個(gè)數(shù)組的長度減一）有關(guān)递递。如果 1 的個(gè)數(shù)為偶數(shù)個(gè)喷橙，那么最后一位是一比特字符，如果 1 的個(gè)數(shù)為奇數(shù)個(gè)登舞，那么最后一位不是一比特字符贰逾。

class Solution(object):
    def isOneBitCharacter(self, bits):
        parity = bits.pop()
        while bits and bits.pop(): parity ^= 1
        return parity == 0

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，其中 N 是 bits 數(shù)組的長度菠秒。
• 空間復(fù)雜度：O(1)疙剑。

-問題23: 詞典中最長的單詞

給出一個(gè)字符串?dāng)?shù)組words組成的一本英語詞典。從中找出最長的一個(gè)單詞践叠，該單詞是由words詞典中其他單詞逐步添加一個(gè)字母組成言缤。若其中有多個(gè)可行的答案，則返回答案中字典序最小的單詞禁灼。

若無答案管挟，則返回空字符串。

示例 1:

輸入: words = ["w","wo","wor","worl", "world"] 輸出: "world"

解釋: 單詞"world"可由"w", "wo", "wor", 和 "worl"添加一個(gè)字母組成匾二。

示例 2:

輸入: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"] 輸出: "apple"

解釋: "apply"和"apple"都能由詞典中的單詞組成哮独。但是"apple"得字典序小于"apply"。

注意:

• 所有輸入的字符串都只包含小寫字母察藐。
• words數(shù)組長度范圍為[1,1000]皮璧。
  -words[i]的長度范圍為[1,30]。

-tags: 算法,字典樹,哈希表

-解答:

方法一：暴力法

對于每個(gè)單詞分飞，我們可以檢查它的全部前綴是否存在悴务，可以通過 Set 數(shù)據(jù)結(jié)構(gòu)來加快查找

算法：

• 當(dāng)我們找到一個(gè)單詞它的長度更長且它的全部前綴都存在，我們將更改答案譬猫。
• 或者讯檐，我們可以事先將單詞排序，這樣當(dāng)我們找到一個(gè)符合條件的單詞就可以認(rèn)定它是答案染服。

class Solution(object):
    def longestWord(self, words):
    ans = ""
    wordset = set(words)
    for word in words:
        if len(word) > len(ans) or len(word) == len(ans) and word < ans:
            if all(word[:k] in wordset for k in xrange(1, len(word))):
                ans = word

    return ans

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(sum w_i^2)别洪。w_i 指的是 words[i] 的長度，在 Set 中檢查 words[i] 全部前綴是否均存在的時(shí)間復(fù)雜度是 O(sum w_i^2)柳刮。
• 空間復(fù)雜度：O(sum w_i^2) 用來存放子串的空間挖垛。

方法二：前綴樹 + 深度優(yōu)先搜索

由于涉及到字符串的前綴，通潮牛可以使用 trie（前綴樹）來解決痢毒。

算法：

• 將所有單詞插入 trie，然后從 trie 進(jìn)行深度優(yōu)先搜索蚕甥，每找到一個(gè)單詞表示該單詞的全部前綴均存在哪替，我們選取長度最長的單詞。
• 在 python 中菇怀，我們使用了 defaultdict 的方法凭舶。而在 java 中晌块，我們使用了更通用的面向?qū)ο蠓椒ā?/li>

class Solution(object):
    def longestWord(self, words):
        Trie = lambda: collections.defaultdict(Trie)
        trie = Trie()
        END = True

        for i, word in enumerate(words):
            reduce(dict.__getitem__, word, trie)[END] = i

        stack = trie.values()
        ans = ""
        while stack:
            cur = stack.pop()
            if END in cur:
                word = words[cur[END]]
                if len(word) > len(ans) or len(word) == len(ans) and word < ans:
                    ans = word
                stack.extend([cur[letter] for letter in cur if letter != END])

        return ans

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(sum w_i)。w_i 指的是 words[i] 的長度库快。該時(shí)間復(fù)雜度用于創(chuàng)建前綴樹和查找單詞摸袁。

如果我們使用一個(gè) BFS 代替 DFS，并在數(shù)組中對子節(jié)點(diǎn)進(jìn)行排序义屏，我們就可以不必檢查每個(gè)節(jié)點(diǎn)上的候選詞是否比答案好靠汁，最佳答案將是最后訪問的節(jié)點(diǎn)。

• 空間復(fù)雜度：O(sum w_i)闽铐，前綴樹所使用的空間蝶怔。

-問題24: 尋找比目標(biāo)字母大的最小字母

給定一個(gè)只包含小寫字母的有序數(shù)組letters 和一個(gè)目標(biāo)字母 target，尋找有序數(shù)組里面比目標(biāo)字母大的最小字母兄墅。

數(shù)組里字母的順序是循環(huán)的踢星。舉個(gè)例子，如果目標(biāo)字母target = 'z' 并且有序數(shù)組為 letters = ['a', 'b']隙咸，則答案返回 'a'沐悦。

示例:

輸入: letters = ["c", "f", "j"] target = "a" 輸出: "c"

輸入: letters = ["c", "f", "j"] target = "c" 輸出: "f"

輸入: letters = ["c", "f", "j"] target = "d" 輸出: "f"

輸入: letters = ["c", "f", "j"] target = "g" 輸出: "j"

輸入: letters = ["c", "f", "j"] target = "j" 輸出: "c"

輸入: letters = ["c", "f", "j"] target = "k" 輸出: "c"

注:

2. letters長度范圍在[2, 10000]區(qū)間內(nèi)。

3. letters 僅由小寫字母組成五督，最少包含兩個(gè)不同的字母藏否。

4. 目標(biāo)字母target 是一個(gè)小寫字母。

-tags: 二分查找,算法

-解答:

方法一：記錄存在的字母

算法

• 我們可以掃描 letters 記錄字母是否存在充包。我們可以用大小為 26 的數(shù)組或者 Set 來實(shí)現(xiàn)副签。
• 然后，從下一個(gè)字母（從比目標(biāo)大一個(gè)的字母開始）開始檢查一下是否存在基矮。如果有的話則是答案淆储。

class Solution(object):
    def nextGreatestLetter(self, letters, target):
        seen = set(letters)
        for i in xrange(1, 26):
            cand = chr((ord(target) - ord('a') + i) % 26 + ord('a'))
            if cand in seen:
                return cand

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(N)。N 指的是 letters 的長度家浇，我們掃描數(shù)組的每個(gè)元素本砰。
• 空間復(fù)雜度：O(1)。seen 最大的空間為 26钢悲。

方法二：線性掃描

算法：
由于 letters 已經(jīng)有序灌具，當(dāng)我們從左往右掃描找到比目標(biāo)字母大字母則該字母就是答案。否則(letters 不為空)答案將是 letters[0]譬巫。

class Solution(object):
    def nextGreatestLetter(self, letters, target):
        for c in letters:
            if c > target:
                return c
        return letters[0]

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(N)。N 指的是 letters 的長度督笆，我們掃描數(shù)組的每個(gè)元素芦昔。
• 空間復(fù)雜度：O(1)。只使用了指針娃肿。

方法三：二分查找

算法：

• 如方法二一樣咕缎，我們想要在有序數(shù)組中查找比目標(biāo)字母大的最小字母珠十，可以使用二分查找：讓我們找到最右邊的位置將 target 插入 letters 中，以便它保持排序凭豪。
• 二分查找分幾輪進(jìn)行焙蹭，在每一輪中我們保持循環(huán)始終在區(qū)間 [lo，hi]嫂伞。讓 mi = (lo + hi) / 2孔厉。若 letters[mi] <= target，則我們修改查找區(qū)間為 [mi + 1, hi]帖努，否則撰豺，我們修改為 [lo, mi]
• 最后，如果插入位置是最后一個(gè)位置 letters.length拼余，則返回 letters[0]污桦。這就是模運(yùn)算的運(yùn)用。

class Solution(object):
    def nextGreatestLetter(self, letters, target):
        index = bisect.bisect(letters, target)
        return letters[index % len(letters)]

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(log N)匙监。N 指的是 letters 的長度凡橱，我們只查看數(shù)組中的 log n個(gè)元素。
• 空間復(fù)雜度：O(1)亭姥。只使用了指針稼钩。

-問題25: 二叉搜索樹中的眾數(shù)

給定一個(gè)有相同值的二叉搜索樹（BST），找出 BST 中的所有眾數(shù)（出現(xiàn)頻率最高的元素）致份。

假定 BST 有如下定義：

• 結(jié)點(diǎn)左子樹中所含結(jié)點(diǎn)的值小于等于當(dāng)前結(jié)點(diǎn)的值
• 結(jié)點(diǎn)右子樹中所含結(jié)點(diǎn)的值大于等于當(dāng)前結(jié)點(diǎn)的值
• 左子樹和右子樹都是二叉搜索樹

例如：
給定 BST [1,null,2,2],
1 \ 2 / 2
返回[2].

提示：如果眾數(shù)超過1個(gè)变抽，不需考慮輸出順序

進(jìn)階：你可以不使用額外的空間嗎？（假設(shè)由遞歸產(chǎn)生的隱式調(diào)用棧的開銷不被計(jì)算在內(nèi)）

-tags: 樹,算法

-解答:

    int maxTimes = 0;
    int thisTimes = 0;
    List<Integer> res = new LinkedList<Integer>();
    TreeNode pre = null;
    public int[] findMode(TreeNode root) {
        inOrder(root);
        int length = res.size();
        int[] rr = new int[length];
        for(int i = 0; i < length; i++) {
            rr[i] = res.get(i);
        } 
        return rr;
    }
    public void inOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        inOrder(root.left);
        if(pre != null && pre.val == root.val) {
            thisTimes++;
        } else {
            thisTimes = 1;
        }
        if(thisTimes == maxTimes) {
            res.add(root.val);
        } else if(thisTimes > maxTimes) {
            maxTimes = thisTimes;
            res.clear();
            res.add(root.val);
        }
        pre = root;
        inOrder(root.right);
    }

-問題26: N叉樹的后序遍歷

給定一個(gè) N 叉樹氮块，返回其節(jié)點(diǎn)值的后序遍歷绍载。

例如，給定一個(gè) 3叉樹 :

image

返回其后序遍歷: [5,6,3,2,4,1].

說明: 遞歸法很簡單滔蝉，你可以使用迭代法完成此題嗎?

-tags: 樹,算法

-解答:
由于遞歸實(shí)現(xiàn) N 叉樹的后序遍歷較為簡單击儡，因此我們只講解如何使用迭代的方法得到 N 叉樹的后序遍歷。

在后序遍歷中蝠引，我們會(huì)先遍歷一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)阳谍，再遍歷這個(gè)節(jié)點(diǎn)本身。例如當(dāng)前的節(jié)點(diǎn)為 u螃概，它的子節(jié)點(diǎn)為 v1, v2, v3 時(shí)矫夯，那么后序遍歷的結(jié)果為

[children of v1], v1, [children of v2], v2, [children of v3], v3, u，

其中 [children of vk] 表示以 vk 為根節(jié)點(diǎn)的子樹的后序遍歷結(jié)果（不包括 vk 本身）吊洼。我們將這個(gè)結(jié)果反轉(zhuǎn)训貌，可以得到

u, v3, [children of v3]', v2, [children of v2]', v1, [children of v1]'，

其中 [a]' 表示 [a] 的反轉(zhuǎn)。此時(shí)我們發(fā)現(xiàn)递沪，結(jié)果和前序遍歷非常類似豺鼻，只不過前序遍歷中對子節(jié)點(diǎn)的遍歷順序是 v1, v2, v3，而這里是 v3, v2, v1款慨。

因此我們可以使用和 N叉樹的前序遍歷 相同的方法儒飒，使用一個(gè)棧來得到后序遍歷。我們首先把根節(jié)點(diǎn)入棧檩奠。

當(dāng)每次我們從棧頂取出一個(gè)節(jié)點(diǎn) u 時(shí)桩了，就把 u 的所有子節(jié)點(diǎn)順序推入棧中。例如 u 的子節(jié)點(diǎn)從左到右為 v1, v2, v3笆凌，那么推入棧的順序應(yīng)當(dāng)為 v1, v2, v3圣猎，這樣就保證了下一個(gè)遍歷到的節(jié)點(diǎn)（即 u 的第一個(gè)子節(jié)點(diǎn) v3）出現(xiàn)在棧頂?shù)奈恢谩Ｔ诒闅v結(jié)束之后乞而，我們把遍歷結(jié)果反轉(zhuǎn)送悔，就可以得到后序遍歷。

class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        if root is None:
            return []
        
        stack, output = [root, ], []
        while stack:
            root = stack.pop()
            if root is not None:
                output.append(root.val)
            for c in root.children:
                stack.append(c)
                
        return output[::-1]

class Solution {
    public List<Integer> postorder(Node root) {
        LinkedList<Node> stack = new LinkedList<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }

      stack.add(root);
      while (!stack.isEmpty()) {
          Node node = stack.pollLast();
          output.addFirst(node.val);
          for (Node item : node.children) {
              if (item != null) {
                  stack.add(item);    
              } 
          }
      }
      return output;
    }
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O(M)爪模，其中 M 是 N 叉樹中的節(jié)點(diǎn)個(gè)數(shù)欠啤。每個(gè)節(jié)點(diǎn)只會(huì)入棧和出棧各一次。

• 空間復(fù)雜度：O(M)屋灌。在最壞的情況下洁段，這棵 N 叉樹只有2層，所有第2層的節(jié)點(diǎn)都是根節(jié)點(diǎn)的孩子共郭。將根節(jié)點(diǎn)推出棧后祠丝，需要將這些節(jié)點(diǎn)都放入棧，共有M - 1個(gè)節(jié)點(diǎn)除嘹，因此棧的大小為O(M)写半。

-問題27: 比較含退格的字符串

給定 S 和 T 兩個(gè)字符串，當(dāng)它們分別被輸入到空白的文本編輯器后尉咕，判斷二者是否相等叠蝇，并返回結(jié)果。 # 代表退格字符年缎。

示例 1：
輸入：S = "ab#c", T = "ad#c" 輸出：true 解釋：S 和 T 都會(huì)變成 “ac”悔捶。
示例 2：
輸入：S = "ab##", T = "c#d#" 輸出：true 解釋：S 和 T 都會(huì)變成 “”单芜。
示例 3：
輸入：S = "a##c", T = "#a#c" 輸出：true 解釋：S 和 T 都會(huì)變成 “c”蜕该。
示例 4：
輸入：S = "a#c", T = "b" 輸出：false 解釋：S 會(huì)變成 “c”，但 T 仍然是 “b”洲鸠。
提示：

2. 1 <= S.length <= 200
3. 1 <= T.length <= 200
4. S 和 T 只含有小寫字母以及字符 '#'蛇损。

-tags: 算法,棧,雙指針

-解答:

class Solution {
    public boolean backspaceCompare(String S, String T) {
        int i, j, k;
        char[] charS, charT;

        i = 0;
        j = 0;
        charS = new char[S.length()];
        charT = new char[T.length()];
        for(k = 0; k < S.length(); k++){
            if(S.charAt(k) == '#'){
                if(i > 0)
                    i--;
            }
            else
                charS[i++] = S.charAt(k);
        } 
        for(k = 0; k < T.length(); k++){
            if(T.charAt(k) == '#'){
                if(j > 0)
                    j--;
            }
            else{
                charT[j++] = T.charAt(k);
            }
        } 
        if(i != j)
            return false;
        for(k = 0; k < i; k++)
            if(charS[k] != charT[k])
                return false;
        return true;
    }
}

-問題28: 遞增順序查找樹

給定一個(gè)樹，按中序遍歷重新排列樹，使樹中最左邊的結(jié)點(diǎn)現(xiàn)在是樹的根淤齐，并且每個(gè)結(jié)點(diǎn)沒有左子結(jié)點(diǎn)，只有一個(gè)右子結(jié)點(diǎn)袜匿。

示例 ：

輸入：

[5,3,6,2,4,null,8,1,null,null,null,7,9]

輸出：

[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

提示：

2. 給定樹中的結(jié)點(diǎn)數(shù)介于 1 和 100 之間更啄。

3. 每個(gè)結(jié)點(diǎn)都有一個(gè)從 0 到 1000 范圍內(nèi)的唯一整數(shù)值。

-tags: 樹,算法,深度優(yōu)先搜索

-解答:

方法一：中序遍歷 + 構(gòu)造新的樹

我們在樹上進(jìn)行中序遍歷居灯，就可以從小到大得到樹上的節(jié)點(diǎn)祭务。我們把這些節(jié)點(diǎn)的對應(yīng)的值存放在數(shù)組中，它們已經(jīng)有序怪嫌。接著我們直接根據(jù)數(shù)組構(gòu)件題目要求的樹即可义锥。

class Solution {    
    public TreeNode increasingBST(TreeNode root) {
        List<Integer> vals = new ArrayList();
        inorder(root, vals);
        TreeNode ans = new TreeNode(0), cur = ans;
        for (int v: vals) {
            cur.right = new TreeNode(v);
            cur = cur.right;
        }
        return ans.right;
    }

    public void inorder(TreeNode node, List<Integer> vals) {
        if (node == null) return;
        inorder(node.left, vals);
        vals.add(node.val);
        inorder(node.right, vals);
    }
}

class Solution:
    def increasingBST(self, root):
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)

        ans = cur = TreeNode(None)
        for v in inorder(root):
            cur.right = TreeNode(v)
            cur = cur.right
        return ans.right

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(N)，其中 N 是樹上的節(jié)點(diǎn)個(gè)數(shù)岩灭。

• 空間復(fù)雜度：O(N)拌倍。

方法二：中序遍歷 + 更改樹的連接方式

和方法一類似，我們在樹上進(jìn)行中序遍歷噪径，但會(huì)將樹中的節(jié)點(diǎn)之間重新連接而不使用額外的空間柱恤。具體地，當(dāng)我們遍歷到一個(gè)節(jié)點(diǎn)時(shí)找爱，把它的左孩子設(shè)為空梗顺，并將其本身作為上一個(gè)遍歷到的節(jié)點(diǎn)的右孩子。

class Solution {
    TreeNode cur;
    public TreeNode increasingBST(TreeNode root) {
        TreeNode ans = new TreeNode(0);
        cur = ans;
        inorder(root);
        return ans.right;
    }

    public void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        node.left = null;
        cur.right = node;
        cur = node;
        inorder(node.right);
    }
}

class Solution:
    def increasingBST(self, root):
        def inorder(node):
            if node:
                inorder(node.left)
                node.left = None
                self.cur.right = node
                self.cur = node
                inorder(node.right)

        ans = self.cur = TreeNode(None)
        inorder(root)
        return ans.right

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(N)车摄，其中 N 是樹上的節(jié)點(diǎn)個(gè)數(shù)寺谤。

• 空間復(fù)雜度：O(H)，其中 H 是數(shù)的高度吮播。