NO CODING NO LIFE: DFS

显示标签为“DFS”的博文。显示所有博文

2015年9月22日星期二

Lintcode: N-Queens I

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.

Have you met this question in a real interview?

Yes

Example

There exist two distinct solutions to the 4-queens puzzle:

[

[".Q..", // Solution 1

"...Q",

"Q...",

"..Q."],

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

"Q...",

"...Q",

".Q.."]

]

Challenge

Can you do it without recursion?

Tags Expand

Recursion

Recursion solution:

Reference:
八皇后问题
http://bangbingsyb.blogspot.com/2014/11/leetcode-n-queens-i-ii.html

use vector<int> &col to remember all cols queens appears
end condition: row == n
recursive condition: current col don't appear in the col vector, and not in diagonal

class Solution {
public:
    /**
     * Get all distinct N-Queen solutions
     * @param n: The number of queens
     * @return: All distinct solutions
     * For example, A string '...Q' shows a queen on forth position
     */
    vector<vector<string> > solveNQueens(int n) {
        // write your code here
        vector<vector<string> > allSol;
        vector<string> sol;
        vector<int> col;
        solveNQ(n, 0, col, sol, allSol);
        return allSol;
    }
private:
    void solveNQ(int n, int irow, vector<int> &col, vector<string> &sol, vector<vector<string> > &allSol){
        if(irow == n){
            allSol.push_back(sol);
            return;
        }
        for(int icol = 0; icol < n; icol++){
            if(isValid(irow, icol, col)){
                string s(n, '.');
                s[icol] = 'Q';
                col.push_back(icol);
                sol.push_back(s);
                solveNQ(n, irow + 1, col, sol, allSol);
                col.pop_back();
                sol.pop_back();
            }
        }
    }
    bool isValid(int irow, int icol, vector<int> &col){
        //improve efficency, can be deleted
        if(irow < col.size()) return false;

        for(int i = 0; i < col.size(); i++){ //(irow, icol) (i, col[i])
            if(icol == col[i]) return false;
            //diagonal judge
            if(abs(irow - i) == abs(icol - col[i])) return false;
        }
        return true;
    }
};

Lintcode second:
back tracking are dfs with limited levels
Logics are mess, remember to use functions to help better format and logics

class Solution {
public:
    /**
     * Get all distinct N-Queen solutions
     * @param n: The number of queens
     * @return: All distinct solutions
     * For example, A string '...Q' shows a queen on forth position
     */
    vector<vector<string> > solveNQueens(int n) {
        // write your code here
        vector<int> rows(n);
        vector<vector<string> > allsol;
        vector<string> sol;
        DFS(0, n, rows, sol, allsol);
        return allsol;
    }
    void DFS(int row, int n, vector<int> &rows, vector<string> &sol, vector<vector<string> > &allsol){
        if(row == n){
            allsol.push_back(sol);
            return;
        }
        if(row > n) return;
        for(int col = 0; col < n; col++){
            //whether can be placed at (row, col)
            //judge whether row and col is safe
            bool valid = true;
            for(int j = 0; j < row; j++){
                int prerow = j;
                int precol = rows[j];
                if(precol == col) {
                    valid = false;
                    break;
                }
                if(abs(row - prerow) == abs(col - precol)) {
                    valid = false;
                    break;
                }
            }
            //if col and row is valid, save into sol and continue DFS, also update rows
            if(valid) {
                string temp;
                for(int i = 0; i < n; i++){
                    if(i == col) temp += "Q";
                    else temp += ".";
                }
                sol.push_back(temp);
                rows[row] = col;
                DFS(row + 1, n, rows, sol, allsol);
                sol.pop_back();
            }
        }
    }
};

2015年9月18日星期五

Lintcode: Subsets

Given a set of distinct integers, return all possible subsets.

Have you met this question in a real interview?

Yes

Example

If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Note

Elements in a subset must be in non-descending order.

The solution set must not contain duplicate subsets.

Tags Expand

Recursion

Initial thought:

I imitate the combination problem:

I resolve this subsets problem into solve combinations problem.

Assume there are n numbers in vector, I can get combinations of k numbers from n

Let k be from 0 to n, and combining all solutions, I will get all subsets.

In below codes, combine () functions works to get combination for different k

Time: O(n! + (n-1)! + (n-2)! + ... + 1)
Space: O(n)

