我写了首诗,把滑动窗口算法变成了默写题 :: labuladong的算法小抄 #1023
Replies: 108 comments 31 replies
-
第2和第3题的 |
Beta Was this translation helpful? Give feedback.
-
是的,但是作者代码也没问题,只能说改成:if(right - left == t.size()) 就可以了,估计作者为了更好的模板话代码才那样写的叭。 |
Beta Was this translation helpful? Give feedback.
-
第二题第三题可以固定滑动窗口的大小为子串的长度来进行滑动吗?感觉可能更方便一点,作者这么写是不是也是为了模板的通用性? |
Beta Was this translation helpful? Give feedback.
-
感谢大佬!! |
Beta Was this translation helpful? Give feedback.
-
76题 : Java 版本 public String minWindow( String s, String t ) {
String res = "";
if ( t.length() > s.length() ) {
return res;
}
HashMap<Character, Integer> need = new HashMap<>();
HashMap<Character, Integer> window = new HashMap<>();
for ( int i = 0; i < t.length(); i++ ) {
char ch = t.charAt( i );
need.put( ch, need.getOrDefault( ch, 0 ) + 1 );
}
int l = 0;
int r = 0;
int valid = 0;
int len = Integer.MAX_VALUE;
int start = 0;
while ( r < s.length() ) {
char ch = s.charAt( r );
r++;
if ( need.containsKey( ch ) ) {
window.put( ch, window.getOrDefault( ch, 0 ) + 1 );
if ( window.get( ch ).equals( need.get( ch ) ) ) {
valid++;
}
}
// 判断左侧窗口是否要收缩
while ( valid == need.size() ) {
// 在这里更新最小覆盖子串
if ( r - l < len ) {
start = l;
len = r - l;
}
// d 是将移出窗口的字符
char d = s.charAt( l );
// 左移窗口
l++;
// 进行窗口内数据的一系列更新
if ( need.containsKey( d ) ) {
if ( window.get( d ).equals( need.get( d ) ) ) {
valid--;
}
window.put( d, window.get( d ) - 1 );
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring( start, start+len );
} |
Beta Was this translation helpful? Give feedback.
-
@MessiahChen > 第二题第三题可以固定滑动窗口的大小为子串的长度来进行滑动吗?感觉可能更方便一点,作者这么写是不是也是为了模板的通用性? 我也发现了这一点,不过细想了一下,如果固定窗口大小,是不是窗口里的每个字符都得比较一次,这样的话时间复杂度就是O(s*t),而东哥的做法只需要比较窗口长度,不用遍历窗口,时间复杂度是O(s)(最差也是O(2s)),不知道是不是这样。 |
Beta Was this translation helpful? Give feedback.
-
3道题目的Java版本在这里! ================ 76. 最小覆盖子串 ================
class Solution {
public String minWindow(String s, String t) {
// 记录t 以及 滑动窗口window中 字符与个数的映射关系
HashMap<Character, Integer> window_map = new HashMap<>();
HashMap<Character, Integer> t_map = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char c1 = t.charAt(i);
t_map.put(c1, t_map.getOrDefault(c1, 0) + 1);
}
// 双指针,
int left = 0;
int right = 0;
int count = 0;
// 用于更新满足的窗口window的长度,如果是len一直是MAX_VALUE,说明没有满足的串
int len = Integer.MAX_VALUE;
// 用于记录window串的起始位置,则返回 s[start, len]
int start = 0;
while (right < s.length()) {
char c = s.charAt(right);
right++;
// 只要c是t中出现的字符就更新
if (t_map.containsKey(c)) {
window_map.put(c, window_map.getOrDefault(c, 0) + 1);
// 更新c字符出现的次数
if (window_map.get(c).equals(t_map.get(c))) {
count++;
}
}
// System.out.println(window_map);
// ----------------------------------
// 收缩window的长度
while (count == t_map.size()) {
// 更新并记录window的长度,以及window的起始位置start
if (right - left < len) {
start = left;
len = right - left;
}
char d = s.charAt(left);
left++;
if (t_map.containsKey(d)) {
if (window_map.get(d).equals(t_map.get(d))) {
count--;
}
window_map.put(d, window_map.get(d) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
}
================ 438. 找到字符串中所有字母异位词 ================
class Solution {
public List<Integer> findAnagrams(String s, String p) {
// ========= 模板:定义相关数据结构,初始化工作============
HashMap<Character, Integer> window_map = new HashMap<>();
HashMap<Character, Integer> p_map = new HashMap<>();
for (int i = 0; i < p.length(); i++){
char c1 = p.charAt(i);
p_map.put(c1, p_map.getOrDefault(c1, 0) + 1);
}
int left, right, count;
left = right = count = 0;
ArrayList<Integer> res = new ArrayList<>();
// ================== 模板:开始滑动窗口=====================
while (right < s.length()) {
// =========== 模板:向右滑动窗口,装填满足的字符到map中==========
char c = s.charAt(right);
right++;
if (p_map.containsKey(c)) {
window_map.put(c, window_map.getOrDefault(c, 0) + 1);
if (window_map.get(c).equals(p_map.get(c))) {
count++;
}
}
// =========== 根据题意:此时“有可能”出现满足条件的解 ==========
while (right - left == p.length()) {
// ============= 根据题意:获取“真正”满足条件的解 =============
if (count == p_map.size()){
res.add(left);
}
// ========== 模板:左指针向右滑动,寻找下一个可行解/优化已知解======
char d = s.charAt(left);
left++;
if (p_map.containsKey(d)) {
if (window_map.get(d).equals(p_map.get(d))) {
count--;
}
window_map.put(d, window_map.getOrDefault(d, 0) - 1);
}
}
}
return res;
}
}
================ 567. 字符串的排列 ================
class Solution {
public boolean checkInclusion(String p, String s) {
// ========= 模板:定义相关数据结构,初始化工作============
HashMap<Character, Integer> window_map = new HashMap<>();
HashMap<Character, Integer> p_map = new HashMap<>();
for (int i = 0; i < p.length(); i++){
char c1 = p.charAt(i);
p_map.put(c1, p_map.getOrDefault(c1, 0) + 1);
}
int left, right, count;
left = right = count = 0;
// ================== 模板:开始滑动窗口=====================
while (right < s.length()) {
// =========== 模板:向右滑动窗口,装填满足的字符到map中==========
char c = s.charAt(right);
right++;
if (p_map.containsKey(c)) {
window_map.put(c, window_map.getOrDefault(c, 0) + 1);
if (window_map.get(c).equals(p_map.get(c))) {
count++;
}
}
// =========== 根据题意:此时“有可能”出现满足条件的解 ==========
while (right - left == p.length()) {
// ============= 根据题意:获取“真正”满足条件的解 =============
if (count == p_map.size()){
return true;
}
// ========== 模板:左指针向右滑动,寻找下一个可行解/优化已知解======
char d = s.charAt(left);
left++;
if (p_map.containsKey(d)) {
if (window_map.get(d).equals(p_map.get(d))) {
count--;
}
window_map.put(d, window_map.getOrDefault(d, 0) - 1);
}
}
}
return false;
}
} |
Beta Was this translation helpful? Give feedback.
-
@Hailei-J @tinainusa @InnovationFlash 你们确定不是自己写错了?我提交了一下都没有问题。 |
Beta Was this translation helpful? Give feedback.
-
很神奇,用你的c++ code跑了下就没问题。 |
Beta Was this translation helpful? Give feedback.
-
虽然速度效果一般,但是通过这个框架能记得比较牢,对于我这种菜鸡简直是福音,感谢大佬!!! |
Beta Was this translation helpful? Give feedback.
-
哈哈哈,这里的确是个思维误区,也不用二楼说的加个条件,我想了一天,还专门把代码跑了一遍发现没错。 |
Beta Was this translation helpful? Give feedback.
-
js 版最小覆盖子串 function minWindow(s, t) {
const needs = {},
window = {};
for (const c of t) {
if (needs[c] === undefined) {
needs[c] = 0;
}
needs[c]++;
window[c] = 0;
}
const needsSize = Object.keys(needs).length;
let left = 0,
right = 0;
let valid = 0;
// 记录最小覆盖子串的起始索引及长度
let start = 0,
len = Infinity;
while (right < s.length) {
// c 是将移入窗口的字符
const c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
if (needs[c] !== undefined) {
window[c]++;
if (window[c] === needs[c]) {
valid++;
}
}
// 判断左侧窗口是否要收缩
while (valid === needsSize) {
// 在这里更新最小覆盖子串
if (right - left < len) {
start = left;
len = right - left;
}
// d 是将移出窗口的字符
const d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
if (needs[d] !== undefined) {
if (window[d] === needs[d]) valid--;
window[d]--;
}
}
}
// 返回最小覆盖子串
return len === Infinity ? "" : s.substr(start, len);
}
console.log(minWindow("aa", "aa")); |
Beta Was this translation helpful? Give feedback.
-
js 版字符串排列 function checkInclusion(s1, s2) {
const needs = {},
window = {};
for (const c of s1) {
if (needs[c] === undefined) {
needs[c] = 0;
}
needs[c]++;
window[c] = 0;
}
const needsSize = Object.keys(needs).length;
let left = 0,
right = 0;
let valid = 0;
while (right < s2.length) {
// c 是将移入窗口的字符
const c = s2[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
if (needs[c] !== undefined) {
window[c]++;
if (window[c] === needs[c]) valid++;
}
// 判断左侧窗口是否要收缩
while (right - left >= s1.length) {
// 在这里判断是否找到了合法的子串
if (valid === needsSize) return true;
// d 是将移出窗口的字符
const d = s2[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
if (needs[d] !== undefined) {
if (window[d] === needs[d]) valid--;
window[d]--;
}
}
}
return false;
}
console.log(checkInclusion("aba", "eidbaaooo")); |
Beta Was this translation helpful? Give feedback.
-
js 最长无重复子串 function lengthOfLongestSubstring(s) {
const window = {};
for (const c of s) {
window[c] = 0;
}
let left = 0,
right = 0;
let result = 0; // 记录结果
while (right < s.length) {
// c 是将移入窗口的字符
const c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
window[c]++;
// 判断左侧窗口是否要收缩
while (window[c] > 1) {
// d 是将移出窗口的字符
const d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
window[d]--;
}
// 在这里更新答案
result = Math.max(result, right - left);
}
return result;
}
console.log(lengthOfLongestSubstring("abcabcbb")); |
Beta Was this translation helpful? Give feedback.
-
请教下,第二题和第三题,如果"ab"和"acb"为什么能够正确判断?我运行作者的代码运行正确,但是改成python就会出错。 |
Beta Was this translation helpful? Give feedback.
-
666 |
Beta Was this translation helpful? Give feedback.
-
滑动窗口算法的代码框架的winodw.add(c),window写错了 |
Beta Was this translation helpful? Give feedback.
-
大佬有个问题,我的理解valid 是不是解释为满足条件的字符种类的个数更合理一点 |
Beta Was this translation helpful? Give feedback.
-
滑动窗口各个时刻window的状态 left++ right++ left++ |
Beta Was this translation helpful? Give feedback.
-
两轮面试都出了子串相关的题目,滑动窗口真好用。 |
Beta Was this translation helpful? Give feedback.
-
我有一个问题,像第二题如果s1= i d e, s2 = e i d b a o o o, 我感觉文中的解法也是会返回true,因为没考虑字符串的排列,求解答,谢谢! |
Beta Was this translation helpful? Give feedback.
-
在最长无重复子串中遇到一个奇怪的问题。我用相同的代码,如果三个测试用例一起测试的话,在第二个就会出错,但是把第一个用例删掉的话,第二个用例就不会错。
}; |
Beta Was this translation helpful? Give feedback.
-
第二题用int array的做法,需要多写一个helper method来比较两个int array,但是时间空间复杂度都更低 class Solution {
public boolean checkInclusion(String s1, String s2) {
// Initialize 2 int arrays to store frequencies of characters in our target and our window
int[] need = new int[26], window = new int[26];
// Our target int array
for(char c:s1.toCharArray()) need[c-'a']++;
int left = 0, right = 0;
// Check our window until the end of the array
while(right < s2.length()) {
char d = s2.charAt(right);
right++;
// If the character exists in our target, increase the corresponding element in our window
if(need[d-'a']!=0) window[d-'a']++;
// When the length of window equals our target string
if(right - left == s1.length()) {
// Check if the frequencies of chars in target and our window are equal
if (areArraysEqual(need,window)) return true;
// Shrink our window and update the frequencies in our window array
char e = s2.charAt(left);
left++;
// If the char to be excluded is in our target, decrease the frequency
if(need[e-'a']!=0) window[e-'a']--;
}
}
return false;
}
// Helper method to judge if 2 int arrays are equal
public boolean areArraysEqual(int[] arr1, int[] arr2) {
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
} |
Beta Was this translation helpful? Give feedback.
-
非常感谢您的邮件。
|
Beta Was this translation helpful? Give feedback.
-
最小覆盖子串里,我没用Integer.MAX_VALUE,而是用了如下的方式,在leetcode中显示266 / 267 testcases passed, 总有一个特别长的test case过不了,请帮我看看是出了什么问题,谢谢!
|
Beta Was this translation helpful? Give feedback.
-
非常感谢,我来一个424. Longest Repeating Character Replacement问题的题解,套用模板: class Solution:
def characterReplacement(self, s: str, k: int) -> int:
if not s:
return 0
# 记录每个字符出现的次数
counter = collections.defaultdict(int)
left = 0
right = 0
maxlen = 0
res = 0
while left <= right and right < len(s):
c = s[right]
right += 1
counter[c] += 1
maxlen = max(maxlen, counter[c])
# 窗口长度减去最大字符出现次数小于 k,表示需要移动左指针
while right - left - maxlen > k:
d = s[left]
left += 1
counter[d] -= 1
# 更新最大长度
res = max(res, right - left)
return res 希望能有所帮助 |
Beta Was this translation helpful? Give feedback.
-
【76. 最小覆盖子串】代码分块,使代码与文中的算法思路对应更直接 【文中算法思路】 class Solution {
String source, target;
Map<Character, Integer> targetCharCount;
Map<Character, Integer> windowCharCount;
int left, right;
int windowValidChars;
int minWindowStart, minWindowLength;
public String minWindow(String s, String t) {
init(s, t); // 第 1 步,初始化
while (canExpand()) { // 第 4 步,重复第 2,3 步
while (canExpand() && !windowContainsSolution()) expandWindow(); // 第 2 步,扩大窗口
while (windowContainsSolution()) { // 第 3 步
updateSolution(); // 更新结果
shrinkWindow(); // 缩小窗口
}
}
return getSolution();
}
void init(String source, String target) {
this.source = source;
this.target = target;
targetCharCount = getCharCount(target);
windowCharCount = new HashMap<>(targetCharCount.size());
left = 0;
right = 0;
windowValidChars = 0;
minWindowStart = 0;
minWindowLength = Integer.MAX_VALUE;
}
Map<Character, Integer> getCharCount(String s) {
int n = s.length();
Map<Character, Integer> charToCount = new HashMap<>(n);
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
charToCount.put(c, charToCount.getOrDefault(c, 0) + 1);
}
return charToCount;
}
boolean canExpand() {
return right < source.length();
}
boolean windowContainsSolution() {
return windowValidChars == targetCharCount.size();
}
void expandWindow() {
char c = source.charAt(right);
int targetCount = targetCharCount.getOrDefault(c, 0);
if (targetCount > 0) {
int oldCount = windowCharCount.getOrDefault(c, 0);
int newCount = oldCount + 1;
windowCharCount.put(c, newCount);
if (newCount == targetCount) windowValidChars++;
}
right++;
}
void updateSolution() {
int thisWindowLength = right - left;
if (thisWindowLength < minWindowLength) {
minWindowStart = left;
minWindowLength = thisWindowLength;
}
}
void shrinkWindow() {
char c = source.charAt(left);
int targetCount = targetCharCount.getOrDefault(c, 0);
if (targetCount != 0) {
int oldCount = windowCharCount.get(c);
windowCharCount.put(c, oldCount - 1);
if (oldCount == targetCount) windowValidChars--;
}
left++;
}
String getSolution() {
return minWindowLength == Integer.MAX_VALUE ? "" : source.substring(minWindowStart, minWindowStart + minWindowLength);
}
} |
Beta Was this translation helpful? Give feedback.
-
没看懂时:写什么玩意 |
Beta Was this translation helpful? Give feedback.
-
一套打通,感谢。写的很丝滑,不用硬套,理解窗口的作用,直接根据题目加上自己对题目的限制条件的理解。 |
Beta Was this translation helpful? Give feedback.
-
写的肿不错啊 |
Beta Was this translation helpful? Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
文章链接点这里:我写了首诗,把滑动窗口算法变成了默写题
评论礼仪 见这里,违者直接拉黑。
Beta Was this translation helpful? Give feedback.
All reactions