字串就是這麼簡單
一、背景
這篇文章簡單的介紹一下字串的使用,然後來看幾道對應的例子。
注:每次我都會把對應的練習題地址傳送到群裡,建議想學演算法的朋友耐心的做一下這些題。
二、字串簡介
字串其實就是一個字元元素組成的陣列。
它幾乎擁有陣列的所有操作功能。
當然,字串和陣列也有一些區別。
這裡主要介紹使用字串時需要注意的問題,尤其是不同語言之間的差異。
1.比較函式
字串一般有自己的比較函式,但是不一定是 ==
運算子。
在 C++
裡面,我們可以使用這個運算子,但是在 Java
裡面,我們就不能使用這個運算子了。
在 Java
裡面, ==
用於判斷兩個物件是否是同一個物件,但是不同物件的值可能是相同的。
2.可變性
不可變意味著字串初始化後,就不能在修改它的內容了。
當然,在 C++
中,預設字串是可變的,我們可以像陣列那樣來修改字串的內容。
而在 Java
中,每個字串都是一個不可變的物件,當對字串操作時,都會生成新的字串(很消耗效能)。
3.附加操作
由於字串已經作為程式語言的內建型別了,所以增加了一些額外的常見操作函式。
比如字串拼接、查詢、子串擷取等。
三、二進位制求和
在《 陣列就是這麼簡單 》裡面有一道題,叫做 加一
。
很多人說這道題太簡單了,現在就加大點難度,兩個字串組成的二進位制數字相加求和。
其實,對於大整數運算,有一個標準的步驟。
第一步將字串翻轉。
平常我們紙上手動計算大數相加時,都是低位對齊,然後從低位到高位計算。
而計算機裡的數字,低位在後面,高位在前面,所以需要字串翻轉。
第二步是求出答案可能的最大長度,然後在兩個字串上高位補零。
由於可能進位,所以一般是兩個字串的最大長度再加一,這樣可以保證計算時不用考慮特殊邊界情況。
第三步就迴圈相加,需要進位則進位,直到迴圈結束。
第四步需要刪除答案高位多於的0。
由於答案可能也是0,所以答案要保留一位。
第五步是對答案翻轉,使得答案滿足計算機的要求:高位在前面低位在後面。
通過這樣五步,所有的大整數運算都可以解決了。
四、實現strStr
首先我們需要明白 strStr
函式的含義。
根據文件定義,這個函式的功能是查詢字串子串的第一個位置。
如果不存在子串,則返回 -1
。
對於這道題,最簡單的就是暴力解決。
具體來說就是列舉第一個字串的每一個位置來當做起點,然後迴圈判斷是否和第二個字串匹配。
當然,這個複雜度是 O(n * m)
的。
面對上面的暴力方法,其實我們有一個更快的方法,名字叫做 KMP
。
這個演算法使用語言描述的方式來理解的話很簡單,但是實現後看程式碼理解起來比較難。
先來看語言描述層面的意思。
假設我們從某個位置 P
開始和字串 needle
比較,比較了 10
個字元後發現不同了。
在暴力方法中,我們直接從 P+1
位置重新開始從頭比較。
其實,我們從 P ~ P+10
的字元我們都已經掃描過了,而且 P ~ P+9
的字元都和 needle
的字首相同。
既然掃描過了,我們能不能直接來判斷下個位置應該從哪個位置開始比較呢?
比如 P ~ P+9
的子串對應於 1234512345
。
如果我們直接從下個位置開始比較,則 P+1
位置的值時 2
,而 needle
第一個位置的值時 1
,顯然不成立。
同理, P+2
位置值是 3
也不成立。
直到 P+5
位置值是 1
是才成立,而且也可以判斷出 P+5 ~ P+9
都是成立的,我們只需要判斷 P+10
的位置是不是 5
。
而 KMP
做到就是這個工作。
這個演算法會先對 needle
進行預處理,計算出到某個位置不相等時,下一次要從哪裡開始。
然後我們掃描目標字串時,只需要不斷的對比,發現不相等了,快速的移動到下一個合適的位置繼續比較。
由於這裡沒有進行冗餘比較,複雜度是 O(N + M)
,其中 N
和 M
分別是兩個字串的長度。
語言描述的含義說完了,剩下的就是使用程式碼將我們描述的邏輯實現了。
這個實現還是相當抽象的,所以大家看著程式碼,找個例子模擬一下才能理解。
五、最長公共字首
題意:給 N
個字串,求最長公共字首。
這道題沒啥說的,迴圈比較即可。
六、最後
對於字串,相關題型其實特別多。
KMP
是首先遇到的最優技術含量的一個演算法,這裡關鍵是理解預處理的 next
陣列的含義,後面會有各種變種的題型的。
-EOF-