Posts tagged as “medium”

花花酱 LeetCode 855. Exam Room

By zxi on July 29, 2018

Problem

In an exam room, there are N seats in a single row, numbered 0, 1, 2, ..., N-1.

When a student enters the room, they must sit in the seat that maximizes the distance to the closest person. If there are multiple such seats, they sit in the seat with the lowest number. (Also, if no one is in the room, then the student sits at seat number 0.)

Return a class ExamRoom(int N) that exposes two functions: ExamRoom.seat() returning an int representing what seat the student sat in, and ExamRoom.leave(int p) representing that the student in seat number p now leaves the room. It is guaranteed that any calls to ExamRoom.leave(p) have a student sitting in seat p.

Example 1:

Input: ["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
Output: [null,0,9,4,2,null,5]
Explanation:
ExamRoom(10) -> null
seat() -> 0, no one is in the room, then the student sits at seat number 0.
seat() -> 9, the student sits at the last seat number 9.
seat() -> 4, the student sits at the last seat number 4.
seat() -> 2, the student sits at the last seat number 2.
leave(4) -> null
seat() -> 5, the student sits at the last seat number 5.

Note:

1 <= N <= 10^9
ExamRoom.seat() and ExamRoom.leave() will be called at most 10^4 times across all test cases.
Calls to ExamRoom.leave(p) are guaranteed to have a student currently sitting in seat number p.

Solution: BST

Use a BST (ordered set) to track the current seatings.

Time Complexity:

init: O(1)

seat: O(P)

leave: O(logP)

Space complexity: O(P)

// Author: Huahua

// Running time: 24 ms

class ExamRoom {

public:

ExamRoom(int N): N_(N) {}

int seat() {

int p = 0;

int max_dist = s_.empty() ? 0 : *s_.begin();

auto left = s_.begin();

auto right = left;

while (left != s_.end()) {

++right;

int l = *left;

int r = right != s_.end() ? *right : (2 * (N_ - 1) - *left);

int d = (r - l) / 2;

if (d > max_dist) {

max_dist = d;

p = l + d;

}

left = right;

}

s_.insert(p);

return p;

}

void leave(int p) {

s_.erase(p);

}

private:

const int N_;

set<int> s_;

};

花花酱 LeetCode 882. Random Point in Non-overlapping Rectangles

By zxi on July 28, 2018

Problem

Given a list of non-overlapping axis-aligned rectangles rects, write a function pick which randomly and uniformily picks an integer point in the space covered by the rectangles.

Note:

An integer point is a point that has integer coordinates.
A point on the perimeter of a rectangle is included in the space covered by the rectangles.
ith rectangle = rects[i] = [x1,y1,x2,y2], where [x1, y1] are the integer coordinates of the bottom-left corner, and [x2, y2] are the integer coordinates of the top-right corner.
length and width of each rectangle does not exceed 2000.
1 <= rects.length <= 100
pick return a point as an array of integer coordinates [p_x, p_y]
pick is called at most 10000 times.

Example 1:

Input: 
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
Output: 
[null,[4,1],[4,1],[3,3]]

Example 2:

Input: 
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
Output: 
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution‘s constructor has one argument, the array of rectangles rects. pick has no arguments. Arguments are always wrapped with a list, even if there aren’t any.

Solution: Binary Search

Same as LeetCode 880. Random Pick with Weight

Use area of the rectangles as weights.

Time complexity: Init: O(n) Pick: O(logn)

Space complexity: O(n)

// Author: Huahua

// Running time: 92 ms

class Solution {

public:

Solution(vector<vector<int>> rects): rects_(std::move(rects)) {

sums_ = vector<int>(rects_.size());

for (int i = 0; i < rects_.size(); ++i) {

sums_[i] = (rects_[i][2] - rects_[i][0] + 1) * (rects_[i][3] - rects_[i][1] + 1);

if (i > 0) sums_[i] += sums_[i - 1];

}

vector<int> pick() {

const int s = nextInt(sums_.back()) + 1;

int index = lower_bound(sums_.begin(), sums_.end(), s) - sums_.begin();

const auto& rect = rects_[index];

return {rect[0] + nextInt(rect[2] - rect[0] + 1),

rect[1] + nextInt(rect[3] - rect[1] + 1)};

}

private:

vector<int> sums_;

vector<vector<int>> rects_;

// Returns a random int in [0, n - 1]

int nextInt(int n) {

return rand() / static_cast<double>(RAND_MAX) * n;

}

};

Problem

Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.

Note:

1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex will be called at most 10000 times.

Example 1:

Input: 
["Solution","pickIndex"]
[[[1]],[]]
Output: [null,0]

Example 2:

Input: 
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output: [null,0,1,1,1,0]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution‘s constructor has one argument, the array w. pickIndex has no arguments. Arguments are always wrapped with a list, even if there aren’t any.

Solution: Binary Search

Convert PDF to CDF
Uniformly sample a value s in [1, sum(weights)].
Use binary search to find first index such that PDF[index] >= s.

Time complexity: Init O(n), query O(logn)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 184 ms

class Solution {

public:

Solution(vector<int> w) {

sums_ = std::move(w);

for (int i = 1; i < sums_.size(); ++i)

sums_[i] += sums_[i - 1];

}

int pickIndex() {

int s = rand() / static_cast<double>(RAND_MAX) * sums_.back() + 1;

return lower_bound(sums_.begin(), sums_.end(), s) - sums_.begin();

// or

// int l = 0;

// int r = sums_.size();

// while (l < r) {

// int m = (r - l) / 2 + l;

// if (sums_[m] < s)

// l = m + 1;

// else

// r = m;

// }

// return l;

}

private:

vector<int> sums_;

};

Problem

Given the radius and x-y positions of the center of a circle, write a function randPoint which generates a uniform random point in the circle.

Note:

input and output values are in floating-point.
radius and x-y position of the center of the circle is passed into the class constructor.
a point on the circumference of the circle is considered to be in the circle.
randPoint returns a size 2 array containing x-position and y-position of the random point, in that order.

Example 1:

Input: 
["Solution","randPoint","randPoint","randPoint"]
[[1,0,0],[],[],[]]
Output: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]

Example 2:

Input: 
["Solution","randPoint","randPoint","randPoint"]
[[10,5,-7.5],[],[],[]]
Output: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution‘s constructor has three arguments, the radius, x-position of the center, and y-position of the center of the circle. randPoint has no arguments. Arguments are always wrapped with a list, even if there aren’t any.

Solution: Polar Coordinate

uniform sample an angle a: [0, 2*Pi)

uniform sample a radius r: [0, 1)

Number of random points in a cycle should be proportional to the square of distance to the center.

e.g. there are 4 times of points with distance d than points with distance d/2.

Thus sqrt(r) is uniformly distributed.

r’ = sqrt(r),

C++

// Author: Huahua

// Running time: 116 ms

class Solution {

public:

Solution(double radius, double x_center, double y_center)

:r_(radius), x_(x_center), y_(y_center) {}

vector<double> randPoint() {

double a = rand() / static_cast<double>(RAND_MAX) * 2 * M_PI;

double r = sqrt(rand() / static_cast<double>(RAND_MAX)) * r_;

return {x_ + r * cos(a), y_ + r * sin(a)};

}

private:

double r_;

double x_;

double y_;

};

花花酱 LeetCode 148. Sort List

By zxi on July 26, 2018

Problem

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Solution: Merge Sort

Top-down (recursion)

Time complexity: O(nlogn)

Space complexity: O(logn)

C++

// Author: Huahua

// Running time: 32 ms

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

ListNode* sortList(ListNode* head) {

// 0 or 1 element, we are done.

if (!head || !head->next) return head;

ListNode* slow = head;

ListNode* fast = head->next;

while (fast && fast->next) {

fast = fast->next->next;

slow = slow->next;

}

ListNode* mid = slow->next;

slow->next = nullptr; // Break the list.

return merge(sortList(head), sortList(mid));

}

private:

ListNode* merge(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

while (l1 && l2) {

if (l1->val > l2->val) swap(l1, l2);

tail->next = l1;

l1 = l1->next;

tail = tail->next;

}

tail->next = l1 ? l1 : l2;

return dummy.next;

}

};

