字符串相关笔试题

在进行相关编程之前必须进行一些条件判断
1、有效性判断，给定字符串是否为空，长度是否为1，长度为1表明可能不需要后续的操作了；
2、与整数有关，则需要考虑正负号问题，还必须考虑精度问题。
3、不要急于编写，先做全面的分析

---

字符串的操作

• 题1：实现strcpy，原型char * mystrcpy(char * src, char *dest)
• 分析：先判定是否是NULL指针，再进行相应的操作；返回是char*是为了链式操作；strcpy的目的存储空间一定要大于等于源的存储空间。

char * mystrcpy(char * src, char *dest)
{
     if(src==NULL || dest==NULL)
          return NULL;
     char * rs = dest;
     while((*dest++ ==  *src++)!='\0');
     return rs;
}

---

• 题2：将整数转化为字符串
• 分析：实际是写itoa函数，先判断正负，如果是负的先转为正的，可以先将每个数字提取出来（采用先对10求余，再除10的方法）再加'0'。

void myitoa(int num, char * str)
{
     char temp[20];
     bool sig = true;
     if(num<0)
     {
          *str++ = '-';
          sig = false;
     }
     int i = 0;
     while(num)
     {
          temp[i++]=(sig?num%10:-(num%10))+'0';
          num /= 10;
     }
     while(i--)
          *str++= temp[i];
     *str = '\0';
}

---

• 题3：字符串循环左右移问题
• 分析：若对使用空间没有限制，则利用strcpy即可，如对空间有要求可以考虑使用翻转。

//字符串左移step位
void myreverse(char * str,int p1, int p2)
{
    while(p1<p2)
    {
        *(str+p1) ^= *(str+p2);
        *(str+p2) ^= *(str+p1);
        *(str+p1) ^= *(str+p2);
        p1++;
        p2--;
    }
}
void strleftmove(char * str, int step)
{
    if(str == NULL)
        return;
    int n = strlen(str);
    myreverse(str,0,step-1);
    myreverse(str,step,n-1);
    myreverse(str,0,n-1);
}

---

• 题4：去除一个顺序排序的字符串中的重复字符
• 分析：由于是排序过的，只要比较相邻的两个是否相等，若不相等则把上一个输出即可。

//去除顺序的重复的字符串
void deleteduplicate(char * str)
{
    if(str == NULL)
        return;
    int num = strlen(str);
    cout<<str[0];
    for(int i = 1; i<num; i++)
        if(str[i]!=str[i-1])
            cout<<str[i];
    cout<<endl;
}

---

• 题5：寻找一个字符串中存在相同的最长子串
• 分析：寻找最长子串，因此可以从最长的子串开始查找，存在相同的子串可以采用，从左往右找和从右往左找，如果存在不同的话返回的序号应该不一致

//查找相同的且长度最长的子串
void maxSameSubstr(string str)
{
    int i,j;
    int num = str.length();
    string substr;
    for(i = num - 1; i>0; i--)      //从最大的子串开始
        for(j = 0; j <num -i;j++)
        {
            substr = str.substr(j,i);
            if (str.find(substr) != str.rfind(substr))
            {
                cout<<substr<<" "<<str.find(substr)<<endl;
                return;
            }
        }
}

---

• 题6：数字压缩，例如11111222223转换成515213
• 分析：只需要计算处前后有多少个相同的数即可

void zipNum1(char * str)
{
    if (str == NULL)
        return;
    int len = strlen(str);
    int sublen = 1;
    int i = 1;
    for(i = 1; i<len; i++)
    {
        if (str[i]!=str[i-1])
        {
            cout<<sublen<<str[i-1];
            sublen = 1;
        }           
        else
            sublen++;
    }
    cout<<sublen<<str[i-1];
}

---

• 题7：昨天看到了一篇文章里面的一个好题目一个经典编程面试题的“隐退”，题目内容如下：

给定一个输入的字符串和一个包含各种单词的字典，用空格将字符串分割成一系列字典中存在的单词。举个例子，如果输入字符串是“applepie”而字典中包含了所有的英文单词，那么我们应该得到返回值“apple pie”。
注意，我故意没有解释或者漏掉了一些细节，从而给候选人一个弄清楚问题的机会。 这里我举一些候选人可能会问的问题，以及我会如何回答
问：如果输入字符串本身是一个单词怎么办？
答：可以把它看作一个特殊情况。
问：我只用考虑分割成两个单词的情况吗？
答：不，但是可以从这种情况开始。
问：如果输入字符串无法被分割成单词怎么办？
答：返回null或者类似的东西。
问：有变位或者拼写错误怎么办？
答：只需要严格分割成字典中有的单词。
问：如果有多种分割可能性怎么办？
答：只需要返回任何一个正确的答案。
问：我在想将字典用前缀树，后缀树，Fibonacci堆实现…
答：你不用实现字典。只需要假设它已经被合理地实现了。
问：字典支持哪些操作？
答：字符串查询——这就是你所需要的全部
问：字典有多大？
答：假设它远远大于输入字符串，但足够装入内存。

• 根据提示写了一个较为通用的写法，采用递归实现，从深递归回溯到现在可以发现其复杂度为O(2^n)。至于动态规划的实现不是很了解，还有待学习动态规划

string segmentStr(string str,set<string> &disc)
{
    if (disc.find(str)!=disc.end())
        return str;
    for (int i = 1; i<str.length(); i++)
    {
        string substr = str.substr(0,i);
        if (disc.find(str)!=disc.end())
        {
            string reback = segmentStr(str.substr(i,str.length()-i),disc);
            if (!reback.empty())
                return substr+" "+reback;
        }
    }
    string s;
    return s;
}

---

reference

• 程序员面试宝典
• 一个经典编程面试题的“隐退”