st

st
2019-03-02 23:29

### 题目描述

#### 样例

Example 1:

Example 2:

Example 3:



### 算法1

##### (brute force with recursion) $O(n^n)$

check every possible prefix of that string in the dictionary of words, if it is found in the dictionary, then the recursive function is called for the remaining portion of that string.

base case: if in some function call it is found that the complete string is in dictionary, then it will return true.

#### C++ 代码

class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
if(wordDict.size()==0) return false;
set<string> _wordDict;
for(auto &x: wordDict){
_wordDict.insert(x);
}
return _wordBreak(s, _wordDict, 0);
}
bool _wordBreak(string s, set<string> _wordDict, int start){
if(start == s.length())
return true;
for(int j = 0; start + j <= s.length(); j++){
if(_wordDict.count(s.substr(start, j)) && _wordBreak(s, _wordDict, start + j)){
return true;
}
}
return false;
}
};
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
return _wordBreak(s, wordDict, 0);
}
bool _wordBreak(string s, vector<string> wordDict, int start){
if(start == s.length())
return true;
for(auto w: wordDict){
int end = start + w.size()-1;
if(end < s.length() && s.substr(start, w.size()) == w){
if(start + w.size() == s.length())
return true;
else if(_wordBreak(s, wordDict, end+1))
return true;
}
}
return false;
}
};



### 算法2

##### (Recursion with memoization) $O(n^2)$

use a set memo to store the false subproblems so that when the recursive function is called with a case we have eevaluated before, we can directly return false without redundant calculation.

the prefix must be true then the recursive function is called. there is no need to store the end index returning true.

#### C++ 代码

class Solution {
public:
vector<string> _wordDict;
set<int> vis;
bool wordBreak(string s, vector<string>& wordDict) {
_wordDict = wordDict;
return _wordBreak(s, 0);
}
bool _wordBreak(string s, int start){
for(auto &w: _wordDict){
int end = start + w.length()-1;
if(end < s.length() && s.substr(start, w.size()) == w){
if(start + w.size() == s.size())
return true;
else if(vis.find(end) != vis.end())
return false;
else if(_wordBreak(s, end+1))
return true;
else vis.insert(end);
}
}
return false;
}
};


### 算法3

##### (bfs) $O(n^2)$

Think the string as a tree, where each node is a prefix/word. Two nodes are connected only if the two words are included in the dict.

The traverse start from the first character of the string and find every possible substring starting with that character. The end index of each word would be pushed in the queue.

If we are able to obtain the last element of the given string as a node (leaf) of the tree, this implies that the given string can be partitioned into substrings which are all a part of the given dictionary.

Use a memo to store some results otherwise would TLE.

#### C++ 代码

// bfs
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
queue<int> prefixQ;
set<int> vis; //memo
prefixQ.push(0);
while(!prefixQ.empty()){
int start = prefixQ.front();
prefixQ.pop();
if(vis.find(start) == vis.end()){
for(auto w: wordDict){
int end = start + w.size()-1;
if(end < s.length() && s.substr(start, w.size()) == w){
if(start + w.size() == s.size())
return true;
else {
prefixQ.push(end+1);
}
}
}
vis.insert(start);
}
}
return false;
}
};


### 算法4

dp 隔板

#### C++ 代码


// dp
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
set<string> _wordDict(wordDict.begin(), wordDict.end());
vector<bool> dp(s.size()+1, false);
dp[0] = true;
for(int i = 0; i <= s.size(); i++){
for(int j = i; j >= 0; j--){
if(dp[j]){
string word = s.substr(j,i-j);
if(_wordDict.find(word)!= _wordDict.end()){
dp[i]=true;
break;
}
}

}
}
return dp[s.size()];
}
};



st
2019-03-01 23:32

### 算法1

##### (recursive) $O(n^2)$

intuitively, 这个每个node有多个指针的链表很像一个图，所以最先想到的是图的遍历。用dfs recursively traverse这个图，clone每一个node。只不过->child这里是->next和->random。

#### C++ 代码

/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;

Node() {}

Node(int _val, Node* _next, Node* _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public:
unordered_map<Node*, Node*> visHash; //assigned outside otherwise stackoverflow
return NULL;
Node* root = new Node(head->val, NULL, NULL);
return root;
}
};


### 算法2

##### (iterative) $O(n)$

link the nodes inside the hash table

#### C++ 代码

/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;

Node() {}

Node(int _val, Node* _next, Node* _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public:
unordered_map<Node*, Node*> hash;
return NULL;
Node* root = new Node(head->val, NULL, NULL);
}
}
}
}