class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > subsets(vector<int> &nums) {
     // write your code here
     vector<vector<int> > res;
     sort(nums.begin(), nums.end());
     for(int i = 0; i <= nums.size(); i++){
         combine(i, nums, res);
     }
     return res;
    }
private:
    void combine(int n, vector<int> &nums, vector<vector<int> > &res){
            vector<int> tempres;
            DFS(0, n, nums, tempres, res);

    }
    void DFS(int start, int n, vector<int> &nums, vector<int> &tempres, vector<vector<int> > &res){
        if(n == 0) {
            res.push_back(tempres);
            return;
        }
        for(int i = start; i < nums.size() - n + 1; i++){
            tempres.push_back(nums[i]);
            DFS(i + 1, n - 1, nums, tempres, res);
            tempres.pop_back();
        }
    }
};

Common solution:
//Reference thoughts and cods
https://siddontang.gitbooks.io/leetcode-solution/content/backtracking/subsets.html

Just push all result in tempres into res when dfs
Time: O(n!)
Space: O(n)

class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > subsets(vector<int> &nums) {
     // write your code here
     vector<vector<int> > res;
     vector<int> tempres;
     sort(nums.begin(), nums.end());
     res.push_back(tempres);
     DFS(0, nums, tempres, res);
     return res;
    }
private:
    void DFS(int start, vector<int> &nums, vector<int> &tempres,vector<vector<int> > &res){
        for(int i = start; i < nums.size(); i++){
            tempres.push_back(nums[i]);
            DFS(i + 1, nums, tempres, res);
            res.push_back(tempres);
            tempres.pop_back();
        }
    }
};

Lintcode: Topological Sorting

Given an directed graph, a topological order of the graph nodes is defined as follow:

For each directed edge A -> B in graph, A must before B in the order list.
The first node in the order can be any node in the graph with no nodes direct to it.

Find any topological order for the given graph.

Have you met this question in a real interview?

Yes

Example

For graph as follow:

The topological order can be:

[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...

Note

You can assume that there is at least one topological order in the graph.

Challenge

Can you do it in both BFS and DFS?

Tags Expand

LintCode Copyright Geeks for Geeks Depth First Search Breadth First Search

九章算法DFS
//both BFS and DFS
http://algorithm.yuanbin.me/zh-cn/graph/topological_sorting.html
//good BFS version
http://meetqun.com/thread-5526-1-1.html

Topological sort is for DAG(Directed acyclic graph)

indgree makes sure the topological order and vertices will not be counted repeatedly.

BFS solution:
s1: calc indegree of all vertices
s2: get the origin(vertice with 0 indegree) and push it into queue
s3: While queue is not empty:
pop the front element as cur and push it into result vector
for cur adjacent vertices:
minus its indegree by 1;
if its indegree equals to 0, push this vertice to result vector

Time: O(V+E)
s1-- O(V+E)
s2-- O(V)
s3-- O(V+E)
Space:O(V)

/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
        // write your code here
        //look for the head node
        vector<DirectedGraphNode*> res;
        if(!graph.size()) return res;
        //get indegree    
        unordered_map<DirectedGraphNode*, int> indegree;
        indeg(graph, indegree);
        //push nodes with 0 indegree and pop to result;
        queue<DirectedGraphNode*> q;
        bfs(graph, indegree, q, res);
        return res;
    }
private:
    void indeg(vector<DirectedGraphNode*> &graph, unordered_map<DirectedGraphNode*, int> &indegree){
        for(int i = 0; i < graph.size(); i++){
            for(int j = 0; j < graph[i]->neighbors.size(); j++){
                if(!indegree.count(graph[i]->neighbors[j])) indegree[graph[i]->neighbors[j]] = 1;
                else indegree[graph[i]->neighbors[j]]++;
            }
        }
    }
    void bfs(vector<DirectedGraphNode*> &graph, unordered_map<DirectedGraphNode*, int> &indegree, queue<DirectedGraphNode*> &q, vector<DirectedGraphNode*> &res){
        for(int i = 0; i < graph.size(); i++){
            if(indegree[graph[i]] == 0) {
                q.push(graph[i]);
                //res.push_back(graph[i]);
            }
        }
        while(!q.empty()){
            DirectedGraphNode* cur = q.front();
            res.push_back(cur);
            q.pop();
            for(int i = 0; i < cur->neighbors.size(); i++){
                indegree[cur->neighbors[i]]--;
                if(indegree[cur->neighbors[i]] == 0) q.push(cur->neighbors[i]);
            }
        }
    }
};

