【算法学习】剑指 Offer II 042 最近请求次数（

发表于

这是我参与11月更文挑战的第1天，活动详情查看：2021最后一次更文挑战

非常感谢你阅读本文~
欢迎【👍点赞】【⭐收藏】【📝评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子 https://juejin.cn/user/2771185768884824/posts 博客原创~

剑指 Offer II 042. 最近请求次数：

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请实现 RecentCounter 类：

  • RecentCounter() 初始化计数器，请求数为 0 。
  • int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

保证 每次对 ping 的调用都使用比之前更大的 t 值。

样例 1

1
2
3
4
5
6
7
8
9
10
11
12
scss复制代码输入：
    inputs = ["RecentCounter", "ping", "ping", "ping", "ping"]
    inputs = [[], [1], [100], [3001], [3002]]
输出：
    [null, 1, 2, 3, 3]

解释：
    RecentCounter recentCounter = new RecentCounter();
    recentCounter.ping(1);     // requests = [1]，范围是 [-2999,1]，返回 1
    recentCounter.ping(100);   // requests = [1, 100]，范围是 [-2900,100]，返回 2
    recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
    recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3

提示

  • 1 <= t <= 109
  • 保证每次对 ping 调用所使用的 t 值都 严格递增
  • 至多调用 ping 方法 104 次

分析

  • 二当家的觉得这道算法题相对来说还是自由度比较高的。
  • 由于有提示中第二条的规定，每次 ping 调用所使用的t值都严格递增，所以可以使用队列，如果已经和最新的t相差超过3000，就可以清除了，按顺序出队列即可，队列中元素最多也只有3000个，也就是每次 ping 最差就是不超过3000次出队列，而队列留下的值恰好就是 ping 方法返回值。
  • 由于有提示中第三条的规定，ping 的最高调用次数已经知道，如果使用可随机访问的数据结构，还可以使用二分查找，时间复杂度上会比按顺序出队列好一些，但是如果 ping 的次数是不一定的，还是用队列好。

题解

java

没有使用自带的二分查找，因为查不到是负数，不是我们想要的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
java复制代码class RecentCounter {
    private int[] q;
    private int head;
    private int tail;

    public RecentCounter() {
        q = new int[10000];
    }

    public int ping(int t) {
        head = binarySearch(q, head, tail, t - 3000);
        q[tail++] = t;
        return tail - head;
    }

    private int binarySearch(int[] a, int fromIndex, int toIndex, int key) {
        int low  = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid    = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return low;  // key not found.
    }
}

c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
c复制代码typedef struct {
    int *q;
    int head;
    int tail;
} RecentCounter;


RecentCounter *recentCounterCreate() {
    RecentCounter *recentCounter = (RecentCounter *) malloc(sizeof(RecentCounter));
    recentCounter->q = (int *) malloc(sizeof(int) * 10000);
    recentCounter->head = 0;
    recentCounter->tail = 0;
    return recentCounter;
}

int binarySearch(int *a, int fromIndex, int toIndex, int key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >> 1;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return low;  // key not found.
}

int recentCounterPing(RecentCounter *obj, int t) {
    obj->head = binarySearch(obj->q, obj->head, obj->tail, t - 3000);
    obj->q[obj->tail++] = t;
    return obj->tail - obj->head;
}

void recentCounterFree(RecentCounter *obj) {
    free(obj->q);
    free(obj);
}

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
cpp复制代码class RecentCounter {
private:
    vector<int> q;
    int head;
public:
    RecentCounter() {
        head = 0;
    }

    int binarySearch(vector<int>& a, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return low;  // key not found.
    }

    int ping(int t) {
        head = binarySearch(q, head, q.size(), t - 3000);
        q.push_back(t);
        return q.size() - head;
    }
};

python

python这次是最简洁的了，主要就是有可以直接用的二分查找。

1
2
3
4
5
6
7
8
9
10
python复制代码class RecentCounter:

    def __init__(self):
        self.q = []
        self.head = 0

    def ping(self, t: int) -> int:
        self.head = bisect.bisect_left(self.q, t - 3000, self.head)
        self.q.append(t)
        return len(self.q) - self.head

go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
go复制代码type RecentCounter struct {
    q    []int
    head int
}

func Constructor() RecentCounter {
    return RecentCounter{[]int{}, 0}
}

func (this *RecentCounter) Ping(t int) int {
    this.head = binarySearch(this.q, this.head, len(this.q), t - 3000)
    this.q = append(this.q, t)
    return len(this.q) - this.head
}

func binarySearch(a []int, fromIndex int, toIndex int, key int) int {
    low := fromIndex
    high := toIndex - 1

    for low <= high {
        mid := (low + high) >> 1
        midVal := a[mid]

        if midVal < key {
            low = mid + 1
        } else if midVal > key {
            high = mid - 1
        } else {
            return mid // key found
        }
    }
    return low // key not found.
}

rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
rust复制代码struct RecentCounter {
  q: Vec<i32>,
  head: i32,
}


/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl RecentCounter {
  fn new() -> Self {
    RecentCounter { q: Vec::new(), head: 0 }
  }

  fn ping(&mut self, t: i32) -> i32 {
    self.head = RecentCounter::binarySearch(&self.q, self.head, self.q.len() as i32, t - 3000);
    self.q.push(t);
    self.q.len() as i32 - self.head
  }

  fn binarySearch(a: &Vec<i32>, fromIndex: i32, toIndex: i32, key: i32) -> i32 {
    let mut low = fromIndex;
    let mut high = toIndex - 1;

    while low <= high {
      let mid = (low + high) >> 1;
      let midVal = a[mid as usize];

      if midVal < key {
        low = mid + 1;
      } else if midVal > key {
        high = mid - 1;
      } else {
        return mid; // key found
      }
    }
    return low;  // key not found.
  }
}

在这里插入图片描述

原题传送门：https://leetcode-cn.com/problems/H8086Q/

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%