leetcode 第 312 場演算法比賽

零、背景

這次比賽題目總是看錯，雖然做出所有題，但是排名很靠後了。

一、按身高排序

題意：給兩個陣列，一個是名字，一個是身高，要求按身高排序，輸出名字。

思路：兩個數組合併為一個數組，再按身高排序輸出名字即可。

二、按位與最大的最長子陣列

題意：給一個數組，所有子陣列的與運算的有一個最大值 K 。

求與運算等於 K 的最長子陣列。

思路：與運算只會越來越來，所以最大值就是陣列的最大值。

然後統計這個最大值連續出現的最多次數即可。

注意實現：看錯題了，看錯與運算後 1 最多的個數。

三、找到所有好下標

題意：給一個數組，求滿足下標之前的 k 個元素是非遞增，之後 K 個元素是非遞減的下標個數。

思路：題目有問題，資料樣例也不能體現出錯誤的題意。

非遞增的反義詞不是遞增序列。

而是 k 個元素任意相鄰的元素都不能是遞增的。

遞減的含義類似。

方法：預處理出所有下標的字首與字尾是否滿足條件，最後再判斷即可。

非遞增預處理：掃描陣列，判斷相鄰元素是否是大於關係，是了，之後的 k 個元素都不滿足非遞增關係。

通過一個遊標標記目前最遠的不滿足非遞增的下標，就可以掃描一遍完成預處理。

四、好路徑的數目

題意：給一個無根樹，如果一個路徑的端點相等且路徑上所有節點值不大於端點值，則稱為好路徑。

求好路徑的個數。

思路：經典的樹上並查集問題。

分析：假設路徑經過當前子樹的根，則遞迴子樹的時候，答案端點在子樹的前提是對應的值需要大於等於當前根的值也需要大於等於子樹根的值。

由此遞迴的演算法也就出來了：

-）遞迴子樹時傳入根的值，返回大於等於根的所有節點集合。

-）不同子樹返回的集合計算出路徑，併合並子樹。

-）合併後的集合裡，小於祖先節點的都需要過濾掉，然後函式返回這個集合。

注意事項：樹上並查集的訣竅就是合併集合時，需要把小集合合併到大集合。

五、最後

這次比賽最後一題比較有意思。

第三題題目有問題，我做了四十分鐘，錯了好幾次，通過猜測題意的方法通過了第三題。

加油，演算法人。

《完》

-EOF-

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

個人微訊號：tiankonguse

公眾號ID：tiankonguse-code