前言

BAT常見的算法面試題解析：
程序員算法基礎(chǔ)——?jiǎng)討B(tài)規(guī)劃
程序員算法基礎(chǔ)——貪心算法
工作閑暇也會(huì)有在線分享，算法基礎(chǔ)教程----騰訊課堂地址敞咧。
今天是LeetCode專場練習(xí)盐捷。

正文

Copy List with Random Pointer

題目鏈接
題目大意：
給出一個(gè)鏈表RandomListNode *next, *random;
每個(gè)節(jié)點(diǎn)有int值偶翅，有兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)碉渡，一個(gè)指向鏈表的任意節(jié)點(diǎn)聚谁；
現(xiàn)在實(shí)現(xiàn)一個(gè)深度復(fù)制，復(fù)制節(jié)點(diǎn)的next滞诺、random形导、還有int值；

題目解析：
要求的是復(fù)制所有的值习霹，其中的next朵耕、int是常規(guī)值，遍歷一遍賦值即可淋叶；
較為復(fù)雜的是random指針的復(fù)制阎曹，random指針有可能指向上一個(gè)節(jié)點(diǎn)，也可能指向下一個(gè)節(jié)點(diǎn)，在賦值的時(shí)候要保持對(duì)應(yīng)的關(guān)系芬膝；
這里可以用hash解決，我們把舊鏈表和新鏈表的節(jié)點(diǎn)一一對(duì)應(yīng)形娇，比如說oldList[i]=>newList[i]锰霜；
那么如果random指針指向oldList[i]，相當(dāng)于新鏈表指向newList[i]桐早；

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *ret = NULL;
        RandomListNode *p = head;
        unordered_map<RandomListNode *, RandomListNode *> hashMap;
        while (p) {
            RandomListNode *node = new RandomListNode(p->label);
            hashMap[p] = node;
            if (ret) {
                ret->next = node;
            }
            ret = node;
            p = p->next;
        }
        p = head;
        ret = hashMap[head];
        while (p) {
            if (p->random) {
                ret->random = hashMap[p->random];
            }
            p = p->next;
            ret = ret->next;
        }
        return hashMap[head];;
    }
};

復(fù)雜度解析：
時(shí)間復(fù)雜度是O(N)
空間復(fù)雜度是O(N)

Insert Interval

題目鏈接
題目大意：
給出n個(gè)不重疊的區(qū)間[x, y]癣缅，并且按照起始坐標(biāo)x進(jìn)行從小到大的排序；
現(xiàn)在新增一個(gè)區(qū)間[a, b]哄酝，為了保持區(qū)間不重疊友存，對(duì)區(qū)間進(jìn)行merge，問剩下的區(qū)間有哪些陶衅；

Example:
**Input: **intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

題目解析：
最直接的做法是對(duì)所有區(qū)間進(jìn)行處理屡立，分情況討論：
1、區(qū)間[x, y]與[a, b] 無重疊搀军，則不變換膨俐；
2、區(qū)間[x, y]與[a, b] 有部分重疊罩句，則拿出來特殊處理焚刺；
最后從情況2的所有區(qū)間和[a, b]中找到一個(gè)區(qū)間的起始最小值、結(jié)束最大值门烂，作為新的區(qū)間乳愉。

但是這樣的代碼復(fù)雜度比較高，更簡潔的做法可以是：
1屯远、把區(qū)間[a, b]放入n個(gè)區(qū)間中蔓姚，按起始和結(jié)束位置從小到大排序；
2慨丐、如果區(qū)間i的起始位置<=區(qū)間i-1的結(jié)束位置赂乐，則認(rèn)為是一個(gè)區(qū)間；

bool cmp(Interval a, Interval b) {
   if (a.start != b.start) {
       return a.start < b.start;
   }
   else {
       return b.end < a.end;
   }
}
class Solution {
public:
   vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
       intervals.push_back(newInterval);
       if (intervals.empty()) return vector<Interval>{};
       vector<Interval> ret;
       sort(intervals.begin(), intervals.end(), cmp);
       ret.push_back(intervals[0]);
       for (int i = 1; i < intervals.size(); ++i) {
           if (ret.back().end < intervals[i].start) { // 新的段
               ret.push_back(intervals[i]);
           }
           else {
               ret.back().end = max(ret.back().end, intervals[i].end);
           }
       }
       return ret;
   }
}leetcode;

復(fù)雜度解析：
方法1
時(shí)間復(fù)雜度是O(N)
空間復(fù)雜度是O(N)

方法2
時(shí)間復(fù)雜度是O(NLogN)
空間復(fù)雜度是O(N)

Word Break

題目鏈接
題目大意：
給出原串s咖气，字符串?dāng)?shù)組dict挨措，要求：
1、把s分成多個(gè)連續(xù)的子串崩溪；
2浅役、每個(gè)子串都在dict里面；
問伶唯，是否有解觉既。

s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

題目解析：
把一個(gè)串分成2個(gè)串的可能性有n種可能，n是字符串長度。
那么對(duì)于串[l, r] 如果[l, k] 和 [k+1, r]是合法的瞪讼，那么[l, r]也是合法的钧椰。
故而用動(dòng)態(tài)規(guī)劃：
dp[i][j] 表示字符串[i, j]是否為合法的子串；
枚舉k∈[i, j] 來判斷分割字符串的位置符欠；
轉(zhuǎn)移轉(zhuǎn)移是O(N)嫡霞，因?yàn)樾枰袛鄥^(qū)間[i, k]和[k+1, j]是否合法（用字典數(shù)配合）；
最后判斷dp[1, n]是否合法希柿。

