211 Add and Search Word - Data structure design

217 Contains Duplicate

来源：Leetcode

原帖：https://leetcode.com/problems/contains-duplicate/

题目：
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

代码：

 class Solution {  
 public:  
   bool containsDuplicate(vector<int>& nums) {  
     unordered_set<int> _set;  
     for (auto i : nums) {  
       if (_set.count(i)) return true;  
       _set.insert(i);  
     }  
     return false;  
   }  
 };  

160 Intersection of Two Linked Lists

来源：Leetcode

原帖：https://leetcode.com/problems/intersection-of-two-linked-lists/

题目：
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
 A:          a1 → a2
                    ↘
                      c1 → c2 → c3
                    ↗          
 B:     b1 → b2 → b3
begin to intersect at node c1.

Notes:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

代码：

 class Solution {  
 public:  
   ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {  
     ListNode *p1 = headA, *p2 = headB;  
     if (!p1 || !p2) return NULL;  
     while (p1 && p2 && p1 != p2) {  
       p1 = p1->next;  
       p2 = p2->next;  
       if (p1 == p2) return p1;  
       if (!p1) p1 = headB;  
       if (!p2) p2 = headA;  
     }  
     return p1;  
   }  
 };  

Wildcard Matching

来源：Leetcode

原帖：https://oj.leetcode.com/problems/wildcard-matching/

题目：
 Implement wildcard pattern matching with support for '?' and '*'.
 '?' Matches any single character.
 '*' Matches any sequence of characters (including the empty sequence).
 The matching should cover the entire input string (not partial).
 The function prototype should be:
 bool isMatch(const char *s, const char *p)
 Some examples:
 isMatch("aa","a") ? false
 isMatch("aa","aa") ? true
 isMatch("aaa","aa") ? false
 isMatch("aa", "*") ? true
 isMatch("aa", "a*") ? true
 isMatch("ab", "?*") ? true
 isMatch("aab", "c*a*b") ? false

代码：

 class Solution {  
 public:  
   // s does NOT include '?' and '*'. p has '?' and '*'  
   //Version 1: iteration  
   bool isMatch(const char *s, const char *p) {  
     const char *start_s = NULL, *start_p = NULL;  
     while (*s != '\0') {  
       if (*p == '?' || *s == *p) {  
         s++;  
         p++;  
       } else if (*p == '*') {  
         while (*p == '*') p++;  
         if (*p == '\0') return true;  
         start_s = s;  
         start_p = p;  
       } else {  
         if (!start_s) return false;  
         s = ++start_s;  
         p = start_p;  
       }  
     }  
     while (*p == '*') p++;  
     return *s == '\0' && *p == '\0';  
   }  
 };  
   
 class Solution {  
 public:  
   //Version 2: recursion:   
   // time limit exceed  
   bool isMatch(const char* s, const char* p) {  
     if (*s == '\0') {  
       while(*p && *p == '*') p++;  
       return *p == '\0';  
     }  
     if (*s == *p || *p == '?') {  
       return isMatch(s+1, p+1);  
     } else if (*p == '*') {  
       while (*p == '*') p++;  
       if (*p == '\0') return true;  
       while (*s != '\0') {  
         if (isMatch(s, p)) return true;  
         s++;  
       }  
     }  
     return false;  
   }  
 };  

Regular Expression Matching

来源：Leetcode

原帖：http://oj.leetcode.com/problems/regular-expression-matching/

题目：
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true  zero or more

思路：
http://www.cnblogs.com/zuoyuan/p/3781773.html
解题思路：正则表达式匹配的判断。网上很多的解法是用递归做的，用java和c++都可以过，但同样用python就TLE，说明这道题其实考察的不是递归。而是动态规划，使用动态规划就可以AC了。这里的'*'号表示重复前面的字符，注意是可以重复0次的。
先来看递归的解法：
如果P[j+1]!='*'，S[i] == P[j]=>匹配下一位(i+1, j+1)，S[i]!=P[j]=>匹配失败；
如果P[j+1]=='*'，S[i]==P[j]=>匹配下一位(i+1, j)或者(i, j+2)，S[i]!=P[j]=>匹配下一位(i,j+2)。
匹配成功的条件为S[i]=='\0' && P[j]=='\0'。

