筆試算法模拟題精解之“尋找等比數列”

【線上程式設計産品介紹】

阿裡雲開發者社群線上程式設計：

免費刷題大神器，助你拿到好offer

周賽月賽不停歇，做題還能領獎品

大賽筆試全真題，常做常新有驚喜

點選連結開始産品體驗：

https://developer.aliyun.com/coding 本文為大家介紹的是“64.尋找等比數列”的解法探究。先來看一下題目内容：

題目詳情

等級：中等

知識點：DP

檢視題目：尋找等比數列

Alice和Bob都是數學高手，有一天Alice給了Bob一個長度為n的數組a，要求Bob在數組中找出3個數，要求三個數能夠組成一個公比為k的等比數列，且不改變三個數在數組a中的位置關系。

為了降低難度，Alice隻要求Bob回答數組a中有多少個這樣的等比數列。

輸入一個整數n表示數組長度、公比k(1<=n,k<=2*10^5)和包含n個數的數組a(-10^9<=ai<=10^9)

輸出一個數字，表示數組a中包含Alice要求的等比數列的數量。

示例1

輸入：

5

2

[1,1,2,2,4]

輸出：

4

題解思路

方法1：逐個周遊（逾時）

最簡單的方法，就是周遊數組中所有可能的三元組，逐個檢驗每組數是否符合公比為k的等比數列的性質。

對于較長的用例，這麼做顯然是逾時的，不通過。

時間複雜度：O(n^3)

空間複雜度：O(1)

方法2：動态規劃

本題充分利用下面兩個隐藏規律，就可以使用動态規劃：

1. “長度為3的等比數列”，滿足了動态規劃的最優子結構性質

數列中每個數字隻有4種可能的狀态。其中帶*号的狀态可以同時存在，且靠後的狀态可以由前面的狀态轉換而來：

• 同時屬于一個或多個等比數列的第1項
• 同時屬于一個或多個等比數列的第2項
• 同時屬于一個或多個等比數列的第3項
• 無法與前後數字組成任何等比數列

1. “不允許調換順序”，滿足動态規劃的子問題不重疊性和無後效性性質

表示數字處于上面哪種狀态，完全由這個數字及其之前的數字決定，它的狀态與它後面數字的情形無關。

這就意味着，一次周遊，同時用map将每個周遊的數字歸屬到前面4種狀态中的1個或多個裡。周遊結束，輸出第3種狀态“同時屬于一個或多個等比數列的第3項”中含有的數字數，就完成了動态規劃的過程。

時間複雜度：O(n)

空間複雜度：O(kn)

看完之後是不是有了答題思路了呢，快來練練手吧：

64.尋找等比數列

線上程式設計周賽、月賽火熱進行中，更有限時答題活動，定制衛衣、雙肩背包、機械鍵盤等多重好禮等你來拿~每天都有好禮相送~點選了解周賽詳情：

線上程式設計3月份比賽正式開啟！機械鍵盤等你拿！