程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> [面試]字符串專題

[面試]字符串專題

編輯:關於C

一,字符串轉化
        將字符串轉換成整數:atoi
        將整數轉換為字符串:itoa
         浮點數與字符串的轉換
1)字符串轉化為整數
        需要注意的地方:
                                       考慮要缜密,注意是否為數字字符;
                                       判斷是否為NULL
                                       開頭的‘+’‘-’符號的判斷
[html] 
#include "stdio.h" 
#include "string.h" 
#include "assert.h" 
 
int isDigit(char c) 

    if(c>='0'&&c<='9') 
        return 1; 
    else 
        return 0;  
     
}  
int myatoi(const char *str) 

    assert(str!=NULL); 
    int count=strlen(str); 
    int result=0; 
     
    int sign=1; 
    if(str[0]=='-') 
    { 
        sign=-1;  
    }  
    else if(str[0]=='+') 
    { 
        sign=1;  
    }  
    else if(isDigit(str[0]))  
    { 
        result=str[0]-'0'; 
        sign=1;  
    }  
    for(int i=1;i<count;++i) 
    { 
        assert(isDigit(str[i])); 
         
        result=result*10+(str[i]-'0'); 
    } 
     
    return result; 
     
     

int  main() 

    printf("%d\n",myatoi("123")); 

 
別看一個這麼簡單的問題,實際要考慮的問題很多。還是看一下glibc的實現吧
[html]
#include "stdio.h" 
#include "string.h" 
#include "assert.h" 
 
#define LONG_MAX 2147483647L  
#define LONG_MIN (-2147483647L-1L) 
 
 
long int _strtol_internal (const char *nptr, char **endptr, int base, int group) 

    //注意要使用unsigned long否則會發生溢出,因為long int最多2147483647L ,無法表示2147483648L 
    unsigned long int result = 0; 
    long int sign = 1; 
    //考慮前導空格 
    while (*nptr == ' ' || *nptr == '\t') 
        ++nptr; 
    //考慮帶有正負號 
    if (*nptr == '-') 
    { 
        sign = -1; 
        ++nptr; 
    } 
    else if (*nptr == '+') 
        ++nptr; 
        //如果出現非法輸入 
    if (*nptr < '0' || *nptr > '9') 
    { 
        if (endptr != NULL) 
            *endptr = (char *) nptr; 
        return 0L; 
    } 
    //考慮進制 
    assert (base == 0); 
    base = 10; 
    if (*nptr == '0') 
    { 
        if (nptr[1] == 'x' || nptr[1] == 'X') 
        { 
            base = 16; 
            nptr += 2; 
        } 
        else 
            base = 8; 
    } 
    //防止非法字符  
    while (*nptr >= '0' && *nptr <= '9') 
    { 
        unsigned long int digval = *nptr - '0'; 
 
        //防止溢出,如果溢出了long的表示范圍,則置errno  
        if (result > LONG_MAX / 10 || (sign > 0 ? result == LONG_MAX / 10 && digval > LONG_MAX % 10 :  
                  (result == ((unsigned long int) LONG_MAX + 1) / 10 && digval > ((unsigned long int) LONG_MAX + 1) % 10))) 
        { 
            errno = ERANGE; 
            return sign > 0 ? LONG_MAX : LONG_MIN; 
        } 
        result *= base; 
        result += digval; 
        ++nptr; 
    } 
    return (long int) result * sign; 

 
         atoi函數就是這個函數講第二個參數置為NULL,第三個參數置為10。不知道你注意到了那些空格,越界之類的判斷沒有。我同學說他寫出來的代碼最後就被要求加上了這些東西,最後還因此被卡掉了(說是考慮不夠慎密,汗)。
2)itoa 函數的實現
      char *itoa( int value, char *string,int radix);
      先看一看使用:
[html] 
#include <stdlib.h> 
#include <stdio.h> 
int main(void) 

    int number = 12345; 
    char string[25]; 
    itoa(number, string, 10); //按十進制轉換 
    printf("integer = %d string = %s\n", number, string); 
    itoa(number, string, 16); //按16進制轉換 
    printf("integer = %d string = %s\n", number, string); 
    return 0; 
}  
 
