Monday, April 26, 2021

Print All Topology Sort

Link

本体是二流就（alien dictionary)。很快秒了，但是追加是输出所有topological sort的组合。卡在这了，

我当时的思路是DFS preprocessing每一个字母可以reach的set，做permutation，reachable的不互换。写着写着发现不对。。。

 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
package AllTopologSort;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world");
        Map<Character, List<Character>> links = new HashMap<>();
        links.put('A', new ArrayList<>());
        links.put('B', new ArrayList<>());
        links.put('C', new ArrayList<>());
        links.put('D', new ArrayList<>());
        links.put('E', new ArrayList<>());

        links.get('A').add('B');
        links.get('A').add('C');
        links.get('B').add('C');

        Map<Character, State> states = new HashMap<>();
        states.put('A', State.INITIVAL);
        states.put('B', State.INITIVAL);
        states.put('C', State.INITIVAL);
        states.put('D', State.INITIVAL);
        states.put('E', State.INITIVAL);

        Map<Character, Integer> degrees = new HashMap<>();
        degrees.put('A', 0);
        degrees.put('B', 1);
        degrees.put('C', 2);
        degrees.put('D', 0);
        degrees.put('E', 0);

        printAllTopologySort(links, states, degrees, new ArrayList<>(), links.size());
    }

    enum State {
        INITIVAL, VISITING, DONE
    }

    static void printAllTopologySort(Map<Character, List<Character>> links, 
                                     Map<Character, State> states,
                                     Map<Character, Integer> degrees,
                                     List<Character> path,
                                     int n) {
        if(path.size() == n){
            System.out.println(path);
        }
        for(char key : links.keySet()){
            if(degrees.get(key)==0 && states.get(key)==State.INITIVAL){
                for(char next : links.get(key)){
                    degrees.put(next, degrees.get(next)-1);
                }
                states.put(key, State.VISITING);
                path.add(key);
                printAllTopologySort(links, states, degrees, path, n);
                states.put(key, State.INITIVAL);
                for(char next : links.get(key)){
                    degrees.put(next, degrees.get(next)+1);
                }
                path.remove(path.size()-1);
            }
        }
    }
}
Posted by at No comments:

Number of Ways Fully Traverse a Matrix

Link


4、一个4*5迷宫里，给定起点终点和障碍，有多少种方法能够从起点走到终点，并把所有的非障碍点都走过。最开始是四个方向，然后问如果八个方向怎么办 ，如果是国际象棋皇后怎么办

 

第四题给的数据规模很小，是不是就是dfs暴力就可以了？

嗨，楼主，最后一题有步数限制嘛？如果没步数限制的话岂不是可以有无数种可能了吗？把所有非障碍点走一遍

10000

00***

00002

 

上图中，1是起点，星号是障碍物，2是终点，这种情况下，如果还得把所有非障碍点都走过一遍的话，第一行的第二列，第三列，第四列都得走两遍，

那上图还是一个VALID的INPUT吗？ 如果是的话，就代表一个点可以走无数遍，如果一个点可以走无数遍，那答案不久无穷大了吗？

 

我写的dfs 然后followup那里的话复杂度爆炸了

 

就是每个点走过且只走一遍，步数是定死的

这个题，要求总共多少种走法，听起来像是动规了。

但是，走的方向是四个方向。没有明显看起来可以递归求解的地方，不知道从哪里下手

segment tree可以handle mutable inputs

 

能想到只有backtrack，太brutal force了，如果有toplogical order的话应该可以用dp

 

是不是可以四维状压dp？dp[x][y][step][state]，起始状态dp[x0][y0][0][state1]，终止状态dp[x1][y1][k][state2]。(x0, y0) = 起点，(x1, y1) = 终点，k = 除了起点、终点和障碍外的格子总数目+1，state都是20位二进制，state1 = 把起点位置设为1，state2 = 除了障碍物以外的所有位置都是1。循环最外层按步数从0到k遍历，内层就不用说了。时间复杂度O(20 * 20 * 方向数 * (1 << 20))

 

 

最后一题可以用DP么，或者说dfs + cache.

 

dp[i][j] means from start to {i, j}, how many ways to reach {i,j},  还需要记录访问了多少空点.

 

