## 本章字符串和鏈表的習題 **1、第一個只出現一次的字符** 在一個字符串中找到第一個只出現一次的字符。如輸入abaccdeff，則輸出b。 **2、對稱子字符串的最大長度** 輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度。比如輸入字符串“google”，由于該字符串里最長的對稱子字符串是“goog”，因此輸出4。 提示：可能很多人都寫過判斷一個字符串是不是對稱的函數，這個題目可以看成是該函數的加強版。 **3、編程判斷倆個鏈表是否相交** 給出倆個單向鏈表的頭指針，比如h1，h2，判斷這倆個鏈表是否相交。為了簡化問題，我們假設倆個鏈表均不帶環。 問題擴展： - 如果鏈表可能有環列? - 如果需要求出倆個鏈表相交的第一個節點列? **4、逆序輸出鏈表** 輸入一個鏈表的頭結點，從尾到頭反過來輸出每個結點的值。 **5、在O(1)時間內刪除單鏈表結點** 給定單鏈表的一個結點的指針，同時該結點不是尾結點，此外沒有指向其它任何結點的指針，請在O(1)時間內刪除該結點。 **6、找出鏈表的第一個公共結點** 兩個單向鏈表，找出它們的第一個公共結點。 **7、在字符串中刪除特定的字符** 輸入兩個字符串，從第一字符串中刪除第二個字符串中所有的字符。 例如，輸入”They are students.”和”aeiou”，則刪除之后的第一個字符串變成”Thy r stdnts.”。 **8、字符串的匹配** 在一篇英文文章中查找指定的人名，人名使用二十六個英文字母（可以是大寫或小寫）、空格以及兩個通配符組成（*、?），通配符“*”表示零個或多個任意字母，通配符“?”表示一個任意字母。如：“J* Smi??” 可以匹配“John Smith” . **9、字符個數的統計** char *str = "AbcABca"; 寫出一個函數，查找出每個字符的個數，區分大小寫，要求時間復雜度是n（提示用ASCII碼） **10、最小子串** 給一篇文章，里面是由一個個單詞組成，單詞中間空格隔開，再給一個字符串指針數組，比如 char *str[]={"hello","world","good"}; 求文章中包含這個字符串指針數組的最小子串。注意，只要包含即可，沒有順序要求。 提示：文章也可以理解為一個大的字符串數組，單詞之前只有空格，沒有標點符號。 **11、字符串的集合** 給定一個字符串的集合，格式如：{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}要求將其中交集不為空的集合合并，要求合并完成后的集合之間無交集，例如上例應輸出{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}。 提示：并查集。 **12、五筆編碼** 五筆的編碼范圍是a ~ y的25個字母，從1位到4位的編碼，如果我們把五筆的編碼按字典序排序，形成一個數組如下： a, aa, aaa, aaaa, aaab, aaac, … …, b, ba, baa, baaa, baab, baac … …, yyyw, yyyx, yyyy 其中a的Index為0，aa的Index為1，aaa的Index為2，以此類推。 - 編寫一個函數，輸入是任意一個編碼，比如baca，輸出這個編碼對應的Index； - 編寫一個函數，輸入是任意一個Index，比如12345，輸出這個Index對應的編碼。 **13、最長重復子串** 一個長度為10000的字符串，寫一個算法，找出最長的重復子串，如abczzacbca,結果是bc。 提示：此題是后綴樹/數組的典型應用，即是求后綴數組的height[]的最大值。 **14、字符串的壓縮** 一個字符串，壓縮其中的連續空格為1個后，對其中的每個字串逆序打印出來。比如"abc efg hij"打印為"cba gfe jih"。 **15、最大重復出現子串** 輸入一個字符串，如何求最大重復出現的字符串呢？比如輸入ttabcftrgabcd,輸出結果為abc, canffcancd,輸出結果為can。 給定一個字符串，求出其最長的重復子串。 分析：使用后綴數組，對一個字符串生成相應的后綴數組后，然后再排序，排完序依次檢測相鄰的兩個字符串的開頭公共部分。 這樣的時間復雜度為： - 生成后綴數組 O(N) - 排序 O(NlogN*N) 最后面的 N 是因為字符串比較也是 O(N) - 依次檢測相鄰的兩個字符串 O(N * N) 故最終總的時間復雜度是 O(N^2*logN) **16、字符串的刪除** 刪除模式串中出現的字符，如“welcome to asted”,模式串為“aeiou”那么得到的字符串為“wlcm t std"，要求性能最優。 **17、字符串的移動** 字符串為*號和26個字母的任意組合，把 *號都移動到最左側，把字母移到最右側并保持相對順序不變，要求時間和空間復雜度最小。 **18、字符串的包含** 輸入： L:“hello”“july” S:“hellomehellojuly” 輸出：S中包含的L一個單詞，要求這個單詞只出現一次，如果有多個出現一次的，輸出第一個這樣的單詞。 **19、倒數第n個元素** 鏈表倒數第n個元素。 提示：設置一前一后兩個指針，一個指針步長為1，另一個指針步長為n，當一個指針走到鏈表尾端時，另一指針指向的元素即為鏈表倒數第n個元素。 **20、回文字符串** 將一個很長的字符串，分割成一段一段的子字符串，子字符串都是回文字符串。有回文字符串就輸出最長的，沒有回文就輸出一個一個的字符。 例如： habbafgh 輸出h,abba,f,g,h。 提示：一般的人會想到用后綴數組來解決這個問題。 **21、最長連續字符** 用遞歸算法寫一個函數，求字符串最長連續字符的長度，比如aaaabbcc的長度為4，aabb的長度為2，ab的長度為1。 **22、字符串反轉** 實現字符串反轉函數。 **22、字符串壓縮** 通過鍵盤輸入一串小寫字母(a~z)組成的字符串。請編寫一個字符串壓縮程序，將字符串中連續出席的重復字母進行壓縮，并輸出壓縮后的字符串。 壓縮規則： - 僅壓縮連續重復出現的字符。比如字符串"abcbc"由于無連續重復字符，壓縮后的字符串還是"abcbc"。 - 壓縮字段的格式為"字符重復的次數+字符"。例如：字符串"xxxyyyyyyz"壓縮后就成為"3x6yz"。 要求實現函數： void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr); - 輸入pInputStr： 輸入字符串lInputLen： 輸入字符串長度 - 輸出 pOutputStr： 輸出字符串，空間已經開辟好，與輸入字符串等長； 注意：只需要完成該函數功能算法，中間不需要有任何IO的輸入輸出 示例 - 輸入：“cccddecc” 輸出：“3c2de2c” - 輸入：“adef” 輸出：“adef” - 輸入：“pppppppp” 輸出：“8p” **23、集合的差集** 已知集合A和B的元素分別用不含頭結點的單鏈表存儲，請求集合A與B的差集，并將結果保存在集合A的單鏈表中。例如，若集合A={5,10,20,15,25,30}，集合B={5,15,35,25}，完成計算后A={10,20,30}。 **24、最長公共子串** 給定字符串A和B，輸出A和B中的第一個最長公共子串，比如A=“wepiabc B=“pabcni”，則輸出“abc”。 **25、均分01** 給定一個字符串，長度不超過100，其中只包含字符0和1,并且字符0和1出現得次數都是偶數。你可以把字符串任意切分，把切分后得字符串任意分給兩個人，讓兩個人得到的0的總個數相等，得到的1的總個數也相等。 例如，輸入串是010111,我們可以把串切位01, 011,和1，把第1段和第3段放在一起分給一個人，第二段分給另外一個人，這樣每個人都得到了1個0和兩個1。我們要做的是讓切分的次數盡可能少。 考慮到最差情況，則是把字符串切分(n - 1)次形成n個長度為1的串。 **26、合法字符串** 用n個不同的字符（編號1 - n），組成一個字符串，有如下2點要求： - 1、對于編號為i 的字符，如果2 * i > n，則該字符可以作為最后一個字符，但如果該字符不是作為最后一個字符的話，則該字符后面可以接任意字符； - 2、對于編號為i的字符，如果2 * i <= n，則該字符不可以作為最后一個字符，且該字符后面所緊接著的下一個字符的編號一定要 >= 2 * i。 問有多少長度為M且符合條件的字符串。 例如：N = 2，M = 3。則abb, bab, bbb是符合條件的字符串，剩下的均為不符合條件的字符串。 假定n和m皆滿足：2<=n,m<=1000000000)。 **27、最短摘要生成** 你我在百度或谷歌搜索框中敲入本博客名稱的前4個字“結構之法”，便能在第一個選項看到本博客的鏈接，如下圖2所示：  在上面所示的圖2中，搜索結果“結構之法算法之道-博客頻道-CSDN.NET”下有一段說明性的文字：“程序員面試、算法研究、編程藝術、紅黑樹4大經典原創系列集錦與總結 作者：July--結構之法算法...”，我們把這段文字稱為那個搜索結果的摘要，亦即最短摘要。我們的問題是，請問，這個最短摘要是怎么生成的呢? **28、實現memcpy函數** 已知memcpy的函數為： ```void* memcpy(void* dest , const void* src , size_t count)```其中dest是目的指針，src是源指針。不調用c++/c的memcpy庫函數，請編寫memcpy。 分析：參考代碼如下： ```cpp void* memcpy(void *dst, const void *src, size_t count) { //安全檢查 assert( (dst != NULL) && (src != NULL) ); unsigned char *pdst = (unsigned char *)dst; const unsigned char *psrc = (const unsigned char *)src; //防止內存重復 assert(!(psrc<=pdst && pdst<psrc+count)); assert(!(pdst<=psrc && psrc<pdst+count)); while(count--) { *pdst = *psrc; pdst++; psrc++; } return dst; } ``` **29、實現memmove函數** 分析：memmove函數是<string.h>的標準函數，其作用是把從source開始的num個字符拷貝到destination。最簡單的方法是直接復制，但是由于它們可能存在內存的重疊區，因此可能覆蓋了原有數據。 比如當source+count>=dest&&source<dest時，dest可能覆蓋了原有source的數據。解決辦法是從后往前拷貝，對于其它情況，則從前往后拷貝。 參考代碼如下： ```cpp //void * memmove ( void * destination, const void * source, size_t num );) void* memmove(void* dest, void* source, size_t count) { void* ret = dest; if (dest <= source || dest >= (source + count)) { //正向拷貝 //copy from lower addresses to higher addresses while (count --) *dest++ = *source++; } else { //反向拷貝 //copy from higher addresses to lower addresses dest += count - 1; source += count - 1; while (count--) *dest-- = *source--; } return ret; } ```