Posts tagged as “math”

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

By zxi on July 28, 2018

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

}

};

花花酱 LeetCode 357. Count Numbers with Unique Digits

By zxi on July 16, 2018

Problem

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10ⁿ.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Solution: Math

f(0) = 1 (0)

f(1) = 10 (0 – 9)

f(2) = 9 * 9 (1-9 * (0 ~ 9 exclude the one from first digit))

f(3) = 9 * 9 * 8

f(4) = 9 * 9 * 8 * 7

…

f(x) = 0 if x >= 10

ans = sum(f[1] ~ f[n])

Time complexity: O(1)

Space complexity: O(1)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int countNumbersWithUniqueDigits(int n) {

if (n == 0) return 1;

vector<int> f(11);

f[1] = 10;

f[2] = 9 * 9;

for (int i = 3; i <= 10; ++i)

f[i] = f[i - 1] * (10 - i + 1);

int ans = 0;

for (int i = 0; i <= min(10, n); ++i)

ans += f[i];

return ans;

}

};

花花酱 LeetCode 840. Magic Squares In Grid

By zxi on July 8, 2018

Problem

A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given an grid of integers, how many 3 x 3 “magic square” subgrids are there? (Each subgrid is contiguous).

Example 1:

Input: [[4,3,8,4],
        [9,5,1,9],
        [2,7,6,2]]
Output: 1
Explanation: 
The following subgrid is a 3 x 3 magic square:
438
951
276

while this one is not:
384
519
762

In total, there is only one magic square inside the given grid.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
0 <= grid[i][j] <= 15

Solution

Time complexity: O(m*n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int numMagicSquaresInside(vector<vector<int>>& grid) {

int m = grid.size();

int n = grid[0].size();

int ans = 0;

for (int i = 0; i < m - 2; ++i)

for (int j = 0; j < n - 2; ++j)

ans += magic(grid, j, i);

return ans;

}

private:

int magic(const vector<vector<int>>& grid, int x, int y) {

vector<int> rows(3);

vector<int> cols(3);

vector<int> exps{15, 15, 15};

int dig = 0;

for (int i = 0; i < 3; ++i)

for (int j = 0; j < 3; ++j) {

int v = grid[y + i][x + j];

if (v <= 0 || v > 9) return 0; // must between 1 and 9

rows[i] += v;

cols[j] += v;

if (i == j) dig += v;

}

return rows == exps && cols == exps && dig == 15;

}

};