Word Ladder II
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
class Solution {
public:
#define rep(i,n) for(int i=0;i<(int)(n);i++)
vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
map<string,int> numedDict;
vector<string> strs;
dict.erase(start),dict.erase(end);
int i=0;strs.push_back(start);numedDict[start]=i++;////@error: strs[i]=start. however strs has not allocated any space, this cause array outflow.
typedef unordered_set<string>::iterator It;
for(It it=dict.begin();it!=dict.end();it++){
strs.push_back(*it);numedDict[*it]=i++;
}
strs.push_back(end);numedDict[end]=i++;
int N=i;
////////////////////////////////////////////
//bfs
queue<string> que;
vector<int> dst(N,-1);
vector<vector<int> > ngh(N,vector<int>());
que.push(start);
dst[0]=1;
while(!que.empty()){
string s=que.front();que.pop();
int v=numedDict[s];
if(dst[v]==dst[N-1]) break; //go to end's layer in the tree
for(int i=0;i<s.length();i++){
char c=s[i];
rep(j,26){
char e='a'+j;
if(e==c) continue;
s[i]=e;
if(numedDict.find(s)==numedDict.end()) continue;
int d=numedDict[s];
if(dst[d]<0){
dst[d]=dst[v]+1;
que.push(s);
}
if(dst[d]==dst[v]+1)
ngh[v].push_back(d);
}
s[i]=c;
}
}
/////////////////////////////////////////////////
vector<vector<string> > res;
vector<int> tmp;
tmp.push_back(0);
dfs(res,tmp,ngh,strs,dst[N-1],N-1,1,0);
return res;
}
void dfs(vector<vector<string> > &res,vector<int> &tmp,const vector<vector<int> > &ngh,const vector<string> &strs,
int maxD,int end,int d,int cur){
if(d==maxD){
if(cur==end) {
vector<string> ttmp;
rep(i,tmp.size()) ttmp.push_back(strs[tmp[i]]);
res.push_back(ttmp);
}
return;
}
rep(j,ngh[cur].size()){
int i=ngh[cur][j];
tmp.push_back(i);
dfs(res,tmp,ngh,strs,maxD,end,d+1,i);
tmp.pop_back();
}
}
};
Surrounded Regions
Given a 2D board containing 'X' and 'O',
capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's
into 'X's in that surrounded region.
For example,
X X X X X O O X X X O X X O X X
After running your function, the board should be:
X X X X X X X X X X X X X O X X
这道题不能用递归来写，要用队列辅助宽搜，否则报＂runtime error",
Populating Next Right Pointers in Each Node II
Total Accepted: 14224 Total
Submissions: 47300My Submissions
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
- You may only use constant extra space.
For example,
Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
tree的bfs的写法。while(..){int n=m;m=0;for(int i=0;i<n;i++){visit(que);} }
class Solution {
public:
void connect(TreeLinkNode *root) {
if(root==NULL) return;
queue<TreeLinkNode *>que;
que.push(root);
int n=0,m=1;
while(!que.empty()){
n=m,m=0;
for(int i=0;i<n;i++){
TreeLinkNode *node=que.front();que.pop();
if(i==n-1) node->next=NULL;
else{
node->next=que.front();
}
if(node->left) que.push(node->left),m++;
if(node->right) que.push(node->right),m++;
}
}
}
};
zigzag bfs tree
还有bfs， 一定要注意先检查好， 再提交
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
queue<TreeNode *>que;
int cnt=1, num = 1;
if(root) que.push(root);
vector<vector<int> > res;
while(!que.empty()){
int n = cnt;
cnt = 0;
vector<int> tmp;
for(int i=0; i<n; i++){////@error: i < cnt
TreeNode *root = que.front(); que.pop();
tmp.push_back(root->val);
if(root->left) que.push(root->left), cnt++;
if(root->right) que.push(root->right), cnt++;
}
if(num%2==0){
int m = tmp.size();
for(int i=0; i<m/2; i++) { //@error: i<=m/2
int t = tmp[i];
tmp[i] = tmp[m-1-i];
tmp[m-1-i] = t;
}
}
res.push_back(tmp);
num++;
}
return res;
}
};