花花酱 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 238. Product of Array Except Self

By zxi on July 16, 2018

Problem:

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4] Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

Solution: DP

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 36 ms

class Solution {

public:

vector<int> productExceptSelf(vector<int>& nums) {

const int n = nums.size();

vector<int> l(n, 1); // l[i] = prod(nums[0] ~ nums[i - 1])

vector<int> r(n, 1); // l[i] = prod(nums[i + 1] ~ nums[n - 1])

vector<int> ans(n);

for (int i = 1; i < n; ++i)

l[i] = l[i - 1] * nums[i - 1];

for (int i = n - 2; i >= 0; --i)

r[i] = r[i + 1] * nums[i + 1];

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

ans[i] = l[i] * r[i];

return ans;

}

};

// Author: Huahua

// Running time: 32 ms

class Solution {

public:

vector<int> productExceptSelf(vector<int>& nums) {

const int n = nums.size();

int l = 1; // l = prod(nums[0] ~ nums[i - 1])

int r = 1; // r = prod(nums[i + 1] ~ nums[n - 1])

vector<int> ans(n, 1);

for (int i = 0; i < n; ++i) {

ans[i] *= l;

ans[n - i - 1] *= r;

l *= nums[i];

r *= nums[n - i - 1];

}

return ans;

}

};

花花酱 LeetCode 739. Daily Temperatures

By zxi on July 16, 2018

Problem

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

Solution: Stack

Use a stack to track indices of future warmer days. From top to bottom: recent to far away.

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 148 ms

class Solution {

public:

vector<int> dailyTemperatures(vector<int>& temperatures) {

const int n = temperatures.size();

stack<int> s;

vector<int> ans(n);

for (int i = n - 1; i >= 0; --i) {

while (!s.empty() && temperatures[s.top()] <= temperatures[i]) s.pop();

ans[i] = s.empty() ? 0 : s.top() - i;

s.push(i);

}

return ans;

}

};

花花酱 LeetCode 870. Advantage Shuffle

By zxi on July 14, 2018

Problem

Given two arrays A and B of equal size, the advantage of A with respect to B is the number of indices i for which A[i] > B[i].

Return any permutation of A that maximizes its advantage with respect to B.

Example 1:

Input: A = [2,7,11,15], B = [1,10,4,11]
Output: [2,11,7,15]

Example 2:

Input: A = [12,24,8,32], B = [13,25,32,11]
Output: [24,32,8,12]

Note:

1 <= A.length = B.length <= 10000
0 <= A[i] <= 10^9
0 <= B[i] <= 10^9

Solution: Greedy 田忌赛马

Use the smallest unused number A[j] in A such that A[j] > B[i], if not possible, use the smallest number in A.

Time complexity: O(nlogn)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 124 ms

class Solution {

public:

vector<int> advantageCount(vector<int>& A, vector<int>& B) {

multiset<int> s(begin(A), end(A));

vector<int> ans;

for (int b : B) {

auto it = s.upper_bound(b);

if (it == s.end()) it = s.begin();

ans.push_back(*it);

s.erase(it);

}

return ans;

}

};

Posts tagged as “medium”

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

Problem

Solution: Math

花花酱 LeetCode 357. Count Numbers with Unique Digits

Problem

Solution: Math

花花酱 LeetCode 238. Product of Array Except Self

Problem:

Solution: DP

花花酱 LeetCode 739. Daily Temperatures

Problem

Solution: Stack

花花酱 LeetCode 870. Advantage Shuffle

Problem

Solution: Greedy 田忌赛马