【五一创作】( 字符串) 409. 最长回文串 ——【Leetcode每日一题】

这篇具有很好参考价值的文章主要介绍了【五一创作】( 字符串) 409. 最长回文串 ——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

❓ 409. 最长回文串

难度:简单

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

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

示例 1:

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

示例 2:

输入:s = “a”
输出:1

示例 3:

输入:s = “aaaaaccc”
输出:7

提示:

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

💡思路:

法一:定长数组

由于字符串s只包含大写字母和小写字母,而大写字母A ~ Z的对应十进制ASCII码为65 ~ 90;小x写字母a ~ z的对应十进制ASCII码为97 ~ 122,所以可以使用长度为 123 的整型数组来统计每个字符出现的个数:

  • 如果是偶数个字符,则一定可以构造成回文字符串;
  • 如果是奇数个字符,则所有奇数个字符都需要减去1,最后加上一个1

法二:哈希表

可以使用哈希表,统计每个字符出现的次数:

  • 如果是偶数个字符,则一定可以构造成回文字符串;
  • 如果是奇数个字符,则所有奇数个字符都需要减去1,最后加上一个1

🍁代码:(Java、C++)

法一:定长数组
Java

class Solution {
    public int longestPalindrome(String s) {
        int[] cnts = new int[123];
        for(char c : s.toCharArray()){
            cnts[c]++;
        }
        int longest = 0;
        int hasOdd = 0;
        for(int cnt : cnts){
            longest += cnt % 2 == 0 ? cnt : cnt - 1;
            if(cnt % 2 != 0) hasOdd = 1;
        }
        return longest + hasOdd;
    }
}

C++

class Solution {
public:
    int longestPalindrome(string s) {
        vector<int> cnts(123);
        for(char c : s){
            cnts[c]++;
        }
        int longest = 0;
        int hasOdd = 0;
        for(int cnt : cnts){
            longest += cnt % 2 == 0 ? cnt : cnt - 1;
            if(cnt % 2 != 0) hasOdd = 1;
        }
        return longest + hasOdd;
    }
};

法二:哈希表
Java

class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> numOfChar = new HashMap<>();
        for(char c : s.toCharArray()){
            numOfChar.put(c, numOfChar.getOrDefault(c, 0) + 1);
        }
        int longest = 0;
        int hasOdd = 0;
        for(char c : numOfChar.keySet()){
            longest += numOfChar.get(c) % 2 == 0 ? numOfChar.get(c) : numOfChar.get(c) - 1;
            if(numOfChar.get(c) % 2 != 0) hasOdd = 1;
        }
        return longest + hasOdd;
    }
}

C++

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> numOfChar;
        for(char c : s){
            numOfChar[c]++;
        }
        int longest = 0;
        int hasOdd = 0;
        for(auto num : numOfChar){
            longest += num.second % 2 == 0 ? num.second : num.second - 1;
            if(num.second % 2 != 0) hasOdd = 1;
        }
        return longest + hasOdd;
    }
};
🚀 运行结果:

【五一创作】( 字符串) 409. 最长回文串 ——【Leetcode每日一题】

🕔 复杂度分析:
  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为字符串s的长度。
  • 空间复杂度 O ( S ) O(S) O(S),其中 S 为字符集大小。法一:我们使用了一个长度为 123 的数组,存储每个字符出现的次数。法二:哈希映射(HashMap)来存储每个字符出现的次数,最多只会存储 52 个键值对。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-429467.html

注: 如有不足,欢迎指正!

到了这里,关于【五一创作】( 字符串) 409. 最长回文串 ——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【字符串 简单】LeetCode 14. 最长公共前缀 Java

    我的思路: 给字符串数组按照字符串的长度从长到短排序,因为最长公共前缀最长的话,也只能是字符串数组中最短的那一个字符串 设置一个index变量,表示当前正在检查字符数组中所有字符串的index位置 循环遍历字符串数组n遍,n也就是最长公共前缀的长度 其他思路,方法

    2024年02月15日
    浏览(40)
  • 【算法|动态规划No.28】leetcode1312. 让字符串成为回文串的最少插入次数

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月06日
    浏览(57)
  • (动态规划) 剑指 Offer 48. 最长不含重复字符的子字符串 ——【Leetcode每日一题】

    难度:中等 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2: 输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”,所

    2024年02月11日
    浏览(60)
  • LeetCode - 1371 每个元音包含偶数次的最长子字符串(Java & JS & Python & C)

    题目来源 1371. 每个元音包含偶数次的最长子字符串 - 力扣(LeetCode) 题目描述 给你一个字符串  s  ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 \\\'a\\\',\\\'e\\\',\\\'i\\\',\\\'o\\\',\\\'u\\\' ,在子字符串中都恰好出现了偶数次。 示例 示例 1 输入:s = \\\"eleetminicoworoep\\\" 输出:

    2024年01月25日
    浏览(44)
  • 编写函数,判断一个字符串是否是回文。在主函数中输入一个字符串,调用自定义函数,输出结果。 所谓回文是指顺读和倒读都一样的字符串。如“AMNMA“是回文。

    编写函数,判断一个字符串是否是回文。在主函数中输入一个字符串,调用自定义函数,输出结果。 所谓回文是指顺读和倒读都一样的字符串。如\\\"AMNMA\\\"是回文。 测试输入:abcba 测试输出:是回文! 这道题要求编写一个函数来判断一个字符串是否是回文,并在主函数中调用该

    2024年02月03日
    浏览(68)
  • 字符串后面补最短长度的字符,使其整体成回文字符串(java)

    给定一个字符串str,只能在str的后面添加字符,想让str整体变成回文串,返回至少要添加几个字符 首先介绍下manacher 算法: Manacher 算法是一种线性时间复杂度的求解最长回文子串的算法。它的核心思想是利用已知回文信息,避免重复计算。 Manacher 算法的基本思想是通过预处

    2024年02月16日
    浏览(37)
  • PTA-判断回文字符串(python)

    判断回文字符串 作者 陈春晖 单位 浙江大学 回文就是字符串中心对称,从左向右读和从右向左读的内容是一样的。 输入一个字符串,判断该字符串是否为回文,只考虑数字和字母字符,字母的大小写没有区别。 输入格式: 输入一个字符串。 输出格式: 是回文,一行输出

    2024年04月12日
    浏览(58)
  • C语言——oj刷题——回文字符串

    问题: 实现一个函数,判断一个字符串是否为回文字符串。 回文字符串是指正读和反读都相同的字符串。例如,\\\"level\\\"、\\\"radar\\\"和\\\"madam\\\"都是回文字符串。 要解决这个问题,我们可以使用两个指针分别指向字符串的首尾字符,然后逐步向中间移动,同时比较指针所指向的字符是

    2024年02月21日
    浏览(46)
  • 【动态规划】【字符串】132.分割回文串 II

    视频算法专题 动态规划汇总 字符串 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。 返回符合要求的 最少分割次数 。 示例 1: 输入:s = “aab” 输出:1 解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。 示例 2: 输入:s = “a”

    2024年02月03日
    浏览(53)
  • C语言学习:输入一行字符串,输出字符串中最长的单词。

    输入一行字符,编写一个函数,将此字符串中最长的单词输出。 代码示例如下: 一、输出字符串中第一个最长单词 测试结果:  二、输出字符串中所有最长单词 评论区指出上述程序不能输出同样最长的两个单词,修改后该程序能输出所有最长单词,即如果有多个同样最长的

    2024年02月05日
    浏览(61)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包