分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
提示：
1 <= s.length <= 16
s 仅由小写英文字母组成
解题思路：像这种找路径的题目大多数是利用回溯去解决，所以关键点在于如何回溯；第二点，如何去判断子串是否是回文串，之前做过题的可能会有印象，利用双指针，但是利用双指针会出现重复计算。所以这里推荐使用动态规划，用 f(i, j) 表示 s.substr(i, j-i+1) 是否为回文串。
动态规划两个步骤：
- 初始化，初始状态是全设为 1
- 状态转移
- i < j 时：
f(i, j) = (s[i] == s[j]) && f(i+1, j-1); - i >= j 时：
f(i, j) = 1;
- i < j 时：
class Solution {
private:
vector<vector<int>> f;
vector<vector<string>> ret;
vector<string> ans;
int n;
public:
void dfs(const string& s, int i) {
if (i == n) {
ret.push_back(ans);
return;
}
for (int j = i; j < n; ++j) {
if (f[i][j]) {
ans.push_back(s.substr(i, j - i + 1));
dfs(s, j + 1);
ans.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
n = s.size();
f.assign(n, vector<int>(n, true));
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
}
}
dfs(s, 0);
return ret;
}
};
分割回文串 II
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：
输入：s = "a"
输出：0
示例 3：
输入：s = "ab"
输出：1
提示：
1 <= s.length <= 2000
s 仅由小写英文字母组成
解题思路，在上一题的基础上稍加修改即可(错误，超出时间限制)；
利用动态规划
- 用 g(i) 表示字符串的前缀 s.substr(0, i) 的最少分割次数。
- 初始化，g(i) = i-1; 也可以直接设为 INT_MAX；
- 状态转移
- g(i) = min{f(j)} + 1; 0 <= j < i, 且 s.substr(j+1, i - j) 是一个回文串。
- 当 s.substr(0, i) 就是一个回文字符串的时候， g(i) = 0;
判断是否为回文串利用上一道题中的动态规划思想， f(i, j) 表示 s.substr(i, j-i+1) 是否是回文串。
class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<int>> f;
f.assign(n, vector<int>(n, true));
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
}
}
vector<int> g(n, INT_MAX);
for (int i = 0; i < n; ++i) {
if (f[0][i]) {
g[i] = 0;
}
else {
for (int j = 0; j < i; ++j) {
if (f[j + 1][i]) {
g[i] = min(g[i], g[j] + 1);
}
}
}
}
return g[n - 1];
}
};
克隆图
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
class Node {
public int val;
public List<Node> neighbors;
}
测试用例格式：
简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。
邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。
给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。
解题思路：首先要明白题目的意思，意思就是拷贝一份，把给的所有节点重新生成并且构成相同的图。
利用广度搜索，对未出现拷贝的 node 进行拷贝，直到没有可拷贝的 node 为止。
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public:
Node* cloneGraph(Node* node) {
unordered_map<int, Node*> si;
queue<Node*> vn;
if(node != NULL) {
vn.push(node);
while(vn.size() != 0) {
for(int i = vn.size(); i > 0; --i) {
Node* no = vn.front();
vn.pop();
if(si.find(no->val) == si.end()) {
Node* tmp = new Node(no->val);
si[no->val] = tmp;
}
for(auto it = no->neighbors.begin(); it != no->neighbors.end(); ++it) {
if(si.find((*it)->val) == si.end()) {
vn.push(*it);
Node* tmp = new Node((*it)->val);
si[(*it)->val] = tmp;
}
si[no->val]->neighbors.push_back(si[(*it)->val]);
}
}
}
}
return si[1];
}
};
加油站
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
说明:
如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。
示例 1:
输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
示例 2:
输入:
gas = [2,3,4]
cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
解题思路：因为需要绕环路行驶一周，所以可以遍历 gas 数组， 从可以开始的节点(gas[i] >= cost[i])开始测试是否能成功。
class Solution {
public:
bool startTrans(vector<int>& gas, vector<int>& cost, int startPoi) {
int remainGas = 0;
// [startPoi, gas.size() - 1]
for(int i = startPoi; i < gas.size(); ++i) {
remainGas = remainGas + gas[i] - cost[i];
if(remainGas < 0) return false;
}
//[0, startPoi)
for(int i = 0; i < startPoi; ++i) {
remainGas = remainGas + gas[i] - cost[i];
if(remainGas < 0) return false;
}
return true;
}
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int res = -1;
for(int i = 0; i < gas.size(); ++i) {
if(gas[i] >= cost[i] && startTrans(gas, cost, i)) {
res = i;
break;
}
}
return res;
}
};
分发糖果
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
- 每个孩子至少分配到 1 个糖果。
- 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
示例 1：
输入：[1,0,2]
输出：5
解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2：
输入：[1,2,2]
输出：4
解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
解题思路：从直线中的最小且没有被分配到糖果开始，依次从左到右分配。这是最容易想出来的办法，也是比较让人理解且容易实现的分配方法。
看了一下题解，可以利用贪心算法，左右两边分别遍历一次即可得到答案。
class Solution {
public:
int candy(vector<int>& ratings) {
multimap<int, int> access;
vector<int> candy;
candy.assign(ratings.size(), -1);
for(int i = 0; i < ratings.size(); ++i) {
access.insert(make_pair(ratings[i], i));
}
for(auto m : access) {
if(candy[m.second] == -1) {
candy[m.second] = 1;
for(int i = m.second - 1; i >= 0; --i) {
if(ratings[i] <= ratings[i+1]) break;
candy[i] = max(candy[i+1] + 1, candy[i]);
}
for(int i = m.second + 1; i < ratings.size(); ++i) {
if(ratings[i] <= ratings[i-1]) break;
candy[i] = max(candy[i-1] + 1, candy[i]);
}
}
}
return accumulate(candy.begin(), candy.end(), 0);
}
};
只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
解题思路：首先看题目的要求，线性时间复杂度（排除排序），不使用额外的空间（排除set， map等标记方案）。
然后根据题目的意思，需要找出非成对出现的元素，那么问题就变成了如何消除成对的元素，也就是在遍历数组的时候成对的数组能够被消除。
即有没有一种运算能够让两个元素相等时的结果为 0，并且这个运算得要满足交换律和结合律。
说实话这个想到确实不容易，四则运算肯定是不符合的。但是作为计算机从业者，要从 01 看问题，对于 01 的操作，取反，与，或，异或运算，左移右移也得考虑。
所以答案就是异或，异或运算满足要求。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
};
只出现一次的数字 II
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
示例 1：
输入：nums = [2,2,3,2]
输出：3
示例 2：
输入：nums = [0,1,0,1,0,1,99]
输出：99
提示：
1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
解题思路：因为是和上一题类似，所以如果是要满足题目的任何要求的话，是拒绝使用排列以及map等方法的。那么可以想到的就是继续利用位运算来解决。
那么如何去利用位运算去解决呢？这就要提到数字电路逻辑的知识点了，也就是门电路和真值表相关的知识。
思路就是记录当前累加结果某一位当前的数值，因为数组中的元素除了结果外，其他的元素都会出现三次。可以知道，如果用位运算，最后的结果也是只会有0或者1，但是在累加的过程中，可能会出现大于 1 的值，而且该值 = (0 + 3 * i) 或者 (1 + 3 * i), i >= 0;
用 a 和 b 在第 i 位共同组成累加结果在第 i 位除以3的余数(因为在某一位上可能会有0， 1， 2) 所以必须要要有两位去表示。
- a 的第 i 位为 0 且 b 的第 i 位为 0，表示 0；
- a 的第 i 位为 0 且 b 的第 i 位为 1，表示 1；
- a 的第 i 位为 1 且 b 的第 i 位为 0，表示 2。
可以得到真值表：(用 cd 表示 ab 经过 x 的值)
| ab | x | cd |
|---|---|---|
| 00 | 0 | 00 |
| 00 | 1 | 01 |
| 01 | 0 | 01 |
| 01 | 1 | 10 |
| 10 | 0 | 10 |
| 10 | 1 | 00 |
然后根据真值表可以得到逻辑电路： c = (a’bx) + (ab’x’) d = (a’b’x) + (a’bx’) = a’(b ⊕ x)
更简单的逻辑电路为：(利用 d 去推 c) c = (d’a’x) + (d’ax’) = d’(a ⊕ x)
class Solution {
public:
int singleNumber(vector<int>& nums) {
int a = 0, b = 0;
for(auto num : nums) {
b = ~a & (b ^ num);
a = ~b & (a ^ num);
}
return b;
}
};
复制带随机指针的链表
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random –> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random –> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
解题思路：和之前的克隆图是一样的类型，利用 map + 遍历搜索。遍历原先的链表，对每个节点 next 和 random 进行判断是否存在，然后建立连接。
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
unordered_map<Node*, Node*> mnn;
mnn[NULL] = NULL;
Node* scan = head;
while(scan != NULL) {
if(mnn.find(scan) == mnn.end()) {
Node* tmp = new Node(scan->val);
mnn[scan] = tmp;
}
if(mnn.find(scan->next) == mnn.end()) {
Node* tmp = new Node(scan->next->val);
mnn[scan->next] = tmp;
}
mnn[scan]->next = mnn[scan->next];
if(mnn.find(scan->random) == mnn.end()) {
Node* tmp = new Node(scan->random->val);
mnn[scan->random] = tmp;
}
mnn[scan]->random = mnn[scan->random];
scan = scan->next;
}
return mnn[head];
}
};
单词拆分
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。 ``` 示例 1：
输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。
示例 2：
输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。 注意你可以重复使用字典中的单词。
示例 3：
输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] 输出: false
解题思路：刚开始的想法就是利用 map 记录 wordDict 中每个单词在字符串 s 出现的起始位置，然后 dfs map。但是超时了，果断放弃。
利用动态规划，定义 dp[i] 表示 s.substr(0, i) 能否被拆分。
初始化： dp[0] = true, 表示空字符串是能被拆分的。
动态转移： dp[j] = dp[i] && s.substr(i, j-i) 在字典存在。
```cpp
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordList;
for(auto word : wordDict) {
wordList.insert(word);
}
vector<bool> dp(s.size() + 1, false);
dp[0] = true;
for(int i = 0; i < s.size(); ++i) {
for(int j = i + 1; j < s.size() + 1; ++j) {
if(dp[i] && wordList.find(s.substr(i, j-i)) != wordList.end()) {
dp[j] = true;
}
}
}
return dp[s.size()];
}
};
单词拆分 II
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
- 分隔时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例 1：
输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
"cats and dog",
"cat sand dog"
]
示例 2：
输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。
示例 3：
输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]
解题思路，因为动态规划无法记录路径，所以需要打印路径的时候，我们可以利用回溯的方法去解决。
但是貌似我在做的时候测试用例改过了？因为就是普普通通的暴力回溯就通过了。。。一脸懵逼。
class Solution {
public:
unordered_set<string> wordList;
vector<string> res;
string path;
void dfs(string s) {
// cout << s << " " << path << endl;
if(s.size() == 0) {
res.push_back(path.substr(0, path.size()-1));
}
for(int i = 0; i <= s.size(); ++i) {
if(wordList.find(s.substr(0, i)) != wordList.end()) {
path = path.append(s.substr(0, i));
path = path.append(" ");
dfs(s.substr(i, s.size()-i));
path = path.substr(0, path.size()-i-1);
}
}
}
vector<string> wordBreak(string s, vector<string>& wordDict) {
wordList = unordered_set(wordDict.begin(), wordDict.end());
dfs(s);
return res;
}
};
