LIKE CODING: April 2021

Thursday, April 29, 2021

LeetCode [1460] Make Two Arrays Equal by Reversing Sub-arrays

1460. Make Two Arrays Equal by Reversing Sub-arrays

Easy

Given two integer arrays of equal length target and arr.

In one step, you can select any non-empty sub-array of arr and reverse it. You are allowed to make any number of steps.

Return True if you can make arr equal to target, or False otherwise.

Example 1:

Input: target = [1,2,3,4], arr = [2,4,1,3]
Output: true
Explanation: You can follow the next steps to convert arr to target:
1- Reverse sub-array [2,4,1], arr becomes [1,4,2,3]
2- Reverse sub-array [4,2], arr becomes [1,2,4,3]
3- Reverse sub-array [4,3], arr becomes [1,2,3,4]
There are multiple ways to convert arr to target, this is not the only way to do so.

Example 2:

Input: target = [7], arr = [7]
Output: true
Explanation: arr is equal to target without any reverses.

Example 3:

Input: target = [1,12], arr = [12,1]
Output: true

Example 4:

Input: target = [3,7,9], arr = [3,7,11]
Output: false
Explanation: arr doesn't have value 9 and it can never be converted to target.

Example 5:

Input: target = [1,1,1,1,1], arr = [1,1,1,1,1]
Output: true

Constraints:

target.length == arr.length
1 <= target.length <= 1000
1 <= target[i] <= 1000
1 <= arr[i] <= 1000

class Solution {
    public boolean canBeEqual(int[] target, int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i : target) map.put(i, map.getOrDefault(i, 0)+1);
        for(int i : arr) map.put(i, map.getOrDefault(i, 0)-1);
        for(int k : map.keySet()){
            if(map.get(k)!=0) return false;
        }
        return true;
    }
}

Wednesday, April 28, 2021

Shortest Cycle in a Directed Graph

https://stackoverflow.com/questions/3911626/find-cycle-of-shortest-length-in-a-directed-graph-with-positive-weights

package ShortestCycle;

import java.util.*;
public class Main {
    public static void main(String[] args) {
        System.out.println("Shortest Cycle");

        Map<Integer, List<Integer>> map = new HashMap<>();
        map.put(0, new ArrayList<>());
        map.put(1, new ArrayList<>());
        map.put(2, new ArrayList<>());
        map.put(3, new ArrayList<>());
        map.put(4, new ArrayList<>());

        map.get(0).add(1);
        map.get(0).add(2);
        map.get(1).add(3);
        map.get(2).add(4);
        map.get(3).add(0);
        map.get(4).add(3);

        List<Integer> prev = new ArrayList<>();
        prev.add(3);

        int[] dist = new int[5];
        Arrays.fill(dist, Integer.MAX_VALUE);
        //dist, index
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0]-b[0]);
        pq.add(new int[]{0, 0});
        while(!pq.isEmpty()){
            int[] top = pq.poll();
            int d = top[0], index = top[1];
            if(d<dist[index]){
                dist[index] = d;
                if(map.containsKey(index)){
                    for(int next : map.get(index)){
                        if(d+1 < dist[next]){
                            pq.add(new int[]{d+1, next});
                        }
                    }
                }
            }
        }

        int min = Integer.MAX_VALUE;
        for(int p : prev){
            min = Math.min(min, dist[p]);
        }
        System.out.println(min+1);
    }
}

Tuesday, April 27, 2021

SnakeAndLadder

Link

package SnakeLadder;

import java.util.*;

public class Main {
    static int N;// number of cells
    static int[] moves;// end of snake or ladder

    public static void main(String[] args) {
        N = 30;
        moves = new int[N];
        Arrays.fill(moves, -1);
        // Ladders
        moves[2] = 21;
        moves[4] = 7;
        moves[10] = 25;
        moves[19] = 28;

        // Snakes
        moves[26] = 0;
        moves[20] = 8;
        moves[16] = 3;
        moves[18] = 6;

        int p = getMinPath();
        System.out.println(p);
    }

