Leetcode 第 179 場比賽回顧

語言: CN / TW / HK

零、背景

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

一、解密字串

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

規則1:對於字母 a-i ,對映到 1-9

規則2:對於字母 j-z ,對映到 10#-26#

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

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

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

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

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

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

二、陣列的區間異或查詢

題意:給一個數組,然後若干詢問。

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

思路:最暴力的是按題意一個個的區間異或。

複雜度: n^2

按照 leetcode 的傳統,這個方法不會超時。

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

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

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

利用字首的結合律,我們可以預先求出所有字首的答案,詢問時,通過相減即可找到答案。

詢問複雜度: O(1)

綜合複雜度: O(n)

三、朋友在看哪些小影片

題意:題意相當複雜。

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

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

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

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

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

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

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

四、最小修改回文串

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

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

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

證明略。

五、最後

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

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

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

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

-EOF-

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

個人微訊號:tiankonguse

QQ演算法群:165531769(不止演算法)

知識星球:不止演算法