全部评论
![](https://uploadfiles.nowcoder.com/files/20240813/120063338_1723523212282/pc_list.png)
我有个思路,时间复杂度是O(n),空间复杂度O(1)。遍历题目给的数组,如果当前数字和左边的数字奇偶不一,则取前面的值;反之,取前面的值➕1。例子1:3 6 7 0 得到数组1 1 1 1。例子2: 3 5 6 8 得到数组1 2 2 3 查询时判断fromi和toi是不是相同就知道是不是同一个奇偶区间了。空间复杂度为O1是因为可以在原数组上做修改,拿一个变量记录下原值。整体思想就是一个数组一定是由不同的奇偶区间组成的,我们只要知道开头和结尾是不是都在一个奇偶区间就行了。
感谢分享
![](https://uploadfiles.nowcoder.com/files/20230418/196308229_1681804456894/企业logo白底80px.jpg)
鹏芯微
校招火热招聘中
官网直投
这个是力扣每日一题上的吧 前段时间刚遇到
前缀和数组,定义:prefix[0] = 1,pre[i] += nums[i] ^ nums[i-1] & 1,i > 1 表示,只要第i个数和前一个数奇偶性不同,则第I个数为1 后面的就是求区间和了,O1秒了 只要区间和等于区间长度,则ok 否则不ok
感谢分享
学到了感谢![](https://uploadfiles.nowcoder.com/images/20220815/318889480_1660553763465/6F6CA9EC40A6F04C7838E4DE94A77241)
编码然后用前缀和?不知道是不是,第一反应![](https://uploadfiles.nowcoder.com/images/20220815/318889480_1660553763490/62AF11E48344D159DA608796DA7D39E5)
前缀和 求区间和是否为0 正数1 负数-1
遍历数组,找到每一段特殊数组,标记为0123456… 如果j-i=arr[j]-arr[i]说明i…j是特殊数组
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享