遇到奇偶性?使用位操作

作者: | 更新日期:

有人说上次比赛第三题我的代码超时,我赶紧看了一下。

本文首发于公众号:天空的代码世界,微信号:tiankonguse
原文地址:https://mp.weixin.qq.com/s/vc-QsIJ7rcst_Ch1EG5R2A

一、背景

上次写了《Leetcode 第152场比赛回顾》,其中第三题没有提供源代码。
很巧,一个勤奋的小伙伴提出一个问题:第三题按照我的方法过不了。

我想怎么可能呢? 试了下确实超时了,再一看题,统计区间奇偶性,不是一个位操作就解决的事情嘛。

于是我花了几分钟改成位操作,一下就过了。
接下来就看看这个骚操作吧。

二、题意

原始题意大家可以去上篇文章《构建回文串检测》看看。

这里我说一下使用数学语言抽象之后的题意。

抽象题意:给我们一个长度为L的字符串,然后N个区间询问,问区间内出现奇数次的字母有多少个。

我的原始做法是预处理整个字符串,统计每个前缀字符串里面所有字母出现的次数。
询问是两个前缀的所有字母个数相减,就可以得到答案了。

预处理的复杂度是O(26 L),所有区间查询的复杂度是26 N
综合复杂度就是O(26L + 26N)

就是这样一个常数复杂度的代码,超时了。

三、位压缩

一看超时了,我就想到位压缩了。

26个字母,使用26位就可以表示了。
而对于个数,其实没必要,我们只关心奇偶性。

首先依旧是预处理。

原先代码是map统计的,每次要赋值26个元素的amp

通过异或来奇偶反转,现在一个整数就解决了。

而对于查询操作,原先是26个字母的统计次数分别相减。

现在则也只需要通过位操作就行了。

这个位操作也是最难理解的地方。
我们分别看每一位就容易理解了。
某一位在左边界是一个奇偶装填,右边界是另外一个奇偶状态。
如果区间内有偶数个字母,那就状态就不变,如果有奇数个,就状态就会发生改变。
所以进行异或就能快速判断区间内是奇数个还是偶数个了。

四、最后

这道题挺好的,其实也可以当做面试题来考。
不知道你们是否看懂了。

-EOF-

本文公众号:天空的代码世界
个人微信号:tiankonguse
QQ算法群:165531769(不止算法)
知识星球:不止算法

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面打开下面的地址进行留言。如果下面没有地址,可以关注公众号留言。
原文地址:https://mp.weixin.qq.com/s/vc-QsIJ7rcst_Ch1EG5R2A

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越