2024-11-20:交替子数组计数。用go语言,给定一个二进制数组 nums,
如果一个子数组中的相邻元素的值都不相同,我们称这个子数组为交替子数组。
请返回数组 nums 中交替子数组的总数。
输入:nums = [0,1,1,1]。
输出:5。
解释:
以下子数组是交替子数组:[0] 、[1] 、[1] 、[1] 以及 [0,1] 。
答案2024-11-20:
chatgpt
题目来自leetcode3101。
1.输入数据:首先,我们有一个二进制数组 nums
,例如 nums = [0, 1, 1, 1]
。我们的目标是计算这个数组中所有交替子数组的数量。
2.交替子数组的定义:交替子数组是指一个子数组中,相邻的元素值必须不同。例如:
2.1.数组 [0]
和 [1]
都是交替子数组,因为它们的元素没有相邻重复的情况。
2.2.数组 [1, 1]
不是交替子数组,因为两个相邻的元素都是 1。
3.初始化变量:
3.1.res
:用于存放交替子数组的总数,初始值为 0。
3.2.cur
:用于记录当前交替子数组的长度,初始值为 0。
3.3.pre
:一个辅助变量,用于保存前一个元素的值,初始设置为 -1(方便与第一个元素进行比较)。
4.遍历数组:
4.1.对于给定的数组 nums
中的每一个元素 a
,执行以下操作:
4.1.1.非重复情况:如果当前元素 a
与前一个元素 pre
不相等,表示交替状态继续,故将当前计数 cur
加 1。
4.1.2.重复情况:如果当前元素 a
与前一个元素 pre
相等,则交替状态被破坏,将当前计数 cur
重置为 1,表示当前元素 a
作为新的交替子数组的起始元素。
4.1.3.更新 pre
为当前的元素 a
,以便于下一次迭代进行比较。
4.1.4.将当前的 cur
值累加到总数 res
中。这将确保包含所有以当前元素为结束元素的交替子数组。
5.结束遍历:当遍历完整个数组后,res
将包含所有可能的交替子数组的总数。
6.返回结果:最后,函数返回 res
,这就是我们需要的交替子数组的数量。
以输入 nums = [0, 1, 1, 1]
作为示例:
0
,cur
增加到 1,res
变为 1(子数组 [0]
)。1
,cur
增加到 2,res
变为 3(包括子数组 [1]
和 [0, 1]
)。1
:1
,由于与前面的 pre
(也是 1
)相等,cur
重置为 1,res
增加到 4(子数组 [1]
)。1
,同样,cur
重置为 1,res
增加到 5(再加上 [1]
)。[0]
、[1]
、[1]
、[1]
、[0, 1]
。nums
的长度。由于只需对数组遍历一次进行计算,所需的操作量与数组长度成正比。res
、cur
、pre
)都是常数空间,不依赖于输入数组的大小,未使用额外的数据结构进行存储。package main
import(
"fmt"
)
func countAlternatingSubarrays(nums []int)int64{
var res, cur int64
pre :=-1
for _, a :=range nums {
if pre != a {
cur++
}else{
cur =1
}
pre = a
res += cur
}
return res
}
func main(){
nums :=[]int{0,1,1,1}
fmt.Println(countAlternatingSubarrays(nums))
}
fn count_alternating_subarrays(nums:Vec<i32>)->i64{
letmut res=0;
letmut cur=0;
letmut pre=-1;// 用于记录前一个值
for&a in&nums {
if pre != a {
cur +=1;// 如果不相同,当前交替子数组长度加1
}else{
cur =1;// 如果相同,重置为1
}
pre = a;
res += cur;// 累加交替子数组的数量
}
res // 返回结果
}
fnmain(){
letnums=vec![0,1,1,1];
println!("{}",count_alternating_subarrays(nums));
}
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有