Tuesday, April 30, 2019

Lintcode 246. Binary Tree Path Sum II

Your are given a binary tree in which each node contains a value. Design an algorithm to get all paths which sum to a given value. The path does not need to start or end at the root or a leaf, but it must go in a straight line down.

Example

Example 1:
Input:
{1,2,3,4,#,2}
6
Output:
[
  [2, 4],
  [1, 3, 2]
]
Explanation:
The binary tree is like this:
    1
   / \
  2   3
 /   /
4   2
for target 6, it is obvious 2 + 4 = 6 and 1 + 3 + 2 = 6.
Example 2:
Input:
{1,2,3,4}
10
Output:
[]
Explanation:
The binary tree is like this:
    1
   / \
  2   3
 /   
4   
for target 10, there is no way to reach it.
Code (Java):

?
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
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
 
 
public class Solution {
    /*
     * @param root: the root of binary tree
     * @param target: An integer
     * @return: all valid paths
     */
    public List<List<Integer>> binaryTreePathSum2(TreeNode root, int target) {
        // write your code here
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
         
        binaryTreePathSum2Helper(root, target, new ArrayList<Integer>(), ans);
         
        return ans;
    }
     
    private void binaryTreePathSum2Helper(TreeNode root, int target, List<Integer> curList, List<List<Integer>> ans) {
        if (root == null) {
            return;
        }
         
        curList.add(root.val);
        int sum = 0;
        for (int i = curList.size() - 1; i >= 0; i--) {
            sum += curList.get(i);
            if (sum == target) {
                List<Integer> temp = new ArrayList<>();
                for (int j = i; j < curList.size(); j++) {
                    temp.add(curList.get(j));
                }
                ans.add(temp);
            }
        }
         
        binaryTreePathSum2Helper(root.left, target, curList, ans);
        binaryTreePathSum2Helper(root.right, target, curList, ans);
         
        curList.remove(curList.size() - 1);
    }
}
Posted by at 1 comment:
Labels:

Lintcode 597. Subtree with Maximum Average

Given a binary tree, find the subtree with maximum average. Return the root of the subtree.

Example

Example 1
Input：
{1,-5,11,1,2,4,-2}
Output：11
Explanation:
The tree is look like this:
     1
   /   \
 -5     11
 / \   /  \
1   2 4    -2 
The average of subtree of 11 is 4.3333, is the maximun.
Example 2
Input：
{1,-5,11}
Output：11
Explanation:
     1
   /   \
 -5     11
The average of subtree of 1,-5,11 is 2.333,-5,11. So the subtree of 11 is the maximun.

Notice

LintCode will print the subtree which root is your return node.
It's guaranteed that there is only one subtree with maximum average.
Code (Java):
?
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
58
59
60
61
62
63
64
65
66
67
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
 
public class Solution {
    /**
     * @param root: the root of binary tree
     * @return: the root of the maximum average of subtree
     */
    public TreeNode findSubtree2(TreeNode root) {
        // write your code here
        if (root == null) {
            return null;
        }
         
        ResultType ans = findSubtree2Helper(root);
         
        return ans.node;
    }
     
    private ResultType findSubtree2Helper(TreeNode root) {
        if (root == null) {
            return new ResultType(0, 0, Integer.MIN_VALUE, null);
        }
         
        ResultType left = findSubtree2Helper(root.left);
        ResultType right = findSubtree2Helper(root.right);
         
        int sum = root.val + left.sum + right.sum;
        int numNodes = left.numNodes + right.numNodes + 1;
        double ave = (double) sum / numNodes;
        TreeNode node = null;
        if (ave > left.maxAve && ave > right.maxAve) {
            node = root;
        } else if (left.maxAve > ave && left.maxAve > right.maxAve) {
            ave = left.maxAve;
            node = left.node;
        }  else {
            ave = right.maxAve;
            node = right.node;
        }
         
        return new ResultType(sum, numNodes, ave, node);
    }
}
 
class ResultType {
    int sum;
    int numNodes;
    double maxAve;
    TreeNode node;
     
    public ResultType(int sum, int numNodes, double maxAve, TreeNode node) {
        this.sum = sum;
        this.numNodes = numNodes;
        this.maxAve = maxAve;
        this.node = node;
    }
}
Posted by at No comments:
Labels:

Lintcode 900. Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Example

Example1
Input: root = {5,4,9,2,#,8,10} and target = 6.124780
Output: 5
Example2
Input: root = {3,2,4,1} and target = 4.142857
Output: 4

Notice

  • Given target value is a floating point.
  • You are guaranteed to have only one unique value in the BST that is closest to the target.

Code (Java):
?
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
 
public class Solution {
    /**
     * @param root: the given BST
     * @param target: the given target
     * @return: the value in the BST that is closest to the target
     */
    public int closestValue(TreeNode root, double target) {
        // write your code here
        int floor = getFloor(root, target);
        int ceil = getCeil(root, target);
         
        if (floor == Integer.MIN_VALUE) {
            return ceil;
        }
         
        if (ceil == Integer.MIN_VALUE) {
            return floor;
        }
         
        if (Math.abs(floor - target) < Math.abs(ceil - target)) {
            return floor;
        } else {
            return ceil;
        }
    }
     
    private int getFloor(TreeNode root, double target) {
        TreeNode p = root;
        TreeNode parent = null;
         
        while (p != null) {
            if ((double)p.val == target) {
                return p.val;
            }
             
            if (p.val < target) {
                parent = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
         
        if (parent == null) {
            return Integer.MIN_VALUE;
        }
         
        return parent.val;
    }
     
    private int getCeil(TreeNode root, double target) {
        TreeNode p = root;
        TreeNode parent = null;
         
        while (p != null) {
            if ((double)p.val == target) {
                return p.val;
            }
             
            if (p.val < target) {
                p = p.right;
            } else {
                parent = p;
                p = p.left;
            }
        }
         
        if (parent == null) {
            return Integer.MIN_VALUE;
        }
         
        return parent.val;
    }
}
Posted by at No comments:
Labels:

Sunday, April 28, 2019

Lintcode 578. Lowest Common Ancestor III

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.
The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.
Return null if LCA does not exist.

Example

Example1
Input: 
{4, 3, 7, #, #, 5, 6}
3 5
5 6
6 7 
5 8
Output: 
4
7
7
null
Explanation:
  4
 / \
3   7
   / \
  5   6

LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
LCA(5, 8) = null
Example2
Input:
{1}
1 1
Output: 
1
Explanation:
The tree is just a node, whose value is 1.

Notice

node A or node B may not exist in tree.
Solution 1: Two pass
?
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
 
 
public class Solution {
    /*
     * @param root: The root of the binary tree.
     * @param A: A TreeNode
     * @param B: A TreeNode
     * @return: Return the LCA of the two nodes.
     */
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        // write your code here
        if (root == null) {
            return null;
        }
         
        if (doesExistInTree(root, A) == false || doesExistInTree(root, B) == false) {
            return null;
        }
         
        return lowestCommonAncestor3Helper(root, A, B);
    }
     
    private TreeNode lowestCommonAncestor3Helper(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null || root == A || root == B) {
            return root;
        }
         
        TreeNode left = lowestCommonAncestor3Helper(root.left, A, B);
        TreeNode right = lowestCommonAncestor3Helper(root.right, A, B);
         
        if (left != null && right != null) {
            return root;
        }
         
        if (left != null) {
            return left;
        }
         
        if (right != null) {
            return right;
        }
         
        return null;
    }
     
    private boolean doesExistInTree(TreeNode root, TreeNode A) {
        if (root == null) {
            return false;
        }
         
        if (root == A) {
            return true;
        }
         
        boolean left = doesExistInTree(root.left, A);
        boolean right = doesExistInTree(root.right, A);
         
        return left || right;
    }
}
Solution 2: One-pass Solution
?
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
 
 
public class Solution {
    /*
     * @param root: The root of the binary tree.
     * @param A: A TreeNode
     * @param B: A TreeNode
     * @return: Return the LCA of the two nodes.
     */
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        // write your code here
        if (root == null || A == null || B == null) {
            return null;
        }
         
        ResultType ans = lowestCommonAncestor3Helper(root, A, B);
         
        if (ans.hasA && ans.hasB) {
            return ans.node;
        }
         
        return null;
    }
     
    private ResultType lowestCommonAncestor3Helper(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null) {
            return new ResultType(false, false, null);
        }
         
        ResultType left = lowestCommonAncestor3Helper(root.left, A, B);
        ResultType right = lowestCommonAncestor3Helper(root.right, A, B);
         
        boolean hasA = root == A || left.hasA || right.hasA;
        boolean hasB = root == B || left.hasB || right.hasB;
         
        if (root == A || root == B) {
            return new ResultType(hasA, hasB, root);
        }
         
        if (left.node != null && right.node != null) {
            return new ResultType(hasA, hasB, root);
        }
         
        if (left.node != null) {
            return new ResultType(hasA, hasB, left.node);
        }
         
        if (right.node != null) {
            return new ResultType(hasA, hasB, right.node);
        }
         
        return new ResultType(hasA, hasB, null);
    }
}
 
class ResultType {
    boolean hasA;
    boolean hasB;
    TreeNode node;
     
    public ResultType(boolean hasA, boolean hasB, TreeNode node) {
        this.hasA = hasA;
        this.hasB = hasB;
        this.node = node;
    }
}
Posted by at No comments:
Labels:

Lintcode 596. Minimum Subtree

Given a binary tree, find the subtree with minimum sum. Return the root of the subtree.

Example

Example 1:
Input:
{1,-5,2,1,2,-4,-5}
Output:1
Explanation:
The tree is look like this:
     1
   /   \
 -5     2
 / \   /  \
0   2 -4  -5 
The sum of whole tree is minimum, so return the root.
Example 2:
Input:
{1}
Output:1
Explanation:
The tree is look like this:
   1
There is one and only one subtree in the tree. So we return 1.

Notice

LintCode will print the subtree which root is your return node.
It's guaranteed that there is only one subtree with minimum sum and the given binary tree is not an empty tree.

Code (Java):
?
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
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
 
public class Solution {
    /**
     * @param root: the root of binary tree
     * @return: the root of the minimum subtree
     */
    private TreeNode minNode = null;
    private int minSum = Integer.MAX_VALUE;
    public TreeNode findSubtree(TreeNode root) {
        // write your code here
        if (root == null) {
            return null;
        }
         
        findSubtreeHelper(root);
         
        return minNode;
    }
     
    private int findSubtreeHelper(TreeNode root) {
        if (root == null) {
            return 0;
        }
         
        int left = findSubtreeHelper(root.left);
        int right = findSubtreeHelper(root.right);
         
        int ret = root.val + left + right;
         
        if (ret < minSum) {
            minSum = ret;
            minNode = root;
        }
         
        return ret;
    }
}
Pure Divide and Conquer with ResultType
?
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
58
59
60
61
62
63
64
65
66
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
 
public class Solution {
    /**
     * @param root: the root of binary tree
     * @return: the root of the minimum subtree
     */
    public TreeNode findSubtree(TreeNode root) {
        // write your code here
        if (root == null) {
            return null;
        }
         
        ResultType ans = findSubtreeHelper(root);
         
        return ans.minNode;
    }
     
    private ResultType findSubtreeHelper(TreeNode root) {
        if (root == null) {
            return new ResultType(0, Integer.MAX_VALUE, null);
        }
         
        ResultType left = findSubtreeHelper(root.left);
        ResultType right = findSubtreeHelper(root.right);
         
        ResultType ans = new ResultType(root.val + left.sum + right.sum,
                                        root.val + left.sum + right.sum,
                                        root);
         
        if (left.minSum < ans.minSum) {
            ans.minSum = left.minSum;
            ans.minNode = left.minNode;
        }
         
        if (right.minSum < ans.minSum) {
            ans.minSum = right.minSum;
            ans.minNode = right.minNode;
        }
         
        return ans;
         
    }
}
 
class ResultType {
    int sum;
    int minSum;
    TreeNode minNode;
     
    public ResultType(int sum, int minSum, TreeNode minNode) {
        this.sum = sum;
        this.minSum = minSum;
        this.minNode = minNode;
    }
}
Posted by at No comments:
Labels:

Friday, April 26, 2019

Lintcode 573. Build Post Office II

Given a 2D grid, each cell is either a wall 2, an house 1 or empty 0 (the number zero, one, two), find a place to build a post office so that the sum of the distance from the post office to all the houses is smallest.
Return the smallest sum of distance. Return -1 if it is not possible.

Example

Example 1:
Input：[[0,1,0,0,0],[1,0,0,2,1],[0,1,0,0,0]]
Output：8
Explanation： Placing a post office at (1,1), the distance that post office to all the house sum is smallest.
Example 2:
Input：[[0,1,0],[1,0,1],[0,1,0]]
Output：4
Explanation： Placing a post office at (1,1), the distance that post office to all the house sum is smallest.

Challenge

Solve this problem within O(n^3) time.

Notice

  • You cannot pass through wall and house, but can pass through empty.
  • You only build post office on an empty.

Code (Java)
?
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
public class Solution {
    /**
     * @param grid: a 2D grid
     * @return: An integer
     */
    public int shortestDistance(int[][] grid) {
        // write your code here
        if (grid == null || grid.length == 0) {
            return 0;
        }
 
        int nRows = grid.length;
        int nCols = grid[0].length;
 
        int[][] numVisited = new int[nRows][nCols];
        int[][] minDist = new int[nRows][nCols];
        int numHouses = 0;
 
        for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nCols; j++) {
                if (grid[i][j] == 1) {
                    numHouses++;
                    bfs(grid, i, j, numVisited, minDist);
                }
            }
        }
 
        // Find the min minDist
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nCols; j++) {
                if (grid[i][j] == 0 && numVisited[i][j] == numHouses) {
                    ans = Math.min(ans, minDist[i][j]);
                }
            }
        }
 
        if (ans == Integer.MAX_VALUE) {
            return -1;
        }
 
        return ans;
    }
 
    private void bfs(int[][] grid, int x, int y, int[][] numVisited, int[][] minDist) {
        int nRows = grid.length;
        int nCols = grid[0].length;
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
        Queue<Integer> queue = new LinkedList<>();
        boolean[][] visited = new boolean[nRows][nCols];
 
        queue.offer(x * nCols + y);
        visited[x][y] = true;
 
        int distance = 0;
        while (!queue.isEmpty()) {
            distance += 1;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int index = queue.poll();
                for (int j = 0; j < 4; j++) {
                    int nx = index / nCols + dirs[j][0];
                    int ny = index % nCols + dirs[j][1];
 
                    if (isValid(grid, visited, nx, ny)) {
                        queue.offer(nx * nCols + ny);
                        visited[nx][ny] = true;
 
                        numVisited[nx][ny] += 1;
                        minDist[nx][ny] += distance;
                    }
                }
            }
        }
    }
 
    private boolean isValid(int[][] grid, boolean[][] visited, int x, int y) {
        int nRows = grid.length;
        int nCols = grid[0].length;
 
        return x >= 0 && x < nRows && y >= 0 && y < nCols && !visited[x][y] && grid[x][y] == 0;
    }
}
Posted by at No comments:
Labels:

