212 Word Search II

来源：Leetcode

原帖：https://leetcode.com/problems/word-search-ii/

题目：
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
For example,
Given words = ["oath","pea","eat","rain"] and board =
 [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
 ]
Return ["eat","oath"].

代码：

 struct TrieNode {  
   bool isWord;  
   string word;  
   unordered_map<char, TrieNode*> next;  
   TrieNode(bool w = false) : isWord(w) {}  
 };  
   
 class Solution {  
 public:  
   void insert(TrieNode*& root, string s) {  
     if (!root) root = new TrieNode();  
     TrieNode* cur = root;  
     for (int i = 0; i < s.size(); ++i) {  
       if (!cur->next.count(s[i])) {  
         cur->next[s[i]] = new TrieNode();  
       }  
       cur = cur->next[s[i]];  
     }  
     cur->isWord = true;  
     cur->word = s;  
   }  
     
   vector<pair<int,int>> offset = {{0,-1},{-1,0},{0,1},{1,0}};  
   void dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, int i, int j,   
       TrieNode* root, vector<string>& res) {  
     int M = board.size(), N = board[0].size();  
     char c = board[i][j];  
     if (!root->next.count(c)) return;  
     if (root->next[c]->isWord) {  
       res.push_back(root->next[c]->word);  
       root->next[c]->isWord = false;  
     }  
     visited[i][j] = true;  
     for (auto o : offset) {  
       int ii = i + o.first, jj = j + o.second;  
       if (ii >= 0 && ii < M && jj >= 0 && jj < N && !visited[ii][jj]) {  
         dfs(board, visited, ii, jj, root->next[board[i][j]], res);  
       }  
     }  
     visited[i][j] = false;  
   }  
     
   vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {  
     if (words.empty()) return {};  
     TrieNode* root = NULL;  
     for (auto s : words) {  
       insert(root, s);  
     }  
     vector<string> res;  
     int M = board.size(), N = board[0].size();  
     vector<vector<bool>> visited(M, vector<bool>(N,false));  
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         dfs(board, visited,i,j,root,res);  
       }  
     }  
     return res;  
   }  
 };  

Word Search I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/word-search/

题目：
Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
 [
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
 ]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

代码：

 class Solution {  
 public:  
   vector<pair<int,int> > offset = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  
   bool exist(vector<vector<char> > &board, string word) {  
     int M = board.size(), N = board[0].size();  
     vector<vector<bool> > visited(M, vector<bool>(N, false)); // visiting status   
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         if (existHelper(board, word, 0, i, j, visited)) {  
           return true;  
         }  
       }      
     }  
     return false;  
   }  
   
   bool existHelper(const vector<vector<char> > &board, const string &word, int deep, int i, int j,   
     vector<vector<bool> > &visited) {  
     int M = board.size(), N = board[0].size();    
     if (deep == word.size()) return true;  
     if (i < 0 || i >= M || j < 0 || j >= N) return false;  
     if (board[i][j] != word[deep] || visited[i][j] == true) return false;  
     visited[i][j] = true;  
     for (auto o : offset) {  
       if (existHelper(board, word, deep + 1, i+o.first, j+o.second, visited)) {  
         return true;  
       }  
     }  
     visited[i][j] = false;  
     return false;  
   }  
 };  

Surrounded Regions

来源：

原帖：https://oj.leetcode.com/problems/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
Solution: Traverse from the boarder to the inside and mark all the 'O's that are not surrounded by 'X' as 'V' (visited).