return root;

}
};


### 算法3

##### (iterative with O(1) space) $O(n)$

1.copy each node. insert the copy node next to the corresponding original one.
2.traverse the list, copy the random ptr
3.restore the original list and return the new one

#### C++ 代码

/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;

Node() {}

Node(int _val, Node* _next, Node* _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public:
Node* l1, *l2, *root;
for(l1 = head; l1 ; l1 = l1->next->next){
l2 = new Node(l1->val, NULL, NULL);
l2->next = l1->next;
l1->next = l2;
}
for(l1 = head; l1; l1 = l1->next->next){
if(l1->random){
l1->next->random = l1->random->next;
}
}
for(l1 = head; l1;l1 = l1->next){
l2 = l1->next;
l1->next = l2->next;
if(l2->next)
l2->next = l2->next->next;
}
return root;
}
};


st
2019-03-01 07:22

### 题目描述

#### 样例

给定数组 nums = [-1, 0, 1, 2, -1, -4]，返回 [ [-1, 0, 1], [-1, -1, 2] ]。


### 算法0

#### C++ 代码

blablabla


### 算法1

#### C++ 代码

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
unordered_set<int> hash;
sort(nums.begin(), nums.end());
for (int st = 0; st < nums.size(); st++) {
int n = nums.size();
while (st > 0 && st < n && nums[st] == nums[st - 1])
st++;
hash.clear();
for (int i = st + 1; i < nums.size(); i++) {
unordered_set<int>::const_iterator got = hash.find(- nums[st] - nums[i]);
if (got == hash.end())
hash.insert(nums[i]);
else {
res.push_back({nums[st], nums[i], - nums[st] - nums[i]});
hash.erase(nums[i]);
while(i > 0 && i < n-1 && nums[i+1] == nums[i]) i++;
}
}
}
return res;
}
};



### 算法2

#### C++ 代码

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
unordered_set<int> hash, vis;
sort(nums.begin(), nums.end());

for (int st = 0; st < nums.size(); st++) {
while (st > 0 && st < nums.size() && nums[st] == nums[st - 1])
st++;
hash.clear();
vis.clear();
for (int i = st + 1; i < nums.size(); i++) {
unordered_set<int>::const_iterator got = hash.find(- nums[st] - nums[i]);
if (got == hash.end())
hash.insert(nums[i]);
else {
res.push_back({nums[st], nums[i], - nums[st] - nums[i]});
vis.insert(- nums[st] - nums[i]);
}
if (vis.find(- nums[st] - nums[i]) != vis.end())
hash.erase(- nums[st] - nums[i]);
}
}
return res;
}
};



### 算法3

#### C++ 代码

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
for (int i=0; i<nums.size(); i++) {
if ((i>0) && (i<nums.size()) && (nums[i]==nums[i-1]))
continue;
int l = i+1, r = nums.size()-1;
while (l<r) {
int s = nums[i]+nums[l]+nums[r];
if (s>0) r--;
else if (s<0) l++;
else {
res.push_back(vector<int> {nums[i], nums[l], nums[r]});
while (l<r && nums[l]==nums[l+1]) l++;
while (l<r && nums[r]==nums[r-1]) r--;
l++; r--;
}
}
}
return res;
}
};



st
2019-02-28 21:16

### 题目描述

#### 样例

输入："babad"



### 算法0

#### C++ 代码

blablabla


### 算法1

#### C++ 代码

blablabla


### 算法2

##### (dp) $O(n^2)$

p(i, j) reperesent whether the substring between i and j (inclusive) is a palindrome.

transition function: p(i, j) = p(i+1, j-1) && (s[i] == s[j])
base case: p(i, i) = true; p(i, i+1) = (s[i] == s[i+1]);

#### C++ 代码


class Solution {
public:
string maxStr = "";
string longestPalindrome(string s) {
if(!s.length())
return maxStr;
if(s.length()==1)
return s;
int n = s.length();
bool p[n][n] = {false};
for(int i = 0; i < n-1; i++){
p[i][i] = true;
p[i][i+1] = (s[i] == s[i+1]);
}
p[n-1][n-1] = true;
p[n-2][n-1] = (s[n-2] == s[n-1]);
for(int j = 2; j < n; j++){
for(int i = j-2; i >= 0; i--){
p[i][j] = (p[i+1][j-1] && s[i] == s[j]);
}
}
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
if(p[i][j] && (j-i+1 > maxStr.length())){
printf("pij = %d %d %d \n", i, j, p[i][j]);
maxStr = s.substr(i, j-i+1);
}
}
}
return maxStr;
}
};



