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


目录
相关文章
|
2天前
|
前端开发 JavaScript 数据处理
前端新手指南:如何解决JavaScript导出CSV文件不完整的问题
【6月更文挑战第4天】在JavaScript中处理CSV文件时,需要特别注意一些特殊字符,例如逗号、双引号、换行符等。这些字符可能会影响CSV文件的解析,导致数据错乱。
12 0
|
23小时前
|
算法 JavaScript 前端开发
在JavaScript中实现基本的碰撞检测算法,我们通常会用到矩形碰撞检测,也就是AABB(Axis-Aligned Bounding Box)碰撞检测
【6月更文挑战第16天】JavaScript中的基本碰撞检测涉及AABB(轴对齐边界框)方法,常用于2D游戏。`Rectangle`类定义了矩形的属性,并包含一个`collidesWith`方法,通过比较边界来检测碰撞。若两矩形无重叠部分,四个条件(关于边界相对位置)均需满足。此基础算法适用于简单场景,复杂情况可能需采用更高级的检测技术或物理引擎库。
13 6
|
2天前
|
XML 前端开发 JavaScript
前端简介(HTML+CSS+JS)
前端简介(HTML+CSS+JS)
|
2天前
|
JavaScript 前端开发 网络协议
前端JS发起的请求能暂停吗?
在讨论前端JS发起的请求是否能暂停时,需要明确两个概念:什么状态可以被认为是“暂停”?以及什么是JS发起的请求?
57 1
前端JS发起的请求能暂停吗?
|
5天前
|
前端开发 JavaScript 安全
TypeScript作为一种静态类型的JavaScript超集,其强大的类型系统和面向对象编程特性为微前端架构的实现提供了有力的支持
【6月更文挑战第11天】微前端架构借助TypeScript提升开发效率和代码可靠性。 TypeScript提供类型安全,防止微前端间通信出错;智能提示和自动补全加速跨代码库开发;重构支持简化代码更新。通过定义公共接口确保一致性,用TypeScript编写微前端以保证质量。集成到构建流程确保顺利构建打包。在微前端场景中,TypeScript是强有力的语言选择。
23 2
|
8天前
|
前端开发 算法 JavaScript
优化算法在前端性能提升中的应用
随着互联网应用的日益复杂,前端性能优化成为开发者关注的焦点。本文探讨了优化算法在前端性能提升中的重要作用,包括对JavaScript代码的优化、资源加载的算法选择以及页面渲染的优化策略。通过合理应用优化算法,可以有效提升前端应用的性能和用户体验。
|
10天前
|
Web App开发 资源调度 JavaScript
【保姆级】前端使用node.js基础教程
【6月更文挑战第3天】Node.js 是基于 Chrome V8 引擎的 JavaScript 运行环境,用于服务器端编程。常用命令包括:安装 Node.js,通过 `node -v` 查看版本;使用 npm(Node 包管理器)进行初始化、安装/卸载包、查看版本和更新;运行 `.js` 脚本;使用 `node inspect` 调试;借助 nodemon 实现自动重启;通过 `npm list` 管理包;
5 0
|
10天前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
14 2
|
10天前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
13 0
|
11天前
|
算法 JavaScript 前端开发
【经典算法】LCR187:破冰游戏(约瑟夫问题,Java/C/Python3/JavaScript实现含注释说明,Easy)
【经典算法】LCR187:破冰游戏(约瑟夫问题,Java/C/Python3/JavaScript实现含注释说明,Easy)
15 1

热门文章

最新文章