花花酱 LeetCode 491. Increasing Subsequences

By zxi on July 17, 2018

Problem

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:

Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

Note:

The length of the given array will not exceed 15.
The range of integer in the given array is [-100,100].
The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

Solution: DFS

Time complexity: O(2^n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 140 ms (<99.88%)

class Solution {

public:

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

vector<vector<int>> ans;

vector<int> cur;

dfs(nums, 0, cur, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, int s, vector<int>& cur, vector<vector<int>>& ans) {

unordered_set<int> seen;

for (int i = s; i < nums.size(); ++i) {

if (!cur.empty() && nums[i] < cur.back()) continue;

// each number can be used only once at the same depth.

if (seen.count(nums[i])) continue;

seen.insert(nums[i]);

cur.push_back(nums[i]);

if (cur.size() > 1)

ans.push_back(cur);

dfs(nums, i + 1, cur, ans);

cur.pop_back();

}

};

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

}

};

Posts published in July 2018

花花酱 LeetCode 491. Increasing Subsequences

Problem

Solution: DFS

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