January 2019 – Page 5 – Huahua’s Tech Road

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.

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;

}

};

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

}

};

Posts published in January 2019

花花酱 LeetCode 969. Pancake Sorting

Solution: Simulation

C++

花花酱 LeetCode 313. Super Ugly Number

Solution 1: Set

C++

Solution 2: Priority Queue

C++