饿了么 笔试 第二问 位运算

首先构建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 &(num -1)==0)
全部评论
点赞 回复
分享
发布于 03-16 16:43 北京
真强啊大佬,咋刷题的教教呗
点赞 回复
分享
发布于 03-16 17:02 安徽
滴滴
校招火热招聘中
官网直投

相关推荐

点赞 评论 收藏
转发
2 8 评论
分享
牛客网
牛客企业服务