代码：

 // rumtime error  
 class Solution {  
 public:  
   typedef vector<vector<char> > BOARDTYPE;    
   vector<pair<int,int> > offset = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};  
   void solve(BOARDTYPE &board) {  
     if (board.empty() || board[0].empty()) return;  
     int M = board.size(), N = board[0].size();  
     for (int j = 0; j < board[0].size(); ++j) {  
      if (board[0][j] == 'O') dfs(board, 0, j);  
      if (board[board.size()-1][j] == 'O') dfs(board, board.size()-1, j);  
     }  
     for (int i = 0; i < board.size(); ++i) {  
      if (board[i][0] == 'O') dfs(board, i, 0);  
      if (board[i][board[0].size()-1] == 'O') dfs(board, i, board[0].size()-1);  
     }  
     // flip remaining 'O' to 'X' and revert 'V' to 'O'  
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         board[i][j] = (board[i][j] == 'V') ? 'O' : 'X';                
       }  
     }  
   }  
     
   void dfs(BOARDTYPE &board, int row, int col) {  
     int M = board.size(), N = board[0].size();  
     board[row][col] = 'V';  
     for (auto o : offset) {  
       int i = row + o.first, j = col + o.second;  
       if (i >= 0 && i < M && j >= 0 && j < N && board[i][j] == 'O') {  
         dfs(board, i, j);  
       }  
     }  
   }  
 };  
   
 class Solution {  
 public:  
   typedef vector<vector<char> > BOARDTYPE;    
   vector<pair<int,int> > offset = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};  
   
   void bfs(BOARDTYPE &board, int row, int col) {  
     if (board[row][col] != 'O') return;  
     int M = board.size(), N = board[0].size();  
     queue<pair<int, int> > q;  
     board[row][col] = 'V';  
     q.push({row, col}); // q.push({i, j}); pair对也可以使用{i, j} instead of make_pair(i,j)  
     while (!q.empty()) {  
       int i = q.front().first, j = q.front().second;  
       q.pop();  
       for (auto o : offset) {  
         int ii = o.first + i, jj = o.second + j;  
         if (ii >= 0 && ii < M && jj >= 0 && jj < N && board[ii][jj] == 'O') {  
           board[ii][jj] = 'V'; // update !!!   
           q.push({ii, jj});  
         }  
       }  
     }  
   }  
   
   void solve(BOARDTYPE &board) {  
     if (board.empty() || board[0].empty()) return;  
     int M = board.size(), N = board[0].size();  
     for (int j = 0; j < board[0].size(); ++j) {  
      if (board[0][j] == 'O') bfs(board, 0, j);  
      if (board[board.size()-1][j] == 'O') bfs(board, board.size()-1, j);  
     }  
     for (int i = 0; i < board.size(); ++i) {  
      if (board[i][0] == 'O') bfs(board, i, 0);  
      if (board[i][board[0].size()-1] == 'O') bfs(board, i, board[0].size()-1);  
     }  
     // flip remaining 'O' to 'X' and revert 'V' to 'O'  
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         board[i][j] = (board[i][j] == 'V') ? 'O' : 'X';                
       }  
     }  
   }  
 };  
   

Restore IP Addresses

来源：Leetcode

原帖：http://oj.leetcode.com/problems/restore-ip-addresses/

题目：
Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

代码：

 class Solution {  
 public:  
   vector<string> restoreIpAddresses(string s) {  
     vector<string> result;  
     string ip;  
     restoreIpAddressHelper(s, result, ip, 0, 0);  
     return result;  
   }  
     
   void restoreIpAddressHelper(const string &s, vector<string> &result, string ip, int deep, int start) {  
     // pruning  
     if (s.size() - start > (4 - deep) * 3) return;  
     if (s.size() - start < 4 - deep) return;  
     if (deep == 4 && start == s.size()) {  
       ip.resize(ip.size() - 1);  
       result.push_back(ip);  
       return;  
     }  
     int num = 0;  
     for (int i = start; i < start + 3; ++i) {  
       num = num * 10 + s[i] - '0';  
       if (num > 255) break;  
       ip.push_back(s[i]);  
       restoreIpAddressHelper(s, result, ip + ".", deep + 1, i + 1);  
       if (num == 0) break; // case 0.0.0.0 or case 255.128.0.23  
     }  
   }  
 };  

