确定字符互异
题目描述
请实现一个算法，确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。
给定一个string iniString，请返回一个bool值,True代表所有字符全都不同，False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。
测试样例：
"aeiou"
返回：True
"BarackObama"
返回：False
#include <stdio.h>
#include <stdbool.h>
bool checkdiff(char *iniString)
{
int a[256]={0};
for(int i=0;iniString[i]!='\0';i++)
{
if(a[iniString[i]] != 0)
return false;
else
a[iniString[i]]=1;
}
return true;
}
int main(int argc, const char * argv[])
{
char str[]="abcde";
printf("%d",checkdiff(str));
return 0;
}
反转字符串
请实现一个算法，在不使用额外数据结构和储存空间的情况下，翻转一个给定的字符串(可以使用单个过程变量)。
给定一个string iniString，请返回一个string，为翻转后的字符串。保证字符串的长度小于等于5000。
测试样例：
"This is nowcoder"
返回："redocwon si sihT"
Java实现
class Reverse {
public:
string reverseString(string iniString) {
int n=iniString.size();
for(int i=0;i<n/2;i++)
{
char temp=iniString[n-i-1];
iniString[n-i-1]=iniString[i];
iniString[i]=temp;
}
return iniString;
}
};
本书中的大部分题目都可以在牛客网在线验证提交，代码部分由于采用java验证，因此略有不同，比如java中可以通过iniString.size()获取元素个数.
C实现时由于函数接口为void reverse(char *str),所以实现方式不同：
#include <stdio.h>
void reverse(char *str)
{
/*str为空，返回，规避解引用空指针*/
if(str == NULL)
return;
char *end = str;
char temp;
while(*end!='\0')
{
end++;
}
/*此时end指向\0,需要指向前一个反转的字符*/
end--;
while(str < end)
{
temp = *str;
*str++ = *end;
*end-- = temp;
}
}
int main(int argc, const char * argv[])
{
char str[]="abcde";
reverse(str);
printf("%s\n",str);
/*程序中不判空，会出现coredump*/
reverse(NULL);
return 0;
}
确定字符串乱序同构
题目描述
给定两个字符串，请编写程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。这里规定大小写为不同字符，且考虑字符串重点空格。
给定一个string stringA和一个string stringB，请返回一个bool，代表两串是否重新排列后可相同。保证两串的长度都小于等于5000。
测试样例：
"This is nowcoder","is This nowcoder"
返回：true
"Here you are","Are you here"
#include <stdio.h>
#include <stdbool.h>
bool checksame(char *src,char *dst)
{
if((NULL == src) ||(NULL == dst) )
return false;
int a[256]={0};
int b[256]={0};
/*生成相应的字符个数，只考虑ASCII码*/
while(*src!='\0')
{
a[*src++] += 1;
}
while(*dst!='\0')
{
b[*dst++] += 1;
}
/*判断两个数组是否相同*/
for(int i=0;i<256;i++)
{
if(a[i]!=b[i])
return false;
}
return true;
}
int main(int argc, const char * argv[])
{
char src[]="www.52coder.net";
char dst[]="52coder.www.net";
printf("%d\n",checksame(src,dst));
char left[]="www.52coder.nett";
char right[]="52coder.www.net";
printf("%d\n",checksame(left,right));
return 0;
}
空格替换
题目描述
请编写一个方法，将字符串中的空格全部替换为“%20”。假定该字符串有足够的空间存放新增的字符，并且知道字符串的真实长度(小于等于1000)，同时保证字符串由大小写的英文字母组成。
给定一个string iniString 为原始的串，以及串的长度 int len, 返回替换后的string。
测试样例：
"Mr John Smith”,13
返回："Mr%20John%20Smith"
”Hello World”,12
返回：”Hello%20%20World”
实现：参考文章替换空格
基本字符串压缩
利用字符重复出现的次数，编写一个方法，实现基本的字符串压缩功能。比如，字符串“aabcccccaaa”经压缩会变成“a2b1c5a3”。若压缩后的字符串没有变短，则返回原先的字符串。
给定一个string iniString为待压缩的串(长度小于等于10000)，保证串内字符均由大小写英文字母组成，返回一个string，为所求的压缩后或未变化的串。
测试样例
"aabcccccaaa"
返回："a2b1c5a3"
abcde"
返回: "abcde"
class Zipper {
public:
string zipString(string iniString)
{
// write code here
if (iniString.size() == 0|| iniString.size() == 1)
return iniString;
/*保存结果*/
string res;
char c = iniString[0];
int num = 0;
int len = iniString.size();
for (int i = 0; i < len; i++)
{
/*未到达字符串末尾，继续判断下一个字符师是否与c相同*/
if (i < len - 1 && iniString[i] == c)
num++;
/*未到达字符串末尾，且当前字符与c不同，拼接字符串，c赋值为当前字符，开始下一个字符的计数*/
else if (i < len - 1 && iniString[i] != c)
{
res += c;
res += to_string(num);
num = 1;
c = iniString[i];
}
/*到达字符串末尾，结束.*/
else if (i == len - 1 && iniString[i] == c)
{
num++;
res += c;
res += to_string(num);
}
else
{
res += c;
res += to_string(num);
res += iniString[i];
res += '1';
}
}
/*如果是abcde这种形式，返回原字符串*/
if (res.size() < iniString.size())
return res;
else
return iniString;
}
};
C实现
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
char* itoa(int value, char* result, int base) {
// check that the base if valid
if (base < 2 || base > 36) { *result = '\0'; return result; }
char* ptr = result, *ptr1 = result, tmp_char;
int tmp_value;
do {
tmp_value = value;
value /= base;
*ptr++ = "zyxwvutsrqponmlkjihgfedcba9876543210123456789abcdefghijklmnopqrstuvwxyz" [35 + (tmp_value - value * base)];
} while ( value );
// Apply negative sign
if (tmp_value < 0) *ptr++ = '-';
*ptr-- = '\0';
while(ptr1 < ptr)
{
tmp_char = *ptr;
*ptr--= *ptr1;
*ptr1++ = tmp_char;
}
return result;
}
void compressstring(char *str)
{
int len = 0;
int count = 0;
int i = 0;
int j = 0;
/*保存需计数的字符*/
char c;
/*结果数组初始化*/
char result[10000]={'\0'};
/*字符个数数组初始化*/
char countstr[32]={'\0'};
/*计算字符串长度*/
while(str[i++]!='\0')
{
len += 1;
}
/*长度为0或1返回*/
if( 0 == len || 1 == len)
return;
/*c赋值*/
c = str[0];
/*遍历字符串*/
for(i = 0,j=0;i < len;i++)
{
/*未到文件尾,且当前字符等于c，count++*/
if((i<len-1)&&(c == str[i]))
{
count += 1;
}
/*未到文件尾，且当前字符不等于c，结束本次计数*/
else if((i < len-1)&&(c != str[i]))
{
result[j++] = c;
/*将count转换成字符串，赋值给result数组*/
itoa(count,countstr,10);
/*将countstr的内容复制到result种*/
int begin = 0;
while(countstr[begin]!='\0')
{
result[j++] = countstr[begin++];
}
/*开始下一轮查找*/
c = str[i];
count = 1;
/*清空数组countstr，此处不清空也没关系，因为函数itoa中已经对最后一个元素后下一个值设置为'\0',而我们上面的while循环中判断是否等于'\0'*/
memset(countstr, 0x0,32);
}
/*到达文件尾，且当前字符等于c*/
else if((i == len-1)&&(c == str[i]))
{
result[j++] = c;
count++;
/*将count转换成字符串，赋值给result数组*/
itoa(count,countstr,10);
/*将countstr的内容复制到result种*/
int begin = 0;
while(countstr[begin]!='\0')
{
result[j++] = countstr[begin++];
}
/*清空数组countstr，此处不清空也没关系，因为函数itoa中已经对最后一个元素后下一个值设置为'\0',而我们上面的while循环中判断是否等于'\0'*/
memset(countstr, 0x0,32);
}
/*最后一个字符与众不同，处理aaabbbbbc形式*/
else
{
result[j++] = c;
/*将count转换成字符串，赋值给result数组*/
itoa(count,countstr,10);
/*将countstr的内容复制到result种*/
int begin = 0;
while(countstr[begin]!='\0')
{
result[j++] = countstr[begin++];
}
result[j++] = str[i];
result[j++] = '1';
result[j]='\0';
/*清空数组countstr，此处不清空也没关系，因为函数itoa中已经对最后一个元素后下一个值设置为'\0',而我们上面的while循环中判断是否等于'\0'*/
memset(countstr, 0x0,32);
}
}
/*打印出来结果字符串长度与原字符串长度*/
printf("%d %d\n",j,len);
/*比较len与j的大小确定需要的结果*/
if (j < len) {
memcpy(str, result, j+1);
printf("%s\n",str);
} else
{
printf("%s\n",str);
}
}
int main(int argc, const char * argv[])
{
char str[]="jjjjjjxxxxxxxooZLLLLLLLLQQQQQQQQQLLLLLLLLECXXXXXXXIIIIIIIIIhjjyyySSooooooooommmuuEEEEEEEEEnnnnnnnffffffAAAAAllllllllbbbbkkkkkkkkkkkkKKKKKKhhhhhhhhhooooooooooYCCCCCCOOOOOOOOOMMMMMMMMMMiiiiiivvvvvvvWWWWkkkkkkwwwwwwwMmmmmmmmmLLLwwwwwwwkkkjjjjjjttttQQQQQQQQQaaaaaaaFFFFFFFlllllllllggggggggggPPPPPPuuuuuuuuaYYYYYYwQQQFFFFFFFFFFaaaaapXXXXXXXxxxxxxQQQQQQQQQsssssGGGGfffffffddddddpppQQQQQQHHHTTTaaaaaaGGGGGGddyyyyyMhhllllllllllNNNNNNNNUUUWWWWWWLLLLLLLLLYYYYYYYYYYTTKKKKKKKKiiiiiiitttttttXXXXXXXXXLLLHZZZZZZZssssjjJJJEEEEEOOOOOttttttttttBBttttttTTTTTTTTTTrrrrttttRRRRRyyooooooaaaaaaaaarrrrrrrPPPPPPPjjPPPPddddddddddHHHHnnnnnnnnnnSSSSSSSSSSzzHHHHHHHHHddddddDDDzzzhhhhhfffffffffftttttteeeeeeeeEEEEEEEEEaaaaaaccccccccccFFFFFFFF";
compressstring(str);
printf("\n");
char str1[]="jjjjjjFFFFFFFF";
compressstring(str1);
printf("\n");
char str2[]="dddsadfjjjjjjFFFFFFFFd";
compressstring(str2);
printf("\n");
char str3[]="abcde";
compressstring(str3);
printf("\n");
char str4[]="ab";
compressstring(str4);
printf("\n");
char str5[]="aaaab";
compressstring(str5);
return 0;
}
itoa函数来源于google搜索到的一个博客,C中缺少相应字符串操作，因此实现比较麻烦。
itoa函数的实现不可谓不妙，需要仔细琢磨实现方式。