数组 - Array

57. 插入区间

非常有意思的情况划分题：

参考：
笨猪爆破组

核心在于：

  1. 推入前段不重叠部分
  2. 更新重叠部分再推入
  3. 推入后段不重叠部分
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
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> retList = new ArrayList<>();
        int idx = 0;
        int n = intervals.length;
        int newLeft = newInterval[0], newRight = newInterval[1];
        // 加入左边不重叠的
        for (; idx < n; idx++) {
            int left = intervals[idx][0], right = intervals[idx][1];
            if (right < newLeft) {
                retList.add(new int[]{left, right});
            } else {
                break;
            }
        }
        // 更新重叠范围
        for (; idx < n; idx++) {
            int left = intervals[idx][0], right = intervals[idx][1];
            if (left > newRight) break;
            newLeft = Math.min(left, newLeft);
            newRight = Math.max(right, newRight);
        }
        retList.add(new int[]{newLeft, newRight});
        // 加入右边不重叠部分
        for (; idx < n; idx++) {
            int left = intervals[idx][0], right = intervals[idx][1];
            retList.add(new int[] {left, right});
        }
        int[][] ret = new int[retList.size()][2];
        for (int i = 0; i < ret.length; i++) {
            ret[i] = retList.get(i);
        }
        return ret;
    }
}

1366. 通过投票对团队排名

直接排序即可，主要检查对于Comparator的应用：

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
class Solution {
    public String rankTeams(String[] votes) {
        int n = votes.length, m = votes[0].length();
        Map<Character, int[]> hm = new HashMap<>();
        for (String vote : votes) {
            char[] cArr = vote.toCharArray();
            for (int i = 0; i < m; i++) {
                int[] cur = hm.getOrDefault(cArr[i], new int[cArr.length]);
                cur[i]++;
                hm.put(cArr[i], cur);
            }
        }
        StringBuilder sb = new StringBuilder();
        List<Map.Entry<Character, int[]>> ls = new ArrayList<>(hm.entrySet());
        Collections.sort(ls, new Comparator<Map.Entry<Character, int[]>>(){
            @Override
            public int compare(Map.Entry<Character, int[]> e1, Map.Entry<Character, int[]> e2) {
                Character e1Key = e1.getKey();
                Character e2Key = e2.getKey();
                int[] e1Value = e1.getValue();
                int[] e2Value = e2.getValue();
                int n = e1Value.length;
                for (int i = 0; i < n; i++) {
                    int first = e1Value[i], second = e2Value[i];
                    if (first == second) {
                        continue;
                    } else {
                        return second - first;
                    }
                }
                return e1Key - e2Key;
            }
        });
        for (Map.Entry<Character, int[]> ele : ls) {
            sb.append(ele.getKey());
        }
        return sb.toString();
    }
}