LeetCode(85) -- 684, 60

P684. Redundant Connection (Medium)

找出第一个形成环的边。

Solution

DFS：

class Solution {
    Set<Integer> seen = new HashSet();
    int MAX_EDGE_VAL = 1000;

    public int[] findRedundantConnection(int[][] edges) {
        // graph 用一个ArrayList的数组来表示。也就是每一个节点的邻居有哪些
        ArrayList<Integer>[] graph = new ArrayList[MAX_EDGE_VAL + 1];
        // 从0到1000，给每个节点都初始化一个空的List
        for (int i = 0; i <= MAX_EDGE_VAL; i++) {
            graph[i] = new ArrayList();
        }

        for (int[] edge: edges) {
            seen.clear();
            if (!graph[edge[0]].isEmpty() && !graph[edge[1]].isEmpty() && dfs(graph, edge[0], edge[1])) {
                return edge;
            }
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        throw new AssertionError();
    }

    public boolean dfs(ArrayList<Integer>[] graph, int source, int target) {
        if (!seen.contains(source)) {
            seen.add(source);
            if (source == target) {
                return true;
            }
            for (int neighbor: graph[source]) {
                if (dfs(graph, neighbor, target)) {
                    return true;
                }
            }
        }
        return false;
    }
}

14%

The Best Solution

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int N = edges.length;
        UnionFind uf = new UnionFind(N + 1);
        
        for (int[] edge : edges) {
            int start = edge[0], end = edge[1];
            if (!uf.union(start, end)) 
                return edge;
        }
        return new int[2];
    }
}

class UnionFind {
    private int[] parent;
    
    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        } 
    }
    
    public boolean union(int i, int j) {
        int p_i = find(i), p_j = find(j);
        if (p_i == p_j) {
            return false;
        }
        parent[p_j] = p_i;
        return true;
    }
    
    public int find(int child) {
        if (parent[child] != child) {
            parent[child] = find(parent[child]);
        }
        return parent[child];
    }
}

P60. Permutation Sequence (Medium)

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

“123” “132” “213” “231” “312” “321” Given n and k, return the kth permutation sequence.

My Solution

class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> digits = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            digits.add(i);
        }
        StringBuilder sb = new StringBuilder();
        while (k != 0) {
            int f = factorial(n - 1);
            int index = (k - 1) / f;
            sb.append(digits.get(index));
            digits.remove(index);
            k %= f;
            n--;
        }
        while (digits.size() > 0) {
            int last = digits.size() - 1;
            sb.append(digits.get(last));
            digits.remove(last);
        }
        return sb.toString();
    }

    private int factorial(int n) {
        int ans = 1;
        for (int i = 1; i <= n; i++) {
            ans *= i;
        }
        return ans;
    }
}

99%

The Best Solution

class Solution {
    public String getPermutation(int n, int k) {
        int countPerHead = 1;
        ArrayList<Integer> myList = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            countPerHead *= i;
            myList.add(i);
        }
        myList.add(n);
        StringBuilder sb = new StringBuilder();
        int count = k;
        int digits = n-1;
        while ( n > sb.length()) {
            int index = (count - 1) / countPerHead;
            count = count - index * countPerHead;
            sb.append(myList.get(index));
            myList.remove(index);
            if (digits != 0) {
                countPerHead = countPerHead / digits--;
            }
        }
        return sb.toString();
    }
}

总体思路差不多，细节上做得比我好。都是通过 (k - 1) / (n - 1)! 找到index，但是他提前把(n - 1)!算出来了，然后每次除以n - 1。