leetcode周赛1562. 查找大小为 M 的最新分组

leetcode周赛1562. 查找大小为 M 的最新分组

十月 29, 2020

leetcode周赛1562. 查找大小为 M 的最新分组

给你一个数组 arr ，该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串，该字符串上的所有位最初都设置为 0 。
在从 1 到 n 的每个步骤 i 中（假设二进制字符串和 arr 都是从 1 开始索引的情况下），二进制字符串上位于位置 arr[i] 的位将会设为 1 。
给你一个整数 m ，请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。一组 1 是一个连续的、由 1 组成的子串，且左右两边不再有可以延伸的 1 。
返回存在长度 恰好 为 m 的 一组 1 的最后步骤。如果不存在这样的步骤，请返回 -1 。

示例 1：
输入：arr = [3,5,1,2,4], m = 1
输出：4
解释：
步骤 1：”00100”，由 1 构成的组：[“1”]
步骤 2：”00101”，由 1 构成的组：[“1”, “1”]
步骤 3：”10101”，由 1 构成的组：[“1”, “1”, “1”]
步骤 4：”11101”，由 1 构成的组：[“111”, “1”]
步骤 5：”11111”，由 1 构成的组：[“11111”]
存在长度为 1 的一组 1 的最后步骤是步骤 4 。

示例 2：
输入：arr = [3,1,5,4,2], m = 2
输出：-1
解释：
步骤 1：”00100”，由 1 构成的组：[“1”]
步骤 2：”10100”，由 1 构成的组：[“1”, “1”]
步骤 3：”10101”，由 1 构成的组：[“1”, “1”, “1”]
步骤 4：”10111”，由 1 构成的组：[“1”, “111”]
步骤 5：”11111”，由 1 构成的组：[“11111”]
不管是哪一步骤都无法形成长度为 2 的一组 1 。

思路

借助题解区的思路，用一个数组存储当前节点连续1的个数，这个当前节点指的是连续1序列的头部和尾部，再用一个map存储整个序列当中长度为n的有几个。每次循环查找长度为m的有几个，如果这次大于1个，那么res就是下一次。

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 {
    /*
    map数组的执行过程
    [0, 0, 0, 1, 0, 0]
    [0, 0, 0, 1, 0, 1]
    [0, 1, 0, 1, 0, 1]
    [0, 3, 1, 3, 0, 1]
    [0, 5, 1, 3, 1, 5]
    */
    public int findLatestStep(int[] arr, int m) {
        int[] map = new int[arr.length + 1];
        int res = -1;
        //index->1 length
        HashMap<Integer,Integer> map2 = new HashMap<>();//length->num
        map2.put(0,0);
        for (int i = 0; i < arr.length; i++) {
            int situation = arr[i];
            int left = 0, right = 0;
            //维护连续的1序列的边界
            if (situation - 1 >= 1) {
                left = map[situation - 1];
            }
            if (situation + 1 < map.length) {
                right = map[situation + 1];
            }
            int newLength = 1 + left + right;
            int lp = 1,rp = map.length - 1;
            if (situation - left >= 1) {
                lp = situation - left;
            }
            if (situation + right <= map.length - 1) {
                rp = situation + right;
            }
            //System.out.println(left+" "+right+" "+lp+" "+rp);
            map[situation] = 1;
            map[lp] = newLength;
            map[rp] = newLength;
            map2.put(left,map2.get(left) - 1);
            map2.put(right,map2.get(right) - 1);
            int k = map2.getOrDefault(newLength,0);
            map2.put(newLength,k + 1);
            if (map2.getOrDefault(m,0) >= 1) {
                res = i + 1;
            }
            System.out.println(Arrays.toString(map));
            //System.out.println(map2);
        }
        return res;

    }
}

leetcode 120