128. Longest Consecutive Sequence
Posted Updated LeetCode / Medium / 复习2 minutes read (About 306 words)

128. Longest Consecutive Sequence

Question

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Solution 1

哈希表，先将所有元素加入哈希表。
然后遍历哈希表，如果表内没有当前数字-1时（没有更小的连续数字），则将temp初始化为1。
当表内有下一个连续数字时，将temp和curNum增加1。

当没有下一个连续数字时，更新结果到res上。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        
        for(int num : nums){
            set.add(num);
        }
        
        int res = 0;
        
        for(int num : set){
            if(!set.contains(num - 1)){
                int temp = 1;
                int curNum = num;
                while(set.contains(curNum + 1)){
                    temp++;
                    curNum++;
                }
                res = Math.max(res, temp);
            }
        }
        return res;
    }
}

Solution 2

先排序，再遍历。
维护一个最大长度res。
用一个temp参数记录连续长度。
如果当前值是上一个值+1，则temp+1。
如果当前值等于上一个值，则continue。
其他情况则更新最大长度res，并将temp恢复为1。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        Arrays.sort(nums);
        int res = 0, temp = 1;
        
        for(int i = 1; i < nums.length; i++){
            if(nums[i] == nums[i-1] + 1){
                temp++;
            }
            else if(nums[i] == nums[i-1]){
                continue;
            }
            else{
                res = Math.max(res, temp);
                temp = 1;
            }
        }
        res = Math.max(res, temp);
        
        return res;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 419 words)

2316. Count Unreachable Pairs of Nodes

Question

You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [a<sub>i</sub>, b<sub>i</sub>] denotes that there exists an undirected edge connecting nodes a<sub>i</sub> and b<sub>i</sub>.

Return the number of pairs of different nodes that are unreachable from each other.

Solution

并查集，将所有元素union，然后计算每个元素所在集之外的元素和相加即可。
注意由于是无向图，因此计算加和时每两个点之间都计算了两次，因此需要将结果除以2。

路径压缩

在进行find()查找时，将经过的每一个节点设置为根节点。
这样做可以有效的降低树高，减少操作次数。
采用递归的形式实现。

按秩合并

用size[]数组记录当前位置的节点数量。
在合并两个数字时，将秩较小的数字指向秩较大的数字。
并更新根节点的size[]值。

Code

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
class Solution {
    public long countPairs(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        long res = 0;
        for(int[] edge : edges){
            uf.union(edge[0], edge[1]);
        }
        
        for(int i = 0; i < n; i++){
            res +=  ( n - uf.getSize(i) );
        }
        return res/2;   //无向图，因此每两个节点计算了两次
    }
    
    class UnionFind {
        int[] parent;
        int[] size;

        public UnionFind(int n){
            parent = new int[n];
            size = new int[n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
                size[i] = 1;
            }
        } 
           
        private int find(int id){
            return parent[id] == id ? id : find(parent[id]);   //路径压缩，将路径上的所有节点归结到根节点上
        }
           
        private boolean union(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return false;
            if(size[p1] > size[p2]){    //按秩进行压缩
                parent[p2] = p1;
                size[p1] += size[p2];
            }
            else{
                parent[p1] = p2;
                size[p2] += size[p1];
            }
            return true;
        }

        public int getSize(int num){
            return size[find(num)];
        }
    }
}****
Posted Updated LeetCode / Medium / 复习6 minutes read (About 841 words)

399. Evaluate Division

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

这道题的核心是边上带权的并查集。
如何在find以及union时计算并更新权重是最重要的。
组合过后，根节点的权重依然为1，以其为标准更新其他节点的权重。

先通过一个哈希表建立字符串与id的映射关系，为每个字符串生成一个单独的id。

然后将一个equation里的两个字符串进行union操作。
并查集初始化时，所有权重为1。

在find时，执行路径压缩时需要用当前的权重weight[id]更新为其自身乘以其上一级的权重weight[origin]。
这里需要注意计算的顺序需要从根上的权重，以递归的形式计算到当前权重。
因此我们需要先单独保存parents[id]的位置。然后find(parents[id])，先计算出其上级的weight。
最后再将weight[id]更新为更新后的上一级的权重乘以自身权重。

1
2
3
int origin = parents[id];
parents[id] = find(parents[id]);
weight[id] *= weight[origin];

在union时，将两个集合中的一个的根指向另一个。
例如当结合a与b两个节点时，我们已经计算过了(a -> b)的权重关系，以及(d -> c)的权重关系。
我们将(b -> d)。这时我们可以通过values[i]得到(a -> d)的权重关系。因此我们可以据此得出以下公式：

weight[(b->c)] = weight[(d->c)] × values[(a->d)]/weight[(a->b)]

1
2
parents[p1] = parents[p2];
weight[p1] = weight[id2]*val/weight[id1];

