摘要:前言的第一題最近的請(qǐng)求次數(shù)寫一個(gè)類來計(jì)算最近的請(qǐng)求。返回從毫秒前到現(xiàn)在的數(shù)。示例輸入輸出提示每個(gè)測(cè)試用例最多調(diào)用次。實(shí)現(xiàn)代碼最近的請(qǐng)求次數(shù)存儲(chǔ)時(shí)間的最小有效時(shí)間的索引從開始遍歷判斷最小的有效時(shí)間是否無效返回有效的元素個(gè)數(shù)
前言
Weekly Contest 109的第一題 最近的請(qǐng)求次數(shù):
解題思路寫一個(gè) RecentCounter 類來計(jì)算最近的請(qǐng)求。
它只有一個(gè)方法:ping(int t),其中 t 代表以毫秒為單位的某個(gè)時(shí)間。
返回從 3000 毫秒前到現(xiàn)在的 ping 數(shù)。
任何處于 [t - 3000, t] 時(shí)間范圍之內(nèi)的 ping 都將會(huì)被計(jì)算在內(nèi),包括當(dāng)前(指 t 時(shí)刻)的 ping。
保證每次對(duì) ping 的調(diào)用都使用比之前更大的 t 值。
示例:
輸入:inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]] 輸出:[null,1,2,3,3]提示:
每個(gè)測(cè)試用例最多調(diào)用 10000 次 ping。
每個(gè)測(cè)試用例會(huì)使用嚴(yán)格遞增的 t 值來調(diào)用 ping。
每次調(diào)用 ping 都有 1 <= t <= 10^9。
本題其實(shí)并不復(fù)雜,但是我在實(shí)現(xiàn)時(shí)由于思考的方向錯(cuò)了,導(dǎo)致了花費(fèi)大量時(shí)間去完成這個(gè)題目。
一開始我的思路是仿照LRU算法,實(shí)現(xiàn)一個(gè)會(huì)移除超出有效范圍[t - 3000, t]的緩存。
但是隨著不斷的嘗試后,發(fā)現(xiàn)其實(shí)只需要統(tǒng)計(jì)時(shí)有效的ping即可。期間遇到過好幾次執(zhí)行超時(shí)的情況,所以需要優(yōu)化統(tǒng)計(jì)有效ping時(shí)的檢索區(qū)間。
所以最終實(shí)現(xiàn)思路如下:
需要一個(gè)存儲(chǔ)所有ping時(shí)間的數(shù)組list和記錄最小有效ping時(shí)間的list索引minIndex
每次ping就從minIndex開始檢索list,直到遇到數(shù)組list中的ping時(shí)間item有效(即item在[t - 3000, t])則中斷循環(huán),否則(item
/** * 933. 最近的請(qǐng)求次數(shù) * @author RJH * create at 2018/11/4 */ public class RecentCounter { /** * 存儲(chǔ)ping時(shí)間的List */ private Listlist; /** * 最小有效ping時(shí)間的索引 */ private int minIndex=0; public RecentCounter() { list=new LinkedList<>(); } public int ping(int t) { list.add(t); for(int i=minIndex;i
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/71997.html
摘要:題目鏈接題目分析這個(gè)題目說實(shí)在的,看得我一臉蒙蔽。返回自毫秒到現(xiàn)在為止的次數(shù)包括當(dāng)前。調(diào)函數(shù)時(shí),傳入的參數(shù)為當(dāng)前的毫秒數(shù)。思路其實(shí)是說,返回前毫秒內(nèi)的次數(shù)。最終代碼若覺得本文章對(duì)你有用,歡迎用愛發(fā)電資助。 D50 933. Number of Recent Calls 題目鏈接 933. Number of Recent Calls 題目分析 這個(gè)題目說實(shí)在的,看得我一臉蒙蔽。 返回自...
摘要:題目地址題目描述寫一個(gè)類來計(jì)算最近的請(qǐng)求。它只有一個(gè)方法,其中代表以毫秒為單位的某個(gè)時(shí)間。返回從毫秒前到現(xiàn)在的數(shù)。任何處于時(shí)間范圍之內(nèi)的都將會(huì)被計(jì)算在內(nèi),包括當(dāng)前指時(shí)刻的。并且刪除要用迭代器來刪除,否則會(huì)引發(fā)。 題目地址:https://leetcode-cn.com/probl...題目描述:寫一個(gè) RecentCounter 類來計(jì)算最近的請(qǐng)求。 它只有一個(gè)方法:ping(int ...
今天我們講講JavaScript隊(duì)列數(shù)據(jù)結(jié)構(gòu)詳解。 什么是隊(duì)列? 隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu),隊(duì)列有兩種操作:插入和刪除;入隊(duì)和出隊(duì)。簡(jiǎn)單來說就是允許插入的一端稱為隊(duì)尾、允許刪除的一端稱為隊(duì)頭; 如下圖展示了棧這個(gè)數(shù)據(jù)結(jié)構(gòu): JavaScript中的隊(duì)列 要知道JavaScript中沒有有關(guān)隊(duì)列的數(shù)據(jù)模型,因此我們需要通過數(shù)組進(jìn)行模擬,當(dāng)數(shù)組中提供的push()和shift()選...
摘要:每個(gè)請(qǐng)求來的時(shí)候都會(huì)先去看看中有沒有,即使使用的是的方式也不免會(huì)讓我對(duì)它的性能產(chǎn)生一些擔(dān)憂,所以性能測(cè)試就必須要來一發(fā)了。注也在阿里云執(zhí)行只要是為了在一個(gè)數(shù)據(jù)中心降低網(wǎng)絡(luò)延遲。測(cè)試因?yàn)榭紤]到服務(wù)器比較穩(wěn)定,減少壓測(cè)總數(shù)。 背景 最近我操刀了leetcode的論壇遷移,整個(gè)過程持續(xù)了幾周的時(shí)間,總算暫時(shí)告了一個(gè)段落。常使用leetcode論壇的用戶應(yīng)該已經(jīng)發(fā)現(xiàn)論壇已經(jīng)大變樣了吧~ 期間遇...
摘要:每個(gè)請(qǐng)求來的時(shí)候都會(huì)先去看看中有沒有,即使使用的是的方式也不免會(huì)讓我對(duì)它的性能產(chǎn)生一些擔(dān)憂,所以性能測(cè)試就必須要來一發(fā)了。注也在阿里云執(zhí)行只要是為了在一個(gè)數(shù)據(jù)中心降低網(wǎng)絡(luò)延遲。測(cè)試因?yàn)榭紤]到服務(wù)器比較穩(wěn)定,減少壓測(cè)總數(shù)。 背景 最近我操刀了leetcode的論壇遷移,整個(gè)過程持續(xù)了幾周的時(shí)間,總算暫時(shí)告了一個(gè)段落。常使用leetcode論壇的用戶應(yīng)該已經(jīng)發(fā)現(xiàn)論壇已經(jīng)大變樣了吧~ 期間遇...
閱讀 3491·2023-04-25 20:41
閱讀 2660·2023-04-25 16:40
閱讀 1433·2021-09-23 11:44
閱讀 1252·2021-09-10 10:51
閱讀 1681·2021-09-07 09:59
閱讀 1642·2019-12-27 12:08
閱讀 552·2019-08-30 15:44
閱讀 3334·2019-08-30 11:08