Posts tagged as “math”

花花酱 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 43. Multiply Strings

By zxi on July 26, 2018

Problem

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution: Simulation

Simulate multiplication one digit at a time.

Time complexity: O(l1*l2)

Space complexity: O(l1 + l2)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

string multiply(string num1, string num2) {

const int l1 = num1.length();

const int l2 = num2.length();

string ans(l1 + l2, '0');

for (int i = l1 - 1; i >= 0; --i)

for (int j = l2 - 1; j >= 0; --j) {

int sum = (ans[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0');

ans[i + j + 1] = (sum % 10) + '0';

ans[i + j] += sum / 10;

}

for (int i = 0; i < ans.length(); ++i)

if (ans[i] != '0' || i == ans.length() - 1) return ans.substr(i);

return "";

}

};

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

By zxi on July 16, 2018

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);

}

};

Posts tagged as “math”

花花酱 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++

花花酱 LeetCode 43. Multiply Strings

Problem

Solution: Simulation

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

Problem

Solution: Math