LeetCode最长回文串使用JavaScript解题|前端学算法

简介: LeetCode最长回文串使用JavaScript解题|前端学算法

最长回文串


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

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

示例 1:

输入:s = "abccccdd"

输出:7

解释:

我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

示例 2:

输入:s = "a"

输入:1

什么是回文串?

正着读和反着读都相同的字符串序列就称为“回文串”,是一个对称的字符串比如说:abba,abcdcba


解题思路



回文串可以分为两类,第一类就是奇数个字符的回文串,除了中间字符以外,其他字符镜面对称,比如aba;第二类就是偶数个回文串:所有的字符全都镜面堆成,比如abba

简单的来说,(有可能除去一个字母外)其他的字母都出现偶数次,

所以此时我们需要统计每个字符出现的次数,可以用哈希表来统计

具体步骤可参考如下:

  • 第一步:创建变量maxLength记录回文串的长度,odd是否有奇数个的字符,strMap用于存储每个字符的数量
  • 第二步:遍历字符串,如果哈希表strMap里没有当前字符则当前字符变成key,且值加一;如果有存在当前字符,则值自加一
  • 第三步:遍历strMap,给当前字符取模(strMap[key] % 2);如果值为0则表明当前字符是偶数个,长度加上当前字符的个数;如果值不是0则表明当前字符有奇数个,有可能是1个也有可能是3个或者5、7、9个,所以可以用此字符长度-1,来说明可以有几个加入到回文串中,并且让odd为true
  • 第四步:判断odd是否为true,如果不是true,那么说明字符串中都是偶数个,最大的长度就是maxLength;如果是true,说明有奇数个,可以再回文串中再加入一个字符,最终长度变为 maxLength+1
var longestPalindrome = function(s) {
    let maxLength = 0; // 计算长度
    let odd = false; // 是否含有奇数个
    let strMap = {};
    for(let i=0;i<s.length;i++){
        if(s[i] in strMap){
            strMap[s[i]] += 1;
        } else {
            strMap[s[i]] = 1;
        }
    }
    for(let key in strMap) {
        if(strMap[key] % 2 === 0) {
            maxLength += strMap[key];
        } else {
            odd = true;
            // 有个能是大于1的奇数个字符
            maxLength += strMap[key]-1;
        }
    }
    if(odd) {
        maxLength+=1;
    }
    return maxLength;
};


image.png


知识点


  • for...of 以任意顺序迭代一个对象的除Symbol以外的可枚举属性
var obj = {a:1, b:2, c:3};
for (let key in obj) {
  console.log("键---值:",key,obj[key]);
  console.log();
}
// Output:
// 键---值: a 1
// 键---值: b 2
// 键---值: c 3


目录
相关文章
|
11月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
109 0
|
11月前
|
人工智能 自然语言处理 程序员
通义灵码:融合创新玩法与探索,重塑LeetCode解题策略
欢迎来到工程师令狐小哥的频道。本文介绍如何利用AI工具高效刷LeetCode,通过通义灵码插件在IntelliJ IDEA中实现代码生成、优化、单元测试等功能,提升编程学习效率。
404 1
通义灵码:融合创新玩法与探索,重塑LeetCode解题策略
|
10月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
210 4
|
11月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
110 2
|
11月前
|
算法 C++
【算法解题思想】动态规划+深度优先搜索(C/C++)
【算法解题思想】动态规划+深度优先搜索(C/C++)
|
11月前
|
算法 Java 程序员
【算法每日一练及解题思路】有n级台阶,一次只能上1级或2级,共有多少种走法?
本文深入解析了“爬楼梯问题”,探讨了递归与迭代两种解法,并提供了Java代码实现。通过分析问题本质,帮助读者理解动态规划技巧,提高解决实际编程问题的能力。关键词:Java, 算法, 动态规划, 爬楼梯问题, 递归, 迭代。
495 0
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
149 6
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
151 1
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
171 1
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
176 0

热门文章

最新文章