Clone Graph

来源：Leetcode

原帖：http://oj.leetcode.com/problems/clone-graph/

题目：
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:
Nodes are labeled from 0 to N - 1, where N is the total nodes in the graph.
We use # as a separator for each node, and , as a separator for each neighbor of the node.
As an example, consider the serialized graph {1,2#2#2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
Connect node 0 to both nodes 1 and 2.
Connect node 1 to node 2.
Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

 Solution: 1. DFS. 2. BFS.

代码：

 /**  
  * Definition for undirected graph.  
  * struct UndirectedGraphNode {  
  *   int label;  
  *   vector<UndirectedGraphNode *> neighbors;  
  *   UndirectedGraphNode(int x) : label(x) {};  
  * };  
  */  
 class Solution {  
 public:  
   typedef UndirectedGraphNode GraphNode;  
   typedef unordered_map<GraphNode*, GraphNode*> MAP;  
   //Version 1: DFS, hash-map  
   GraphNode* cloneGraph(GraphNode *node) {  
     MAP map;  
     return cloneGraphHelper(node, map);  
   }  
     
   GraphNode* cloneGraphHelper(GraphNode *node, MAP &map) {  
     if (!node) return NULL;  
     if (map.count(node)) return map[node];        
     GraphNode* newNode = new GraphNode(node->label);  
     map[node] = newNode;  
     for (int i = 0; i < node->neighbors.size(); ++i) {  
       newNode->neighbors.push_back(cloneGraphHelper(node->neighbors[i], map));  
     }  
     return newNode;  
   }  
 };  
   
 class Solution {  
 public:  
   typedef UndirectedGraphNode GraphNode;  
   typedef unordered_map<GraphNode*, GraphNode*> MAP;  
     
   //Version 2: BFS, HashMap  
   GraphNode *cloneGraph(GraphNode *node) {  
     if (!node) return NULL;  
     queue<GraphNode*> q;  
     q.push(node);  
     MAP map;  
     map[node] = new GraphNode(node->label);  
     while (!q.empty()) {  
       GraphNode *oriNode = q.front();   
       q.pop();  
       GraphNode *newNode = map[oriNode];  
       for (int i = 0; i < oriNode->neighbors.size(); ++i) {  
         GraphNode *oriNeighbor = oriNode->neighbors[i];  
         if (map.find(oriNeighbor) != map.end()) {  
           newNode->neighbors.push_back(map[oriNeighbor]); // already visited!不再加入队列中  
           continue;  
         }  
         GraphNode *newNeighbor = new GraphNode(oriNeighbor->label);  
         newNode->neighbors.push_back(newNeighbor);  
         map[oriNeighbor] = newNeighbor; // set up hash-map  
         q.push(oriNeighbor); // push for next visit  
       }  
     }  
     return map[node];  
   }  
 };  

Subsets II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/subsets-ii/

题目：
Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets.
For example,
If S = [1,2,2], a solution is:
 [
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
 ]

代码：

 class Solution {  
 public:  
   //Version 1: 从树状结构考虑递归方法  
   vector<vector<int> > subsetsWithDup(vector<int> &S) {  
     vector<vector<int> > result;  
     if (S.empty()) return result;  
     sort(S.begin(), S.end());  
     vector<int> oneset;  
     subsetsWithDupHelper(S, 0, oneset, result);  
     return result;  
   }  
   
   void subsetsWithDupHelper(vector<int> &S, int start, vector<int> &oneset, vector<vector<int> > &result) {  
     result.push_back(oneset);  
     for (int i = start; i < S.size(); ++i) {  
       if (i != start && S[i] == S[i - 1]) {  
         continue;  
       }    
       oneset.push_back(S[i]);  
       subsetsWithDupHelper(S, i + 1, oneset, result);  
       oneset.pop_back();  
     }  
   }   
 };  
   
 // {}  
 // 1  
 // 2  
 // 1,2  
 // 2,2  
 // 1,2,2  
 class Solution {  
 public:  
   vector<vector<int> > subsetsWithDup(vector<int> &S) {  
     sort(S.begin(), S.end());  
     vector<vector<int>> ret = {{}};  
     int size = 0, startIndex = 0;  
     for (int i = 0; i < S.size(); i++) {  
       startIndex = i >= 1 && S[i] == S[i - 1] ? size : 0;  
       size = ret.size();  
       for (int j = startIndex; j < size; j++) {  
         vector<int> temp = ret[j];  
         temp.push_back(S[i]);  
         ret.push_back(temp);  
       }  
     }  
     return ret;  
   }  
 };  

Subsets I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/subsets/

题目：
Given a set of distinct integers, S, return all possible subsets.
Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:
 [
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
 ]

代码：

 class Solution {  
 public:  
   void subsetHelper(const vector<int> &S, int start, vector<int> &oneset, vector<vector<int> > &result) {  
     result.push_back(oneset);  
     for (int i = start; i < S.size(); ++i) {  
       oneset.push_back(S[i]);  
       subsetHelper(S, i + 1, oneset, result);  
       oneset.pop_back();  
     }  
   }  
   
   //Version 1: 从树状结构考虑递归方法  
   vector<vector<int> > subsets(vector<int> &S) {  
     vector<vector<int> > result;  
     if (S.empty()) return result;  
     sort(S.begin(), S.end());  
     vector<int> oneset;  
     subsetHelper(S, 0, oneset, result);  
     return result;  
   }  
 };  
   
 // Bitwise solution. each bit has two state, present or not.  
 class Solution {  
 public:  
   vector<vector<int> > subsets(vector<int> &S) {  
     sort (S.begin(), S.end());  
     int elem_num = S.size();  
     int subset_num = pow (2, elem_num);  
     vector<vector<int> > subset_set (subset_num, vector<int>());  
     for (int i = 0; i < elem_num; i++)  
       for (int j = 0; j < subset_num; j++)  
         if ((j >> i) & 1)  
           subset_set[j].push_back (S[i]);  
     return subset_set;  
   }  
 };  
   
 // iteration  
 class Solution {  
 public:  
   vector<vector<int> > subsets(vector<int> &S) {  
     vector<vector<int> > R;  
     R.push_back(vector<int>());  
     sort(S.begin(), S.end());  
     for (int i = 0; i<S.size(); i++) {  
       int Rsize = R.size();  
       for (int j = 0; j<Rsize; j++) {  
         vector<int> sub(R[j]);  
         sub.push_back(S[i]);  
         R.push_back(sub);  
       }  
     }  
     return R;  
   }  
 };  

Permutations II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/permutations-ii/

题目：
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
 For example,
 [1,1,2] have the following unique permutations:
 [1,1,2], [1,2,1], and [2,1,1].

代码：

 class Solution {  
 public:  
   vector<vector<int>> permuteUnique(vector<int> &num) {  
     vector<vector<int>> result;  
     if (num.empty()) return result;  
     sort(num.begin(), num.end());  
     vector<bool> avail(num.size(),true);  
     vector<int> onepum;  
     permuteHelper(num, onepum, avail, result);  
     return result;  
   }  
   
   void permuteHelper(const vector<int> &num, vector<int> &onepum, vector<bool> &avail, vector<vector<int> > &result) {  
     if (onepum.size() == num.size()) {  
       result.push_back(onepum);  
       return;  
     }  
     int last_index = -1;  
     for (int i = 0; i < num.size(); ++i) {  
       if (!avail[i]) continue;  
       // 1233 -> 1323  
       if (last_index != -1 && num[i] == num[last_index]) {  
         continue; // last_index stores the position been visited          
       }  
       avail[i] = false;  
       onepum.push_back(num[i]);  
       permuteHelper(num, onepum, avail, result);  
       onepum.pop_back();  
       avail[i] = true;  
       last_index = i;  
     }  
   }  
 };  
   

Permutations I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/permutations/

题目：
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

代码：

 class Solution {  
 public:  
   vector<vector<int>> permute(vector<int> &num) {  
     if (num.empty()) {}  
     vector<vector<int> > result;  
     vector<bool> avail(num.size(), true);  
     vector<int> onepum;  
     permuteHelper(num, avail, onepum, result);  
     return result;  
   }  
   
   void permuteHelper(const vector<int> &num, vector<bool> &avail, vector<int> &onepum, vector<vector<int>> &result) {  
     if (onepum.size() == num.size()) {  
       result.push_back(onepum);  
       return;  
     }      
     for (int i = 0; i < num.size(); ++i) {  
       if (avail[i]) {  
         avail[i] = false;  
         onepum.push_back(num[i]);  
         permuteHelper(num, avail, onepum, result);  
         onepum.pop_back();  
         avail[i] = true;  
       }  
     }  
   }  
 };  

N-Queens II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/n-queens-ii/

题目：
The n-queens puzzle is the problem of placing n queens on an n*n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
 [
 [".Q..",  // Solution 1
 "...Q",
 "Q...",
 "..Q."],

 ["..Q.",  // Solution 2
 "Q...",
 "...Q",
 ".Q.."]
 ]

代码：

 class Solution {  
 public:  
   //Version 1: recursion  
   int totalNQueens(int n) {  
     vector<int> board(n, -1); // store board (col) configuration from row 0...n-1.  
     int res = 0;  
     totalNQueensHelper(n, 0, board, res);  
     return res;  
   }  
     
   void totalNQueensHelper(int n, int row, vector<int>& board, int &res) {  
     if(row == n) {  
       res++;  
       return;  
     }  
     for(int i = 0; i < n; ++i) {  
       if(isValid(board, row, i)) {  
         board[row] = i;  
         totalNQueensHelper(n, row + 1, board, res);  
         board[row] = -1;  
       }  
     }  
   }  
     
   bool isValid(vector<int>& board, int row, int col) {  
     for (int i = 0; i < row; ++i) {  
       if (board[i] == col || row - i == abs(col - board[i])) {  
         return false;                
       }  
     }  
     return true;  
   }  
 };  
   
 class Solution {  
 public:   
   //Version 2: Bit version  
   int totalNQueens(int n) {  
     int result = 0;  
     totalNQueensHelp(n, 0, 0, 0, result);  
     return result;  
   }  
   
   void totalNQueensHelp(int n, int col, int ld, int rd, int &result) {  
     if (col == (1 << n) - 1) {  
       result++;  
       return;  
     }  
     int avail = ~(col | ld | rd);  
     for (int i = n - 1; i >= 0; --i) {  
       int pos = 1 << i;  
       if (avail & pos) {  
         totalNQueensHelp(n, col | pos, (ld | pos) << 1, (rd | pos) >> 1, result);          
       }  
     }  
   }  
 };  
   

N-Queens I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/n-queens/

题目：
The n-queens puzzle is the problem of placing n queens on an n*n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
 [
 [".Q..",  // Solution 1
 "...Q",
 "Q...",
 "..Q."],

 ["..Q.",  // Solution 2
 "Q...",
 "...Q",
 ".Q.."]
 ]
 Solution: Recursion (DFS). Use bit-manipulation solution (See N-QueensII for more details).

代码：

 class Solution {  
 public:  
   vector<vector<string> > solveNQueens(int n) {  
     vector<vector<string> > result;  
     vector<string> onePath;  
     solveNQueensHelper(n, 0, 0, 0, onePath, result);  
     return result;  
   }  
     
   // col: 第几列被占据; ld: 左45度对角线被占据; rd: 右45度对角线被占据  
   void solveNQueensHelper(int n, int col, int ld, int rd, vector<string> &onePath,   
     vector<vector<string> > &result) {  
     if (col == (1 << n) - 1) { // all cols are full 1111  
       result.push_back(onePath);  
       return;  
     }  
     int avail = ~(col | ld | rd); // find all available positions  
     for (int i = n - 1; i >= 0; --i) { // n =4, start 'Q...'   
       int pos = 1 << i;  
       if (avail & pos) {  
         string s(n, '.');  
         s[i] = 'Q';  
         onePath.push_back(s);  
         solveNQueensHelper(n, col | pos, (ld | pos) << 1, (rd | pos) >> 1, onePath, result);   
         onePath.pop_back();  
       }  
     }  
   }  
 };  

Combination Sum II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/combination-sum-ii/

题目：
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations
in C where the candidate numbers sums to T. Each number in C may only be used once in the combination. Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2, .. , ak) must be in non-descending order. (ie, a1 <= a2 <= ... <= ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

代码：

 class Solution {  
 public:  
   vector<vector<int>> combinationSum2(vector<int> &num, int target) {  
     vector<vector<int> > res;  
     sort(num.begin(), num.end());  
     vector<int> com;  
     combinationSum2Helper(num, target, 0, com, res);  
     return res;  
   }  
   
   void combinationSum2Helper(const vector<int> &num, int target, int start, vector<int> &com, vector<vector<int>> &res) {  
     if (target == 0) {  
       res.push_back(com);  
       return;  
     }  
     for (int i = start; i < num.size() && num[i] <= target; ++i) {  
       if (i > start && num[i] == num[i - 1]) {  
         continue; // avoid duplicates  
       }  
       com.push_back(num[i]);  
       combinationSum2Helper(num, target - num[i], i + 1, com, res);  
       com.pop_back();  
     }  
   }  
 };  

Combination Sum I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/combination-sum/

题目：
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers. Elements in a combination (a1, a2, .. , ak) must be in non-descending order. (ie, a1 <= a2 <= ... <= ak). The solution set must not contain duplicate combinations. For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]
Solution: Sort & Recursion.

