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


目录
相关文章
|
10天前
|
算法 JavaScript 前端开发
在JavaScript中实现基本的碰撞检测算法,我们通常会用到矩形碰撞检测,也就是AABB(Axis-Aligned Bounding Box)碰撞检测
【6月更文挑战第16天】JavaScript中的基本碰撞检测涉及AABB(轴对齐边界框)方法,常用于2D游戏。`Rectangle`类定义了矩形的属性,并包含一个`collidesWith`方法,通过比较边界来检测碰撞。若两矩形无重叠部分,四个条件(关于边界相对位置)均需满足。此基础算法适用于简单场景,复杂情况可能需采用更高级的检测技术或物理引擎库。
48 6
|
8天前
|
算法 Java
[Java·算法·简单] LeetCode 283. 移动零
[Java·算法·简单] LeetCode 283. 移动零
16 2
|
11天前
|
存储 算法 调度
力扣中级算法(Python)
力扣中级算法(Python)
|
11天前
|
算法 Python
力扣初级算法(Python)(二)
力扣初级算法(Python)(二)
|
11天前
|
算法 Python
力扣初级算法(Python)(一)
力扣初级算法(Python)(一)
|
12天前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
16天前
|
存储 算法 数据可视化
如何使用多种算法解决LeetCode第135题——分发糖果问题
如何使用多种算法解决LeetCode第135题——分发糖果问题
|
12天前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
12天前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