3.6　超級回文數

這是一道力扣（LeetCode）上難度級別為困難的題目，讓我們一起來看一下。

題目描述（第906題）

如果一個正整數自身是回文數，而且它也是另一個回文數的平方，那么我們稱這個數為超級回文數。

現在，給定兩個正整數L和R（以字符串形式表示），返回包含在范圍[L,R]中的超級回文數的數目。

示例

輸入：L="4"，R="1000"

輸出：4

解釋：4、9、121和484是超級回文數。

注意：676不是超級回文數：26 * 26=676，但26不是回文數。

提示

●　1 ≤len(L)≤ 18。

●　1 ≤len(R)≤18。

●　L和R表示在[1,1018)范圍內的整數的字符串。

●　int(L)≤int(R)。

思路

暴力地對math.floor()到math.ceil()范圍內的數進行遍歷，并逐個判斷其是否為回文數，如果是，則繼續判斷其平方是否是回文即可。

上面代碼的時間復雜度顯然已經大于O(-)，代入題目給出的數據范圍大概率會超時，需要考慮剪枝。關于如何根據題目數據范圍判斷算法是否可行可參考第20.1節的相關內容。

剪枝是一種非常重要的思想，本書會在第20章進行詳細講述。

為什么不直接構造一個回文數Q呢？這樣就省去了判斷Q是否是一個回文數的過程，直接判斷Q的平方即可。

這樣的話，問題被轉化為如何構造回文數，其核心代碼如下。

如果i是123，那么r就應該為321，Q就應該為123×100+321 % 100，即12300+21，即12321。

回文中心有兩種，一種是回文中心為單個字符，一種是回文中心為兩個字符，因此上面的算法并不完備，我們還需要考慮回文中心為兩個字符的情況。拿上面的例子來說，就少考慮了123321這種情況。我們只需要補充這種情況即可。

代碼如下所示。

這種算法的時間復雜度會比上面的稍微好一點，可以通過力扣（LeetCode）所有的測試用例，但是還有優化空間，讀者不妨思考一下如何優化該算法。我也會在后面的章節帶讀者一步一步優化類似的題目，幫助讀者打開思路。

代碼

復雜度分析

●　時間復雜度：O()，其中W為R的上限，在這道題中就是1018，而18的1/4是4.5，因此代碼中循環到105是足夠的。

●　空間復雜度：用seen來存儲所有出現過的超級質數，因此空間復雜度為，其中cnt為[L,R]間的超級回文數的個數，也就是問題的解。