f*********m
发帖数: 726 | 1 在前面一位牛妹的帖子里看到的。
Given a string, find longest substring which contains just two unique
characters.
谢谢。 |
r*******e
发帖数: 7583 | 2 两个指针一前一后，扫一遍就行了把
【在 f*********m 的大作中提到】
: 在前面一位牛妹的帖子里看到的。
: Given a string, find longest substring which contains just two unique
: characters.
: 谢谢。
|
p****e
发帖数: 3548 | 3 夹着就不行了吧
abaabc
【在 r*******e 的大作中提到】
: 两个指针一前一后，扫一遍就行了把
|
p****e
发帖数: 3548 | 4 #include
using namespace std;
string find2char(const string & s){
size_t size = s.size();
if(size <= 2) return s.substr(0, size);
vector index(256, -1);
int maxlen = 1, len, p1 = 0, p2 = 0, pm_begin = 0;
index[s[0]] = 0;
for(int i=1; i < size; ++i){
if(index[s[i]] >= 0){
index[s[i]] = i;
continue;
}
index[s[i]] = i;
p2 = i;
break;
}
if(p2 == 0) return s.substr(pm_begin, size);
maxlen = p2 - p1 + 1;
len = p2 - p1 + 1;
for(int i = p2 + 1; i < size; ++i){
if(index[s[i]]>=0){
index[s[i]] = i;
++len;
continue;
}
if(len > maxlen){
maxlen = len;
pm_begin = p1;
}
if(index[s[p1]] > index[s[p2]]){
int temp = index[s[p2]];
index[s[p2]] = -1;
p1 = temp + 1;
}
else{
int temp = index[s[p1]];
index[s[p1]] = -1;
p1 = temp + 1;
}
p2 = i;
index[s[i]] = i;
len = p2 - p1 + 1;
}
if(len > maxlen){
maxlen = len;
pm_begin = p1;
}
return s.substr(pm_begin, maxlen);
}
int main() {
// Start typing your code here...
string s ( "abaaabcccccaaaccccdd");
cout << find2char(s) << endl;
return 0;
} |
r*******e
发帖数: 7583 | 5 扫的时候用个hashmap计数，跟夹着不夹着没关系
【在 p****e 的大作中提到】
: 夹着就不行了吧
: abaabc
|
l*****s
发帖数: 774 | 6 这个hashmap计数太巧妙了，我自己估计想不到，到面试的时候紧张更想不到了。
试着写了一下：
class Solution
{
public:
std::string twoUnique(std::string & s)
{
if(s.size() <= 2) return s;
int max_start = 0;
int max_len = 2;
int i = 0;
int j = 0;
std::unordered_map m;
while(i<=j && j< s.size())
{
while(m.size() <= 2 && j
{
if(m.count(s[j]) == 0)
m[s[j]] = 1;
else
++m[s[j]];
if(m.size() <= 2 && (j-i+1) > max_len)
{
max_start = i;
max_len = j-i+1;
}
++j;
}
if(j==s.size()) return s.substr(max_start, max_len);
if(m[s[i]] == 1)
m.erase(s[i]);
else
--m[s[i]];
++i;
}
}
};
【在 r*******e 的大作中提到】
: 扫的时候用个hashmap计数，跟夹着不夹着没关系
|
d****n
发帖数: 233 | 7 I posted a solution (in C#) here:
http://codeanytime.blogspot.com/2013/05/longest-substring-which
【在 l*****s 的大作中提到】
: 这个hashmap计数太巧妙了，我自己估计想不到，到面试的时候紧张更想不到了。
: 试着写了一下：
: class Solution
: {
: public:
: std::string twoUnique(std::string & s)
: {
: if(s.size() <= 2) return s;
: int max_start = 0;
: int max_len = 2;
|
e*******i
发帖数: 56 | 8 No map is needed. Source is as following:
///////////////
#include
using namespace std;
int findLongest(char *s, char **start)
{
if(!s) return 0;
char first, second;
char *beginOfPreviousChar;
int currMax=0;
char *curr=s;
first=*s;
*start=s;
while(*curr)
{
if(*curr!=first) break;
currMax++;
curr++;
}
if( !*curr ) return currMax; //end of string
else
{
second=*curr;
beginOfPreviousChar=curr;
}
int max=0;
do
{
if( first==*curr || second==*curr )
currMax++;
else
{
if(currMax>max)
{
max=currMax;
*start=curr-max;
}
currMax=curr-beginOfPreviousChar+1;
}
if(second!=*curr)
{
first=second;
second=*curr;
beginOfPreviousChar=curr;
}
}while(*curr++);
return max;
}
int main()
{
char *start;
char s[]="aabaaabbbaabab";
int res= findLongest(s, &start);
cout<<"res is"<
while(res>0)
{
cout<<*start++;
res--;
}
cout<
} |
p****e
发帖数: 3548 | 9 赞这个，简洁高效
【在 e*******i 的大作中提到】
: No map is needed. Source is as following:
: ///////////////
: #include
: using namespace std;
: int findLongest(char *s, char **start)
: {
:
: if(!s) return 0;
: char first, second;
: char *beginOfPreviousChar;
|
d****n
发帖数: 233 | 10 Nice, marked.
【在 e*******i 的大作中提到】
: No map is needed. Source is as following:
: ///////////////
: #include
: using namespace std;
: int findLongest(char *s, char **start)
: {
:
: if(!s) return 0;
: char first, second;
: char *beginOfPreviousChar;
|
f*********m
发帖数: 726 | 11 看到大家的回复，我意识到可能是我把题意理解错了。我的理解是只有两个字符是不重
复的（unique），可以包括其他的重复字符。比如输入是 addabcccb，输出是ddabccc
， a和b是两个unique字符，c和d可以重复。
这样理解的话似乎更难了，还有线性解法吗？
（已在原贴进行了更新。）
谢谢。 |
d****n
发帖数: 233 | 12 You can do the following:
1. scan the whole string to build a hashmap with each character as the key
and frequent as value.
2. from both end of the string, recursively check if current substring
contains two unique chars.
if not, chop the beginning char, return if the remaining substring meet
requirement,else add back the beginning char, chop the end char and see if
the requirement meet.
it should be O(N).
ddabccc
【在 f*********m 的大作中提到】
: 看到大家的回复，我意识到可能是我把题意理解错了。我的理解是只有两个字符是不重
: 复的（unique），可以包括其他的重复字符。比如输入是 addabcccb，输出是ddabccc
: ， a和b是两个unique字符，c和d可以重复。
: 这样理解的话似乎更难了，还有线性解法吗？
: （已在原贴进行了更新。）
: 谢谢。
|
