Saturday, August 22, 2015

LintCode(16) Permutations II

Given a list of numbers with duplicate number in it. Find all unique permutations.
Have you met this question in a real interview? 
Yes
Example
For numbers [1,2,2] the unique permutations are:
[
    [1,2,2],
    [2,1,2],
    [2,2,1]
]

Challenge
Do it without recursion.



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    vector<vector<int> > permuteUnique(vector<int> &nums) {
        // write your code here
        vector<vector<int>> result;
        vector<int> solution;
        if (nums.empty())
            return result;
        vector<bool> visited(nums.size(),false);
        sort(nums.begin(),nums.end());
        dfs(nums,result,solution, visited);
        return result;
    }
    
    void dfs(vector<int>& nums, vector<vector<int>>&result, vector<int>& solution, vector<bool>& visited){
        if (solution.size()==nums.size()){
            result.push_back(solution);
            return;
        }
        for (int i=0; i<nums.size(); i++){
            if (visited[i])
                continue;
            visited[i]=true;
            solution.push_back(nums[i]);
            dfs(nums,result, solution, visited);
            solution.pop_back();
            visited[i]=false;
            while(nums[i]==nums[i+1])
                i++;
        }
    }
};
Posted by at No comments:
Labels:

LintCode(15) Permutations

Given a list of numbers, return all possible permutations.
Have you met this question in a real interview? 
Yes
Example
For nums = [1,2,3], the permutations are:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Challenge
Do it without recursion.


没啥好说的。。。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    vector<vector<int> > permute(vector<int> nums) {
        // write your code here
        vector<vector<int>> result;
        vector<int> solution;
        if (nums.size()==0)
            return result;
        sort(nums.begin(), nums.end());
        vector<bool> visited(nums.size(), false);
        dfs(nums,result,solution, visited);
        return result;
    }
    
    void dfs(vector<int>& nums, vector<vector<int>>& result, vector<int>& solution, vector<bool>& visited){
        if (solution.size()==nums.size()){
            result.push_back(solution);
            return;
        }
        for (int i=0; i<nums.size(); i++){
            if (visited[i])
                continue;
            visited[i]=true;
            solution.push_back(nums[i]);
            dfs(nums,result, solution, visited);
            visited[i]=false;
            solution.pop_back();
        }
    }
};
Posted by at No comments:
Labels:

LintCode(18) Subsets II

Given a list of numbers that may has duplicate numbers, return all possible subsets
Have you met this question in a real interview? 
Yes
Example
If S = [1,2,2], a solution is:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Note
Each element in a subset must be in non-descending order.
The ordering between two subsets is free.
The solution set must not contain duplicate subsets.

画一画就知道了，每次遍历的时候只取出第一个有重复的数字就是了。。。所以加了个剪枝。。。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > subsetsWithDup(const vector<int> &S) {
        // write your code here
        vector<vector<int>> result;
        vector<int> solution;
        vector<int> input(S.begin(),S.end());
        sort(input.begin(),input.end());
        dfs(result, solution, input, 0);
        return result;
    }
    
    void dfs(vector<vector<int>>& result, vector<int>& solution, vector<int>& input, int ind){
        result.push_back(solution);
        if(solution.size()==input.size())
            return;
        for (int i= ind; i<input.size(); i++){
            if (i!=ind && input[i]==input[i-1])
                continue;
            solution.push_back(input[i]);
            dfs(result, solution, input, i+1);
            solution.pop_back();
        }
    }
};
Posted by at No comments:
Labels:

LintCode(17) 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.

经典的回溯，没啥好说的，直接贴答案吧。。。看不懂自己画个图就知道了


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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>> result;
     vector<int> solution;
     sort(nums.begin(),nums.end());
     dfs(nums,result,solution, 0);
     return result;
    }
    
    void dfs(vector<int>& nums, vector<vector<int>>& result, vector<int>& solution,int ind){
        result.push_back(solution);
        if (solution.size()==nums.size())
            return;
        for (int i=ind; i<nums.size(); i++){
            solution.push_back(nums[i]);
            dfs(nums,result,solution,i+1);
            solution.pop_back();
        }
    }
};
Posted by at No comments:
Labels:

