侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【字符串】最长回文串

GabrielxD
2022-04-22 / 0 评论 / 0 点赞 / 117 阅读 / 446 字
温馨提示:
本文最后更新于 2022-10-11,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

409. 最长回文串


给定一个包含大写字母和小写字母的字符串 s ,返回 通过这些字母构造成的 最长的回文串

在构造过程中,请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

示例 1:

输入: s = "abccccdd"
输出: 7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

示例 2:

输入: s = "a"
输入: 1

示例 3:

输入: s = "bb"
输入: 2

提示:

  • 1 <= s.length <= 2000
  • s 只能由小写和/或大写英文字母组成

解题

方法一:记录频次

思路

记录每个字符出现的次数,偶数次的字符全用,奇数次的字符则少用一个,如果有多余的奇数次字符,则中间可以用一个。

代码

class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> frequencies = new HashMap<>();
        for(char ch : s.toCharArray()) {
            frequencies.put(ch, frequencies.getOrDefault(ch, 0) + 1);
        }

        int ans = 0;
        boolean hasOdd = false;
        for (int frequence : frequencies.values()) {
            if ((frequence & 1) == 0) {
                ans += frequence;
            } else {
                ans += frequence - 1;
                if (!hasOdd) {
                    hasOdd = true;
                }
            }
        }

        return hasOdd ? ans + 1 : ans;
    }
}

优化

使用数组记录

class Solution {
    public int longestPalindrome(String s) {
        int[] frequencies = new int[58];
        for(char ch : s.toCharArray()) {
            frequencies[ch - 'A']++;
        }

        int ans = 0;
        for (int frequence : frequencies) {
            ans += frequence - (frequence & 1);
        }

        return ans < s.length() ? ans + 1 : ans;
    }
}

优化

n >> 1 << 1,一个数做右移一位再左移一位,如果它是偶数则保持不变,如果是奇数则二进制最低位没了。

class Solution {
    public int longestPalindrome(String s) {
        int[] frequencies = new int[58];
        for(char ch : s.toCharArray()) {
            frequencies[ch - 'A']++;
        }

        int ans = 0;
        for (int frequence : frequencies) {
            ans += frequence >> 1 << 1;
        }

        return ans < s.length() ? ans + 1 : ans;
    }
}
0

评论区