饿了么 笔试 第二问 位运算
首先构建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个岗位
点赞 评论 收藏
转发