代码：

 class Solution {  
 public:  
   bool isMatch(const char *s, const char *p) {  
     if (*p == '\0') return *s == '\0';  
     if (*(p+1) == '*') {  
       if (isMatch(s, p+2)) return true; // match 0  
       while (*s && (*s == *p || *p == '.')) { // match 1,2,...  
         if (isMatch(s+1, p+2)) return true;  
         s++;  
       }  
     } else if (*s && (*p == *s || *p == '.') && isMatch(s+1, p+1)) // always check *s  
         return true;  
     return false;  
   }  
 };  
   
 // dp solution  
 class Solution {  
 public:  
   bool isMatch(const char* s, const char* p) {  
     if (*p == '\0') return *s == '\0';  
     int M = strlen(s), N = strlen(p);  
     vector<vector<bool> > dp(M+1, vector<bool>(N+1, false)); // 前i个字符in s和前j个字符in p的匹配  
     dp[0][0] = true;  
     for (int j = 0; j < N; ++j)  
       dp[0][j+1] = p[j] == '*' ? (j >= 1 && dp[0][j-1]) : false;   
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         if (s[i] == p[j] || p[j] == '.') {  
           dp[i+1][j+1] = dp[i][j];  
         } else if (p[j] == '*') {  
           dp[i+1][j+1] = dp[i+1][j-1] || ((s[i] == p[j-1] || p[j-1] == '.') && dp[i][j+1]);  
         }  
       }  
     }  
     return dp[M][N];  
   }  
 };  

186 Reverse Words In a String II

来源：Leetcode

原帖：https://leetcode.com/problems/reverse-words-in-a-string-ii/

题目：
Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters. The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example,
Given s = "the sky is blue", return "blue is sky the".
Could you do it in-place without allocating extra space?

代码：

 class Solution {  
 public:  
   // in-place reverse  
   void reverseWords(string &s) {  
     reverse(s.begin(), s.end());  
     int end = 0;  
     for (int i = 0; i < s.size(); ++i) {  
       if (s[i] == ' ') continue;  
       if (end != 0) s[end++] = ' ';  
       int l = i, h = i;  
       while (i != s.size() && s[i] != ' ') {  
         h++; i++;  
       }  
       reverse(s.begin() + l, s.begin() + h);  
       for (int j = l; j < h; ++j) {  
         s[end++] = s[j];  
       }  
     }  
     s.resize(end);    
   }  
 };  

157 Read N Characters Given Read4

来源：Leetcode

原帖：https://leetcode.com/problems/read-n-characters-given-read4/

题目：
The API: int read4(char *buf) reads 4 characters at a time from a file. The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file. By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.
Note:
The read function will only be called once for each test case.
// Forward declaration of the read4 API.
int read4(char *buf);

代码：

 class Solution {  
 public:  
   /**  
    * @param buf Destination buffer  
    * @param n  Maximum number of characters to read  
    * @return  The number of characters read  
    */  
   int read(char *buf, int n) {  
     char buffer[4];  
     int cnt = 0;  
     while (cnt < n) {  
       int sz = read4(buffer);  
       if (cnt + sz >= n) {  
         memcpy(buf+cnt, buffer, n-cnt);  
         cnt = n;  
       } else {  
         memcpy(buf+cnt, buffer, sz);  
         cnt += sz;  
       }  
       //sz = min(sz, n-cnt);  
       //memcpy(buf + cnt, buffer, sz);  
       //cnt += sz;  
       if (sz < 4) break;  
     }  
     return cnt;  
   }  
 };  

151 Reverse Words In a String I

来源：Leetcode

原帖：https://oj.leetcode.com/problems/reverse-words-in-a-string/

题目：
Given an input string, reverse the string word by word. For example,
Given s = "the sky is blue", return "blue is sky the".
click to show clarification. Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a word. Could the input string contain leading or trailing spaces? Yes. However, your reversed string should not contain leading or trailing spaces. How about multiple spaces between two words? Reduce them to a single space in the reversed string.

