{"id":4248,"date":"2018-11-04T01:20:59","date_gmt":"2018-11-04T08:20:59","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4248"},"modified":"2018-11-04T01:21:56","modified_gmt":"2018-11-04T08:21:56","slug":"leetcode-933-number-of-recent-calls","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/queue\/leetcode-933-number-of-recent-calls\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 933. Number of Recent Calls"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Write a class\u00a0RecentCounter<\/code>\u00a0to count recent requests.<\/p>\n

It has only one method:\u00a0ping(int t)<\/code>, where t represents some time in milliseconds.<\/p>\n

Return the number of\u00a0ping<\/code>s that have been made from 3000 milliseconds ago until now.<\/p>\n

Any ping with time in\u00a0[t - 3000, t]<\/code>\u00a0will count, including the current ping.<\/p>\n

It is guaranteed that every call to\u00a0ping<\/code>\u00a0uses a strictly larger value of\u00a0t<\/code>\u00a0than before.<\/p>\n

Example 1:<\/strong><\/p>\n

Input: <\/strong>inputs = [\"RecentCounter\",\"ping\",\"ping\",\"ping\",\"ping\"]<\/span>, inputs = [[],[1],[100],[3001],[3002]]<\/span>\r\nOutput: <\/strong>[null,1,2,3,3]<\/span><\/pre>\n
Note:<\/strong><\/p>\n
    \n
  1. Each test case will have at most\u00a010000<\/code>\u00a0calls to\u00a0ping<\/code>.<\/li>\n
  2. Each test case will call\u00a0ping<\/code>\u00a0with strictly increasing values of\u00a0t<\/code>.<\/li>\n
  3. Each call to ping will have\u00a01 <= t <= 10^9<\/code>.<\/li>\n<\/ol>\n
    Solution: Queue<\/h1>\n
    Use a FIFO queue to track all the previous pings that are within 3000 ms to current.<\/p>\n
    Time complexity: Avg O(1), Total O(n)<\/p>\n
    Space complexity: O(n)<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    class RecentCounter {\r\npublic:\r\n    RecentCounter() {}\r\n    \r\n    int ping(int t) {\r\n      while (!q.empty() && t - q.front() > 3000) q.pop();\r\n      q.push(t);\r\n      return q.size();\r\n    }\r\nprivate:\r\n  queue<int> q;\r\n};<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem Write a class\u00a0RecentCounter\u00a0to count recent requests. It has only one method:\u00a0ping(int t), where t represents some time in milliseconds. Return the number of\u00a0pings that…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[429],"tags":[222,213],"class_list":["post-4248","post","type-post","status-publish","format-standard","hentry","category-queue","tag-easy","tag-queue","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4248","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4248"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4248\/revisions"}],"predecessor-version":[{"id":4250,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4248\/revisions\/4250"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4248"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4248"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4248"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}