1375. 二进制字符串前缀一致的次数 (opens new window)

1.哈希

分析：使用哈希保存每个连续区间，因为存在头尾的情况，因此同一个区间需要保存两次(头为key和尾为key)。

• 搜索时，如果当前元素相邻的左右位置存在可合并区间，那么进行区间扩张，更新该区间的左右边界。更新时需要考虑左右区间同时合并的情况。

• 如果当前哈希表当中仅存在左边界为1的区间，那么当前符合前缀一致。

注意：本题有一个关键的前提，每个位置的元素只会被翻转一次，flips不存在重复元素。

class Solution {
    public int numTimesAllBlue(int[] flips) {
        int res=0;
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<flips.length;i++){
            if(map.containsKey(flips[i]+1)||map.containsKey(flips[i]-1)){
                //存在可合并的情况
                if(map.containsKey(flips[i]+1)){
                    //判断是否是两端可以合并的情况
                    if(map.containsKey(flips[i]-1)){
                        int left=map.get(flips[i]-1);
                        int right=map.get(flips[i]+1);
                        map.remove(flips[i]-1);
                        map.remove(flips[i]+1);
                        map.put(left,right);
                        map.put(right,left);
                    }
                    else{
                        int right=map.get(flips[i]+1);
                        map.remove(flips[i]+1);
                        map.put(right,flips[i]);
                        map.put(flips[i],right);  
                    }                
                }
               else{
                    int left=map.get(flips[i]-1);
                    map.remove(flips[i]-1);
                    map.put(left,flips[i]);
                    map.put(flips[i],left);
                }
            }
            else{
                map.put(flips[i],flips[i]);
            }
            if(map.containsKey(1)){
                if((map.get(1)==1&&map.size()==1)||(map.get(1)!=1&&map.size()==2)) res++;
            } 
        }
        return res;
    }
}

2.利用填充占位性质优化

利用数组性质：

• 数组不存在重复元素
• 数组每个元素大小不超过数组的长度

满足前缀一致等价于前i个数每一个索引位置都被填充了，换而言之因为没有重复，也等价于索引的最大值(当前索引)等于前i个元素的最大值。

class Solution {
    public int numTimesAllBlue(int[] flips) {
        int max=Integer.MIN_VALUE,res=0;
        for(int i=0;i<flips.length;i++){
            max=Math.max(max,flips[i]);
            if(max==i+1) res++;
        }
        return res;
    }
}