LintCode(34) N-Queens II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
Have you met this question in a real interview? 
Yes

Example
For n=4, there are 2 distinct solutions.

承接上题，变了个花样。。。不过可以看出这种题目的规律。。。其实很羞愧的一直在想dp的事情，貌似dp是解不出的。。。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    /**
     * Calculate the total number of distinct N-Queen solutions.
     * @param n: The number of queens.
     * @return: The total number of distinct solutions.
     */
    int totalNQueens(int n) {
        // write your code here
        if (n==0)
            return 0;
        vector<int> solution;
        int res=0;
        dfs(solution, res, n);
    
        return res;
    }
    
    void dfs(vector<int>& solution, int& res, int n){
        if (solution.size()==n)
            res++;
        for (int i=0; i<n; i++){
            if (!isValid(solution, i))
                continue;
            solution.push_back(i);
            dfs(solution, res, n);
            solution.pop_back();
        }
    }
    
    bool isValid(vector<int>& solution, int ind){
        if (solution.empty())
            return true;
        int n=solution.size();
        for (int i=0; i<n; i++){
            if (solution[i]==ind)
                return false;
            if (solution[i]+i==ind+n)
                return false;
            if (i-solution[i] == n-ind)
                return false;
        }
        return true;
    }
    
};
Posted by at No comments:
Labels:

LintCode(33) 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.
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?

基本算是暴力搜索了，剪枝的部分在于判断是不是一个合适的解，知道形成一个完整解之后，build string然后push到容器里。 本质是DFS， 加一点判断对角线的下三滥trick， 所以很无聊


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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>> result;
        vector<int> solution;
        if (n==0)
            return result;
        helper(result, solution, n);
        return result;
    }
    
    void helper(vector<vector<string>>& result, vector<int>& solution, int n){
        if (solution.size()==n){
            build_result(result, solution);
            return;
        }
        for (int i = 0; i<n; i++){
            if (!isValidSolution(solution, i))
                continue;
            solution.push_back(i);
            helper(result, solution, n);
            solution.pop_back();
        }
    }
    
    void build_result(vector<vector<string>>& result,const vector<int>& solution){
        int n=solution.size();
        vector<string> res(n, string(n,'.'));
        for (int i=0; i<n; i++){
            res[i][solution[i]]='Q';
        }
        result.push_back(res);
    }
    
    bool isValidSolution(const vector<int>& solution, int ind){
        int n = solution.size();
        if (n==0)
            return true;
        for (int i=0; i<n; i++){
            if (solution[i]==ind)
                return false;
            if (i-solution[i]==n-ind)
                return false;
            if (i+solution[i] == n+ind)
                return false;
        }
        return true;
    }
    
};
Posted by at No comments:
Labels:

LintCode(127) Topological Sorting Show result

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:
picture
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.


有向图的排序，基本上还是考察概念
遍历所有给定node的neighbors， 来mark 每一个被遍历的node的边数，因为是neighbors,所以必然有至少一个与他相连， 而没有被遍历到的自然为第一个被排出的。 然后push到q上去，想象把这个node从图中拿掉，那么他所有的neighbor必然少一条边，这个时候再减少计数，如果归零，则push到q上去。。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * 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.
     */
    typedef DirectedGraphNode Node;
    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
        // write your code here
        unordered_map<Node*, int> map;
        for (int i=0; i<graph.size(); i++){
            Node* node = graph[i];
            for (int j=0; j<node->neighbors.size(); j++){
                Node* neighbor = node->neighbors[j];
                if (map.find(neighbor) == map.end())
                    map[neighbor]=1;
                else
                    map[neighbor]++;
            }
        }
        vector<Node*> result;
        queue<Node*> fifo;
        for (int i=0; i<graph.size(); i++){
            if (map.find(graph[i]) == map.end()){
                fifo.push(graph[i]);
                result.push_back(graph[i]);
            }
        }
        
        while(!fifo.empty()){
            Node* node = fifo.front();
            fifo.pop();
            for (int i=0; i<node->neighbors.size(); i++){
                Node* neighbor = node->neighbors[i];
                if (--map[neighbor] == 0){
                    fifo.push(neighbor);
                    result.push_back(neighbor);
                    map.erase(neighbor);
                }
            }
        }
        return result;
    }
};
Posted by at No comments:
Labels: ,

