FanluLeetcode/src/array/SummaryRanges.java at master · Fanlu91/FanluLeetcode · GitHub

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
package array;
// Source : https://leetcode.com/problems/summary-ranges/
// Id     : 228
// Author : Fanlu Hai | https://github.com/Fanlu91/FanluLeetcode
// Date   : 2021/2/11
// Topic  : array
// Level  : Easy
// Other  :
// Tips   :
// Links  :
// Result : 8.88% 26.69%

import java.util.LinkedList;
import java.util.List;

public class SummaryRanges {
    // 8.88% 10 ms 26.69%
    public List<String> summaryRanges(int[] nums) {
        List<String> ans = new LinkedList<>();
        if (nums.length == 0)
            return ans;
        String tmp = "" + nums[0];
        int tmpSize = 1;
        if (nums.length == 1) {
            ans.add(tmp);
            return ans;
        }

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1] + 1) {
                tmpSize++;
            } else {
                if (tmpSize == 1)
                    ans.add(tmp);
                else
                    ans.add(tmp + "->" + nums[i - 1]);
                tmpSize = 1;
                tmp = "" + nums[i];
            }
        }

        if (tmpSize == 1)
            ans.add(tmp);
        else
            ans.add(tmp + "->" + nums[nums.length - 1]);

        return ans;
    }


    /**
     * union find
     */
//    public List<String> summaryRanges(int[] nums) {
//        List<String> ans = new LinkedList<>();
//
//    }
//
//    class UoinFind {
//        int[] parent;
//        int[] size;
//        int count;
//
//        public UoinFind(int n) {
//            this.parent = new int[n];
//            this.size = new int[n];
//            this.count = n;
//            for (int i = 0; i < n; i++) {
//                parent[i] = i;
//                size[i] = 1;
//            }
//        }
//
//        public void union(int p, int q) {
//            int rootP = find(p);
//            int rootQ = find(q);
//            if (rootP == rootQ)
//                return;
//            if (size[rootP] > size[rootQ]) {
//                parent[rootQ] = rootP;
//                size[rootP] += size[rootQ];
//            } else {
//                parent[rootP] = rootQ;
//                size[rootQ] += size[p];
//            }
//            count--;
//        }
//
//        public int find(int n) {
//            while (parent[n] != n) {
//                // 进行路径压缩
//                parent[n] = parent[parent[n]];
//                n = parent[n];
//            }
//            return n;
//        }
//
//        public boolean connected(int p, int q) {
//            int rootP = find(p);
//            int rootQ = find(q);
//            return rootP == rootQ;
//        }
//
//    }
}