代码：

 class Solution {  
 public:  
   vector<vector<int>> combinationSum(vector<int> &candidates, int target) {  
     vector<vector<int> > res;  
     sort(candidates.begin(), candidates.end()); // 如果没有要求结果是非下降序列，则sort是非必要的  
     vector<int> com;  
     combinationSumHelper(candidates, target, 0, com, res);  
     return res;  
   }  
   
   void combinationSumHelper(const vector<int> &num, int target, int start, vector<int> &com, vector<vector<int>> &res) {  
     if (target == 0) {  
       res.push_back(com);  
       return;  
     }  
     for (int i = start; i < num.size() && target >= num[i]; ++i) {  
       com.push_back(num[i]);  
       combinationSumHelper(num, target - num[i], i, com, res);  
       com.pop_back();  
     }  
   }  
 };  

Generate Parentheses

来源：Leetcode

原帖：http://oj.leetcode.com/problems/generate-parentheses/

题目：
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

代码：

 class Solution {  
 public:  
   vector<string> generateParenthesis(int n) {  
     vector<string> result;  
     generateParenthesisHelper(n, n, "", result);  
     return result;  
   }  
   
   void generateParenthesisHelper(int left, int right, string s, vector<string> &result) {  
     if (left == 0 && right == 0) {  
       result.push_back(s);        
     }  
     if (left > 0) {  
       generateParenthesisHelper(left - 1, right, s + "(", result);        
     }  
     if (right > left) {  
       generateParenthesisHelper(left, right - 1, s + ")", result);        
     }  
   }  
 };  