LintCode(135) 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.

For example, given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3] 
Have you met this question in a real interview? 
Yes
Example
given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3] 

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.

这基本算是回溯法的经典题目了，之前朋友面试碰到过类似的，就是给 1， 5， 10， 25的硬币，求有多少种组合可以组成一个给定的币值， 其实就是这个题目。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    /**
     * @param candidates: A list of integers
     * @param target:An integer
     * @return: A list of lists of integers
     */
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        // write your code here
        vector<vector<int>> result;
        vector<int> solution;
        sort(candidates.begin(), candidates.end());
        helper(result, solution, candidates, 0, target);
        return result;
    }
    
    void helper(vector<vector<int>>& result, vector<int>& solution, vector<int>& candidates, int ind, int target){
        if (target<0)
            return;
        if (target==0){
            result.push_back(solution);
            return;
        }
        for (int i=ind; i<candidates.size(); i++){
            solution.push_back(candidates[i]);
            helper(result,solution, candidates, i, target-candidates[i]);
            solution.pop_back();
        }
    }
};
Posted by at No comments:
Labels:

LintCode(137): 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 uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
       1
      / \
     /   \
    0 --- 2
         / \
         \_/

这个题目和linked list with random pointer 遍历差不多，先复制点，在复制边，

 复制点的时候用一个hash table来避免循环， 用一个queue来实现广度优先， 为了第二次链接边的时候减小复杂度，维护一个vector来记录每一次被push进去的顺序，这要更新边的时候只需要遍历这个vector就好了。。。

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
    typedef UndirectedGraphNode n;
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        // write your code here
        if (!node)
            return node;
        vector<n*> seq;
        unordered_map<n*, n*> map;
        queue<n*> q;
        q.push(node);
        seq.push_back(node);
        map[node] = new n(node->label);
        while(!q.empty()){
            n* tmp= q.front();
            q.pop();
            for (int i=0; i<tmp->neighbors.size(); i++){
                n* sub=tmp->neighbors[i];
                if (map.find(sub)!=map.end())
                    continue;
                map[sub] = new n(sub->label);
                q.push(sub);
                seq.push_back(sub);
            }
        }
        
        for (int i=0; i<seq.size(); i++){
            n* tmp=seq[i];
            for (int j=0; j<tmp->neighbors.size(); j++){
                map[tmp]->neighbors.push_back(map[tmp->neighbors[j]]);
            }
        }
        return map[node];
    }
};
Posted by at No comments:
Labels:

Friday, August 21, 2015

LintCode(136): 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.
Have you met this question in a real interview? 
Yes
Example
given s = "aab",
Return
  [
    ["aa","b"],
    ["a","a","b"]
  ]
回溯法，这种求combination的题目，一般就是DFS 的暴力搜索了，连模板其实都一样。。。之前做OA的时候碰到过一个求按照棋盘走的电话号码搜索，都是思想一样的。。

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    /**
     * @param s: A string
     * @return: A list of lists of string
     */
    vector<vector<string>> partition(string s) {
        // write your code here
        vector<vector<string>> result;
        vector<string> solution;
        if (s.empty())
            return result;
        helper(result, solution, s, 0);
        return result;
    }
    
    void helper(vector<vector<string>>& result, vector<string>& solution,
                const string& s, int ind)
    {
        if (ind>=s.size()){
            result.push_back(solution);
            return;
        } 
        for (int i=ind; i<s.size(); i++){
            if (!isPalindrome(s, ind, i))
                continue;
            solution.push_back(s.substr(ind, i-ind+1));
            helper(result, solution, s, i+1);
            solution.pop_back();
        }
    }
    
    bool isPalindrome(const string& s, int beg, int end){
        while(beg<end){
            if (s[beg++]!=s[end--])
                return false;
        }
        return  true;
    }
};
Posted by at No comments:
Labels:
Subscribe to: Posts (Atom)