求G加一题的线性解法 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

求G加一题的线性解法

求G加一题的线性解法# JobHunting - 待字闺中

f*m2013-05-29 07:05

1 楼

在前面一位牛妹的帖子里看到的。
Given a string, find longest substring which contains just two unique
characters.
谢谢。

r*e2013-05-29 07:05

2 楼

两个指针一前一后，扫一遍就行了把

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

: 在前面一位牛妹的帖子里看到的。
: Given a string, find longest substring which contains just two unique
: characters.
: 谢谢。

p*e2013-05-29 07:05

3 楼

夹着就不行了吧
abaabc

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

: 两个指针一前一后，扫一遍就行了把

p*e2013-05-29 07:05

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*e2013-05-29 07:05

5 楼

扫的时候用个hashmap计数，跟夹着不夹着没关系

【在 p****e 的大作中提到】

: 夹着就不行了吧
: abaabc

l*s2013-05-29 07:05

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*n2013-05-29 07:05

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*i2013-05-29 07:05

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<while(res>0)
{
cout<res--;
}
cout<}

p*e2013-05-29 07:05

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*n2013-05-29 07:05

10 楼

Nice, marked.

【在 e*******i 的大作中提到】

f*m2013-05-29 07:05

11 楼

看到大家的回复，我意识到可能是我把题意理解错了。我的理解是只有两个字符是不重
复的（unique），可以包括其他的重复字符。比如输入是 addabcccb，输出是ddabccc
， a和b是两个unique字符，c和d可以重复。
这样理解的话似乎更难了，还有线性解法吗？
（已在原贴进行了更新。）
谢谢。

d*n2013-05-29 07:05

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可以重复。
: 这样理解的话似乎更难了，还有线性解法吗？
: （已在原贴进行了更新。）
: 谢谢。