class Solution {
public:
    bool dp[N];
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet;
        for (int i = 0; i < wordDict.size(); ++i) {
            wordSet.insert(wordDict[i]);
        }
        memset(dp, 0, sizeof(dp));
        dp[0] = true;
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (dp[j]) {
                    string substr = string(s.begin() + j, s.begin() + i);
                    if (wordSet.find(substr) != wordSet.end()) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        return dp[s.size()];
    }
}leetcode;

復(fù)雜度解析：
時(shí)間復(fù)雜度
O(N^3) N^2的狀態(tài)* N的字典數(shù)判斷诊沪。
空間復(fù)雜度
O(N^2+M) N^2是狀態(tài)數(shù)量，M是字典數(shù)曾撤；

優(yōu)化方案：
1端姚、dp用1維表示；dp[i] 表示前i個(gè)是否合理挤悉，轉(zhuǎn)移的時(shí)候dp[i]=dp[k] && substr(k+1, i)
2渐裸、判斷substr是否存在時(shí)，可以用字典數(shù)装悲；

Word Break II

題目鏈接
在前文Word Break的基礎(chǔ)上橄仆，輸出所有的解。

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
"cats and dog",
"cat sand dog"
]

題目解析：
用vector來存可能的解衅斩，然后用dfs來輸出即可盆顾。

class Solution {
public:
    vector<int> g[N];
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        vector<string> ret;
        unordered_set<string> wordSet;
        for (int i = 0; i < wordDict.size(); ++i) {
            wordSet.insert(wordDict[i]);
        }
        vector<bool> dp(s.length() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (dp[j]) {
                    string substr = string(s.begin() + j, s.begin() + i);
                    if (wordSet.find(substr) != wordSet.end()) {
                        //                        cout << i << " " << j << " " << substr << endl;
                        dp[i] = true;
                        g[i].push_back(j);
                    }
                }
            }
        }
        vector<string> cur;
        if (dp[s.length()]) {
            dfs(s, ret, cur, s.length());
        }
        return ret;
    }
    
    void dfs(string &s, vector<string> &ret, vector<string> &cur, long n) {
        for (int i = 0; i < g[n].size(); ++i) {
            string str = string(s.begin() + g[n][i], s.begin() + n);
            cur.push_back(str);
            dfs(s, ret, cur, g[n][i]);
            cur.pop_back();
        }
        if (n == 0) {
            string str = cur.back();
            for (int i = cur.size() - 2; i >= 0; --i) {
                str += string(" ");
                str += cur[i];
            }
//            cout << str << endl;
            ret.push_back(str);
        }
    }
}leetcode;

LRU Cache

題目鏈接
題目大意：
實(shí)現(xiàn)一個(gè)最近最少使用的緩存算法，要求：
get(key) - 返回緩存中key對(duì)應(yīng)的值畏梆，如果沒有存在緩存您宪，返回-1；
set(key, value) - 設(shè)置緩存中的key對(duì)應(yīng)的value奠涌；
緩存有固定大小宪巨。

題目解析：
緩存需要維護(hù)兩個(gè)信息，
1是key和value的對(duì)應(yīng)溜畅；
2是value的有效時(shí)間捏卓；
時(shí)間是從小到大，每次會(huì)把一個(gè)大的值插入（新值）慈格，同時(shí)可能刪掉舊值怠晴；（命中）
那么維護(hù)一個(gè)value的有效時(shí)間，優(yōu)先隊(duì)列浴捆；

這種做法蒜田，單次操作的時(shí)間復(fù)雜度是O(LogN)，和題目要求的O(1)有較大的差距选泻；

O(1)表示存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)只能用數(shù)組或者h(yuǎn)ash加鏈表的方式冲粤。
數(shù)組的讀取是O(1)美莫，但是增刪是O(N)的操作；
hash+鏈表的方式較為符合題目的要求梯捕，可以實(shí)現(xiàn)大致O(1)的查找厢呵，也可以實(shí)現(xiàn)O(1)的增刪操作；
基于此數(shù)據(jù)結(jié)構(gòu)傀顾，我們可以延伸出以下的解法：
1襟铭、使用雙向鏈表存儲(chǔ)每個(gè)key和value；
2锣笨、每次get、set已有節(jié)點(diǎn)時(shí)道批，把節(jié)點(diǎn)放到鏈表的最前面错英；
3、每次set的時(shí)候如果size已經(jīng)達(dá)到限制隆豹，則去掉尾部節(jié)點(diǎn)椭岩，然后在頭部增加節(jié)點(diǎn)；

接下來的問題是如何實(shí)現(xiàn)O(1)的讀取璃赡，O(1)的大小判斷判哥，以及O(1)的鏈表移動(dòng)；
O(1)的讀取碉考，我們引入unordered_map塌计，然后每次根據(jù)key去獲取當(dāng)前節(jié)點(diǎn)；（unordered_map 比 map 更快）
O(1)的增刪操作侯谁，我們通過list.splice函數(shù)實(shí)現(xiàn)锌仅；（因?yàn)槭请p向鏈表，O(1)的增刪并不難實(shí)現(xiàn)）
O(1)的大小判斷墙贱，list獲取size是O(N)的復(fù)雜度热芹，所以我們引入一個(gè)變量curSize來記錄當(dāng)前節(jié)點(diǎn)數(shù)量；

總結(jié)

從簡單的指針復(fù)制和區(qū)間重疊處理惨撇，再到分詞伊脓、LRU實(shí)現(xiàn)，LeetCode的題目更適合面試魁衙，這次的題目準(zhǔn)備既是為自己練習(xí)报腔，也是為了方便后續(xù)面試。