zjkang blog: Graph

Showing posts with label Graph. Show all posts

Tuesday, May 19, 2015

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

Monday, May 18, 2015

Task Schedule

来源：itint5

原帖：http://www.itint5.com/oj/#10

题目：
有n个任务需要完成（编号1到n），任务之间有一些依赖关系，如果任务a依赖于任务b和c，那么只有当任务b和任务c完成之后才能完成任务a。给定所有的依赖关系，判断这些任务是否能够完成。如果能够完成，请给出一个合法的任务完成序列。
样例：
n=5
1->2,3
3->4
上述样例中任务1依赖于任务2和任务3，任务3依赖于任务4，那么存在合法的任务完成序列4,3,2,1,5
Solution: topological sorting
Refer to http://www.geeksforgeeks.org/topological-sorting/

代码：

 /*  
  * deps[id]表示任务id所依赖的任务  
  * 如果存在合法的任务完成序列，返回true，否则返回false  
  * 合法的任务序列请存放在参数result中（已经分配空间，不需要push_back）  
    2->1; 3->1  
    4->3  
    拓扑排序方法如下:  
    (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.  
    (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.  
    (3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.  
  */  
   
 typedef int JobID;  
 // BFS  
 // deps: <key, node(-->key) INDEGREE>  
 // rmap: <key, node(<--key) OUTDEGREE>  
 bool jobSchedule(const map<JobID, vector<JobID> > &deps, int n, vector<JobID> &result) {  
   vector<JobID> indegree(n+1, 0); // 计算图形入度  
   map<JobID, vector<JobID>> rmap; //   
   for (auto it = deps.begin(); it != deps.end(); it++) {  
     indegree[it->first] = it->second.size();  
     for (int i = 0; i < it->second.size(); i++) {  
       rmap[it->second[i]].push_back(it->first);  
     }  
   }  
   stack<JobID> s;  
   for (int i = 1; i <= n; i++) {  
     if(indegree[i] == 0) {  
       s.push(i);  
     }  
   }  
   for (int i = 0; i < n; i++) {  
     if (s.empty()) return false;  
     JobID id = s.top(); s.pop();  
     result[i] = id;  
     for (int j = 0; j < rmap[id].size(); j++) {  
       indegree[rmap[id][j]]--;  
       if(indegree[rmap[id][j]] == 0) {  
         s.push(rmap[id][j]);  
       }  
     }  
   }  
   return true;  
 }

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

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

Combinations

来源：Leetcode

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

题目：
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

代码：

 class Solution {  
 public:  
   vector<vector<int> > combine(int n, int k) {  
     vector<vector<int> > res;  
     vector<int> onecom;  
     combineHelper(n, k, 1, onecom, res);  
     return res;  
   }  
     
   void combineHelper(int n, int k, int start, vector<int> &onecom, vector<vector<int> > &res) {  
     int m = onecom.size();  
     if (m == k) {  
       res.push_back(onecom);  
       return;  
     }  
     for (int i = start; i <= n - (k - m) + 1; ++i) { // index = n-(k-m);  
       onecom.push_back(i);  
       combineHelper(n, k, i + 1, onecom, res);  
       onecom.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();  
     }  
   }  
 };

Monday, April 20, 2015

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

Bipartite Graph

来源：Twitter Second Phone Interview, EPI

原帖：http://www.fgdsb.com/2015/01/03/check-whether-a-graph-is-bipartite-or-not/

题目：

A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of same set.

Assign RED color to the source vertex (putting into set U).
Color all the neighbors with BLUE color (putting into set V).
Color all neighbor’s neighbor with RED color (putting into set U).
This way, assign color to all vertices such that it satisfies all the constraints of m way coloring problem where m = 2.
While assigning colors, if we find a neighbor which is colored with same color as current vertex, then the graph cannot be colored with 2 vertices (or graph is not Bipartite)

Time Complexity of the above approach is same as that Breadth First Search. In above implementation is O(V^2) where V is number of vertices. If graph is represented using adjacency list, then the complexity becomes O(V+E).

思路：使用BFS遍历

代码：

 // bipartite graph   
 // G=[(1,2), (2,3), (3,4)] yes   
 // G=[(1,2), (2,3), (3,1)] no   
 // G=[(1,2), (2,3), (3,4), (4,1)] yes    
   
 // adjacency list   
 struct GraphNode {   
   int visited; // -1 visited, 0: 1-color1; 1: 2-colors;   
   vector<GraphNode*> neighbors;   
 };   
   
 // adjacency matrixs   
 // vector<vector<int>> graph;   
 // vector<int> color(num_nodes);   
   
 bool isBipartite(vector<GraphNode*> g) {   
   if (g.empty()) return false;   
   for (int i = 0; i < g.size(); ++i) {   
     if (g[i]->visited == -1) {   
       g[i]->visited = 0;   
       queue<GraphNode*> q;   
       q.push(g[i]);   
       while (!q.empty()) {   
         auto node = q.front(); q.pop();       
         auto neighbors = node->neighbors;   
         for (int k = 0; k < neighbors.size(); ++k) {   
           if (neighbors[k]->visited == -1) {   
             neighbors[k]->visited = node->visited == 0 ? 1 : 0;   
             q.push(neighbors[k]);   
           } else {   
             if (neighbors[k]->visited == node->visited) return false;   
           }   
         }   
       }   
     }   
   }   
   return true;   
 }