dp[i][j]  = if ([i-1][j] not visited) + dp[i-1][j]  same to {i + 1, j} {i, j-1} {i, j + 1}.  另外感觉起点和终点有一定的限制, 如果两点是全局 4 * 5 随机的话, 会非常复杂。 这个时候貌似就需要用双向dfs+ cache了。 也就是从起点, 和终点各自开始dfs, 有相交点时, 两个的遍历必须访问了所有空点, 然后走法是相乘。 当然，做这些都是个人猜的，不一定work.

 

最后那个用 dp bitmask？ 毕竟网格很少

如果每个点走过且走以遍，步数是定死的话，步数要求就是所有可以走的点的个数呗。那么就算可以走四个方向，应该也可以动规。

不用记录之前走过哪些点，只用记录现在的位置，和走过的步数。

等步数到了上限的时候，发觉自己还没在终点，就返回0，在终点的话就返回1.因为如果步数又到了上限，人也在终点，那不就是代表所有可以走的点都走过了，而且只走了一遍嘛？

以上思路是DFS+MEMO。

所以是DP[ROW][COL][STEPS]

 

最后一题需要状态压缩，每个状态包含当前坐标x，y以及所有已经走过的点，因为4x5，可以用一个整数表示x，y 以及20个点，如果嫌状态压缩麻烦，可以只压缩所有已经走过的点，可以用一个三维数组保存状态[X][Y][status] 




 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
import java.util.*;
public class Main {
    public static void main(String[] args) {
        System.out.println("heello world");
        
        int[][] matrix = new int[][]{{0,0,0},{0,0,0},{0,0,0}};
        Problem pb = new Problem(matrix);;
        int r = pb.getWays();
        System.out.println(r);
        
    }
}

class Problem{
    int[][] matrix;
    int m, n;
    int[][] dir = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    int[][][] dp;
    Problem(int[][] _matrix){
        matrix = _matrix;
        m = matrix.length;
        n = matrix[0].length;
    }

    int getWays(){
        int N = m*n;
        dp = new int[m][n][(int)Math.pow(2,N)];
        dp[0][0][1] = 1;
        int fullState = 0;
        
        for(int i=0; i<N; ++i){
            fullState |= 1<<i;
        }
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(matrix[i][j]==1){//block
                    int k = i*n+j;
                    fullState = fullState & (~(1<<k));
                }
            }
        }

        helper(0, 0, 1);

        return dp[m-1][n-1][fullState];
    }

    void helper(int i, int j, int state){
        for(int[] d : dir){
            int i0 = i+d[0], j0 = j+d[1];
            if(i0>=0 && i0<m && j0>=0 && j0<n && matrix[i0][j0]==0){
                int k = i0*n+j0;
                int mask = 1<<k;
                if((state&mask) !=0 ) continue;//visited alreay
                int state0 = state | mask;
                dp[i0][j0][state0] += dp[i][j][state];
                helper(i0, j0, state0);
            }
        }
    }
}
Posted by at No comments:

Range product (Binary Index Tree)

 arr = [1,2,3,4,5,6,7]. return the sub array product [i, j].

https://iq.opengenus.org/fenwick-tree-range-product/


 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
import java.util.*;
public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world");

        RangeProduct rp = new RangeProduct(new int[]{1,2,3,4,5,6,7});
        rp.buildBIT();
        rp.print();
        //System.out.println(rp.getPrefixProd(5));
        System.out.println(rp.getRangeProd(1, 3));
        

    }
}

class RangeProduct{
    int[] arr;
    int n;
    int[] bit;

    RangeProduct(int[] _arr){
        arr = _arr;
        n = arr.length;
    }

    int getParent(int x){
        return x - (x&(-x));
    }

    int getNext(int x){
        return x + (x&(-x));
    }

    //nlogn
    void buildBIT(){
        bit = new int[n+1];
        Arrays.fill(bit, 1);
        for(int i=1; i<=n; ++i){
            int v = arr[i-1];
            int j = i;
            while(j<=n){
                bit[j] *= v;
                j = getNext(j);
            }
        }
    }

    int getPrefixProd(int i){
        i++;
        int prod = 1;
        while(i>0){
            prod *= bit[i];
            i = getParent(i);
        }
        return prod;
    }