代码：

 class Solution {  
   void reverseWords(string &s) {  
     stringstream ss(s);  
     vector<string> vs;  
     string word;  
     while (ss >> word) {  
       vs.push_back(word);  
     }  
     reverse(vs.begin(), vs.end());  
     for (size_t i = 0; i < vs.size(); ++i {  
       if (i ! = 0) ss << ' ';  
         ss << vs[i];  
     }  
     s = ss.str();  
   }  
 };  
   
 class Solution {  
 public:  
   void reverseWords(string &s) {  
     string result;  
     int pos = 0;  
     for (int i = 0; i < s.size(); i ++){  
       if (s[i] == ' '){  
         if (i > pos )  
           result = s.substr(pos,i-pos)+ " " + result ;  
         pos = i + 1;  
       }  
       else if (i == s.size()-1)  
         result = s.substr(pos,s.size()-pos)+" "+result;  
     }  
     s = result.substr(0,result.size()-1) ;  
   }  
 };  
   

Max Points on a Line

来源：Leetcode

原帖：https://oj.leetcode.com/problems/max-points-on-a-line/

题目：
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

代码：

 /**  
  * Definition for a point.  
  * struct Point {  
  *   int x;  
  *   int y;  
  *   Point() : x(0), y(0) {}  
  *   Point(int a, int b) : x(a), y(b) {}  
  * };  
  */  
   
 class Solution {  
 public:  
   // int GCD(int a, int b){  
   //   if(a == 0)   
   //     return b;  
   //   else   
   //     return GCD(a, b%a);  
   // }  
     
   struct hashfunc {   
     size_t operator() (const pair<int,int>& l) const {   
       return l.first ^ l.second;   
     }  
   };    
     
   int maxPoints(vector<Point> &points) {  
     int res = 0;  
     for (int i = 0; i < points.size(); i++) {  
       unordered_map<pair<int,int>,int,hashfunc> lines;  
       int localmax = 0, vertical = 0, overlap = 0;  
       for (int j = i + 1; j < points.size(); j++){  
         if (points[j].x == points[i].x && points[j].y == points[i].y){  
           overlap++;  
           continue;  
         } else if (points[j].x == points[i].x) {  
           vertical++;  
         } else {  
           int yd = points[j].y - points[i].y, xd = points[j].x - points[i].x;  
           int gcd = __gcd(yd, xd);  
           yd /= gcd;  
           xd /= gcd;  
           lines[{xd, yd}]++;  
           localmax = max(lines[{xd, yd}], localmax);  
         }  
         localmax = max(vertical, localmax);  
       }  
       res = max(res, localmax+overlap+1);  
     }    
     return res;  
   }  
 };  
   

Word Ladder II

来源：Leetcode

原帖：https://oj.leetcode.com/problems/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"]
Return
 [
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
 ]
Note:
All words have the same length.
All words contain only lowercase alphabetic characters.
Solution: Idea is from blog: http://blog.csdn.net/niaokedaoren/article/details/8884938

代码：

 class Solution {  
 public:  
     vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {  
     // If A->C and B->C, then traces[C] contains A and B. This is used for recovering the paths.  
     unordered_map<string, vector<string>> traces;   
     queue<string> q;  
     q.push(start);  
     bool found = false;  
     while (!q.empty()) {  
       int size = q.size();  
       unordered_set<string> level;  
       for (int i = 0; i < size; ++i) {  
         string word = q.front(); q.pop();  
         string nextWord = word;  
         for (size_t j = 0; j < nextWord.size(); ++j) {  
           char before = nextWord[j];  
           for (char c = 'a'; c <= 'z'; c++) {  
             if (c == before) continue;  
             nextWord[j] = c;  
             if (nextWord == end)  
               found = true;  
             if (nextWord == end || dict.find(nextWord) != dict.end()) {  
               traces[nextWord].push_back(word);  
               level.emplace(nextWord);  
             }  
           }  
           nextWord[j] = before;  
         }     
       }  
       if (found) break;  
       for (auto it = level.begin(); it != level.end(); it++) {  
         q.push(*it);  
         dict.erase(*it);  
       }  
     }  
     vector<vector<string> > result;  
     vector<string> onePath;  
     if (!traces.empty()) {  
       buildResult(traces, result, onePath, end, start);        
     }  
     return result;  
   }  
   
   // backtracking to target (start word), then reverse the root->leaf order  
   // DFS  
   void buildResult(unordered_map<string, vector<string> > &traces, vector<vector<string>> &result,   
            vector<string> &onePath, string word, const string &target) {  
     if (word == target) { // word = start word   
       vector<string> copy(onePath);  
       copy.push_back(word);  
       reverse(copy.begin(), copy.end());  
       result.push_back(copy);  
       return;  
     }  
     vector<string> &s = traces[word];  
     onePath.push_back(word);  
     for (int i = 0; i < s.size(); ++i) {  
       buildResult(traces, result, onePath, s[i], target);  
     }  
     onePath.pop_back();  
   }    
 };  
   

Word Ladder I

来源：Leetcode

原帖：https://oj.leetcode.com/problems/word-ladder/

题目：
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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"]
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.

代码：

 class Solution {  
 public:  
   int ladderLength(string start, string end, unordered_set<string> &dict) {  
     queue<pair<string, int> > q; // (word, transformation steps)  
     q.push({start, 1});  
     while (!q.empty()) {  
       pair<string, int> front = q.front(); q.pop();  
       string word = front.first;  
       for (size_t i = 0; i < word.size(); i++) {  
         char before = word[i];      
         for (char c = 'a'; c <= 'z'; c++) {  
           if (c == before) continue;  
           word[i] = c;  
           if (word == end) {  
             return front.second + 1; // return shortest length              
           }  
           if (dict.find(word) != dict.end()) {  
             q.push({word, front.second + 1});  
             dict.erase(word);  
           }  
         }  
         word[i] = before;  
       }  
     }  
     return 0;  
   }  
 };  

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';                
       }  
     }  
   }  
 };  
   

