2024-03-16 16:43 已编辑
不愿透露姓名的神秘牛友
饿了么 笔试 第二问 位运算
首先构建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个岗位 点赞 评论 收藏
分享
