leetcode 第 310 場演算法比賽

語言: CN / TW / HK

零、背景

這次比賽題目有點意思,我感覺做題速度還可以,結果依舊沒進前百名。

不知是大家變強了,還是我變弱了。

一、出現最頻繁的偶數元素

題目:給一個數組,統計出現次數最高的偶數數字是哪個。

思路:map 統計偶數,遍歷尋找最大頻次即可。

小技巧:一種不需要空間的方法是原地排序,然後連續出現的數字就是這個數字的頻次。

二、子字串的最優劃分

題意:給一個字串,問最少可以劃分多少了沒有交集的子字串,使得每個子字串中沒有重複字母。

思路:貪心。

邊遍歷邊統計每個字母出現的次數,一旦重複就是分割線,統計器重置為0。

三、將區間分為最少組數

題意:給一些左右封閉區間,問最少可以劃分多少個區間集合,使得集合內的區間沒有交集。

思路:貪心。

每輪選擇最小的左區間,然後選擇下個沒有交集的最小的左區間,直到找不到,則形成一個集合。

不斷的重複上面的操作,最終統計的集合個數就是答案。

四、最長遞增子序列 II

題意:給一個數組,求 LIS,即最長遞增子序列。

要求:子序列相鄰元素的差值不超過 k。

思路: n log(n) 的經典動態規劃我不知道能不能做這道題。

我是使用最原生的方法來做這道題的。

當前值 v 為結尾的最優值,要麼不變,要麼是 [v-k, v-1] 結尾的最優值再加1。

所以我們需要一個數據結構,能夠快速查詢區間 [v-k, v-1] 的最優值,並且能更新當前點的最優值。

這就是典型的線段樹。

PS:比賽的時候,我腦子短路,誤認為區間內值不為0的都還需要加1,浪費不少時間在改線段樹模板。

五、最後

這次比賽中間兩題都是貪心,最後一題線段樹,挺有意思的。

只可惜我想錯了,浪費不少時間,沒能進去前百名。

加油,演算法人。

《完》

-EOF-

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

個人微訊號:tiankonguse

公眾號ID:tiankonguse-code