Problem

Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.

Do NOT use system’s Math.random().

Example 1:

Input: 1
Output: [7]

Example 2:

Input: 2
Output: [8,4]

Example 3:

Input: 3
Output: [8,1,10]

Note:

rand7 is predefined.
Each testcase has one argument: n, the number of times that rand10 is called.

Solution: Math

Time complexity: O(49/40) = O(1)

// Author: Huahua

// Running time: 112 ms

class Solution {

public:

int rand10() {

int target = 40;

while (target >= 40)

target = 7 * (rand7() - 1) + (rand7() - 1);

return target % 10 + 1;

}

};

Time complexity: O(7/6 + 7 / 5) = O(1)

// Author: Huahua

// Running time: 112 ms

class Solution {

public:

int rand10() {

int i = INT_MAX;

int j = INT_MAX;

while (i > 6) i = rand7(); // i = [1, 2, 3, 4, 5, 6]

while (j > 5) j = rand7(); // j = [1, 2, 3, 4, 5]

return j + 5 * (i & 1);

}

};

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”.

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Your implementation should support following operations:

MyCircularQueue(k): Constructor, set the size of the queue to be k.
Front: Get the front item from the queue. If the queue is empty, return -1.
Rear: Get the last item from the queue. If the queue is empty, return -1.
enQueue(value): Insert an element into the circular queue. Return true if the operation is successful.
deQueue(): Delete an element from the circular queue. Return true if the operation is successful.
isEmpty(): Checks whether the circular queue is empty or not.
isFull(): Checks whether the circular queue is full or not.

Example:

MyCircularQueue circularQueue = new MyCircularQueue(3); // set the size to be 3
circularQueue.enQueue(1);  // return true
circularQueue.enQueue(2);  // return true
circularQueue.enQueue(3);  // return true
circularQueue.enQueue(4);  // return false, the queue is full
circularQueue.Rear();  // return 3
circularQueue.isFull();  // return true
circularQueue.deQueue();  // return true
circularQueue.enQueue(4);  // return true
circularQueue.Rear();  // return 4

Note:

All values will be in the range of [0, 1000].
The number of operations will be in the range of [1, 1000].
Please do not use the built-in Queue library.

Solution: Simulate with an array

We need a fixed length array, and the head location as well as the size of the current queue.

We can use q[head] to access the front, and q[(head + size – 1) % k] to access the rear.

Time complexity: O(1) for all the operations.
Space complexity: O(k)

C++

// Author: Huahua

class MyCircularQueue {

public:

MyCircularQueue(int k): q_(k) {}

bool enQueue(int value) {

if (isFull()) return false;

q_[(head_ + size_) % q_.size()] = value;

++size_;

return true;

}

bool deQueue() {

if (isEmpty()) return false;

head_ = (head_ + 1) % q_.size();

--size_;

return true;

}

int Front() { return isEmpty() ? -1 : q_[head_]; }

int Rear() { return isEmpty() ? -1 : q_[(head_ + size_ - 1) % q_.size()]; }

bool isEmpty() { return size_ == 0; }

bool isFull() { return size_ == q_.size(); }

private:

vector<int> q_;

int head_ = 0;

int size_ = 0;

};

Java

class MyCircularQueue {

private int[] q;

private int head;

private int size;

public MyCircularQueue(int k) {

this.q = new int[k];

this.head = 0;

this.size = 0;

}

public boolean enQueue(int value) {

if (this.isFull()) return false;

this.q[(this.head + this.size) % this.q.length] = value;

++this.size;

return true;

}

public boolean deQueue() {

if (this.isEmpty()) return false;

this.head = (this.head + 1) % this.q.length;

--this.size;

return true;

}

public int Front() {

return this.isEmpty() ? -1 : this.q[this.head];

}

public int Rear() {

return this.isEmpty() ? -1 : this.q[(this.head + this.size - 1) % this.q.length];

}

public boolean isEmpty() { return this.size == 0; }

public boolean isFull() { return this.size == this.q.length; }

}

Python3

class MyCircularQueue:

def __init__(self, k: int):

self.q = [0] * k

self.k = k

self.head = self.size = 0

def enQueue(self, value: int) -> bool:

if self.isFull(): return False

self.q[(self.head + self.size) % self.k] = value

self.size += 1

return True

def deQueue(self) -> bool:

if self.isEmpty(): return False

self.head = (self.head + 1) % self.k

self.size -= 1

return True

def Front(self) -> int:

return -1 if self.isEmpty() else self.q[self.head]

def Rear(self) -> int:

return -1 if self.isEmpty() else self.q[(self.head + self.size - 1) % self.k]

def isEmpty(self) -> bool:

return self.size == 0

def isFull(self) -> bool:

return self.size == self.k

Posts published in “Desgin”

花花酱 LeetCode 872. Implement Rand10() Using Rand7()

Problem

Solution: Math

花花酱 LeetCode 622. Design Circular Queue

Solution: Simulate with an array

C++

Java

Python3