Leetcode 第 179 場比賽回顧

零、背景

這次比賽的題都是基礎題，考察敲程式碼速度的時候到了。

一、解密字串

題意：給一個字母到數字的加密規則，然後給一個加密後的字串，求加密前的字串。

規則1：對於字母 a-i ，對映到 1-9 。

規則2：對於字母 j-z ，對映到 10#-26# 。

思路：簡單來說，加密規則就是字母對映到以 1 開始計數的數字，對於兩位數字，後面需要加一個 # 符號。

那解密規則就是一個逆過程。

但是這個加密不是一個好的加密演算法，因為讀第一個字元後，存在不確定性，即後面有多種可能。

比如遇到字元 1 時，可能是字元 a ，也可能是字母 j ，也可能是 k ，這個情況有11中。

所以我們需要向後探測這個具體是哪種情況。

具體來說就是看有沒有 # 符號，然後分情況判斷。

二、陣列的區間異或查詢

題意：給一個數組，然後若干詢問。

每個詢問是一個子陣列區間，求這個子陣列的異或結果。

字首優化：異或和求和類似，具有結合性的規律。

具體來說就是，對於 a<b<c ， f(a, c) = f(f(a,b-1), f(b,c)) 。

所有能夠使用字首和的公式都需要滿足這個結合律。

三、朋友在看哪些小影片

題意：題意相當複雜。

首先有 n 個人，每個人有一個自己看的小影片列表，每個人有一個朋友列表。

level 解釋：最少需要經過 level 層才能認識的朋友。

目標：查詢某個人第 level 層轉彎抹角的朋友看到小影片列表。

輸出規則：優先按小影片觀看次數排序，一樣了按小影片名字排序。

思路：題意看懂了發現沒什麼難度。

第一步找到 level 層的朋友列表。

第二部統計這些朋友看的小影片，排序即可。

四、最小修改回文串

題意：給一個字串，問最少插入多少個字元，能夠使得字串是迴文串。

思路：假設已經插入是迴文串了，我們忽略哪些插入以及插入匹配的字元，剩餘的字元肯定是原字串中最長的對稱相等序列。

即尋找最長的迴文子序列，剩餘的就是需要插入匹配的。

證明略。

五、最後

面對簡單的題，我使用洪荒之力去敲鍵盤，可耐還是敲得太慢。

看前百名裡，第一名用了 8 分鐘，最後一名用了 35 分鐘，而我用了 45 分鐘。

還有很大的進步空間，準備每天練 10 分鐘的打字，看看效果吧。

PS：昨天註冊了 B 站，發現 B 站需要答 100 道題才能發彈幕，果然是一個獨特的公司，

-EOF-

本文公眾號：天空的程式碼世界

個人微訊號：tiankonguse

QQ演算法群：165531769（不止演算法）

知識星球：不止演算法