## 本章字符串和鏈表的習題
**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 = 2 * i。
問有多少長度為M且符合條件的字符串。
例如:N = 2,M = 3。則abb, bab, bbb是符合條件的字符串,剩下的均為不符合條件的字符串。
假定n和m皆滿足:2<=n,m<=1000000000)。
**27、最短摘要生成**
你我在百度或谷歌搜索框中敲入本博客名稱的前4個字“結構之法”,便能在第一個選項看到本博客的鏈接,如下圖2所示:
[](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/21~22/22.1.gif)
在上面所示的圖2中,搜索結果“結構之法算法之道-博客頻道-CSDN.NET”下有一段說明性的文字:“程序員面試、算法研究、編程藝術、紅黑樹4大經典原創系列集錦與總結 作者:July--結構之法算法...”,我們把這段文字稱為那個搜索結果的摘要,亦即最短摘要。我們的問題是,請問,這個最短摘要是怎么生成的呢?
**28、實現memcpy函數**
已知memcpy的函數為:?`void* memcpy(void* dest , const void* src , size_t count)`其中dest是目的指針,src是源指針。不調用c++/c的memcpy庫函數,請編寫memcpy。
分析:參考代碼如下:
~~~
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函數是的標準函數,其作用是把從source開始的num個字符拷貝到destination。最簡單的方法是直接復制,但是由于它們可能存在內存的重疊區,因此可能覆蓋了原有數據。
比如當source+count>=dest&&source<dest時,dest可能覆蓋了原有source的數據。解決辦法是從后往前拷貝,對于其它情況,則從前往后拷貝。
參考代碼如下:
~~~
//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;
}
~~~
- 關于
- 第一部分 數據結構
- 第一章 字符串
- 1.0 本章導讀
- 1.1 旋轉字符串
- 1.2 字符串包含
- 1.3 字符串轉換成整數
- 1.4 回文判斷
- 1.5 最長回文子串
- 1.6 字符串的全排列
- 1.10 本章習題
- 第二章 數組
- 2.0 本章導讀
- 2.1 尋找最小的 k 個數
- 2.2 尋找和為定值的兩個數
- 2.3 尋找和為定值的多個數
- 2.4 最大連續子數組和
- 2.5 跳臺階
- 2.6 奇偶排序
- 2.7 荷蘭國旗
- 2.8 矩陣相乘
- 2.9 完美洗牌
- 2.15 本章習題
- 第三章 樹
- 3.0 本章導讀
- 3.1 紅黑樹
- 3.2 B樹
- 3.3 最近公共祖先LCA
- 3.10 本章習題
- 第二部分 算法心得
- 第四章 查找匹配
- 4.1 有序數組的查找
- 4.2 行列遞增矩陣的查找
- 4.3 出現次數超過一半的數字
- 第五章 動態規劃
- 5.0 本章導讀
- 5.1 最大連續乘積子串
- 5.2 字符串編輯距離
- 5.3 格子取數
- 5.4 交替字符串
- 5.10 本章習題
- 第三部分 綜合演練
- 第六章 海量數據處理
- 6.0 本章導讀
- 6.1 關聯式容器
- 6.2 分而治之
- 6.3 simhash算法
- 6.4 外排序
- 6.5 MapReduce
- 6.6 多層劃分
- 6.7 Bitmap
- 6.8 Bloom filter
- 6.9 Trie樹
- 6.10 數據庫
- 6.11 倒排索引
- 6.15 本章習題
- 第七章 機器學習
- 7.1 K 近鄰算法
- 7.2 支持向量機
- 附錄 更多題型
- 附錄A 語言基礎
- 附錄B 概率統計
- 附錄C 智力邏輯
- 附錄D 系統設計
- 附錄E 操作系統
- 附錄F 網絡協議