本文主要是介绍学习记录: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;
}
讲解
- 首先获取 s1 和 s2 的长度。如果 s1 的长度大于 s2,直接返回 false,因为不可能在一个更短的字符串中找到一个更长的字符串的排列。
- 创建两个 Map,count1 用于存储 s1 中每个字符的频率,count2 用于存储 s2 中当前窗口(长度为 len1)的字符频率。
- 遍历 s1 中的每个字符,使用 Map 的 set 方法 更新字符频率。如果该字符已经存在于 count1 中,则频率加 1;如果不存在,则初始化为 1。 同样地,遍历 s2 的前 len1 个字符,填充 count2。
- 在填充完 count2 后,首先检查 count1 和 count2 是否相等。如果相等,说明 s2 的前 len1 个字符就是 s1 的一个排列,返回 true。
- 使用 for 循环遍历 s2,从 len1 到 len2:
将当前字符 s2[i] 加入到 count2 中,更新其频率。
计算滑动窗口的左边界字符 s2[i - len1],将其频率减 1。如果减到 0,则从 count2 中删除该字符。- 每次更新 count2 后,检查 count1 和 count2 是否相等。如果相等,返回 true。
- 辅助函数 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;
};
讲解
- 计算 s1 和 s2 的长度。如果 s1 的长度大于 s2,则不可能包含其排列,直接返回 false。
- 创建两个数组 s1Count 和 s2Count,大小为 26(对应英文字母 a-z),用来统计每个字符的出现频率。
- 循环,统计 s1 和 s2 的前 s1Length 个字符的频率。
- 比较频率数组
定义一个辅助函数 checkEqual,用于比较两个频率数组是否相等。
如果 s1Count 和 s2Count 相等,说明 s2 的前 s1Length 个字符是 s1 的一个排列,直接返回 true。- 滑动窗口遍历 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;
}
讲解
- 外层循环用于确定子字符串的起始位置。
- 内层循环用于确定子字符串的结束位置。
- 使用 slice 方法获取从 start 到 end 的子字符串。
- 使用一个数组 charCount 来记录当前子字符串中每个字符的频率。
- 计算当前子字符串中字符的最大频率 **maxCount ** 。
- 计算将当前子字符串变为相同字符所需的更改次数 **changesNeeded ** 。
- 如果所需的更改次数小于或等于 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;
}
讲解
这个看了讲解,很细,先看网上的思路:
- 定义窗口:使用两个指针 left 和 right 来表示当前窗口的范围。
- 记录字符频率:使用一个数组或对象来记录当前窗口中每个字符的频率。
- 计算最大频率:在每次扩展窗口时,计算当前窗口内字符的最大频率。
- 判断窗口有效性:如果窗口的大小减去最大频率大于 k,则说明需要缩小窗口。
- 更新最大长度:在每次调整窗口后,更新最长的子字符串长度。
结合代码:
- 字符频率数组:
count 数组用于记录每个字符**(A-Z)**的频率。数组大小为 26,因为只有 26 个大写字母。- 左右指针:
left 指针用于表示当前窗口的左边界。
maxCount 用于记录当前窗口内字符的最大频率。
maxLength 用于记录找到的最长只包含相同字母的子字符串的长度。- 遍历字符串:
使用 right 指针遍历字符串 s,不断扩展窗口- 更新字符频率:
每次扩展 right 指针时,更新当前字符的频率。通过 charCodeAt() 方法获取字符的 ASCII 码并计算其在 count 数组中的索引。- 更新最大频率:
更新窗口内的最大字符频率 **maxCount ** 。- 判断窗口有效性:
如果当前窗口的大小减去最大频率大于 k,则说明需要缩小窗口。通过移动 left 指针来实现。
在缩小窗口的同时,更新 count 数组中对应字符的频率。- 更新最长子字符串的长度:
在每次调整窗口后,更新最长的子字符串长度,计算当前窗口的大小 right - left + 1。- 返回结果:
最后返回找到的最长只包含相同字母的子字符串的长度。
总结
之前学习的知识在现在能用上了,比如 Map,双指针 等等,虽然我用的磕磕绊绊,甚至有的还无法结合在一起解题。但是,还是那句话:循环真好用!
这篇关于学习记录:js算法(二十一):字符串的排列、替换后的最长重复字符的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!