    int getRangeProd(int i, int j){
        int prodj = getPrefixProd(j);
        int prodi = i==0 ? 1 : getPrefixProd(i-1);
        if(prodi!=0) return prodj/prodi;

        j++;
        int parent = getParent(j);
        int prod = 1;
        while(parent>=i){
            if(bit[j]==0) return 0;
            prod *= bit[j];
            j = parent;
            parent = getNext(j);
        }
        while(j>i){
            if(arr[j-1]==0) return 0;
            prod*=arr[j-1];
            j--;
        }
        return prod;
    }

    void print(){
        System.out.println(Arrays.toString(bit));
    }
}
Posted by at No comments:

Thursday, April 15, 2021

LeetCode [1448] Count Good Nodes in Binary Tree

 1448. Count Good Nodes in Binary Tree

Medium

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

 

Example 1:

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.

Example 2:

Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Example 3:

Input: root = [1]
Output: 1
Explanation: Root is considered as good.

 

Constraints:

  • The number of nodes in the binary tree is in the range [1, 10^5].
  • Each node's value is between [-10^4, 10^4].

 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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int cnt = 0;
    public int goodNodes(TreeNode root) {
        helper(root, Integer.MIN_VALUE);
        return cnt;
    }
    
    void helper(TreeNode node, int max){
        if(node==null) return;
        if(node.val>=max) cnt++;
        int m = Math.max(max, node.val);
        helper(node.left, m);
        helper(node.right, m);
    }
}
Posted by at No comments:

Saturday, April 3, 2021

LeetCode [938] Range Sum of BST

 938. Range Sum of BST

Easy

Given the root node of a binary search tree, return the sum of values of all nodes with a value in the range [low, high].

 

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23

 

Constraints:

  • The number of nodes in the tree is in the range [1, 2 * 104].
  • 1 <= Node.val <= 105
  • 1 <= low <= high <= 105
  • All Node.val are unique.

 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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int sum = 0;
    public int rangeSumBST(TreeNode root, int low, int high) {
        helper(root, low, high);
        return sum;
    }
    
    void helper(TreeNode node, int low, int high){
        if(node==null) return;
        if(node.val>=low && node.val<=high) sum += node.val;
        if(!(node.val<=low)) helper(node.left, low, high);
        if(!(node.val>=high)) helper(node.right, low, high);
    }
}
Posted by at No comments:

Friday, April 2, 2021

LeetCode [1570] Dot Product of Two Sparse Vectors

 1570. Dot Product of Two Sparse Vectors

Medium

Given two sparse vectors, compute their dot product.

Implement class SparseVector:

  • SparseVector(nums) Initializes the object with the vector nums
  • dotProduct(vec) Compute the dot product between the instance of SparseVector and vec

A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.

Follow up: What if only one of the vectors is sparse?

 

Example 1:

Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8

Example 2:

Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]
Output: 0
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 0

Example 3:

Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]
Output: 6

 

Constraints:

  • n == nums1.length == nums2.length
  • 1 <= n <= 10^5
  • 0 <= nums1[i], nums2[i] <= 100

 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 SparseVector {
    Map<Integer, Integer> map;
    SparseVector(int[] nums) {
        map = new HashMap<>();
        for(int i=0; i<nums.length; ++i){
            map.put(i, nums[i]);
        }
    }
    
	// Return the dotProduct of two sparse vectors
    public int dotProduct(SparseVector vec) {
        int sz1 = map.size();
        int sz2 = vec.map.size();
        if(sz1<sz2) return helper(map, vec.map);
        else return helper(vec.map, map);
    }
    
    int helper(Map<Integer, Integer> map1, Map<Integer, Integer> map2){
        int s = 0;
        for(Map.Entry<Integer, Integer> en : map1.entrySet()){
            int index = en.getKey();
            int value = en.getValue();
            if(map2.containsKey(index)){
                s += value*map2.get(index);
            }
        }
        return s;
    }
}

// Your SparseVector object will be instantiated and called as such:
// SparseVector v1 = new SparseVector(nums1);
// SparseVector v2 = new SparseVector(nums2);
// int ans = v1.dotProduct(v2);
Posted by at No comments:
Subscribe to: Posts (Atom)