Java

// Author: Huahua

// Running time: 6 ms

class Solution {

public ListNode sortList(ListNode head) {

if (head == null || head.next == null) return head;

ListNode slow = head;

ListNode fast = head.next;

while (fast != null && fast.next != null) {

fast = fast.next.next;

slow = slow.next;

}

ListNode mid = slow.next;

slow.next = null;

return merge(sortList(head), sortList(mid));

}

private ListNode merge(ListNode l1, ListNode l2) {

ListNode dummy = new ListNode(0);

ListNode tail = dummy;

while (l1 != null && l2 != null) {

if (l1.val > l2.val) {

ListNode tmp = l1;

l1 = l2;

l2 = tmp;

}

tail.next = l1;

l1 = l1.next;

tail = tail.next;

}

tail.next = (l1 != null) ? l1 : l2;

return dummy.next;

}

Python3

# Author: Huahua, 232 ms

class Solution:

def sortList(self, head):

def merge(l1, l2):

dummy = ListNode(0)

tail = dummy

while l1 and l2:

if l1.val > l2.val: l1, l2 = l2, l1

tail.next = l1

l1 = l1.next

tail = tail.next

tail.next = l1 if l1 else l2

return dummy.next

if not head or not head.next: return head

slow = head

fast = head.next

while fast and fast.next:

fast = fast.next.next

slow = slow.next

mid = slow.next

slow.next = None

return merge(self.sortList(head), self.sortList(mid))

bottom up

Time complexity: O(nlogn)

Space complexity: O(1)

// Author: Huahua

// Running time: 32 ms

class Solution {

public:

ListNode* sortList(ListNode* head) {

// 0 or 1 element, we are done.

if (!head || !head->next) return head;

int len = 1;

ListNode* cur = head;

while (cur = cur->next) ++len;

ListNode dummy(0);

dummy.next = head;

ListNode* l;

ListNode* r;

ListNode* tail;

for (int n = 1; n < len; n <<= 1) {

cur = dummy.next; // partial sorted head

tail = &dummy;

while (cur) {

l = cur;

r = split(l, n);

cur = split(r, n);

auto merged = merge(l, r);

tail->next = merged.first;

tail = merged.second;

}

return dummy.next;

}

private:

// Splits the list into two parts, first n element and the rest.

// Returns the head of the rest.

ListNode* split(ListNode* head, int n) {

while (--n && head)

head = head->next;

ListNode* rest = head ? head->next : nullptr;

if (head) head->next = nullptr;

return rest;

}

// Merges two lists, returns the head and tail of the merged list.

pair<ListNode*, ListNode*> merge(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

while (l1 && l2) {

if (l1->val > l2->val) swap(l1, l2);

tail->next = l1;

l1 = l1->next;

tail = tail->next;

}

tail->next = l1 ? l1 : l2;

while (tail->next) tail = tail->next;

return {dummy.next, tail};

}

};

Posts tagged as “medium”

花花酱 LeetCode 855. Exam Room

Problem

Solution: BST

花花酱 LeetCode 882. Random Point in Non-overlapping Rectangles

Problem

Solution: Binary Search

Related Problems

花花酱 LeetCode 880. Random Pick with Weight

Problem

Solution: Binary Search

Related Problems

花花酱 LeetCode 883. Generate Random Point in a Circle

Problem

Solution: Polar Coordinate

C++