Thursday, April 25, 2019

Lintcode 794. Sliding Puzzle II

On a 3x3 board, there are 8 tiles represented by the integers 1 through 8, and an empty square represented by 0.
A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.
Given an initial state of the puzzle board and final state, return the least number of moves required so that the initial state to final state.
If it is impossible to move from initial state to final state, return -1.

Example

Example 1:
Input:
[
 [2,8,3],
 [1,0,4],
 [7,6,5]
]
[
 [1,2,3],
 [8,0,4],
 [7,6,5]
]
Output:
4

Explanation:
[                 [
 [2,8,3],          [2,0,3],
 [1,0,4],   -->    [1,8,4],
 [7,6,5]           [7,6,5]
]                 ]

[                 [
 [2,0,3],          [0,2,3],
 [1,8,4],   -->    [1,8,4],
 [7,6,5]           [7,6,5]
]                 ]

[                 [
 [0,2,3],          [1,2,3],
 [1,8,4],   -->    [0,8,4],
 [7,6,5]           [7,6,5]
]                 ]

[                 [
 [1,2,3],          [1,2,3],
 [0,8,4],   -->    [8,0,4],
 [7,6,5]           [7,6,5]
]                 ]
Example 2：
Input:
[[2,3,8],[7,0,5],[1,6,4]]
[[1,2,3],[8,0,4],[7,6,5]]
Output:
-1