### 算法3

#### C++ 代码

class Solution {
public:
string maxStr = "";
string longestPalindrome(string s) {
if(!s.length() || s.length()==1) return s;
for(int i = 0; i < s.size(); i++){
for(int j = 0; i-j>=0 && i+j<s.length(); j++){
if(s[i-j] == s[i+j]){
//printf("i-j= %d, i+j= %d\n", i-j, i+j);
//printf("i = %d, j = %d\n", i, j);
if(j*2+1 > maxStr.length())
maxStr = s.substr(i-j, j*2+1);
}
else break;

}
for(int j = 0; i-j>=0 && i+1+j<s.length(); j++){
if(s[i] == s[i+1] && s[i-j] == s[i+1+j]){
if (j*2+2 > maxStr.length())
maxStr = s.substr(i-j, j*2+2);
}
else break;

}
}
return maxStr;
}
};


### 算法4

#### C++ 代码

class Solution {
public:
string longestPalindrome(string s)
{
string T;// Transform S to T
for(int i=0;i<s.size();i++)
T+="#"+s.substr(i,1);
T.push_back('#');

vector<int> P(T.size(),0); // Array to record longest palindrome
int center=0,boundary=0,maxLen=0,resCenter=0;
for(int i=1;i<T.size()-1;i++) {
int iMirror=2*center-i; // calc mirror i = center-(i-center)
P[i]=(boundary>i)?min(boundary-i,P[iMirror]):0; // shortcut
while(i-1-P[i]>=0&&i+1+P[i]<=T.size()-1&&T[i+1+P[i]] == T[i-1-P[i]]) // Attempt to expand palindrome centered at i
P[i]++;
if(i+P[i]>boundary) { // update center and boundary
center = i;
boundary = i+P[i];
}
if(P[i]>maxLen) { // update result
maxLen = P[i];
resCenter = i;
}
}
return s.substr((resCenter - maxLen)/2, maxLen);
}
};


st
2019-02-28 08:59

### 题目描述

#### 样例

给定 "abcabcbb"，答案是"abc"，长度是3.



### 算法1

#### C++ 代码

// brute force
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int maxLen = 0;
if(!s.size())
return maxLen;
for(int i = 0; i < s.size(); i++){
for(int j = 0; j < s.size(); j++){
if(isUniq(s, i, j))
maxLen = max(maxLen, j-i+1);
}
}
return maxLen;
}
bool isUniq(string s, int start, int end){
set<char> uniqSet;
for(int i = start; i <= end; i++){
if(uniqSet.count(s[i]))
return false;
uniqSet.insert(s[i]);
}
return true;
}
};


### 算法2

##### (slide window with set or hashmap) $O(2n)$

yxc的方法好像属于这一类。hashmap或set里保存该双指针中间的substring的char frequency。右端指针每前进一位要到hashmap/set里判断是否出现过。如果出现，左端指针前进一位并更新hashmap/set，直到右端指针指向的char被删掉为止，然后更新maxLen。

#### C++ 代码


// slide window with set
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int maxLen = 0;
set<char> uniqSet;
if(!s.length())
return maxLen;
int n = s.length();
int i = 0, j = 0;
while(i<n && j<n){
if(!uniqSet.count(s[j])){
uniqSet.insert(s[j]);
maxLen = max(maxLen, j-i+1);
j++;
}
else{

uniqSet.erase(s[i]);
i++;

}
}
return maxLen;
}
};

// slide window with hashmap
class Solution {
public:
int ans = 0;
int lengthOfLongestSubstring(string s) {
unordered_map<char ,int> hash;
if(s == "") return ans;
for(int i = 0, j = 0; j < s.size(); j++){
if(++hash[s[j]] > 1){
while(i < j){
hash[s[i]]--;
i++;
if(hash[s[j]] == 1){
break;
}
}
}
ans = max(ans, j-i+1);
}
return ans;
}
};



### 算法3

##### (slide window optimized with hashmap) $O(n)$

hashmap key是char value是最后一次访问到该char的index。右端指针每前进一位要到hashmap里判断是否出现过。如果出现，左端指针前进到该重复char的最后一次出现的index的后一位。相当于直接跳过了一段与没有包含该重复char的序列。更新hashmap，然后更新maxLen。

#### C++ 代码


