算法筆試模拟題精解之“破譯密碼”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家介紹其中的 第97題：破譯密碼 的題目解析，具體如下：

題目描述

題目等級：中等

知識點：尺取法

檢視題目：破譯密碼

給你一個長度為n的序列，元素标号1-n。問能夠找到多少對不同的（L,R）（1 <= L <= R），使得在子序列[L,R]記憶體在出現頻率不低于K的元素？

輸入序列大小n（1 <= n <= 10^4）、出現頻率k（1 <= k <= n）和一個包含n個整數的數組，第i個整數表示序列的第i個元素為ai(1 <= ai <= 10^9)。

輸出滿足條件的子序列個數。

示例1

輸入：

4

2

[1 ,2 ,1 ,2]

輸出：

3

注意

三個子序列分别為[1,3],[1,4],[2,4]

解題思路:尺取法

與57超級區間那道題是類似的方法。

設目前區間為[L, R]。初始L = R = 0；使用尺取法需要判斷什麼時候調整L和R。

情況1：假設對于某個區間[L1, R1]滿足題目要求。則保持L1不變，依次增加R1直到n為止的所有區間都滿足題目的要求。

情況2：假設對于某個區間[L2，R2]不滿足題目要求。則需要保持L2不動，增加R2才可能滿足滿足題目要求。

情況3：是情況2拓展。如果[L2，n]不滿足題目要求，則任何i>L2，區間[i, n]都不滿足題目要求。

使用一個 2*n 的數組numb來記錄目前區間[L, R]内每個元素的出現次數。numbL和numbR表示區間[L, R]對應的numb數組範圍。因為每個數都是按照進入區間[L, R]的順序離開區間[L, R]的，相當于一個隊列，是以numb數組可以用numbL和numbR來表示目前區間[L, R]内的元素，而不用考慮中間某個數不在區間[L, R]内的情況。

計算過程

1. 初始L = R = 0；sum = 0; 用來計算滿足條件的區間個數
2. 判斷區間 [L, R] 的情況，滿足情況1，則sum++; R++。滿足情況2， L++。滿足情況3，結束計算。
3. R每次加1，都要給numb數組中對應的數出現次數+1。當是一個新數時，要使numbR++；

4. L每次減1，都要給numb數組中對應的數出現次數-1。當減為0時，要使numbL++

   對于情況1，因為L不變時，後面的所有R都滿足條件，是以可以修改為sum+=n-R+1； L++。

時間複雜度O(n^2) 修改之前最差為O(n^2)

空間複雜度O(2*n) numb數組的空間

看完之後是不是有了想法了呢，快來練練手吧>>