word ladder(C++ code)

LeetCode Word Ladder, Feb 11
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

思路：bfs,我用map来记录每个单词的depth的，大集合用了1932ms...其实不需要用map，可以用两个int记录当前层和下一层的节点数，当前层用完后，当前层移到下一层，下一层则重设为0，同时update depth。这样稍微快一点，1.4s左右。。

0. int ladderLength(string start, string end, unordered_set<string> &dict) {    
1.     
2.         if(start == end) return 1;    
3.         //prev counts words of current level, next counts for next level, depth denotes current level.  
4.         //same level means same distance from original word.  
5.         int depth = 1, prev =1, next = 0;     
6.         //queue stores intermediate words  
7.         queue<string> q;    
8.      
9.         q.push(start);    
10.         //set stores visited words to avoid redundant work.  
11.         unordered_set<string> visited;    
12.     
13.         visited.insert(start);    
14.     
15.   while(!q.empty()) {    
16.     
17.     string cur = q.front();    
18.     
19.     q.pop(); prev--;    
20.     //for each letter in the intermediate word, iterate over 26 options and push it into queue if it's a word,   
21.     //don't forget to update level count next.   
22.     for(int i = 0; i < cur.length(); i++){    
23.     
24.        for(int j = 0; j < 26; j++){    
25.     
26.          string mid = cur;    
27.     
28.          mid[i] = 'a' + j;    
29.     
30.          if(dict.find(mid) != dict.end() && visited.find(mid) == visited.end()){    
31.     
32.            visited.insert(mid);    
33.     
34.            q.push(mid);    
35.     
36.            next += 1;    
37.     
38.            if(mid == end) return depth + 1;    
39.          }    
40.        }     
41.    }    
42.     
43.   if(prev == 0) {prev = next; next = 0; depth++;}    
44.    
45.   }    
46.         return 0;    
47. }    

-------------用map的---------------

int ladderLength(string start, string end, unordered_set<string> &dict) {

        if(start == end) return 1;
        map<string,int> visited;

        queue<string> q;

        q.push(start);

        visited[start] = 1;

      

while(!q.empty()) {

    string cur = q.front();

    q.pop();

   for(int i = 0; i < cur.length(); i++){

       for(int j = 0; j < 26; j++){

         string mid = cur;

         mid[i] = 'a' + j;

         if(mid == end) return visited[cur] + 1;

         if(dict.find(mid) != dict.end() && visited.find(mid) == visited.end()){

           visited[mid] = visited[cur] + 1;

           q.push(mid);

     

         }

       }

   }
}

        return 0;
    }

graph split （C++）

2维0，1矩阵。判断有多少个封闭的全是0的area。DFS，BFS的方法都要写。

void dfs(const vector<vector<int>> &G, int i, int j){
  if(i<0 || i >= rown || j<0 || j >= coln) return;
  if(G[i][j] == 1 || visited[i][j] == 1) return;
  visited[i][j] = 1;
  dfs(G, i - 1, j);
  dfs(G, i + 1, j);
  dfs(G, i, j+1);
  dfs(G, i, j-1);
}

int count(vector<vector<int>>G){
  if(G.empty()) return 0;
  int count;
 int rown = G.size(), coln = G[0].size;
 vector<vector<int>> visited(rown, vector<int>(coln,0));
  for(i = 0; i < rown; i++) {
    for(j = 0; j < coln; j++){
      if(visited[i][j] == 0&& G[i][j] == 0) {  
            count++;
          dfs(G,i, j, rown, coln);
        }
      }
    }

return count;

}