最后，当所有节点都被合并后，我们可以遍历queries。
从哈希表获得对应字符串的id。
当有字符串未在哈希表中时，返回-1.0。
否则计算两个id对应的权重，并添加到答案中。

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
class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        double[] ret = new double[queries.size()];
        HashMap<String, Integer> map = new HashMap<>();
        UnionFind uf = new UnionFind(equations.size() * 2);
        int id = 0;
        for(int i = 0; i < equations.size(); i++){
            String var1 = equations.get(i).get(0);
            String var2 = equations.get(i).get(1);
            if( !map.containsKey( var1 ) ){
                map.put( var1, id );
                id++;
            }
            if( !map.containsKey( var2 ) ){
                map.put( var2, id );
                id++;
            }
            uf.union(map.get(var1), map.get(var2), values[i]);
        }
        for(int i = 0 ; i < queries.size(); i++){
            String var1 = queries.get(i).get(0);
            String var2 = queries.get(i).get(1);
            Integer id1 = map.get(var1);
            Integer id2 = map.get(var2);
            if(id1 == null || id2 == null) ret[i] = -1.0;
            else ret[i] = uf.isConnected(id1, id2);
        }
        return ret;
    }
    
    class UnionFind{
        int[] parents;
        double[] weight;
        public UnionFind(int n){
            parents = new int[n];
            weight = new double[n];
            for(int i = 0; i < parents.length; i++){
                parents[i] = i;
                weight[i] = 1.0;
            }
        }
        public int find(int id){
            if (id != parents[id]) {
                int origin = parents[id];
                parents[id] = find(parents[id]);
                weight[id] *= weight[origin];
            }
            return parents[id];
        }
        public boolean union(int id1, int id2, double val){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return false;
            parents[p1] = parents[p2];
            weight[p1] = weight[id2]*val/weight[id1];
            return true;
        }
        public double isConnected(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return weight[id1] / weight[id2];
            else return -1.0;
        }
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 353 words)

1202. Smallest String With Swaps

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

并查集，注意要使用路径压缩否则会超时。
先将所有配对联通。然后创建一个数组group记录每个字符串位置的分组情况。
根据分组，借助优先队列保存字符串。
通过哈希表创建group和PriorityQueue的映射。
按当前位置的分组情况和优先队列的顺序来添加字符串。
最后返回字符串。

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
class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        StringBuffer sb = new StringBuffer();
        UnionFind uf = new UnionFind(s.length());
        
        for(List<Integer> pair : pairs){
            uf.union(pair.get(0), pair.get(1));    
        }
        
        int[] group = new int[s.length()];
        for(int i = 0; i < s.length(); i++){
            group[i] = uf.find(i);
        }
        
        HashMap<Integer, PriorityQueue<Character>> map = new HashMap<>();
        
        for(int i = 0; i < s.length(); i++){
            PriorityQueue<Character> bin = map.getOrDefault(group[i], new PriorityQueue<Character>());
            bin.add(s.charAt(i));
            map.put(group[i], bin);
        }
        for(int i = 0; i < s.length(); i++){
            sb.append(map.get(group[i]).poll());
        }
        return sb.toString();
    }
    
    class UnionFind {
        int[] parent;
        int[] count;
        public UnionFind(int n){
            parent = new int[n];
            count = new int[n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
                count[i] = 1;
            }
        } 
        
        private int find(int id){
            if(parent[id] == id) return id;
            parent[id] = find(parent[id]);
            return parent[id];
        }
        
        private boolean union(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return false;
            if(count[p1] > count[p2]) parent[p2] = p1;
            else parent[p1] = p2;
            return true;
        }
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 380 words)

1584. Min Cost to Connect All Points

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

并查集，最小生成树(Minimum spanning tree)，Kruskal算法。
Edge辅助类，保存并计算两点的id和其曼哈顿距离。
将edges根据其距离排序。

遍历所有的edge，如果edge的两点没有合并，则合并两点，并取这条边作为结果。
加和所有的结果，答案就是最小值。

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
class Solution {
    public int minCostConnectPoints(int[][] points) {
        List<Edge> edges = new ArrayList<Edge>();
        int min = 0;
        for(int i = 0; i < points.length; i++){
            for(int j = i+1; j < points.length; j++){
                 edges.add(new Edge(points, i, j));
            }
        }
        
        Collections.sort(edges, (a, b) -> a.length - b.length);
        UnionFind uf = new UnionFind(points.length);
        
        for(Edge e : edges){
            if(uf.union(e.id1, e.id2)){
                min += e.length;
            }
        }
        return min;
    }

    class UnionFind{
        private int[] parents;
        private int[] size;
    
        public UnionFind(int n){
            size = new int[n];
            parents = new int[n];
            for(int i = 0; i < n; i++){
                parents[i] = i;
                size[i] = 1;
            }
        }
    
        public int find(int id){
            if(parents[id] == id) return id;
            return find(parents[id]);
        }
    
        public boolean union(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            
            if(p1 == p2) return false;
        
            if(size[p1] < size[p2]){
                parents[p1] = p2;
                size[p2] += size[p1];
            }
            else{
                parents[p2] = p1;
                size[p1] += size[p2];
            }
            return true;
        }
    }

    class Edge{
        int id1;
        int id2;
        int length;
        public Edge(int[][] points, int _id1, int _id2){
            id1 = _id1;
            id2 = _id2;
            length = Math.abs(points[id1][0] - points[id2][0]) + Math.abs(points[id1][1] - points[id2][1]);
        }
    }
}
Follow

Recents

Archives

Links

×