学习记录: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

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

如何将Tomcat容器替换为Jetty容器

《如何将Tomcat容器替换为Jetty容器》:本文主要介绍如何将Tomcat容器替换为Jetty容器问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat容器替换为Jetty容器修改Maven依赖配置文件调整(可选)重新构建和运行总结Tomcat容器替

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.