程序员进阶之算法练习（三十二）LeetCode专场
正文
Copy List with Random Pointer
题目链接 题目大意： 给出一个链表RandomListNode *next, *random; 每个节点有int值，有两个指针，一个指向下一个节点，一个指向链表的任意节点； 现在实现一个深度复制，复制节点的next、random、还有int值；
题目解析： 要求的是复制所有的值，其中的next、int是常规值，遍历一遍赋值即可； 较为复杂的是random指针的复制，random指针有可能指向上一个节点，也可能指向下一个节点，在赋值的时候要保持对应的关系； 这里可以用hash解决，我们把旧链表和新链表的节点一一对应，比如说oldList[i]=>newList[i]； 那么如果random指针指向oldList[i]，相当于新链表指向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];;
}
};复杂度解析： 时间复杂度是O(N) 空间复杂度是O(N)
Insert Interval
题目链接 题目大意： 给出n个不重叠的区间[x, y]，并且按照起始坐标x进行从小到大的排序； 现在新增一个区间[a, b]，为了保持区间不重叠，对区间进行merge，问剩下的区间有哪些；
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].
题目解析： 最直接的做法是对所有区间进行处理，分情况讨论： 1、区间[x, y]与[a, b] 无重叠，则不变换； 2、区间[x, y]与[a, b] 有部分重叠，则拿出来特殊处理； 最后从情况2的所有区间和[a, b]中找到一个区间的起始最小值、结束最大值，作为新的区间。
但是这样的代码复杂度比较高，更简洁的做法可以是： 1、把区间[a, b]放入n个区间中，按起始和结束位置从小到大排序； 2、如果区间i的起始位置<=区间i-1的结束位置，则认为是一个区间；
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;复杂度解析： 方法1 时间复杂度是O(N) 空间复杂度是O(N)
方法2 时间复杂度是O(NLogN) 空间复杂度是O(N)
Word Break
题目链接 题目大意： 给出原串s，字符串数组dict，要求： 1、把s分成多个连续的子串； 2、每个子串都在dict里面； 问，是否有解。
s = "leetcode", dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
题目解析： 把一个串分成2个串的可能性有n种可能，n是字符串长度。 那么对于串[l, r] 如果[l, k] 和 [k+1, r]是合法的，那么[l, r]也是合法的。 故而用动态规划： dp[i][j] 表示字符串[i, j]是否为合法的子串； 枚举k∈[i, j] 来判断分割字符串的位置； 转移转移是O(N)，因为需要判断区间[i, k]和[k+1, j]是否合法（用字典数配合）； 最后判断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;复杂度解析： 时间复杂度 O(N^3) N^2的状态* N的字典数判断。 空间复杂度 O(N^2+M) N^2是状态数量，M是字典数；
优化方案： 1、dp用1维表示；dp[i] 表示前i个是否合理，转移的时候dp[i]=dp[k] && substr(k+1, i) 2、判断substr是否存在时，可以用字典数；
Word Break II
题目链接 在前文Word Break的基础上，输出所有的解。
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
题目链接 题目大意： 实现一个最近最少使用的缓存算法，要求： get(key) - 返回缓存中key对应的值，如果没有存在缓存，返回-1； set(key, value) - 设置缓存中的key对应的value； 缓存有固定大小。
题目解析： 缓存需要维护两个信息， 1是key和value的对应； 2是value的有效时间； 时间是从小到大，每次会把一个大的值插入（新值），同时可能删掉旧值；（命中） 那么维护一个value的有效时间，优先队列；
这种做法，单次操作的时间复杂度是O(LogN)，和题目要求的O(1)有较大的差距；
O(1)表示存储的数据结构只能用数组或者hash加链表的方式。 数组的读取是O(1)，但是增删是O(N)的操作； hash+链表的方式较为符合题目的要求，可以实现大致O(1)的查找，也可以实现O(1)的增删操作； 基于此数据结构，我们可以延伸出以下的解法： 1、使用双向链表存储每个key和value； 2、每次get、set已有节点时，把节点放到链表的最前面； 3、每次set的时候如果size已经达到限制，则去掉尾部节点，然后在头部增加节点；
接下来的问题是如何实现O(1)的读取，O(1)的大小判断，以及O(1)的链表移动； O(1)的读取，我们引入unordered_map，然后每次根据key去获取当前节点；（unordered_map 比 map 更快） O(1)的增删操作，我们通过list.splice函数实现；（因为是双向链表，O(1)的增删并不难实现） O(1)的大小判断，list获取size是O(N)的复杂度，所以我们引入一个变量curSize来记录当前节点数量；
总结
从简单的指针复制和区间重叠处理，再到分词、LRU实现，LeetCode的题目更适合面试，这次的题目准备既是为自己练习，也是为了方便后续面试。