fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
滑动窗口技巧 :: labuladong的算法小抄
- 字符串的排列
class Solution {
public boolean checkInclusion(String s1, String s2) {
int left = 0, right = 0;
int valid = 0;
Map<Character,Integer> need = new HashMap<>();
Map<Character,Integer> window = new HashMap<>();
for(char c : s1.toCharArray()){
need.put(c,need.getOrDefault(c,0)+1);
}
while(right<s2.length()){
char inc = s2.charAt(right);
right++;
if(need.containsKey(inc)){
window.put(inc,window.getOrDefault(inc,0)+1);
if(window.get(inc).equals(need.get(inc))) valid++;
}
/*
若向右扩展的“窗口”中包含满足条件的串。
条件：包含s1字符串中所有的字符，且各个字符个数等于（或等于）所需个数。
*/
while(valid==need.size()){/*从左侧缩小“窗口”时，若满足窗口中“刚好”包含s1中所有字符，
且个数与s1中各个字符数目相同，则满足题目条件返回True。*/
if(right-left==s1.length()) return true;
char outc = s2.charAt(left);
left++;
if(need.containsKey(outc)){
if(window.get(outc).equals(need.get(outc))) valid--;
window.put(outc,window.get(outc)-1);
}
}
}
return false;
}
}
class Solution {
public static String minWindow(String s, String t) {
int sLen = s.length();
int tLen = t.length();
HashMap<Character,Integer> hs = new HashMap(sLen);
HashMap<Character,Integer> ht = new HashMap(tLen);
for(int i=0;i<tLen;i++){
ht.put(t.charAt(i),ht.getOrDefault(t.charAt(i),0)+1);
}
int left = 0 ,right = 0;
int ok = 0;
int start=0,len = Integer.MAX_VALUE;
while(right<sLen){
char c = s.charAt(right);
right++;
if(ht.containsKey(c)){
hs.put(c,hs.getOrDefault(c,0)+1);
if(hs.get(c)==ht.get(c)){
ok++;
}
}
while(ok == ht.size()){
if(right - left <len){
start = left;
len = right - left;
}
char d = s.charAt(left);
left++;
if(ht.containsKey(d)){
if(hs.get(d)==ht.get(d)){
ok--;
}
hs.put(d,hs.get(d)-1);
}
}
}
return (len == Integer.MAX_VALUE) ? "" : s.substring(start,start+len);
}
}
@Zhaobudaoyuema 写给楼上的同学，我用java跟你遇到了一样的问题，检查半天之后发现是Integer的问题，你代码中的hs.get(c)==ht.get(c)和hs.get(d)==ht.get(d)应该用equals。原因是Integer的包装类会自动缓存-128～127，只有在这个间隔内才可以用==比较。 你可以尝试以下代码 Integer i1 = 127; Integer i2 = 127; i1 == i2; 结果为true Integer i1 = 128; Integer i2 = 128; i1 == i2; 结果为false
@c137Ming 说得对，@Zhaobudaoyuema @HuaHero Java 的包装类都应该用 equals 方法判断相等，== 可能造成很奇怪的结果。感谢你们的指出，我在文章中补充说明下这一点，似乎很多读者都遇到了这个问题。