Challenge

  • How to optimize the memory?
  • Can you solve it with A* algorithm?

Code (Java):
?
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
public class Solution {
    /**
     * @param init_state: the initial state of chessboard
     * @param final_state: the final state of chessboard
     * @return: return an integer, denote the number of minimum moving
     */
    public int minMoveStep(int[][] init_state, int[][] final_state) {
        String start = matrixToString(init_state);
        String end = matrixToString(final_state);
 
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
 
        queue.offer(start);
        visited.add(start);
 
        int numSteps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String currState = queue.poll();
                if (currState.equals(end)) {
                    return numSteps;
                }
 
                for (String nextState : getNextStates(currState)) {
                    if (!visited.contains(nextState)) {
                        queue.offer(nextState);
                        visited.add(nextState);
                    }
                }
            }
 
            numSteps++;
        }
 
        return -1;
    }
 
    private String matrixToString(int[][] matrix) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                sb.append(matrix[i][j]);
            }
        }
 
        return sb.toString();
    }
 
    private List<String> getNextStates(String state) {
        int index = state.indexOf('0');
        int x = index / 3;
        int y = index % 3;
 
        List<String> ans = new ArrayList<>();
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dirs[i][0];
            int ny = y + dirs[i][1];
 
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                char[] stateChar = state.toCharArray();
                stateChar[x * 3 + y] = stateChar[nx * 3 + ny];
                stateChar[nx * 3 + ny] = '0';
                ans.add(new String(stateChar));
            }
        }
 
        return ans;
    }
 
}
Posted by at No comments:
Labels:

Lintcode 531. Six Degrees

Six degrees of separation is the theory that everyone and everything is six or fewer steps away, by way of introduction, from any other person in the world, so that a chain of "a friend of a friend" statements can be made to connect any two people in a maximum of six steps.
Given a friendship relations, find the degrees of two people, return -1 if they can not been connected by friends of friends.

Example

Example1
Input: {1,2,3#2,1,4#3,1,4#4,2,3} and s = 1, t = 4 
Output: 2
Explanation:
    1------2-----4
     \          /
      \        /
       \--3--/
Example2
Input: {1#2,4#3,4#4,2,3} and s = 1, t = 4
Output: -1
Explanation:
    1      2-----4
                 /
               /
              3
Code (Java):
?
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
58
59
60
61
/**
 * Definition for Undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) {
 *         label = x;
 *         neighbors = new ArrayList<UndirectedGraphNode>();
 *     }
 * };
 */
 
 
public class Solution {
    /*
     * @param graph: a list of Undirected graph node
     * @param s: Undirected graph node
     * @param t: Undirected graph nodes
     * @return: an integer
     */
    public int sixDegrees(List<UndirectedGraphNode> graph, UndirectedGraphNode s, UndirectedGraphNode t) {
        // write your code here
        if (graph == null || graph.size() == 0) {
            return 0;
        }
 
        // build the graph
        //
        Map<UndirectedGraphNode, List<UndirectedGraphNode>> adjList = new HashMap<>();
        for (UndirectedGraphNode node : graph) {
            adjList.put(node, node.neighbors);
        }
 
        int len = 0;
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        Set<UndirectedGraphNode> visited = new HashSet<>();
 
        queue.offer(s);
        visited.add(s);
 
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                UndirectedGraphNode curNode = queue.poll();
                if (curNode == t) {
                    return len;
                }
 
                for (UndirectedGraphNode neighbor : adjList.get(curNode)) {
                    if (!visited.contains(neighbor)) {
                        queue.offer(neighbor);
                        visited.add(neighbor);
                    }
                }
            }
            len += 1;
        }
 
        return -1;
    }
}
Posted by at 1 comment:
Labels:

Lintcode 598. Zombie in Matrix

Given a 2D grid, each cell is either a wall 2, a zombie 1 or people 0 (the number zero, one, two).Zombies can turn the nearest people(up/down/left/right) into zombies every day, but can not through wall. How long will it take to turn all people into zombies? Return -1 if can not turn all people into zombies.

Example

Example 1:
Input:
[[0,1,2,0,0],
 [1,0,0,2,1],
 [0,1,0,0,0]]
Output:
2
Example 2:
Input:
[[0,0,0],
 [0,0,0],
 [0,0,1]]
Output:
4
Code (Java):
?
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
58
59
60
61
62
63
64
65
66
67
68
public class Solution {
    /**
     * @param grid: a 2D integer grid
     * @return: an integer
     */
    public int zombie(int[][] grid) {
        // write your code here
        if (grid == null || grid.length == 0) {
            return 0;
        }
 
        int ans = 0;
        int nRows = grid.length;
        int nCols = grid[0].length;
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
        Queue<Integer> queue = new LinkedList<>();
        boolean[][] visited = new boolean[nRows][nCols];
 
        // step 1: put all 1s to the queue
        //
        for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nCols; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(i * nCols + j);
                    visited[i][j] = true;
                }
            }
        }
 
        while (!queue.isEmpty()) {
            int size = queue.size();
            ans += 1;
            for (int i = 0; i < size; i++) {
                int curNode = queue.poll();
                for (int j = 0; j < 4; j++) {
                    int nx = curNode / nCols + dirs[j][0];
                    int ny = curNode % nCols + dirs[j][1];
 
                    if (isValid(grid, visited, nx, ny)) {
                        queue.offer(nx * nCols + ny);
                        visited[nx][ny] = true;
                        grid[nx][ny] = 1; // mark as zoobie
                    }
                }
            }
        }
 
        // finally check if there are still zero 0s
        //
        for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nCols; j++) {
                if (grid[i][j] == 0) {
                    return -1;
                }
            }
        }
 
        return ans;
    }
 
    private boolean isValid(int[][] grid, boolean[][] visited, int x, int y) {
        int nRows = grid.length;
        int nCols = grid[0].length;
 
        return x >= 0 && x < nRows && y >= 0 && y < nCols && !visited[x][y] && grid[x][y] == 0;
    }
}
Posted by at No comments:
Labels:

Lintcode 618. Search Graph Nodes

Given a undirected graph, a node and a target, return the nearest node to given node which value of it is target, return NULL if you can't find.
There is a mapping store the nodes' values in the given parameters.

Example

Example 1:
Input:
{1,2,3,4#2,1,3#3,1#4,1,5#5,4}
[3,4,5,50,50]
1
50
Output:
4
Explanation:
2------3  5
 \     |  | 
  \    |  |
   \   |  |
    \  |  |
      1 --4
Give a node 1, target is 50

there a hash named values which is [3,4,10,50,50], represent:
Value of node 1 is 3
Value of node 2 is 4
Value of node 3 is 10
Value of node 4 is 50
Value of node 5 is 50

Return node 4
Example 2:
Input:
{1,2#2,1}
[0,1]
1
1
Output:
2

Notice

It's guaranteed there is only one available solution
Code (Java):
?
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
/**
 * Definition for graph node.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) {
 *         label = x; neighbors = new ArrayList<UndirectedGraphNode>();
 *     }
 * };
 */
 
 
public class Solution {
    /*
     * @param graph: a list of Undirected graph node
     * @param values: a hash mapping, <UndirectedGraphNode, (int)value>
     * @param node: an Undirected graph node
     * @param target: An integer
     * @return: a node
     */
    public UndirectedGraphNode searchNode(ArrayList<UndirectedGraphNode> graph,
                                          Map<UndirectedGraphNode, Integer> values,
                                          UndirectedGraphNode node,
                                          int target) {
        // BFS
        //
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        Set<UndirectedGraphNode> visited = new HashSet<>();
 
        // pre-process the graph
        //
        Map<UndirectedGraphNode, List<UndirectedGraphNode>> adjList  = new HashMap<>();
        for (UndirectedGraphNode e : graph) {
            adjList.put(e, e.neighbors);
        }
 
        queue.offer(node);
        visited.add(node);
 
        while (!queue.isEmpty()) {
            UndirectedGraphNode curNode = queue.poll();
            if (values.get(curNode) == target) {
                return curNode;
            }
 
            for (UndirectedGraphNode neighbor : adjList.get(curNode)) {
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
 
        return null;
    }
}
Posted by at No comments:
Labels:

Lintcode 624. Remove Substrings

Given a string s and a set of n substrings. You are supposed to remove every instance of those n substrings from s so that s is of the minimum length and output this minimum length.

Example

Example 1:
Input:
"ccdaabcdbb"
["ab","cd"]
Output:
2
Explanation: 
ccdaabcdbb -> ccdacdbb -> cabb -> cb (length = 2)
Example 2:
Input:
"abcabd"
["ab","abcd"]
Output:
0
Explanation: 
abcabd -> abcd -> "" (length = 0)

Solution: BFS
?
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
public class Solution {
    /*
     * @param s: a string
     * @param dict: a set of n substrings
     * @return: the minimum length
     */
    public int minLength(String s, Set<String> dict) {
        // write your code here
        if (s == null || s.length() == 0) {
            return 0;
        }
 
        if (dict == null || dict.size() == 0) {
            return s.length();
        }
 
        // BFS
        //
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(s);
        visited.add(s);
 
        int ans = s.length();
 
        while (!queue.isEmpty()) {
            String curStr = queue.poll();
            for (String dictWord : dict) {
                for (int i = 0; i < curStr.length(); i++) {
                    int startIdx = curStr.indexOf(dictWord, i);
                    if (startIdx != -1) {
                        String newStr = curStr.substring(0, startIdx) + curStr.substring(startIdx + dictWord.length());
                         
                        if (newStr.length() < ans) {
                            ans = newStr.length();
                        }
 
                        if (!visited.contains(newStr)) {
                            queue.offer(newStr);
                            visited.add(newStr);
                        }
                    }
                }
            }
        }
 
        return ans;
    }
}

Posted by at No comments:
Labels:

Tuesday, April 23, 2019

Lintcode 605. Sequence Reconstruction

Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 10^4. Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.

Example

Example 1:
Input:org = [1,2,3], seqs = [[1,2],[1,3]]
Output: false
Explanation:
[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.
Example 2:
Input: org = [1,2,3], seqs = [[1,2]]
Output: false
Explanation:
The reconstructed sequence can only be [1,2].
Example 3:
Input: org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
Output: true
Explanation:
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].
Example 4:
Input:org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
Output:true
Code (Java):
?
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
public class Solution {
    /**
     * @param org: a permutation of the integers from 1 to n
     * @param seqs: a list of sequences
     * @return: true if it can be reconstructed only one or false
     */
    public boolean sequenceReconstruction(int[] org, int[][] seqs) {
        // write your code here
        if (org == null || org.length == 0) {
            if(seqs == null || seqs.length == 0) {
                return true;
            }
             
            for (int[] seq : seqs) {
                if (seq != null && seq.length != 0) {
                    return false;
                }
            }
             
            return true;
        }
        if (seqs == null || seqs.length == 0) {
            return false;
        }
        for (int[] seq : seqs) {
            if (seq.length == 0) {
                return false;
            }
        }
         
        int numNodes = org.length;
         
        // step 1: build graph
        //
        Map<Integer, Set<Integer>> graph  = new HashMap<>();
        boolean validGraph = buildGraph(numNodes, seqs, graph);
        if (!validGraph) {
            return false;
        }
         
         
        // step 2: topological sorting
        //
        int[] ans = new int[numNodes];
        boolean isValid = toplogicalSorting(graph, ans);
        if (!isValid) {
            return false;
        }
         
        for (int i = 0; i < numNodes; i++) {
            if (org[i] != ans[i]) {
                return false;
            }
        }
         
        return true;
    }
     
    private boolean buildGraph(int numNodes, int[][] seqs, Map<Integer, Set<Integer>> adjList) {
        // create nodes
        //
        for (int i = 1; i <= numNodes; i++) {
            adjList.put(i, new HashSet<>());
        }
         
        // create edges
        //
        for (int[] seq : seqs) {
            for (int j = 0; j < seq.length; j++) {
                if (seq[j] <= 0 || seq[j] > numNodes) {
                    return false;
                }
                if (j != seq.length - 1) {
                    adjList.get(seq[j]).add(seq[j + 1]);
                }
            }
        }
         
        return true;
    }
     
    private boolean toplogicalSorting(Map<Integer, Set<Integer>> adjList, int[] ans) {
        int index = 0;
        // step 1: create indegree Map
        //
        Map<Integer, Integer> indegreeMap = new HashMap<>();
        int numNodes = ans.length;
        for (int i = 1; i <= numNodes; i++) {
            indegreeMap.put(i, 0);
        }
         
        for (int node : adjList.keySet()) {
            for (int neighbor : adjList.get(node)) {
                int indegree = indegreeMap.get(neighbor);
                indegree += 1;
                indegreeMap.put(neighbor, indegree);
            }
        }
         
        // step 2: get all nodes with 0 indegree
        //
        Queue<Integer> queue = new LinkedList<>();
        for (int node : indegreeMap.keySet()) {
            if (indegreeMap.get(node) == 0) {
                queue.offer(node);
            }
             
            if (queue.size() > 1) {
                return false;
            }
        }
         
        // step 3: poll all nodes from the queue, remove the indegree by 1 for the neighbors
        //
        while (!queue.isEmpty()) {
            int curNode = queue.poll();
            ans[index++] = curNode;
             
            for (int neighbor : adjList.get(curNode)) {
                int indegree = indegreeMap.get(neighbor) - 1;
                indegreeMap.put(neighbor, indegree);
                if (indegree == 0) {
                    queue.offer(neighbor);
                }
            }
             
            if (queue.size() > 1) {
                return false;
            }
        }
         
        return index == numNodes;
    }
}

Posted by at No comments:
Labels:
Subscribe to: Posts (Atom)