整形轉化為字符串(這裡默認十進制的轉換)
[html] view plaincopy
//整形轉成字符串函數實現 
//題目不難,重點考察面試者對問題考慮的全面程度 
#include <iostream> 
using namespace std; 
void itoa_mf(int num,char str[]) 

    int sign = num; 
    int i = 0; 
    int j = 0; 
    char temp[100]; 
    if(sign < 0)//如果是負數就去掉符號,將-1234轉成1234 
    { 
        num = -num; 
    } 
     
    do//轉成字符串,1234轉成"4321" 
    { 
        temp[i] = num % 10 + '0'; 
        num /= 10; 
        i++; 
    }while(num > 0); 
    if(sign < 0)//如果是負數的話,加個符號在末尾,如:"4321-" 
    { 
        temp[i++] = '-'; 
    } 
    temp[i] = '\0'; 
    i--; 
    //將temp數組中逆序輸入到str數組中 
    //將"4321-" ====> "-1234" 
    while(i >= 0) 
    { 
        str[j] = temp[i]; 
        j++; 
        i--; 
    } 
    //字符串結束標識 
    str[j] = '\0'; 

int main() 

    int a = +123; 
    char s[100]; 
    itoa_mf(a,s); 
    cout << s << endl; 
 

二,找出字符串的最長子串,要求子串的所有字符相同
         例如:str ="sssddddabcdef"  則輸出字串為:dddd
[html] 
#include <stdlib.h> 
#include <stdio.h> 
#include <string.h>  
char* GetSubstring(char* strSource) 

  char* strSubstring; //用於保存得到的子串,大小在找到最大子串後再確定,作為返回值 
  int nLen;           //源字符串長度 
  int nCurPos;        //當前統計字符串的頭指針位置(相對於原字符串第一個字符的位置) 
  int nCurCount;      //當前統計字符串的長度(有相同字符組成的子字符串) 
  int nPos;          //當前最長的子串的頭指針位置 
  int nCount;        //當前最長的子串的長度 
 
  nLen = strlen(strSource); 
 
  //初始化變量 
  nCount = 1; 
  nPos = 0; 
  nCurCount = 1; 
  nCurPos = 0; 
 
  //遍歷整個字符串 
  for(int i = 1; i < nLen; i++) 
  { 
    if(strSource[i] == strSource[nCurPos])//如果當前字符與子串的字符相同,子串長度增1 
      nCurCount++; 
    else  //如果不相同,開始統計新的子串 
    { 
      if(nCurCount > nCount)//如果當前子串比原先最長的子串長,把當前子串信息(起始位置 + 長度)保留下來 
      { 
        nCount = nCurCount; 
        nPos = nCurPos; 
      } 
      //長度復值為1,新串的開始位置為i 
      nCurCount = 1; 
      nCurPos = i; 
    } 
  } 
 
  //為返回的子串分配空間(長度為nCount,由於要包括字符串結束符\0,故大小要加1)   
  strSubstring = (char*)malloc(nCount + 1); 
 
  //復制子串(用其他函數也可以) 
  for(int i = 0; i < nCount; i++) 
    strSubstring[i] = strSource[nPos + i]; 
  strSubstring[nCount] = '\0'; 
 
  return strSubstring; 
}  
 
int main() 

  //輸入一個字符串strSource 
  char *strSource="absceeeecd";  
  char* strSubstring = GetSubstring(strSource); 
 
  printf("最長子串為:%s\n長度為:%d",strSubstring,strlen(strSubstring)); 
 
  //釋放strSubstring 
  free(strSubstring); 

 
三,求兩個字符串的最大公共子字符串
        算法時間復雜度:O(n^2)
        思想:兩個字符串先從第一個字串的第一個字符開始,依次與第二個字串的各個位置字串比較字串
                    需要記錄下最長公共子串在str1中的位置和子串長度