// slide window optimized with hashmap
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.length();
int maxLen = 0;
unordered_map<char, int> charToIdx;
for(int i = 0, j = 0; j < n; j++){
if(charToIdx.count(s[j]))
i = max(i, charToIdx[s[j]]);
maxLen = max(maxLen, j-i+1);
charToIdx[s[j]] = j+1;
}
return maxLen;
}
};



### 算法4

#### C++ 代码


// slide window quick
class Solution{
public:
int lengthOfLongestSubstring(string s) {
vector<int> charToIdx(256, -1);
int maxLen = 0;
for (int i = -1, j = 0; j != s.length(); j++) {
if (charToIdx[s[j]] > i)
i = charToIdx[s[j]];
charToIdx[s[j]] = j;
maxLen = max(maxLen, j - i);
}
return maxLen;
}
};



//分析的不对的地方求指正。

st
2019-01-13 07:18
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
bool isNumber(string s) {
int i = 0;
while(i<s.size() && s[i] == ' ') i++;
int j = s.size()-1;
while(j>=0 && s[j] == ' ') j--;
if(i>j) return false;
s = s.substr(i,j-i+1);
if(s[0] == '-' || s[0] == '+') s = s.substr(1);
if(s.empty() || s[0] == '.' && s.size() == 1) return false;
int dot = 0, e = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] >= '0' && s[i] <= '9');
else if(s[i] == '.'){
dot++;
if(e || dot>1) return false;
}
else if(s[i] == 'e' || s[i] == 'E'){
e++;
if(i == s.size()-1 || !i || e>1 || i==1 && s[0]=='.') return false;
if(s[i+1] == '+' || s[i+1] == '-'){
if(i+1 == s.size()-1) return false;
i++;
}
}
else return false;
}
return true;
}
};


st
2019-01-13 06:56
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.length(), m = p.length();
vector<vector<int>> f(n+1, vector<int>(m+1, 0));
s = " " + s, p = " " + p;
f[0][0] = 1;
for(int i = 0; i <= n; i++){
for(int j = 1; j <= m; j++){
if(i > 0 && ((s[i] == p[j] || p[j] == '.') && f[i-1][j-1])) f[i][j] = 1;
if(p[j] == '*' && f[i][j-2]) f[i][j] = 1;
if(i>0 && p[j] == '*' && (s[i] == p[j-1] || p[j-1] == '.') && f[i-1][j-2]) f[i][j] = 1;
if(i>0 && p[j] == '*' && (s[i] == p[j-1] || p[j-1] == '.') && f[i-1][j]) f[i][j] = 1;

}
}
return f[n][m];
}
};


st
2019-01-13 05:01
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
vector<int> get_val(vector<TreeNode*> level)
{
vector<int> res;
for (auto &u : level)
res.push_back(u->val);
return res;
}
vector<vector<int>> printFromTopToBottom(TreeNode* root) {
vector<vector<int>>res;
if (!root) return res;
vector<TreeNode*>level;
level.push_back(root);
res.push_back(get_val(level));
bool zigzag = true;
while (true)
{
vector<TreeNode*> newLevel;
for (auto &u : level)
{
if (u->left) newLevel.push_back(u->left);
if (u->right) newLevel.push_back(u->right);
}
if (newLevel.size())
{
vector<int>temp = get_val(newLevel);
if (zigzag)
reverse(temp.begin(), temp.end());
res.push_back(temp);
level = newLevel;
}
else break;
zigzag = !zigzag;
}
return res;
}
};


st
2019-01-13 04:26
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
/**
* 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<int> get_val(queue<TreeNode*> q){
vector<int> ans;
while(!q.empty()){
TreeNode* x = q.front();
ans.push_back(x->val);
q.pop();
}
return ans;
}
vector<vector<int>> printFromTopToBottom(TreeNode* root) {
vector<vector<int>> ans;
if(!root) return ans;
queue<TreeNode*> q;
q.push(root);
ans.push_back(get_val(q));
while(1){
queue<TreeNode*> new_q;
while(!q.empty()){
TreeNode* t = q.front();
q.pop();
if(t->left) new_q.push(t->left);
if(t->right) new_q.push(t->right);
}
if(!new_q.empty()) {
ans.push_back(get_val(new_q));
q = new_q;
}
else break;
}
return ans;
}
};


st
2019-01-13 04:10
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
/**
* 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<int> printFromTopToBottom(TreeNode* root) {
vector<int> ans;
if(!root) return ans;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode* t = q.front();
q.pop();
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
ans.push_back(t->val);
}
return ans;
}
};