1.3-1

设计算法并写出代码移除字符串中重复的字符，不能使用额外的缓存空间。注意： 可以使用额外的一个或两个变量，但不允许额外再开一个数组拷贝。

* 算法

o(n^2)

* 代码

#include <iostream>
#include <string>
using namespace std;


string removeDuplicate2(string s)
{
int len = s.length();
if(len < 2) return s;
string str = "";
for(int i=0; i<len; ++i)
{
if(s[i] != '\0')
{
str += s[i];
for(int j=i+1; j<len; ++j)
if(s[j]==s[i])
s[j] = '\0';
}
}
return str;
}


string removeDuplicate1(string s){
}

int main() {
string s1 = "abcde";
string s2 = "aaabbb";
string s3 = "";
string s4 = "abababc";
string s5 = "ccccc";

cout << removeDuplicate2(s5) << " " << endl;
}

1.3-1

给定两个字符串，编程，确定其中一个字符串的字符重新排序后，是否能变成另一个字符

* 算法1

• 区分大小写，空白符
• 排序，然后比较字符串

o(nlgn)

* 代码

#include <iostream>
#include<string>
using namespace std;


bool isAnagram1(string s,string t){
if(s=="" || t=="") return false;
if(s.length()!=t.length()) return false;

sort(s.begin(),s.end());
sort(t.begin(),t.end());

if(s==t) return true;
else return false;
}

int main(){
string s="abcdefg";
string t="bacdefg";

cout<<isAnagram1(s,t)<<endl;

return 0;
}

* 算法2

• 由于组成变位词的字符是一模一样的， 因此我们可以先统计每个字符串中各个字符出现的次数， 然后看这两个字符串中各字符出现次数是否一样。如果是，则它们是一对变位词。 这需要开一个辅助数组来保存各字符的出现次数。我们可以开一个大小是256的整数数组， 遍历第一个字符串时，将相应字符出现的次数加1；遍历第二个字符串时， 将相应字符出现的次数减1。最后如果数组中256个数都为0，说明两个字符串是一对变位词。 (第1个字符串中出现的字符都被第2个字符串出现的字符抵消了)， 如果数组中有一个不为0，说明它们不是一对变位词。

o(n)

* 代码

#include <iostream>
#include<string>
using namespace std;


bool isAnagram2(string s,string t){
if(s=="" || t=="") return false;
if(s.length() != t.length()) return false;

int len = s.length();
int c[256];
memset(c, 0, sizeof(c));

for(int i=0; i<len; ++i){
++c[(int)s[i]];
--c[(int)t[i]];
}

for(int i=0; i<256; ++i)
if(c[i] != 0)
return false;
return true;

}

int main(){
string s="abcdefg";
string t="bacdefg";

cout<<isAnagram2(s,t)<<endl;

return 0;
}