饿了么 笔试 第二问 位运算

首先构建int dp[n],dp[i]表示从字符串索引0-i的字符数统计变量。
递推公式:dp[i] = dp[i-1]^(1<<(s.charAt(i)-'a')),异或可以很好的体现字符个数的奇偶数变化。

那么i-j是否能构成回文怎么判断?很简单:
int num = dp[j]^dp[i-1];

如果num中1的位数不超过一个,就说明可以构成回文,否则不可以(最多存在一种奇数个的字符)。
那么怎么判断呢?也很简单:
if(num &amp;(num -1)==0)
全部评论
真强啊大佬,咋刷题的教教呗
点赞 回复 分享
发布于 2024-03-16 17:02 安徽
点赞 回复 分享
发布于 2024-03-16 16:43 北京

相关推荐

怎么起名字:早知道就不读书了,害得我送外卖还得扶眼镜
点赞 评论 收藏
分享
评论
2
8
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务