最近比较忙所有关于5D2 便宜买到的信息请咨询boson 等 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PhotoGear - 摄影器材

最近比较忙所有关于5D2 便宜买到的信息请咨询boson 等

最近比较忙所有关于5D2 便宜买到的信息请咨询boson 等# PhotoGear - 摄影器材

x*g2011-10-14 07:10

1 楼

这道题真的easy吗？
438. Find All Anagrams in a String

e*t2011-10-14 07:10

2 楼

谢谢！
不好意思

d*n2011-10-14 07:10

3 楼

很久没刷题了，当年也没做到这个题。
用2分钟时间想了想，能想到的思路是找出所有子串，然后扔到hashmap里面同时计数，
扔的时候不考虑字母顺序，复杂度N^3，电面都过不了的水平。
唉，还是得刷题啊。

f*r2011-10-14 07:10

4 楼

這個很容易
先算目標字符串長度為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*42011-10-14 07:10

5 楼

class Solution {
public:
vector findAnagrams(string s, string p) {
int m = s.length();
int n = p.length();
vector res;

if (mreturn 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;rightif (!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*g2011-10-14 07:10

6 楼

就是这道吧 76. Minimum Window Substring
76可是hard啊

【在 f*********r 的大作中提到】

: 這個很容易
: 先算目標字符串長度為n
: 然後從長字符串掃描。每過一個字符，計算前面n個字符的集合，和目標字符串字符集
: 合比較
: 所謂字符集合是說，裏面有什麽字符，每個字符出現了多少次。比如p=="hello"，就是
: e-1, h-1, l-2, o-1（把序排好）
: 字符衹有32種，沒掃一個字符，多出當前字符，減少一個字符（就是前面數第n個沒了
: ）。所以沒處理一個字符的時間度是一定的
: 這個字符集合的空間也是一定的
: 所以空間度是常數，時間是綫性

s*x2011-10-14 07:10

7 楼

不错，第一次看到只用一个 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)