Huahua’s Tech Road

花花酱 LeetCode 970. Powerful Integers

By zxi on January 5, 2019

Given two non-negative integers x and y, an integer is powerful if it is equal to x^i + y^j for some integers i >= 0 and j >= 0.

Return a list of all powerful integers that have value less than or equal to bound.

You may return the answer in any order. In your answer, each value should occur at most once.

Example 1:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation: 
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2

Example 2:

Input: x = 3, y = 5, bound = 15
Output: [2,4,6,8,10,14]

Note:

1 <= x <= 100
1 <= y <= 100
0 <= bound <= 10^6

Solution: Brute Force

Time complexity: O(log(bound) / log(x) * log(bound) / log(y))
Space complexity: O(log(bound) / log(x) * log(bound) / log(y))

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<int> powerfulIntegers(int x, int y, int bound) {

unordered_set<int> ans;

for (int a = 1; a < bound; a *= x) {

for (int b = 1; a + b <= bound; b *= y) {

ans.insert(a + b);

if (y == 1) break;

}

if (x == 1) break;

}

return {begin(ans), end(ans)};

}

};

花花酱 LeetCode 969. Pancake Sorting

By zxi on January 5, 2019

Given an array A, we can perform a pancake flip: We choose some positive integer k <= A.length, then reverse the order of the first k elements of A. We want to perform zero or more pancake flips (doing them one after another in succession) to sort the array A.

Return the k-values corresponding to a sequence of pancake flips that sort A. Any valid answer that sorts the array within 10 * A.length flips will be judged as correct.

Example 1:

Input: [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: A = [3, 2, 4, 1]
After 1st flip (k=4): A = [1, 4, 2, 3]
After 2nd flip (k=2): A = [4, 1, 2, 3]
After 3rd flip (k=4): A = [3, 2, 1, 4]
After 4th flip (k=3): A = [1, 2, 3, 4], which is sorted.

Example 2:

Input: [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.

Note:

1 <= A.length <= 100
A[i] is a permutation of [1, 2, ..., A.length]

Solution: Simulation

Put the largest element to its position. Each element requires two flips
e.g. [3, 2, 4, 1]
largest element: 4, index: 2
flip1: [4, 2, 3, 1]
flip2: [1, 3, 2, 4]
Repeat for [1, 3, 2]…

Time complexity: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

vector<int> pancakeSort(vector<int>& A) {

const int n = A.size();

vector<int> ans;

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

int p = max_element(begin(A), end(A) - i) - begin(A);

ans.push_back(p + 1);

std::reverse(begin(A), begin(A) + p + 1);

ans.push_back(n - i);

std::reverse(begin(A), begin(A) + n - i);

}

return ans;

}

};

花花酱 LeetCode 313. Super Ugly Number

By zxi on January 2, 2019

Write a program to find the n^th super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k.

Example:

Input: n = 12, primes = [2,7,13,19] 
Output: 32  
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12               super ugly numbers given primes = [2,7,13,19] of size 4.

Note:

1 is a super ugly number for any given primes.
The given numbers in primes are in ascending order.
0 < k ≤ 100, 0 < n ≤ 10⁶, 0 < primes[i] < 1000.
The n^th super ugly number is guaranteed to fit in a 32-bit signed integer.

Solution 1: Set

Maintain an ordered set of super ugly numbers, each time extract the smallest one, and multiply it with all primes and insert the new number into set.

Time complexity: O(n*k*logn)
Space complexity: O(n)

C++

// Author: Huahua, running time: 484 ms

class Solution {

public:

int nthSuperUglyNumber(int n, vector<int>& primes) {

if (n == 1) return 1;

set<int> q{begin(primes), end(primes)};

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

auto it = begin(q);

int t = *it;

q.erase(it);

for (int p : primes) {

if (INT_MAX / t < p) continue;

q.insert(p * t);

}

return *begin(q);

}

};

Solution 2: Priority Queue

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua, 40 ms

