⼏种字符串处理的题
1.对于两个字符串A和B，如果A和B中出现的字符种类相同且每种字符出现的次数相同，则A和B互为变形词，请设计⼀个⾼效算法，检查两给定串是否互为变形词。
给定两个字符串A和B及他们的长度，请返回⼀个bool值，代表他们是否互为变形词。
测试样例：
"abc",3,"bca",3
返回：true
/*利⽤数组模拟hash表，将每⼀个字符对应的ascii码作为数组的下标
　每当对应字符出现就让初始化为0的数组赋值为1，这样另外⼀个字符串
　只需要在这个数组⾥⾯查，如果对应的每个字符对应的数组元素都为1，则
　说明两个字符串互为变形词，反之不是*/
class Transform {
public:
bool chkTransform(string A, int lena, string B, int lenb) {
// write code here
if(lena!=lenb)//长度不等直接返回false
return false;
const char *pA=A.c_str();//将string转化为const char*
const char *pB=B.c_str();
int arr[256]={0};
while(*pA){
arr[*pA]=1;
pA++;
}
while(*pB){
if(arr[*pB]!=1)
return false;
pB++;
}
return true;
}
};
2.如果对于⼀个字符串A，将A的前⾯任意⼀部分挪到后边去形成的字符串称为A的旋转词。⽐如A="12345",A的旋转词有"12345","23451","34512","45123"和"51234"。对于两个字符串A和B，请判断A和B是否互为旋转词。
给定两个字符串A和B及他们的长度lena，lenb，请返回⼀个bool值，代表他们是否互为旋转词。
测试样例：
"cdab",4,"abcd",4
返回：true
class Rotation {
public:
bool chkRotation(string A, int lena, string B, int lenb) {
// write code here
if(lena!=lenb)
return false;
string C=A+A;
const char* pC=C.c_str();
const char* pB=B.c_str();
if(NULL==strstr(pC,pB))
return false;
else
return true;
}
};
3.对于⼀个字符串，请设计⼀个算法，将字符串的长度为len的前缀平移到字符串的最后。
  给定⼀个字符串A和它的长度，同时给定len，请返回平移后的字符串。
  测试样例：
  "ABCDE",5,3
  返回："DEABC"
class Translation {
public:
string stringTranslation(string A, int n, int len) {
// write code here
reverseString(A,0,len-1);
reverseString(A,len,n-1);
reverseString(A,0,n-1);
}
void reverseString(string& str,int low,int high){
int i=low;
int j=high;
while(i<j){
swap(str[i],str[j]);
i++;
j--;
}
}
};
  4.对于⼀个给定的字符串数组，请到⼀种拼接顺序，使所有⼩字符串拼接成的⼤字符串是所有可能的拼接中字典序最⼩的。
  给定⼀个字符串数组strs，同时给定它的⼤⼩，请返回拼接成的串。
  测试样例：
  ["abc","de"],2
  "abcde"
bool compare(string str1,string str2){
return str1+str2<str2+str1?true:false;
}
字符串处理函数 如果是a展示bclass Prior {
public:
string findSmallest(vector<string> strs, int n) {
// write code here
sort(strs.begin(),d(),compare);
string newStr;
for(int i=0;i<n;i++){
newStr+=strs[i];
}
return newStr;
}
};
5.请编写⼀个⽅法，将字符串中的空格全部替换为“%20”。假定该字符串有⾜够的空间存放新增的字符，并且知道字符串的真实长度(⼩于等于1000)，同时保证字符串由⼤⼩写的英⽂字母组成。
  　给定⼀个string iniString 为原始的串，以及串的长度 int len, 返回替换后的string。
  　测试样例：
      "Mr John Smith”,13
    返回："Mr%20John%20Smith"
      ”Hello  World”,12
    返回：”Hello%20%20World”
class Replacement {
public:
string replaceSpace(string iniString, int length) {
// write code here
int count=0,i=0;
while(iniString[i]){
if(iniString[i]==' ')
count++;
i++;
}
int newlen=2*count+length;
char* newStr=new char[newlen+1];
int k=newlen-1;
for(int j=length-1;j>=0;j--){
if(iniString[j]==' '){
newStr[k--]='0';
newStr[k--]='2';
newStr[k--]='%';
}
else{
newStr[k--]=iniString[j];
}
}
newStr[newlen]='\0';
return newStr;
}
};
6.　对于⼀个字符串，请设计⼀个算法，只在字符串的单词间做逆序调整，也就是说，字符串由⼀些由空格分隔的部分组成，你需要将这些部分逆序。
  给定⼀个原字符串A和他的长度，请返回逆序后的字符串。
    "dog loves pig",13
　返回："pig loves dog"
class Reverse {
public:
string reverseSentence(string A, int n) {
// write code here
reverseString(A,0,n-1);
int i=0,j=0;
for(i=0;i<n;i++){
if(A[i]==' '){
reverseString(A,j,i-1);
j=i+1;
}
}
reverseString(A,j,i-1);
return A;
}
void reverseString(string &str,int low,int high){
int i=low;
int j=high;
while(i<j){
swap(str[i],str[j]);
i++;
j--;
}
}
};
  7.对于两棵彼此独⽴的⼆叉树A和B，请编写⼀个⾼效算法，检查A中是否存在⼀棵⼦树与B树的拓扑结构完全相同。给定两棵⼆叉树的头结点A和B，请返回⼀个bool值，代表A中是否存在⼀棵同构于B的⼦树。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class IdenticalTree {
public:
bool chkIdentical(TreeNode* A, TreeNode* B) {
// write code here
string str1;
string str2;
treeToString(A,str1);
treeToString(B,str2);
return strstr(str1.c_str(),str2.c_str())==NULL?false:true;
}
void treeToString(TreeNode* t,string& str){
if(t==NULL){
str.push_back('#');
return;
}
str.push_back('0'+t->val);
treeToString(t->left,str);
treeToString(t->right,str);
}
};

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。