Leetcode 第130場比賽回顧
一、背景
發現一個Leetcode的一個重大祕密,偷偷告訴你。
leetcode這次舉辦比賽的官方人員肯定監聽我的QQ演算法群的聊天記錄了。
我昨晚才在群裡說我比賽從來沒做過四題,每次都是三題。
然後今天比賽他們就放水了,給了我一次機會。
按照國人的邏輯,這個是實錘的事情了。
好了,下面來看看這次比賽 Leetcode 是如何放水讓我做出四道題的吧。
二、可被 5 整除的二進位制字首
題號:1029
題目:Binary Prefix Divisible By 5
地址:https://leetcode.com/contest/weekly-contest-130/problems/binary-prefix-divisible-by-5/
原始碼:https://github.com/tiankonguse/leetcode-solutions/blob/master/contest/130/A.cpp
題意:告訴你一個 0
和 1
組成的二進位制字串,判斷所有的字首二進位制串是否可被 5
整除。
思路:由於是求所有字首的答案,那掃描一遍,計算出所有字首的十進位制數字,判斷即可。
這裡有個注意事項時,十進位制數字可能很大,需要邊計算邊取模。
關鍵思想與原理如下:
pre(i) = pre(i-1)*2 + val[i]) pre(i) % 5 = (pre(i-1)*2 + val[i])%5 = (pre(i-1)% 5)*2 + val[i])%5
class Solution { public: vector<bool> prefixesDivBy5(vector<int>& A) { vector<bool> ans; int now = 0; for(int i=0; i<A.size(); i++) { now = (now * 2 + A[i])%5; if(now ==0) { ans.push_back(1); } else { ans.push_back(0); } } return ans; } };
三、負二進位制轉換
題號:1028
題目:Convert to Base -2
地址:https://leetcode.com/contest/weekly-contest-130/problems/convert-to-base-2/
原始碼:https://github.com/tiankonguse/leetcode-solutions/blob/master/contest/130/B.cpp
題意:對於二進位制,大家沒有疑問,公式是 2^0 + 2^1 + 2^2 + ...
。
-2
的公式:
(-2)^0 + (-2)^1 + (-2)^3 +...
給你一個數字 N
,求其 -2
進位制。
思路:首次看到這道題時,我是一臉懵逼的。
第一個疑問是:這樣能表示所有的數字嗎?
於是在紙上隨便舉了一個例子,發現真的可以。
發現真的可以時,也找到幾個特徵。
特徵一:二進位制的公式裡,正負符號是相反的。
特徵二:如果在正常的二進位制位置上符號為正時,可以使用更高位減去當前位得到答案。
例如:假設第 2k+1
位在正常二進位制應該是 1
,但是在負二進位制裡基數是 -2
,我們計算的結果是 (-2)^(2k+1)
。
我們的目標是求 2^(k+1)
。
那我們給整個二進位制加上 (-2)^(2k+2)
即可得到目標。
推理如下:
(-2)^(2k+2) + (-2)^(2k+1) =2^(2k+2) - 2^(2k+1) =2*2^(2k+1) - 2^(2k+1) =2^(2k+1)
既然這樣,我們只需要模擬大整數加法,遇到需要加 2^(2k+2)
時,進一位即可。
string baseNeg2(int N) { if(N == 0){ return "0"; } string ans; int pre = 0; int bit = 0; while(N>0 || pre >0){ int sum = N%2 + pre; if(sum == 0){ ans.push_back('0'); }else if(sum == 1){ ////根據奇偶性決定是否進位 pre = bit%2; ans.push_back('1'); }else if(sum == 2){ pre = 1; //進位 ans.push_back('0'); } bit++; N = N/2; } std::reverse(ans.begin(), ans.end()); return ans; }
四、連結串列中的下一個更大節點
題號:1030
題目:Next Greater Node In Linked List
地址:https://leetcode.com/contest/weekly-contest-130/problems/next-greater-node-in-linked-list/
原始碼:https://github.com/tiankonguse/leetcode-solutions/blob/master/contest/130/C.cpp
題意:給一個連結串列,求出每個節點之後第一個大於當前節點的值。
思路:由於是求之後第一個大於的值,很容易發現有一個特徵。
特徵:零 i<j
且 val[i] >= val[j]
, 我們可以證明,任何時候 i
都比 j
更優。
具體意思就是,對於 i
前面的數字,如果在 i
和 j
裡面選擇一個答案的話,我們只能選擇 i
。
這個思想其實單調佇列,前面的比賽已經提到無數次了。
所以第一種方法就是:逆序遍歷序列,維護一個單調佇列即可。
但是,當我敲程式碼的時候,發現輸入的是連結串列。
那好辦,先把連結串列轉換為陣列即可。
那有沒有直接掃描連結串列就得到答案呢?
還真有。
恰好在昨晚,在我的 不知演算法
QQ群裡,有人問最長遞增子序列有比 n log(n)
更優的演算法嗎?
我問他的想法時,他說記得可以使用 DP
+ RMQ
優化到 n log(n)
。
我想了想,認為只需要使用單調佇列優化即可達到 n log(n)
。
隨後我也給出了其嚴格的證明推理,為什麼會更優。
面對這種題型,如果使用陣列儲存的話,我們稱為單調佇列。
其實,也可以使用 map
儲存的,思想依舊是單調佇列。
既然可以使用 map
儲存,我們就可以從前到後掃描了。
只不過相反,這裡掃描到一個點時,是為了尋找這個點時前面那些點的答案。
假設我們維護了這樣一個數據結構:全是還知道答案的點。
掃描到一個位置時,資料結構裡面,比這個位置小的點的答案 全是這個位置。
然後更新資料結構:刪除已經找到答案的點,然後當前位置加入資料結構。
PS:這裡有一個注意事項:位置的值可能重複,所以值相同時,所有的下標都需要儲存下來。
五、飛地的數量
題號:1031
題目:Number of Enclaves
地址:https://leetcode.com/contest/weekly-contest-130/problems/number-of-enclaves/
原始碼:https://github.com/tiankonguse/leetcode-solutions/blob/master/contest/130/D.cpp
題意:給一個地圖:海與陸地,詢問沒有和邊界相連的陸地的個數(孤島)。
思路:大水題,一個 DFS
或者 BFS
即可。
正常思路是遍歷每個點,當前點未訪問過時,開始搜尋。
如果發現了邊界,將搜尋的所有點都標記為非孤島。
如果未發現邊界,將搜尋的所有點都標記為孤島。
最後計數即可。
比較優秀的思路是直接掃描四個邊界,就行搜尋標記。
注意事項:每個點只能遞迴搜尋一次,搜尋之後,就應該標記為訪問過,後面不能在訪問,否則複雜度將是 O(n^4)
。
複雜度: O(n^2)
,其實就是地圖的大小。
六、最後
這次比賽,涉及到了兩道數學題、一個單調佇列題、一道搜尋題。
都是較為基礎的題,大家可以練習一下。
-EOF-