# 程序员进阶之算法练习（三十二）LeetCode专场

### 正文

#### Copy List with Random Pointer

```class Solution {
public:
RandomListNode *ret = NULL;
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;
}
while (p) {
if (p->random) {
ret->random = hashMap[p->random];
}
p = p->next;
ret = ret->next;
}
}
};```

#### Insert Interval

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].

```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;```

#### Word Break

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

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

```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;```

#### Word Break II

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

```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

O(1)表示存储的数据结构只能用数组或者hash加链表的方式。 数组的读取是O(1)，但是增删是O(N)的操作； hash+链表的方式较为符合题目的要求，可以实现大致O(1)的查找，也可以实现O(1)的增删操作； 基于此数据结构，我们可以延伸出以下的解法： 1、使用双向链表存储每个key和value； 2、每次get、set已有节点时，把节点放到链表的最前面； 3、每次set的时候如果size已经达到限制，则去掉尾部节点，然后在头部增加节点；

0 条评论

• ### leetcode––为求职为生的编程网站

前言 leetcode是一个在线编程网站，题目源于各大公司的面试、有各种解法、多语言和在线测试支持； 我们扫一眼leetcode上的Company：Googl...

• ### 程序员进阶之算法练习（十七）

前言 正文6道题目来自leetcode––为求职为生的编程网站，目的是工作闲暇之时锤炼代码功底。 如何从这篇文章受益？ 先看题目大意，对照Example的样...

• ### iOS开发笔记（十）— Xcode、UITabbar、特殊机型问题分析

【问题分析】通过多个文件尝试，发现并非完全不能索引头文件，而是只能索引和当前文件在同级目录的头文件； 有点猜测是Xcode10.1的原因，但是在升级完的半年多...

• ### Deep visual domain adaptation: A survey

深度视觉域适配作为一个解决大量标注数据缺失的新的学习技巧而出现。与传统的学习共享特征子空间或使用浅层表示重用重要源实例的方法相比，深度域适应方法通过将域适应嵌入...

• ### Python有趣时刻，这些代码让你大呼"

不知道大家第一眼看了这个代码，什么感受？我第一眼的感受是密密麻麻一大堆，读都不想读

• ### 在Windows商店应用中使用浅色主题

在开发商店应用时会遇到这样的情况，设计师给我们的设计是浅色背景/深色文本，而商店应用默认是深色背景/浅色文本。那我们需要在每个页面去显式声明背景色和前景色吗，这...

• ### 【leetcode】String to Integer (atoi)

Implement atoi to convert a string to an integer.

• ### 【玩转腾讯云】3分钟打造个人专属云盘，速度吊打某云盘

②选择自定义配置——计费模式为“按量付费”——地域选择“北京”——可用区选择“随机可用区”——网络选择“默认”即可

• ### 简单几步，利用Serverless，让COS中文件变更自动刷新CDN

SCF能实现事件式的触发，让你的一段代码跑在云上，无需自己去搭建服务器。而这里我们要利用能力：COS文件上传/删除的触发器。

• ### 微信小程序 this.getOpenerEventChannel is not a function

小程序 添加新的功能， 页面跳转后，通过事件的发布订阅，实现 from => to 或者 to=> from 数据传递