Sudoku Solver

来源：Leetcode

原帖：http://oj.leetcode.com/problems/sudoku-solver/

题目：
Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character '.'. You may assume that there will be only one unique solution.
Solution: back-tracking... Recursion.
Note: Backtracking...
http://blog.csdn.net/linhuanmars/article/details/20748761
这道题的方法就是用在N-Queens中介绍的常见套路。简单地说思路就是循环处理子问题，对于每个格子，带入不同的9个数，然后判合法，如果成立就递归继续，结束后把数字设回空

代码：

 class Solution {  
 public:  
   typedef vector<vector<char>> BOARDTYPE;  
   const int N = 9;  
   
   void getNextEmpty(BOARDTYPE &board, int &row, int &col) {  
     do {  
       if (board[row][col] == '.') return;  
       row = (col == N - 1) ? row + 1 : row;  
       col = (col + 1) % N;  
     } while (row < N);  
   }  
     
   void getAvailable(BOARDTYPE &board, vector<bool> &avail, int row, int col) {  
     for (int i = 0; i < 9; ++i) {  
       if (board[row][i] != '.') {  
         avail[board[row][i] - '1'] = false;  
       }  
       if (board[i][col] != '.') {  
         avail[board[i][col] - '1'] = false;  
       }  
       int box_i = row/3*3 + i/3;  
       int box_j = col/3*3 + i%3;  
       if (board[box_i][box_j] != '.') {  
         avail[board[box_i][box_j] - '1'] = false;  
       }  
     }  
   }  
   
   bool solveSudokuHelper(BOARDTYPE &board, int row, int col) {  
     getNextEmpty(board, row, col); // get next empty position [row, col]  
     if (row == 9) return true;  
     vector<bool> avail(9, true);  
     getAvailable(board, avail, row, col); // available value at(row, col) in row/col/box check   
     for (int i = 0; i < 9; ++i) {  
       if (!avail[i]) continue;  
       board[row][col] = i + '1';  
       if (solveSudokuHelper(board, row, col)) return true;  
       board[row][col] = '.';  
     }  
     return false;  
   }  
     
   void solveSudoku(BOARDTYPE &board) {  
     solveSudokuHelper(board, 0, 0);  
   }  
 };  
   

Valid Sudoku

来源：Leetcode

原帖：http://oj.leetcode.com/problems/valid-sudoku/

题目：
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules (http://sudoku.com.au/TheRules.aspx). The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

代码：

 class Solution {  
 public:  
   bool isValidSudoku(vector<vector<char>> &board) {  
     const int N = 9;  
     vector<int> col(N, 0), box(N, 0);  
     for (int i = 0; i < N; ++i) { // row traverse   
       int row = 0; // update row bit  
       for (int j = 0; j < N; ++j) { // col traverse  
         if (board[i][j] == '.') continue;  
         int bit = 1 << (board[i][j] - '1');  
         int box_index = i/3*3 + j/3;  
         if ((row & bit) || (col[j] & bit) || (box[box_index] & bit)) {  
           return false;            
         }          
         row |= bit;  
         col[j] |= bit;  
         box[box_index] |= bit;  
       }  
     }  
     return true;  
   }  
 };  

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;  
   }  
 };