[html] 
#include<iostream> 
#include<cstring> 
#include<cassert> 
using namespace std; 
void findMaxSubstr(const char * str1 , const char * str2 , char * maxSubstr) 

    assert((str1!=NULL)&&(str2!=NULL)); 
    assert(maxSubstr!=NULL); 
    int maxPos=-1; 
    int maxLen=0; 
    int k;  
    for(int i=0; i<strlen(str1); i++) 
    { 
        for(int j=0; j<strlen(str2); j++) 
        { 
            if(str1[i]==str2[j]) 
            { 
                for(k=1; (str1[i+k]==str2[j+k])&&(str1[i+k]!='\0'); k++) 
                             ; 
                    if(k>maxLen) 
                    { 
                        maxPos=i; 
                        maxLen=k; 
                    } 
            } 
        } 
    } 
    if(maxPos==-1) 
    { 
        maxSubstr[0]='\0'; 
    } 
    else 
    { 
        memcpy(maxSubstr , str1+maxPos , maxLen); 
        maxSubstr[maxLen]='\0'; 
    } 

int main() 

    char substr[20]; 
    findMaxSubstr("tianshuai" , "mynameistianshuai" , substr); 
    cout<<substr<<endl; 
    return 0; 

 
四,字符串查找並記錄出現次數(普通與kmp)(觀察strstr實現),替代
          函數原型:extern char *strstr(char *str1, char *str2);
   功能:找出str2字符串在str1字符串中第一次出現的位置(不包括str2的串結束符)
          使用:printf("%s",strstr("tianshuai","shuai"));
                      輸出:shuai
             實現:
[html] 
#include "stdio.h" 
char *strstr(char *buf, char *sub) 

    register char *bp; 
    register char *sp; 
 
    if (!*sub) 
        return buf; 
    while (*buf) 
   { 
        bp = buf; 
        sp = sub; 
        do  
        { 
            if (!*sp) 
                return buf; 
        } while (*bp++ == *sp++); 
        buf += 1;//從下一個位置查找  
    } 
    return 0; 

int main() 

    printf("%s",strstr("tianshuai","tian"));  
     
}  
求子串的個數只需要略微更改一下就可以
[html]
#include "stdio.h" 
  
int  strstr(char *buf, char *sub) 

    register char *bp; 
    register char *sp; 
     
    int count=0; 
    int pos=0;  
      
    if (!*sub) 
        return 0; 
    while (*buf) 
   { 
        bp = buf; 
        sp = sub; 
        pos=0;  
        do  
        { 
            pos++;  
            if (!*sp) 
            { 
                count++;  
            }  
                //return buf; 
        } while (*bp++ == *sp++); 
         
        buf += pos;//從下一個位置查找  
    } 
    return count; 

int main() 

    printf("%d",strstr("tianshuai,tianshuai,tianshui","tian"));  
     
}  


五,解析一個字符串,對字符串中重復出現的字符,只在第一次出現時保留,就是去除重復的字符。
         如:abdabbefgf -> abdefg。
         根據字符集,建立一個flag數組用來表示是否出現過。
六,給出一個函數來輸出一個字符串的所有排列
        字典序生成算法問題:字典序
        采用next_permutation的算法思想,首先進行一個字符重排序找到按字典序最小的那個字符序列,以它為開端逐步生成所有排列。
七,翻轉字符串
         參考例子
八,從一個字符串中找出第一個不重復字符
         這個也比較簡單,類似於5的方法。
九,去除字符串中相鄰兩個字符的重復
         這個應該等價於題目5
十,判斷字符串是否含有回文字符子串
        枚舉字符串的每個位置,作為回文串的中間位置(分偶數奇數兩種情況),如果找到或者找不到都會立即停止,所以總的復雜度不超過O(n)
十一,求最長回文子串
         dp
                f[i][j] = f[i+1][j-1]
               s[i] == s[j]
         false s[i] != s[j]
        當然這裡有一個小小的限定,f[i][j]表示以i,j為首尾的回文串能否構成。然後再找到一個最長的就可以算法,復雜度O(n^2)。實際上這個問題只要枚舉回文串的中間位置就可以了,這樣實際上就跟10一樣了。不過10只需判斷是否存在,這需要找到最長的那個。
