算法筆試模拟題精解之“變換的密鑰”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家介紹其中的第58題：變換的密鑰 的題目解析，具體如下：

題目描述

題目等級：中等

知識點：廣度優先搜尋/BFS、Floyed最短路、圖

檢視題目：變換的密鑰

Tom最開始有一個密鑰s1，s1是長度為n的由小寫字母組成的字元串。Jerry也有一個長度為n的由小寫字母組成的密鑰s2。

現在有m組關系，每組關系由兩個數字[u,v]構成(1<=u,v<=26)，表示26個字母表中的第u個小寫字母可以直接轉換為第v個小寫字母。

假設u=1，v=2,那麼說明字母'a'可以直接轉換為字母'b'。現在Tom對于s1的每個字母使用無數次轉換，請判斷s1能否轉換為s2。

輸入内容為四部分，第一部分為n(1<=n<=100000)，代表字元串的長度。接下來兩部分分别是長度為n的s1,s2。

第四部分為m（1 <=m <=325），代表關系個數。接下來是m組[u,v]關系。

如果s1能變成s2,則輸出YES,否則輸出NO。

示例1

輸入：

6

"aabbcc"

"cdbcad"

4

[[1,3],[3,1],[1,4],[2,3]]

輸出：

"YES"

注意

可以轉換多次，比如a可以轉換為b，而b可以轉換為c，則a可以轉換為c。

樣例：aabbcc->cabbcc->cdbbcc->cdbccc->cdbcac->cdbcaa->cdbcad

解題思路一：一般思路

根據題意，隻要根據給出的初始關系，計算出對于每個字母可以變成的字母，就可以直接判斷s1能不能轉化成s2了。

例如樣例中計算過後

a -> a,c,d
b -> b,c
c -> a,c,d
d -> d           

對于這個結果，可以使用一個26

*

26的二維數組change來儲存。每一行表示原始字母，每一清單示可以變換成的字母。1表示可以變化，0表示不能變換。

計算過程：

1． 初始化，根據給出的關系填充數組

2． 記得數組對角線要填為1，表示每個字母可以不進行變換，是自己本身。

3． 計算經過無數次變換後的數組。

對于第三步可以直接進行多次for循環，因為數組不大，一般不會逾時。

方法二：矩陣快速幂

經過0-2次變換後可以達到的字母的結果相當于change

*

change，0-3次對應的相當于change

*

change

*

change，0-n次對應的就是change^n。這是一個矩陣求幂的過程。

對于求幂操作有可以加快計算的方法，叫做矩陣快速幂。這裡用求數的次幂舉例。

假設要求 x^13。直接的方法是進行12次相乘。

我們可以觀察到13 = 8 + 4 + 1= 2^3 + 2^2 + 1

是以x^13 = x^8 + x^4 + x= (x^4)^2 + (x^2)^2 + 0*(x)^2 + x

從右向左，每一項都是前一項的平方。這樣原來需要12次乘法的操作變成了3次懲罰，3次加法（第二項系數為0，不用加）。

與求數的次幂類似，矩陣也可以用相同的方法加速計算。對于這道題本身，因為矩陣中非0的結果表示可以進行變換，是以相乘時沒有必要算出具體的值，隻需要判斷結果是否非0。

因為隻有26個字母，是以隻需要算到26次幂就可以了，也可以計算32次幂來去掉加法的部分。

時間複雜度O(5

*

26

*

*

26) 5是求32次幂需要的矩陣乘法次數。26

*

*

26是一次乘法需要的時間複雜度。

空間複雜度O(2

*

*

26) 一個二維數組儲存目前結果，一個儲存相乘後的結果。

看完之後是不是有了想法了呢，快來練練手吧>>