struct Node {

int num;

int index;

int prime;

bool operator>(const Node& o) const {

if (this->num == o.num) return this->index > o.index;

return this->num > o.num;

}

};

class Solution {

public:

int nthSuperUglyNumber(int n, vector<int>& primes) {

if (n == 1) return 1;

vector<int> nums(n, 1);

priority_queue<Node, vector<Node>, greater<Node>> q;

for (int p : primes)

q.push({p, 1, p});

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

nums[i] = q.top().num;

while (nums[i] == q.top().num) {

Node node = std::move(q.top()); q.pop();

node.num = nums[node.index++] * node.prime;

q.push(std::move(node));

}

return nums.back();

}

};

花花酱 LeetCode 968. Binary Tree Cameras

By zxi on December 31, 2018

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Example 1:

Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Note:

The number of nodes in the given tree will be in the range [1, 1000].
Every node has value 0.

Solution: Greedy + Recursion

Time complexity: O(n)
Space complexity: O(h)

C++

enum class State { NONE = 0, COVERED = 1, CAMERA = 2 };

class Solution {

public:

int minCameraCover(TreeNode* root) {

if (dfs(root) == State::NONE) ++ans_;

return ans_;

}

private:

int ans_ = 0;

State dfs(TreeNode* root) {

if (!root) return State::COVERED;

State l = dfs(root->left);

State r = dfs(root->right);

if (l == State::NONE || r == State::NONE) {

++ans_;

return State::CAMERA;

}

if (l == State::CAMERA || r == State::CAMERA)

return State::COVERED;

return State::NONE;

}

};

花花酱 LeetCode 967. Numbers With Same Consecutive Differences

By zxi on December 30, 2018

Problem

Return all non-negative integers of length N such that the absolute difference between every two consecutive digits is K.

Note that every number in the answer must not have leading zeros except for the number 0 itself. For example, 01 has one leading zero and is invalid, but 0 is valid.

You may return the answer in any order.

Example 1:

Input: N = 3, K = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

Example 2:

Input: N = 2, K = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Note:

1 <= N <= 9
0 <= K <= 9

Solution: Search

Time complexity: O(2^N)
Space complexity: O(N)

C++/DFS

// Author: Huahua, running time: 8ms

class Solution {

public:

vector<int> numsSameConsecDiff(int N, int K) {

vector<int> ans;

if (N == 1) ans.push_back(0);

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

dfs(N - 1, K, i, ans);

return ans;

}

private:

void dfs(int N, int K, int cur, vector<int>& ans) {

if (N == 0) {

ans.push_back(cur);

return;

}

int l = cur % 10;

if (l + K < 10)

dfs(N - 1, K, cur * 10 + l + K, ans);

if (l >= K && K != 0)

dfs(N - 1, K, cur * 10 + l - K, ans);

}

};

C++/BFS

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<int> numsSameConsecDiff(int N, int K) {

deque<int> q{1,2,3,4,5,6,7,8,9};

if (N == 1) q.push_front(0);

while (--N) {

int size = q.size();

while (size--) {

int num = q.front(); q.pop_front();

int r = num % 10;

if (r + K <= 9)

q.push_back(num * 10 + r + K);

if (r - K >= 0 && K != 0)

q.push_back(num * 10 + r - K);

}

return vector<int>(cbegin(q), cend(q));

}

};

Huahua's Tech Road

花花酱 LeetCode 970. Powerful Integers

Solution: Brute Force

C++

花花酱 LeetCode 969. Pancake Sorting

Solution: Simulation

C++

花花酱 LeetCode 313. Super Ugly Number

Solution 1: Set

C++

Solution 2: Priority Queue

C++

花花酱 LeetCode 968. Binary Tree Cameras

Solution: Greedy + Recursion

C++

花花酱 LeetCode 967. Numbers With Same Consecutive Differences

Problem

Solution: Search

C++/DFS

C++/BFS