當然這個問題還有更快的算法:http://richardxx.yo2.cn/articles/kmp和extend-kmp算法.html
------------------------------------------------------引用開始------------------------------------------------------------------------
             KMP的另外一個研究方向是Extend KMP(以下簡稱EK),它是說求得T與所有的S(i)的最長公共前綴(LCP),當然,要控制復雜度在線性以內。
             EK我第一次聽說是07年baidu校園招聘的筆試題中,它當時的題目是求最長回文子串,當然這是一個耳熟能詳,路人皆知可以用Suffix Array很好解決的問題。事後聽一個同學說他寫了三個算法:Suffix Array,Suffix Tree和EK,當時就不明白EK是什麼東西,但又沒當面問他,於是這個東西就擱置了很久。知道後來北大的月賽一道題說可以用EK來做,我才終於從03年林希德的文章中開始認識到它,就像KMP一樣,這個算法也一下就吸引了我。
           設Q(i)表示T和S(i )的後綴的LCP,P(i)表示T和T(i)的後綴的LCP,那麼和KMP一樣,我們試圖用P來求得Q,而P可以用自匹配求得,並且和求Q的過程相似。
           我以求P為例簡要說明一下。P(2)就直接匹配即可,從i = 3開始,如下:
                      設k < i,E(k) = k + P(k) - 1,且對所有j < i,有E(k) >= E(j)。
                      那麼,當E(k) >= i時,便可以推知T(i) = T( i - k + 1 ),於是如果P( i - k + 1 ) < E(k) - i + 1,那麼P(i) = P( i - k + 1),否則P(i) >= P( i - k + 1 ),從E(k)開始向後匹配到E(i),有P(i) = E(i) - i + 1,並且更新 k = i;
                      還有就是E(k) < i,肯定有E(k) = i - 1,不過這個不重要,重要的是直接從i開始做暴力匹配即可得到E(i),則P(i) = E(i) - i + 1,更新k = i。
                      希望我把EK說清楚了,不過這種東西還是自己推導一下有意思,而且記憶周期更長。
           最後來羅列下題目。KMP的經典題目是POJ 2185,是要找最小覆蓋矩形,如果你認為懂KMP了就去嘗試它。EK的經典題是POJ 3376,有一定挑戰;當然還有就是上面說的最長回文子串,提醒下用分治+EK來做是其中一種方法。
嗯,下次打算說下Suffix Array,主要是它那個傳說中的線性DC3算法,不過我現在還沒把握能不能簡單的把它說清楚,姑且認為可以吧。
------------------------------------------------------引用結束------------------------------------------------------------------------
十二,字符串移位包含的問題
            題目:給定兩個字符串S1與S2,要求判定S2是否能夠被通過s1作循環移位得到的字符串包含,例如,給定s1=AABCD與S2=CDAA,返回true;給定s1=ABCD 與 s2=ACBD,返回false.
            直接枚舉匹配或者比較s2能否匹配s1s1,以第一個為例也就是說比較AABCDAABCD和CDAA。
十三,strlen strcpy(注意重疊)
[html] 
#include "stdio.h" 
#include "assert.h" 
  
char *<span>strcpy</span> (char *dest,const char *src) 

    assert(src!=NULL);  
    char *temp=dest; 
    while((*dest++=*src++)!='\0') 
            ; 
    return dest; 

 
int main() 

    char *dest; 
    char *src="tianshuai"; 
    <span>strcpy</span>(dest,src); 
    printf("%s",dest);  
}  

上面這個比較復雜,再看FreeBsd的實現
 
 char *strcpy(char * __restrict to, const char * __restrict from)
 {
        char *save = to;
        for (; (*to = *from) != 0; ++from, ++to);
        return(save);
 }
十四,去掉中文中的英文字符
            主要根據字節的第一位進行判斷。
十五,求一個字符串中連續出現次數最多的子串


作者:tianshuai11
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved