optimal

OptimalSolution（4）--字符串问题（1）简单

⼀、判断两个字符串是否互为变形词

问题：给定两个字符串str1和str2，如果str1和str2中出现的字符种类⼀样且每种字符出现的次数也⼀样，那么str1与str2互为变形词。

举例：str1=“123”，str2=“231”，返回true。str1=“123”，str2=“2331”，返回fal。

思路：如果str1和str2长度不同，直接返回fal。如果长度相同，假设出现字符的编码值在0~255之间，那么先申请⼀个长度为256的整

型数组map。map[a]=b代表字符串编码为a的字符出现了b次。初始始map都为0。然后遍历str1，统计每种字符出现的数量，⽐如遍历到字

符‘a’，则令map[97]++，这样map就成了str1中每种字符的词频统计表。然后遍历str2，没遍历⼀个字符都在map中把词频减去1，如果减少

之后的值⼩于0，直接返回fal。如果遍历完str2，map中也没出现负值，返回true。

publicbooleanisDeformation(Stringstr1,Stringstr2){

if(str1==null||str2==null||()!=()){

returnfal;

}

char[]chas1=Array();

char[]chas2=Array();

int[]map=newint[256];

for(inti=0;i<;i++)map[chas1[i]]++;

for(inti=0;i<;i++){

if(map[chas2[i]]--==0)returnfal;

}

returntrue;

}

判断两个字符串是否互为变形词

⼆、字符串中数字⼦串的求和

题⽬：给定⼀个字符串str，求其中全部数字串所代表的数字之和。其中：1.忽略⼩数点字符，例如“A1.3”，其中包含两个数字1和3。2.

如果紧贴数字⼦串的左侧出现字符‘-’，当连续出现的数量为奇数时，则数字视为负，连续出现的数量为偶数时，则数字视为正。例如“A-

1BC--12”，其中包含-1和12

解法：（1）⽣成三个变量，整型变量res表⽰⽬前的累加和；整型变量num表⽰当前收集到的数字；布尔型变量posi，表⽰如果把num

累加到res⾥，num是正还是负。初始时，res=0，num=0，posi=true。（2）如果遍历到的字符cha是‘0’~‘9’，则cha-‘0’的值记为cur，posi表

⽰cur的符号。例如：str=“123”，初始时num=0，posi=true。则num=0*10+1，num=1*10+2，num=12*10+3。假设str=“-123”，那么

posi=fal，此时num=0*10+(-1)，num=-1*10+(-2)，num=-12*10+(-3)，因此有num=num*10+(posi?cur:-cur)（3）如果遍历到的字符

cha不是‘0’~‘9’，说明前⼀阶段的数已经明确是num了，因此先令res+=num，然后令num=0。此时如果cha不是‘-’，令posi=true。如果cha

是‘-’，此时看cha的前⼀个字符，如果cha的前⼀个字符也是‘-’，则posi=！posi；否则令posi=fal。（4）还需要注意的是，由于res+=num

发⽣在⾮数字字符之前，如果字符串最后⼀位是数字字符，就使得最后⼀个num⽆法加到res上，因此最后还需要res+=num。

publicintnumSum(Stringstr){

if(str==null)return0;

char[]charArr=Array();

intres=0;

intnum=0;

booleanposi=true;

intcur=0;

for(inti=0;i<;i++){

cur=charArr[i]-'0';

if(cur<0||cur>9){

res+=num;

num=0;

if(charArr[i]=='-'){

if(charArr[i-1]=='-'){

posi=!posi;

}el{

posi=fal;

}

}el{

posi=true;

}

}el{

num=num*10+(posi?cur:-cur);

}

}

res+=num;

returnres;

}

字符串中数字⼦串的求和

三、去掉字符串中连续出现k个0的⼦串

题⽬：给定⼀个字符串str和⼀个整数k，如果str中正好有连续的k个‘0’字符出现时，把k个连续的‘0’字符去除，返回处理后的字符串。

解法：（1）⽣成两个变量。整型变量count表⽰⽬前连续个‘0’的数量；整型变量start表⽰连续出现连续个‘0’的开始位置。初始

时，count=0，start=-1（2）如果cha是字符‘0’，令start=start==-1？i：start，即如果start不等于-1，说明之前就已经处在连续的‘0’的阶

段，所以start不变，count++（3）如果cha不是‘0’，如果count等于k，说明之前发现的连续k个‘0’可以从start位置开始去掉，如果不等于，说

明之前发现的连续的‘0’的数量不是k个，因此不能去掉，最后令count=0，start=-1。（4）如果str是以‘0’结尾的，可能会出现最后⼀组k个连

续的‘0’没有去掉的情况，所以要检查⼀下count是否等于k。

注意：下⾯这段代码中，chas[start++]=0;表⽰的是，ASCII码表中0表⽰null，因此如果str“a0000b000c00”，k=4，则结果为“a

b000c00”

if(count==k){

while(count--!=0){

chas[start++]=0;

}

}

完整代码：

publicStringremoveKZeros(Stringstr,intk){

if(str==null||k<1)returnstr;

char[]chas=Array();

intcount=0,start=-1;

for(inti=0;i<;i++){

if(chas[i]=='0'){

count++;

start=start==-1?i:start;

}el{

if(count==k){

while(count--!=0){

chas[start++]=0;

}

}

count=0;

start=-1;

}

}

if(count==k){

while(count--!=0){

chas[start++]=0;

}

}

f(chas);

}

去掉字符串中连续出现k个0的⼦串

四、判断两个字符串是否互为旋转词

题⽬：如果⼀个字符串str，把字符串str前⾯任意的部分挪到后⾯形成的字符串叫做str的旋转词。例如str=“12345”，则str的旋转词

为“12345”，“23451”，“34512”，“45123”和“51234”

解法：如果a和b的长度不⼀样那么返回fal。如果a和b长度⼀样，先⽣成变量Stringb2=b+b，然后看b2中是否包含字符串a。例

如，a=“cdab”，b=“abcd”，那么b2=“abcdabcd”，则b2[0...3]、b2[1...4]、b2[2...5]、b2[3...6]、b2[4...7]都是b的旋转词。即如果⼀个字符串b的

长度为N，在通过b⽣成的b2中，任意长度为N的⼦串都是b的旋转词，⽽且b2中包含字符串b的所有旋转词。（可以通过KMP算法实现时间

复杂度为O(N)）

publicbooleanisRotation(Stringa,Stringb){

if(a==null||b==null||()!=()){

returnfal;

}

Stringb2=b+b;

ns(a);

}

判断两个字符串是否为旋转词

五、替换字符串中连续出现的指定字符串

问题：给定三个字符串str、from和to，把str中所有from的⼦串全部替换成to字符串，对连续出现from的部分要求只替换成⼀个to字符

串。

例如：str=“123abc”，from=“abc”，to=“4567”，返回“1234567”。str=“123abcabc”，from=“abc”，to=“X”，返回“123X”

思路：把str中from部分所有位置的字符编码设为0（即空字符），例如str=“12abcabca4”，from=“abc”，处理后str为

[‘1’,‘2’,0,0,0,0,0,0,‘a’,‘4’]，然后把不为0的区域拼在⼀起，连续为0的部分⽤to代替，即“12”+to+“a4”

解法：（1）⽣成整型变量match，表⽰⽬前匹配到from字符串的什么位置，初始时，match=0（2）如果str[i]==from[match]。如果

match是from的最后⼀个字符的位置，说明str中发现了from字符串，则从i位置向左的M个位置，都把字符编码设为0，M为from的长度，然后

令match=0，如果match不是from最后⼀个字符的位置，令match++，继续遍历str的下⼀个字符串（3）如果str[i]!=from[match]，说明匹配失

败，令match=0,（4）拼接字符串。

注意：对于连续的0的区域的处理⽅式

if(chas[i]==0&&(i==0||chas[i-1]!=0)){

res=res+cur+to;

cur="";

}

完整代码：

publicStringreplace(Stringstr,Stringfrom,Stringto){

if(str==null||from==null||("")||("")){

returnstr;

}

char[]chas=Array();

char[]chaf=Array();

intmatch=0;

for(inti=0;i<;i++){

if(chas[i]==chaf[match++]){

if(match==){

clear(chas,i,);

match=0;

}

}el{

match=0;

}

}

Stringres="";

Stringcur="";

for(inti=0;i<;i++){

if(chas[i]!=0){

cur=cur+f(chas[i]);

}

if(chas[i]==0&&(i==0||chas[i-1]!=0)){

res=res+cur+to;

cur="";

}

}

if(!(""))res=res+cur;

returnres;

}

publicvoidclear(char[]chas,intend,intlen){

while(len--!=0){

chas[end--]=0;

}

}

替换字符串中连续出现的指定字符串

六、字符串的统计字符串

题⽬1：给定⼀个字符串str，返回str的统计字符串，例如，“aaabbadddffc”的统计字符串为“a_3_b_2_a_1_d_3_f_2_c_1”

解法：（1）如果str为空，那么统计字符串不存在（2）如果str不为空，⽣成String类型的变量res表⽰统计字符串，整型变量num代表当

前字符的数量。初始时res只包含str[0]，同时num=1（3）从str[1]开始遍历，如果str[i]==str[i-1]，说明当前连续的字符str[i-1]还没结束，令

num++。（4）如果str[i]!=str[i-1]，说明到str[i-1]已经结束，令res=res+“_”+num+“_”+str[i]，然后令num=1（5）当遍历结束时，最后的字符还

没有放⼊res，所以令res=res+“_”+num

publicStringconcat(Strings1,Strings2,Strings3){

returns1+"_"+s2+(("")?s3:"_"+s3);

}

publicStringgetCountString(Stringstr){

if(str==null||("")){

return"";

}

char[]chs=Array();

Stringres=f(chs[0]);

intnum=1;

for(inti=1;i<;i++){

if(chs[i]!=chs[i-1]){

res=concat(res,f(num),f(chs[i]));

num=1;

}el{

num++;

}

}

returnconcat(res,f(num),"");

}

返回字符串的统计字符串

题⽬2：给定⼀个字符串的统计字符串cstr，再给定⼀个整数index，返回cstr所代表的原始字符串上的第index个字符。

解法：（1）⽣成布尔型变量stage，stage为true时表⽰要遇到字符，为fal表⽰要遇到字符统计。字符型变量cur表⽰在上⼀个遇到字

符阶段时，遇到的是cur字符。整型变量num，表⽰在上⼀个遇到连续字符统计的阶段，字符出现的数量。整型变量sum，表⽰⽬前遍历到

cstr的位置相当于原字符串什么位置。初始时，stage=true，cur=0（空字符），num=0，sum=0（2）以cstr=“a_100_b_2_c_4”,index=105

为例，遍历完str[0]='a'后cur=‘a’；遇到str[1]='_'，stage=!stage；表⽰接下来⼏个字符表⽰出现次数，依次为num=1，num=10，num=100；

然后是下划线，此时stage=!stage，表⽰要遇到的是字符；遇到str[6]='b'，即⼀个新的字符出现了，此时sum+=num，即sum=100，也就是

原字符串有100个a，由于100<105，因此继续遍历；...每次遇到⼀个新字符，都把上⼀个num加到sum上，如果sum已经到达index，那么就

返回上⼀个字符cur。

注意：num=num*10+chs[i]-'0';将字符串因此转换成整数

publicchargetCharAt(Stringcstr,intindex){

if(cstr==null||("")){

return0;

}

char[]chs=Array();

booleanstage=true;

intsum=0;

intnum=0;

charcur=0;

for(inti=0;i<;i++){

if(chs[i]=='_'){

stage=!stage;

}elif(stage){

sum+=num;

if(sum>index){

returncur;

}

num=0;

cur=chs[i];

}el{

num=num*10+chs[i]-'0';

}

}

returnsum+num>index?cur:0;

}

根据统计字符串及索引范返回原字符串中的字符

七、字符串的调整与替换

问题1：给定⼀个字符类型的数组chas，chas右半区全是空字符，左半区不含有空字符。将左半区左右的空格字符替换成“%20”，假设

chas右半区⾜够⼤，可以满⾜替换所需要的空间。例如“abc空字符”，替换后左半区为“a%20b%20%20c”

解法：（1）先遍历⼀次，可以得到两个信息，chas的左半区长度记为len，左半区空格记为num，即空格被“%20”替换后长度为

len+2*num。（2）从左半区的最后⼀个字符开始倒着遍历，同时将字符复制到新长度的最后的位置，并依次向左倒着复制。遇到空格就依

次把“0”、“2”和“%”进⾏复制。

注意：1.⼀个for⽅法可以同时得到len和num，这种技巧值得学习。2.从右往左倒着遍历。

publicvoidreplace(char[]chas){

if(chas==null||==0){

return;

}

intnum=0;

intlen=0;

for(len=0;len<&&chas[len]!=0;len++){

if(chas[len]==''){

num++;

}

}

intj=len+num*2-1;

for(inti=len-1;i>-1;i--){

if(chas[i]!=''){

chas[j--]=chas[i];

}el{

chas[j--]='0';

chas[j--]='2';

chas[j--]='%';

}

}

}

问题2：给定⼀个字符类型的数组chas，其中只含有数字字符和“*”字符，想将“*”字符挪到chas的左边，数字字符挪到chas的右边。例

如“12**345”，调整后为“**12345”。

解法：和问题1⼀样，依然是从右往左复制，遇到数字直接复制，遇到“*”不复制，当把数字字符复制完，把左半区全部设置成“*”即可。

注意：for(;j>-1;){chas[j--]='*';}这种表达。

publicvoidmodify(char[]chas){

if(chas==null||==0){

return;

}

intj=-1;

for(inti=-1;i>-1;i--){

if(chas[i]!='*'){

chas[j--]=chas[i];

}

}

for(;j>-1;){

chas[j--]='*';

}

}

⼋、反转字符串

问题1：给定字符类型数组chas，在单词键做依序调整。例如：“doglovespig”为“piglovesdog”。“I'mastudent.”为“'m”

解法：先把chas整体逆序，在把每个单词逆序。例如：“gipvolgod”→“piglovesdog”

注意：不能⽤String提供给你的rever⽅法，要⾃⼰实现才⾏。

publicvoidrever(char[]chas,intstart,intend){

chartmp=0;

while(start

tmp=chas[start];

chas[start]=chas[end];

chas[end]=tmp;

start++;

end--;

}

}

整体⽅法：注意for循环⾥⾯对于双指针l和r的使⽤技巧，这种⾼级表达要关注。

publicvoidrorateWord(char[]chas){

if(chas==null||==0){

return;

}

rever(chas,0,-1);

intl=-1;

intr=-1;

for(inti=0;i<;i++){

if(chas[i]!=''){

l=i==0||chas[i-1]==''?i:l;

r=i==-1||chas[i+1]==''?i:r;

}

if(l!=-1&&r!=-1){

rever(chas,l,r);

l=-1;

r=-1;

}

}

}

问题2：给定字符类型数组chas和整数size，把⼤⼩为size的左半区整体移到右半区。例如“ABCDE”且size=3，则“DEABC”

解法1：先把chas[0...size-1]部分逆序，再把chas[size...N-1]部分逆序，最后把chas整体逆序。

publicvoidrorate1(char[]chas,intsize){

if(chas==null||size<=0||size>=){

return;

}

rever(chas,0,size-1);

rever(chas,size,-1);

rever(chas,0,-1);

}

九、找到指定的新类型字符

问题：新类型字符是长度为1或者2的字符串。表现形式为：仅⼀个⼩写字母；⼤写+⼩写；⼤写+⼤写。给定字符串str，找出第k个的新

类型字符串。例如：str=“aaABCDEcBCg”，当k=7时，返回“Ec”。

思路：str=“aaABCDEcBCg”可以被拆成“a”，“a”，“AB”，“CD”，“Ec”，“BC”，“g”。k=7时，uNum=5；k=4时，uNum=2；k=10

时，uNum=2。

解法：（以⼩写字母为分隔符）从k-1位置开始，向左统计连续出现的⼤写字母的数量uNum，遇到⼩写字母就停⽌。如果uNum为奇

数，str[k-1...k]就是要找的；如果uNum为偶数且str[k]是⼤写字母，str[k...k+1]就是要找的；如果uNum为偶数且str[k]是⼩写字母，则str[k]是要

找的。

注意：if((uNum&1)==1)⽤来判断uNum是奇数还是偶数

publicStringpointNewChar(Strings,intk){

if(s==null||("")||k<0||k>=()){

return"";

}

char[]chas=Array();

intuNum=0;

for(inti=k-1;i>=0;i--){

if(!rCa(chas[i])){

break;

}

uNum++;

}

if((uNum&1)==1){

ing(k-1,k+1);

}

if(rCa(chas[k])){

ing(k,k+2);

}

f(chas[k]);

}