首页 🍒LeetCode,🐶算法

1TUQ1nFmIt.png

思路

感觉这个题和并查集有点像,定义一个数组v,v[i]表示i所在位置的连续1的长度,比如"11101"这种情况时v为:[3, 3, 3, 0, 1]
当字符串s[i]变成1的时候可以看一下v[i]的左右是否为0

  • 为0的话直接让v[i] = 1即可
  • 不为0就要看左右是不是都不为0

    • 如果只是一边不为0,那么v[i] = v[i - 1] + 1, v[i - v[i - 1]]++,表示插入左边的集合,比如[2, 2, 0, 0, 0, 1]的时候如果当前读的数字为3那就需要让3的位置置为1,左边不为0就变成了[3, 3, 3, 0, 0, 1]。右边同理
    • 如果两边都不为0的话那么就要让两端的集合都改变,改变的数值为v[n - 1] + v[n + 1] + 1
      当更新集合的时候判断一下当前集合的数值,如果 == m,res = i 即可。

我这里在更新集合的时候只把集合的首尾数据更新了,因为新插入的数值一定不会在集合里面,所以只需要维护集合边界即可

class Solution {
   public:
    int findLatestStep(vector<int>& arr, int m) {
        if (m == arr.size()) {
            return m;
        }
        int size = arr.size() + 2; // 因为arr的数从1开始所以需要+1,后面还要判断集合的尾部防止越界所以又+1
        vector<int> v(size, 0);
        int res = -1;
        for (int i = 0; i < arr.size(); i++) {
            int n = arr[i];
            if (v[n - 1] != 0 && v[n + 1] != 0) {
                int q = v[n - 1] + v[n + 1] + 1;
                if (v[n - v[n - 1]] == m || v[n + v[n + 1]] == m) {
                    res = i;
                }
                v[n - v[n - 1]] = q;
                v[n + v[n + 1]] = q;
            } else if (v[n - 1] != 0) {
                if (v[n - 1] == m) {
                    res = i;
                }
                v[n] = v[n - 1] + 1;
                v[n - v[n - 1]]++;
            } else if (v[n + 1] != 0) {
                if (v[n + 1] == m) {
                    res = i;
                }
                v[n] = v[n + 1] + 1;
                v[n + v[n + 1]]++;
            } else {
                v[n] = 1;
            }
        }
        return res;
    }
};



文章评论