学习记录:js算法(二十一):字符串的排列、替换后的最长重复字符

本文主要是介绍学习记录:js算法(二十一):字符串的排列、替换后的最长重复字符,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 字符串的排列
      • 我的思路
      • 网上思路
    • 替换后的最长重复字符
      • 我的思路
      • 网上思路
    • 总结

字符串的排列

给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false
换句话说,s1 的排列之一是 s2 的 子串 。

示例 1:
输入:s1 = "ab" s2 = "eidbaooo"
输出:true
解释:s2 包含 s1 的排列之一 ("ba").示例 2:
输入:s1= "ab" s2 = "eidboaoo"
输出:false

我的思路
老样子,循环,写的时候还是用了 Map()
网上思路
使用滑动窗口

我的思路

function checkInclusion(s1, s2) {const len1 = s1.length;const len2 = s2.length;if (len1 > len2) return false;const count1 = new Map();const count2 = new Map();for (let char of s1) {count1.set(char, (count1.get(char) || 0) + 1);}for (let i = 0; i < len1; i++) {count2.set(s2[i], (count2.get(s2[i]) || 0) + 1);}if (mapsEqual(count1, count2)) return true;for (let i = len1; i < len2; i++) {count2.set(s2[i], (count2.get(s2[i]) || 0) + 1);const oldChar = s2[i - len1];count2.set(oldChar, count2.get(oldChar) - 1);if (count2.get(oldChar) === 0) {count2.delete(oldChar);}if (mapsEqual(count1, count2)) return true;}return false;
}
function mapsEqual(map1, map2) {if (map1.size !== map2.size) return false;for (let [key, value] of map1) {if (map2.get(key) !== value) return false;}return true;
}

讲解

  1. 首先获取 s1s2 的长度。如果 s1 的长度大于 s2,直接返回 false,因为不可能在一个更短的字符串中找到一个更长的字符串的排列。
  2. 创建两个 Mapcount1 用于存储 s1 中每个字符的频率,count2 用于存储 s2 中当前窗口(长度为 len1)的字符频率。
  3. 遍历 s1 中的每个字符,使用 Map 的 set 方法 更新字符频率。如果该字符已经存在于 count1 中,则频率加 1;如果不存在,则初始化为 1。 同样地,遍历 s2 的前 len1 个字符,填充 count2
  4. 在填充完 count2 后,首先检查 count1count2 是否相等。如果相等,说明 s2 的前 len1 个字符就是 s1 的一个排列,返回 true
  5. 使用 for 循环遍历 s2,从 len1 到 len2:
    将当前字符 s2[i] 加入到 count2 中,更新其频率。
    计算滑动窗口的左边界字符 s2[i - len1],将其频率减 1。如果减到 0,则从 count2 中删除该字符。
  6. 每次更新 count2 后,检查 count1count2 是否相等。如果相等,返回 true
  7. 辅助函数 mapsEqual: 用于比较两个 Map 是否相等。
    首先检查两个 Map 的大小是否相等,如果不相等,返回 false。
    然后遍历 map1,检查 map2 中是否存在相同的键和对应的值。如果有不匹配的情况,则返回 false
    如果所有键值对都匹配,则返回 true

网上思路

var checkInclusion = function (s1, s2) {const s1Length = s1.length;const s2Length = s2.length;if (s1Length > s2Length) return false;const s1Count = Array(26).fill(0);const s2Count = Array(26).fill(0);// 统计 s1 中每个字符的频率for (let i = 0; i < s1Length; i++) {s1Count[s1.charCodeAt(i) - 'a'.charCodeAt(0)]++;s2Count[s2.charCodeAt(i) - 'a'.charCodeAt(0)]++;}// 比较 s1Count 和 s2Countconst checkEqual = (a, b) => {for (let i = 0; i < 26; i++) {if (a[i] !== b[i]) return false;}return true;};if (checkEqual(s1Count, s2Count)) return true;// 滑动窗口for (let i = s1Length; i < s2Length; i++) {s2Count[s2.charCodeAt(i) - 'a'.charCodeAt(0)]++;s2Count[s2.charCodeAt(i - s1Length) - 'a'.charCodeAt(0)]--;if (checkEqual(s1Count, s2Count)) return true;}return false;
};

讲解

  1. 计算 s1 和 s2 的长度。如果 s1 的长度大于 s2,则不可能包含其排列,直接返回 false
  2. 创建两个数组 s1Count 和 s2Count,大小为 26(对应英文字母 a-z),用来统计每个字符的出现频率。
  3. 循环,统计 s1s2 的前 s1Length 个字符的频率。
  4. 比较频率数组
    定义一个辅助函数 checkEqual,用于比较两个频率数组是否相等。
    如果 s1Count 和 s2Count 相等,说明 s2 的前 s1Length 个字符是 s1 的一个排列,直接返回 true
  5. 滑动窗口遍历 s2
    s1Length 开始,遍历 s2 的剩余部分,使用滑动窗口的方式更新 s2Count。每次添加一个新字符 s2[i] 并移除一个旧字符 s2[i - s1Length]
    每次更新后,检查 s1Count 和 s2Count 是否相等。

替换后的最长重复字符

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符,并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
在执行上述操作后,返回 包含相同字母的最长子字符串的长度。

示例 1:
输入:s = "ABAB", k = 2
输出:4
解释:用两个'A'替换为两个'B',反之亦然。示例 2:
输入:s = "AABABBA", k = 1
输出:4
解释:
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
可能存在其他的方法来得到同样的结果。

我的思路
循环
网上思路
滑动窗口

我的思路