DFS solution 1:
Not real DFS, actually just like BFS, use stack replace the queue in BFS solution
s1: calc indegree of all vertices
s2: DFS the vertice with 0 indegree
s3: DFS( minus adjacent vertices' indegrees by 1, if any vertice indegree is 0, bfs this vertice)

O(V+E)

/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
        // write your code here
        //look for the head node
        vector<DirectedGraphNode*> res;
        if(!graph.size()) return res;
        //get indegree    
        unordered_map<DirectedGraphNode*, int> indegree;
        indeg(graph, indegree);
        //push nodes with 0 indegree and pop to result;
        for(int i = 0; i < graph.size(); i++){
            if(indegree[graph[i]] == 0) DFS(indegree, graph[i], res);
        }
        return res;
    }
private:
    void indeg(vector<DirectedGraphNode*> &graph, unordered_map<DirectedGraphNode*, int> &indegree){
        for(int i = 0; i < graph.size(); i++){
            for(int j = 0; j < graph[i]->neighbors.size(); j++){
                /*if(!indegree.count(graph[i]->neighbors[j])) indegree[graph[i]->neighbors[j]] = 1;
                else indegree[graph[i]->neighbors[j]]++;*/
                indegree[graph[i]->neighbors[j]]++;
            }
        }
    }
    void DFS(unordered_map<DirectedGraphNode*, int> &indegree, DirectedGraphNode* node, vector<DirectedGraphNode*>& res){
        indegree[node]--;
        res.push_back(node);
        for(int i = 0; i < node->neighbors.size(); i++){
            indegree[node->neighbors[i]]--;
            if(indegree[node->neighbors[i]] == 0) DFS(indegree, node->neighbors[i], res);
        }
    }
};

DFS solution 2:
Used a stack to record DFS order and pint the stack
In DFS, we push current node in stack in the end

a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.

//thought reference:
http://www.geeksforgeeks.org/topological-sorting/
//thought / process /codes reference
https://www.youtube.com/watch?v=jksMzq4LgfM

/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
        // write your code here
        //look for the head node
        vector<DirectedGraphNode*> res;
        if(!graph.size()) return res;
        //get indegree    
        unordered_map<DirectedGraphNode*, int> indegree;
        indeg(graph, indegree);
        //push nodes with 0 indegree and pop to result;
        unordered_set<DirectedGraphNode*> mark;
        stack<DirectedGraphNode*> s;
        for(int i = 0; i < graph.size(); i++){
            if(indegree[graph[i]] == 0) DFS(mark, graph[i], s);
        }
        while(!s.empty()){
            res.push_back(s.top());
            s.pop();
        }
        return res;
    }
private:
    void indeg(vector<DirectedGraphNode*> &graph, unordered_map<DirectedGraphNode*, int> &indegree){
        for(int i = 0; i < graph.size(); i++){
            for(int j = 0; j < graph[i]->neighbors.size(); j++){
                /*if(!indegree.count(graph[i]->neighbors[j])) indegree[graph[i]->neighbors[j]] = 1;
                else indegree[graph[i]->neighbors[j]]++;*/
                indegree[graph[i]->neighbors[j]]++;
            }
        }
    }
    void DFS(unordered_set<DirectedGraphNode*> &mark, DirectedGraphNode* node, stack<DirectedGraphNode*> &s){
        mark.insert(node);
        for(int i = 0; i < node->neighbors.size(); i++){
            if(!mark.count(node->neighbors[i])) DFS(mark, node->neighbors[i], s);
        }
        s.push(node);
    }
};

Lintcode second:

/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
        // write your code here
        //get indegrees
        unordered_map<DirectedGraphNode*, int> indegrees;
        for(int i = 0; i < graph.size(); i++){
            for(int j = 0; j < graph[i]->neighbors.size(); j++){
                indegrees[graph[i]->neighbors[j]]++;
            }
        }
        //get head
        queue<DirectedGraphNode*> q;
        for(int i = 0; i < graph.size(); i++){
            if(indegrees[graph[i] ] == 0) q.push(graph[i]);
        }
        //start sort
        vector<DirectedGraphNode*> res;
        while(!q.empty()){
            DirectedGraphNode* cur = q.front();
            res.push_back(cur);
            q.pop();
            for(int i = 0; i < cur->neighbors.size(); i++){
                indegrees[cur->neighbors[i]]--;
                if(indegrees[cur->neighbors[i]] == 0) q.push(cur->neighbors[i]);
            }
        }
        return res;
    }
};