x********g
发帖数: 3 | 1 这道题真的easy吗？
438. Find All Anagrams in a String |
d*******n
发帖数: 43 | 2 很久没刷题了，当年也没做到这个题。
用2分钟时间想了想，能想到的思路是找出所有子串，然后扔到hashmap里面同时计数，
扔的时候不考虑字母顺序，复杂度N^3，电面都过不了的水平。
唉，还是得刷题啊。 |
f*********r
发帖数: 7485 | 3 這個很容易
先算目標字符串長度為n
然後從長字符串掃描。每過一個字符，計算前面n個字符的集合，和目標字符串字符集
合比較
所謂字符集合是說，裏面有什麽字符，每個字符出現了多少次。比如p=="hello"，就是
e-1, h-1, l-2, o-1（把序排好）
字符衹有32種，沒掃一個字符，多出當前字符，減少一個字符（就是前面數第n個沒了
）。所以沒處理一個字符的時間度是一定的
這個字符集合的空間也是一定的
所以空間度是常數，時間是綫性
我一看就想出來了
【在 x********g 的大作中提到】
: 这道题真的easy吗？
: 438. Find All Anagrams in a String
|
n*******4
发帖数: 20 | 4 class Solution {
public:
vector findAnagrams(string s, string p) {
int m = s.length();
int n = p.length();
vector res;
if (m
return res;
if (m==0 ||n==0)
return res;
unordered_map countMap;
unordered_set usedChars;
for (auto ch:p){
countMap[ch]++;
usedChars.insert(ch);
}
int left=0;
int right;
int count=0;
for (right=0;right
if (!usedChars.count(s[right])){
continue;
}
countMap[s[right]]--;
if (countMap[s[right]]>=0)
count++;
while (count==n) {
if (right-left+1==p.length()) {
res.push_back(left);
}
if (usedChars.count(s[left])){
countMap[s[left]]++;
if (countMap[s[left]]>0)
count--;
}
left++;
}
}
return res;
}
};
【在 d*******n 的大作中提到】
: 很久没刷题了，当年也没做到这个题。
: 用2分钟时间想了想，能想到的思路是找出所有子串，然后扔到hashmap里面同时计数，
: 扔的时候不考虑字母顺序，复杂度N^3，电面都过不了的水平。
: 唉，还是得刷题啊。
|
x********g
发帖数: 3 | 5 就是这道吧 76. Minimum Window Substring
76可是hard啊
【在 f*********r 的大作中提到】
: 這個很容易
: 先算目標字符串長度為n
: 然後從長字符串掃描。每過一個字符，計算前面n個字符的集合，和目標字符串字符集
: 合比較
: 所謂字符集合是說，裏面有什麽字符，每個字符出現了多少次。比如p=="hello"，就是
: e-1, h-1, l-2, o-1（把序排好）
: 字符衹有32種，沒掃一個字符，多出當前字符，減少一個字符（就是前面數第n個沒了
: ）。所以沒處理一個字符的時間度是一定的
: 這個字符集合的空間也是一定的
: 所以空間度是常數，時間是綫性
|
s**x
发帖数: 7506 | 6 不错， 第一次看到只用一个 map 做的， 开始以为错了。 这个一个 map 理解起来很
别扭。
【在 n*******4 的大作中提到】
: class Solution {
: public:
: vector findAnagrams(string s, string p) {
: int m = s.length();
: int n = p.length();
: vector res;
:
: if (m: return res;
: if (m==0 ||n==0)
|
o*q
发帖数: 630 | 7 这题是简单的sliding window, 窗口是fixed size。
不是一堆这种差不多的题吗？ |
o*q
发帖数: 630 | 8 号称要刷1000题的，你们该总结下题型，每种刷几道就行了，不用那么多。 |
u********s
发帖数: 1047 | 9 这个还真是easy，毕竟我第一次就做出来了。。。就是简单的window，我是用array计数 |
T**********a
发帖数: 324 | 10 76我想了一分钟才想出解法。难度确实要大一些
【在 x********g 的大作中提到】
: 就是这道吧 76. Minimum Window Substring
: 76可是hard啊
|
