JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2024-09-28
目录

二进制字符串前缀一致的次数Java

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

给你一个长度为 n 、下标从 1 开始的二进制字符串,所有位最开始都是 0 。我们会按步翻转该二进制字符串的所有位(即,将 0 变为 1)。

给你一个下标从 1 开始的整数数组 flips ,其中 flips[i] 表示对应下标 i 的位将会在第 i 步翻转。

二进制字符串 前缀一致 需满足:在第 i 步之后,在 闭 区间 [1, i] 内的所有位都是 1 ,而其他位都是 0 。

返回二进制字符串在翻转过程中 前缀一致 的次数。

示例 1:

输入:flips = [3,2,4,1,5]
输出:2
解释:二进制字符串最开始是 "00000" 。
执行第 1 步:字符串变为 "00100" ,不属于前缀一致的情况。
执行第 2 步:字符串变为 "01100" ,不属于前缀一致的情况。
执行第 3 步:字符串变为 "01110" ,不属于前缀一致的情况。
执行第 4 步:字符串变为 "11110" ,属于前缀一致的情况。
执行第 5 步:字符串变为 "11111" ,属于前缀一致的情况。
在翻转过程中,前缀一致的次数为 2 ,所以返回 2 。

示例 2:

输入:flips = [4,1,2,3]
输出:1
解释:二进制字符串最开始是 "0000" 。
执行第 1 步:字符串变为 "0001" ,不属于前缀一致的情况。
执行第 2 步:字符串变为 "1001" ,不属于前缀一致的情况。
执行第 3 步:字符串变为 "1101" ,不属于前缀一致的情况。
执行第 4 步:字符串变为 "1111" ,属于前缀一致的情况。
在翻转过程中,前缀一致的次数为 1 ,所以返回 1 。

提示:

  • n == flips.length
  • 1 <= n <= 5 * 104
  • flips 是范围 [1, n] 中所有整数构成的一个排列

# 思路

这题关键是读懂题目含义,
让所有开着的灯都变成蓝色的时刻的性质是:此时点亮最远的灯的位置恰巧等于点亮灯的个数。
若点亮最远的灯的位置大于此时点亮灯的个数,则意味着在点亮最远的灯的位置之前存在着未点亮的灯。

# 解法


class Solution {
    //这题关键是读懂题目含义,
    // 让所有开着的灯都变成蓝色的时刻的性质是:此时点亮最远的灯的位置恰巧等于点亮灯的个数。
    // 若点亮最远的灯的位置大于此时点亮灯的个数,则意味着在点亮最远的灯的位置之前存在着未点亮的灯。
    public int numTimesAllBlue(int[] light) {
        int size = light.length;
        int count = 0, maxReachingPoint = 0;
        for (int i = 0 ; i < size; i++){
            maxReachingPoint = Math.max(maxReachingPoint, light[i]);
            if ( i + 1 == maxReachingPoint){
                count += 1;
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
#Java
最近更新
01
1686. 石子游戏VI Java
09-07
02
1687. 从仓库到码头运输箱子 Java
09-07
03
1688. 比赛中的配对次数 Java
09-07
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式