359. Logger Rate Limiter & 362. Design Hit Cou

go4it 發(fā)布于2019-08-14 17:27 / 1226人閱讀

摘要：題目鏈接和基本一樣，都可以用，但是大了之后會(huì)有很多無效的時(shí)間保存在里面，要的話，可能需要遍歷或者用輔助，時(shí)間復(fù)雜度超過，所以用一個(gè)來做，每次根據(jù)新的改變。

359. Logger Rate Limiter

題目鏈接：https://leetcode.com/problems...

和Design Hit Counter基本一樣，都可以用hashmap，但是timestamp大了之后會(huì)有很多無效的時(shí)間保存在hashmap里面，要remove的話，可能需要遍歷hashmap或者用list輔助，時(shí)間復(fù)雜度超過O(1)，所以用一個(gè)rotate array來做，每次根據(jù)新的timestamp改變array。

public class Logger {
    Set[] record;
    int[] times;
    public Logger() {
        record = new Set[10];
        for(int i = 0; i < record.length; i++) record[i] = new HashSet();
        times = new int[10];
        Arrays.fill(times, -10);
    }
    
    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity. */
    public boolean shouldPrintMessage(int timestamp, String message) {
        for(int i = 0; i < times.length; i++) {
            if(timestamp - times[i] < 10 && record[i].contains(message)) {
                return false;
            }
        }
        int index = timestamp % 10;
        if(timestamp - times[index] >= 10) {
            // rotate
            times[index] = timestamp;
            record[index] = new HashSet();
        }
        record[index].add(message);
        return true;
    }
}

362. Design Hit Counter

題目鏈接：https://leetcode.com/problems...

public class HitCounter {

    /** Initialize your data structure here. */
    int[] times;
    int[] hits;
    public HitCounter() {
        times = new int[300];
        hits = new int[300];
    }
    
    public void hit(int timestamp) {
        if(times[timestamp%300] != timestamp) {
            times[timestamp%300] = timestamp;
            hits[timestamp%300] = 1;
        }
        else hits[timestamp%300]++;
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        int count = 0;
        for(int i = 0; i < 300; i++) {
            if(timestamp - times[i] < 300) {
                count += hits[i];
            }
        }
        return count;
    }
}