    static int getMinPath(){
        Queue<Integer> que = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        que.add(0);
        visited.add(0);
        int path = 0;
        
        while(!que.isEmpty()){
            int sz = que.size();
            for(int i=0; i<sz; ++i){
                int cell = que.poll();
                if(cell==(N-1)) return path;

                for(int k=1; k<=6; ++k){
                    if(cell+k<N && !visited.contains(cell+k)){
                        que.add(cell+k);
                        visited.add(cell+k);

                        if(moves[cell+k]>=0){
                            que.add(moves[cell+k]);
                            visited.add(moves[cell+k]);
                        } 
                    }
                }
            }
            path++;
        }

        return path;
    }
}

Employee architecture

Link

题目大意应该是给雇主关系结构图，是direct graph，会给adjacent list，好像允许有employee有>=1 boss。一般首先会问这个关系是不是valid ？

我个人的理解valid是两个条件:

1. 所有的node都在一个群，有一个root。

2. 不能有cycle。

因为题目允许有>=1 个boss，所以indgree可以>=1。

我思路是两部：

1.所以node一个群，把图当成indirect graph，然后union find，看最后是不是所有都connected。

2.有向图 check cycle。

如果两步都通过，就说明是valid。

1. 地里最近常出现的雇主关系题最开始就是dfs找有多少个员工 followup就是讨论一下各种可能出现的情况包括loop怎么判断

检查是树还是森林，使用dfs在无向graph上即可。

有无cycle，蠡口，儿凝器canFinish()最简单的是topological sort。

DFS无向图，从任何一点出发，走一边能全部visit并且不会遇到visited的node，就是tree吗？

不过这个题目，结构可能不是标准的tree，因为可能允许一个node有多个parent。这样用DFS可能不行。

恩， topological sorting查有向图cycle也可以。

orginization employee architecture, find eid score from repporting tree, find loops and dual reporting in reporting tree. 应该属于简单题，就是层次多。

package EmploySystem;

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Map<Character, List<Character>> map = new HashMap<>();
        map.put('A', new ArrayList<>());
        map.put('B', new ArrayList<>());
        map.put('C', new ArrayList<>());
        map.put('D', new ArrayList<>());
        map.put('E', new ArrayList<>());

        map.get('A').add('B');
        map.get('A').add('C');
        map.get('A').add('E');
        map.get('B').add('A');
        map.get('D').add('E');

        boolean valid = isValid(map);
        System.out.println("Valid: " + valid);
        if(valid){
            Set<Character> employees = getAllEmployees('A', map);
            System.out.println(employees.toString());
        }
    }

    static boolean hasCycle(Map<Character, List<Character>> map, 
                            Set<Character> visited,
                            Set<Character> path,
                            char employee){
        visited.add(employee);
        if(map.containsKey(employee)){
            for(char next : map.get(employee)){
                if(path.contains(next)) return true;
                if(!visited.contains(next)){
                    path.add(next);
                    if(hasCycle(map, visited, path, next)) return true;
                    path.remove(next);
                }
            }
        }
        return false;
    }

    static boolean isValid(Map<Character, List<Character>> map){
        Set<Character> visited = new HashSet<>();
        Set<Character> path = new HashSet<>();
        for(char employee : map.keySet()){
            path.add(employee);
            if(hasCycle(map, visited, path, employee)) return false;
            path.remove(employee);
        }
        return true;
    }

    static Set<Character> getAllEmployees(char employer, 
                                          Map<Character, List<Character>> map){
        Set<Character> employees = new HashSet<>();
        if(map.containsKey(employer)){
            for(char employee : map.get(employer)){
                employees.add(employee);
                employees.addAll(getAllEmployees(employee, map));
            }
        }
        return employees;
    }
}

Monday, April 26, 2021

Print All Topology Sort

Link

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

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

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

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]

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