var characterReplacement = function (s, k) {let maxLength = 0;for (let start = 0; start < s.length; start++) {for (let end = start; end < s.length; end++) {const substring = s.slice(start, end + 1);const charCount = new Array(26).fill(0);for (let char of substring) {charCount[char.charCodeAt() - 'A'.charCodeAt()]++;}const maxCount = Math.max(...charCount);const changesNeeded = substring.length - maxCount;if (changesNeeded <= k) {maxLength = Math.max(maxLength, substring.length);}}}return maxLength;
}

讲解

  1. 外层循环用于确定子字符串的起始位置。
  2. 内层循环用于确定子字符串的结束位置。
  3. 使用 slice 方法获取从 startend 的子字符串。
  4. 使用一个数组 charCount 来记录当前子字符串中每个字符的频率。
  5. 计算当前子字符串中字符的最大频率 **maxCount ** 。
  6. 计算将当前子字符串变为相同字符所需的更改次数 **changesNeeded ** 。
  7. 如果所需的更改次数小于或等于 k,则更新最长子字符串的长度。

网上思路

var characterReplacement = function (s, k) {const count = new Array(26).fill(0); // 用于记录字符频率let left = 0; // 左指针let maxCount = 0; // 当前窗口内字符的最大频率let maxLength = 0; // 最长子字符串的长度for (let right = 0; right < s.length; right++) {// 更新当前字符的频率count[s[right].charCodeAt() - 'A'.charCodeAt()]++;// 更新窗口内的最大字符频率maxCount = Math.max(maxCount, count[s[right].charCodeAt() - 'A'.charCodeAt()]);// 如果当前窗口的大小减去最大频率大于 k,则需要缩小窗口while (right - left + 1 - maxCount > k) {count[s[left].charCodeAt() - 'A'.charCodeAt()]--;left++;}// 更新最长子字符串的长度maxLength = Math.max(maxLength, right - left + 1);}return maxLength;
}

讲解
这个看了讲解,很细,先看网上的思路:

  1. 定义窗口:使用两个指针 left 和 right 来表示当前窗口的范围。
  2. 记录字符频率:使用一个数组或对象来记录当前窗口中每个字符的频率。
  3. 计算最大频率:在每次扩展窗口时,计算当前窗口内字符的最大频率。
  4. 判断窗口有效性:如果窗口的大小减去最大频率大于 k,则说明需要缩小窗口。
  5. 更新最大长度:在每次调整窗口后,更新最长的子字符串长度。

结合代码:

  1. 字符频率数组:
    count 数组用于记录每个字符**(A-Z)**的频率。数组大小为 26,因为只有 26 个大写字母。
  2. 左右指针:
    left 指针用于表示当前窗口的左边界。
    maxCount 用于记录当前窗口内字符的最大频率。
    maxLength 用于记录找到的最长只包含相同字母的子字符串的长度。
  3. 遍历字符串:
    使用 right 指针遍历字符串 s,不断扩展窗口
  4. 更新字符频率:
    每次扩展 right 指针时,更新当前字符的频率。通过 charCodeAt() 方法获取字符的 ASCII 码并计算其在 count 数组中的索引。
  5. 更新最大频率:
    更新窗口内的最大字符频率 **maxCount ** 。
  6. 判断窗口有效性:
    如果当前窗口的大小减去最大频率大于 k,则说明需要缩小窗口。通过移动 left 指针来实现。
    在缩小窗口的同时,更新 count 数组中对应字符的频率。
  7. 更新最长子字符串的长度:
    在每次调整窗口后,更新最长的子字符串长度,计算当前窗口的大小 right - left + 1
  8. 返回结果:
    最后返回找到的最长只包含相同字母的子字符串的长度。

总结

之前学习的知识在现在能用上了,比如 Map双指针 等等,虽然我用的磕磕绊绊,甚至有的还无法结合在一起解题。但是,还是那句话:循环真好用!

这篇关于学习记录:js算法(二十一):字符串的排列、替换后的最长重复字符的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1128602

相关文章

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》:本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST(抽象语法树)、字符串操作... 目录前言解决方案方法一:使用正则表达式方法二:使用 Pyparsing方法三:使用 AST方法四:使用字

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

在Spring Boot中浅尝内存泄漏的实战记录

《在SpringBoot中浅尝内存泄漏的实战记录》本文给大家分享在SpringBoot中浅尝内存泄漏的实战记录,结合实例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录使用静态集合持有对象引用,阻止GC回收关键点:可执行代码:验证:1,运行程序(启动时添加JVM参数限制堆大小):2,访问 htt

JS+HTML实现在线图片水印添加工具

《JS+HTML实现在线图片水印添加工具》在社交媒体和内容创作日益频繁的今天,如何保护原创内容、展示品牌身份成了一个不得不面对的问题,本文将实现一个完全基于HTML+CSS构建的现代化图片水印在线工具... 目录概述功能亮点使用方法技术解析延伸思考运行效果项目源码下载总结概述在社交媒体和内容创作日益频繁的

Node.js 数据库 CRUD 项目示例详解(完美解决方案)

《Node.js数据库CRUD项目示例详解(完美解决方案)》:本文主要介绍Node.js数据库CRUD项目示例详解(完美解决方案),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考... 目录项目结构1. 初始化项目2. 配置数据库连接 (config/db.js)3. 创建模型 (models/

使用Node.js制作图片上传服务的详细教程

《使用Node.js制作图片上传服务的详细教程》在现代Web应用开发中,图片上传是一项常见且重要的功能,借助Node.js强大的生态系统,我们可以轻松搭建高效的图片上传服务,本文将深入探讨如何使用No... 目录准备工作搭建 Express 服务器配置 multer 进行图片上传处理图片上传请求完整代码示例

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2