Letter Combinations of a Phone Number

来源：Leetcode

原帖：http://oj.leetcode.com/problems/letter-combinations-of-a-phone-number/

题目：
Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

代码：

 class Solution {  
 public:  
   vector<string> letterCombinations(string digits) {  
     if (digits.empty()) return {};  
     vector<string> mapping = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  
     string s;  
     vector<string> result;  
     letterCombinationsHelper(digits, mapping, s, result);  
     return result;  
   }  
     
   void letterCombinationsHelper(const string& digits, vector<string>& mapping, string& s, vector<string> &result) {  
     if (s.size() == digits.size()) {  
       result.push_back(s);  
       return;  
     }  
     string &letters = mapping[digits[s.size()] - '2'];   
     for (int i = 0; i < letters.size(); ++i) {  
       s.push_back(letters[i]);  
       letterCombinationsHelper(digits, mapping, s, result);  
       s.pop_back();  
     }  
   }  
 };  
   
 class Solution {  
 public:  
   vector<string> letterCombinations(string digits) {  
     string mapping[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  
     vector<string> res;  
     if (digits.empty()) return {};  
     for (int i = 0; i < digits.size(); ++i) {  
       vector<string> tmp;  
       auto& letters = mapping[digits[i] - '2'];  
       for (int j = 0; j < letters.size(); ++j) {  
         if (res.empty()) {  
           string s(1, letters[j]);  
           tmp.push_back(s);   
           continue;  
         }  
         for (int k = 0; k < res.size(); ++k) {  
           tmp.push_back(res[k] + letters[j]);  
         }  
       }  
       res = move(tmp);  
     }  
     return res;  
   }  
 };  

Palindrome Partitioning I

来源：Leetcode

原帖：https://oj.leetcode.com/problems/palindrome-partitioning/

题目：
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
 [
  ["aa","b"],
  ["a","a","b"]
 ]

代码：

 class Solution {  
 public:  
   bool isPalindrome(const string &s) {  
     int i = 0, j = s.size()-1;  
     while (i < j) {  
       if (s[i] != s[j]) return false;  
       i++; j--;  
     }  
     return true;  
   }  
   
   void partitionHelper(const string &s, int start, vector<string> &path, vector<vector<string> >& res) {  
     if (start == s.size()) {  
       res.push_back(path);  
       return;  
     }  
     string palindrom;  
     for (int i = start; i < s.size(); ++i) {  
       palindrom.push_back(s[i]);  
       if (isPalindrome(palindrom)) {  
         path.push_back(palindrom);  
         partitionHelper(s, i + 1, path, res);  
         path.pop_back();           
       }  
     }  
   }  
   
   vector<vector<string>> partition(string s) {  
     vector<string> path;  
     vector<vector<string> > res;  
     partitionHelper(s, 0, path, res);  
     return res;  
   }  
 };  

Print a Binary Tree in Vertical Order

来源：Facebook电面

原帖：http://www.mitbbs.com/article_t/JobHunting/32946511.html
            http://www.geeksforgeeks.org/print-binary-tree-vertical-order-set-2/

题目：

Given a binary tree, print it vertically. The following example illustrates vertical order traversal.

           1
        /    \
       2      3
      / \    / \
     4   5  6   7
             \   \
              8   9 
               
     
The output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9

思路：这道题dfs + map (因为需要key的顺序保存，所以使用map).或者bfs + map也可。

代码版本使用了bfs + map， 由于dfs不能保证层的顺序。

代码：

 struct TreeNode {  
      int val;  
      TreeNode* left, *right;  
      TreeNode(int v) : val(v), left(NULL), right(NULL) {};  
 };  
   
 vector<vector<int>> verticalPrintBinaryTree(TreeNode* root) {  
      vector<vector<int>> res;  
      if (!root) return res;  
      map<int, vector<int>> table;  
      queue<pair<TreeNode*, int>> q;  
      q.push({root, 0});  
      table[0].push_back(root->val);  
   
       while (!q.empty()) {  
           auto node = q.front().first;  
           int label = q.front().second;  
           q.pop();  
           if (node->left) {  
                table[label-1].push_back(node->left->val);  
                q.push({node->left, label-1});  
           }  
           if (node->right) {  
                table[label+1].push_back(node->right->val);  
                q.push({node->right, label+1});  
           }  
      }  
   
       for (auto it = table.begin(); it != table.end(); ++it) {  
           res.push_back(it->second);  
      }  
      return res;  
 }  
   
 void print(vector<vector<int>>& num) {  
      for (int i = 0; i < num.size(); ++i) {  
           for (int j = 0; j < num[i].size(); ++j) {  
                cout << num[i][j] << " ";  
           }  
           cout << endl;  
      }  
 }  
   
 int main() {  
   TreeNode *root = new TreeNode(1);  
   root->left = new TreeNode(2);  
   root->right = new TreeNode(3);  
   root->left->left = new TreeNode(4);  
   root->left->right = new TreeNode(5);  
   root->right->left = new TreeNode(6);  
   root->right->right = new TreeNode(7);  
   root->right->left->right = new TreeNode(8);  
   root->right->right->right = new TreeNode(9);  
   cout << "Vertical order traversal is \n";  
   vector<vector<int>> res = verticalPrintBinaryTree(root);  
   print(res);  
   return 0;  
 }  
   

200 Number of Islands

来源：Leetcode, Google常考题

原帖：https://leetcode.com/problems/number-of-islands/

题目：
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
You may assume all four edges of the grid are all surrounded by water.
思路：找到连通域的数目，典型的bfs, dfs题目。

代码：DFS

 class Solution {  
 public:  
     vector<pair<int,int>> offset = {{0,-1},{-1,0},{0,1},{1,0}};  
     void dfs(vector<vector<char>> &grid, vector<vector<bool>> &visited, int r, int c) {  
         int M = grid.size(), N = grid[0].size();  
         visited[r][c] = true;  
         for (auto o : offset) {  
             int i = r + o.first, j = c + o.second;  
             if (i < 0 || i >= M || j < 0 || j >= N) continue;  
             if (grid[i][j] == '0' || visited[i][j]) continue;  
             dfs(grid, visited, i, j);  
         }  
     }  
   
     int numIslands(vector<vector<char>> &grid) {  
         if (grid.empty() || grid[0].empty()) return 0;  
         int M = grid.size(), N = grid[0].size();  
         vector<vector<bool>> visited(M,vector<bool>(N,false));  
         int count = 0;  
         for (int i = 0; i < M; ++i) {  
             for (int j = 0; j < N; ++j) {  
                 if (grid[i][j] == '1' && !visited[i][j]) {  
                     count++;  
                     dfs(grid, visited, i,j);  
                 }  
             }  
         }  
         return count;  
     }  
 };  

代码：BFS

 class Solution {  
 public:  
     vector<pair<int,int>> offset = {{0,-1},{-1,0},{0,1},{1,0}};  
     int numIslands(vector<vector<char>> &grid) {  
         if (grid.empty() || grid[0].empty()) return 0;  
         int M = grid.size(), N = grid[0].size();  
         vector<vector<bool>> visited(M,vector<bool>(N,false));  
         int count = 0;  
         for (int i = 0; i < M; ++i) {  
             for (int j = 0; j < N; ++j) {  
                 if (grid[i][j] == '1' && !visited[i][j]) {  
                     count++;  
                     queue<pair<int,int>> q;  
                     visited[i][j] = true;  
                     q.push({i,j});  
                     while (!q.empty()) {  
                         auto neigh = q.front(); q.pop();  
                         for (auto o : offset) {  
                             int r = neigh.first + o.first, c = neigh.second + o.second;  
                             if (r < 0 || r >= M || c < 0 || c >= N) continue;  
                             if (visited[r][c] || grid[r][c] == '0') continue;  
                             visited[r][c] = true;  
                             q.push({r,c});  
                         }  
                     }  
                 }  
             }  
         }  
         return count;  
     }  
 };