-------------------
void bfs(const vector<vector<int>> &G, int i, int j){
  queqe<pair<int,int>> q;
  q.push(make_pair(i,j));
  while(!q.empty()){
     i = queue.front().first; j = queue.front().second;
     queue.pop();
     visited[i][j] = 1;
     if(i > 0 && visited[i-1][j] == 0 && G[i-1][j] == 0) queue.push(make_pair(i-1,j));
     if(j> 0 && visited[i][j-1] == 0 && G[i][j-1] == 0) queue.push(make_pair(i,j-1));
     if(i < rown - 1 && visited[i+1][j] == 0 && G[i+1][j] == 0) queue.push(make_pair(i+1,j));
     if(j < coln - 1 && visited[i][j+1] == 0&& G[i][j+1] == 0) queue.push(make_pair(i,j+1));
  }
 

}


int count(vector<vector<int>>G){
  if(G.empty()) return 0;
  int count;
 int rown = G.size(), coln = G[0].size;
 vector<vector<int>> visited(rown, vector<int>(coln,0));
  for(i = 0; i < rown; i++) {
    for(j = 0; j < coln; j++){
      if(visited[i][j] == 0&& G[i][j] == 0) {  
            count++;
          bfs(G,i, j, rown, coln);
        }
      }
    }

return count;

}

Binary Tree Zigzag Level Order Traversal (C++ code)

LeetCode Binary Tree Zigzag Level Order Traversal, Sep 29 '12
难度4，出现频率3
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]

]

思路： 跟level order traversal一致，只是多一个flag记录每层正向还是逆向。

0. vector<vector<int>> zigzagLevelOrder(TreeNode *root){  
1.   vector<vector<int>> res;  
2.   if(!root) return res;   
3.   vector<int> level;  
4.   queue<TreeNode *> myque;  
5.   bool flag = true;   
6.   TreeNode *last = root;  
7.   myque.push(root);   
8.   //main loop  
9.   while(!myque.empty()){  
10.    root = myque.front();  
11.    myque.pop();  
12.    if(root->left) myque.push(root->left);  
13.    if(root->right) myque.push(root->right);  
14.    if(flag == true)level.push_back(root->val);  
15.    else level.insert(level.begin(), root->val);  
16.    //when current level ends, store level in result, reset flag and level variable.  
17.    if(root == last){  
18.      res.push_back(level);  
19.      level.clear();  
20.      last = myque.back();  
21.      flag = !flag;   
22.    }   
23.   }  
24.   return res;   
25. }   

Binary Tree Level Order Traversal I, II(C++ code)

LeetCode Binary Tree Level Order Traversal,Sep 29 
 难度3，出现频率4
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
].

思路： 辅助数据结构queue，每次从头pop一个node， 后面就push node's children.这里要求每层单存一个list,

所以记得用一个指针last记录每层的最后一个node，每当遍历到last时，更新last为当前queue的末尾。

Code如下：

vector<vector<int>> levelOrder(TreeNode *root){
  vector<vector<int>> res;
  if(!root) return res;
  queue<TreeNode *> myque;
  vector<int> level;
  TreeNode *last = root;
  myque.push(root);

  while(!myque.empty()){
     root = myque.front();
     myque.pop();
     level.push_back(root->val);
    if(root->left) myque.push(root->left);
    if(root->right) myque.push(root->right);
    
    if(root == last) {
     last = myque.back();
     res.push_back(level);
     level.clear();
    }
  }
  
  return res;
} 


Binary Tree Level Order Traversal II, Oct 1 '12
难度3，出现频率1
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7]
  [9,20],
  [3],
]

思路： 从上题基本一样，只是每个level存进result的时候，是从头存进去。

vector<vector<int>> levelOrder(TreeNode *root){
  vector<vector<int>> res;
  if(!root) return res;
  queue<TreeNode *> myque;
  vector<int> level;
  TreeNode *last = root;
  myque.push(root);

  while(!myque.empty()){
     root = myque.front();
     myque.pop();
     level.push_back(root->val);
    if(root->left) myque.push(root->left);
    if(root->right) myque.push(root->right);
    
    if(root == last) {
     last = myque.back();
     res.insert(res.begin(),level);
     level.clear();
    }
  }
  
  return res;
}