饿了么 笔试 第二问 位运算
首先构建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)
递推公式: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)
全部评论
分享
真强啊大佬,咋刷题的教教呗
分享
滴滴
官网直投
相关推荐
点赞 评论 收藏
转发
点赞 评论 收藏
转发
投递饿了么等公司10个岗位 > 🔥笔试编程真题宝典💯
点赞 评论 收藏
转发