Posts tagged as “medium”

花花酱 LeetCode 638. Shopping Offers

By zxi on August 6, 2018

Problem

In LeetCode Store, there are some kinds of items to sell. Each item has a price.

However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.

You are given the each item’s price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.

Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.

You could use any of special offers as many times as you want.

Example 1:

Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation: 
There are two kinds of items, A and B. Their prices are $2 and $5 respectively. 
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B. 
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.

Example 2:

Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation: 
The price of A is $2, and $3 for B, $4 for C. 
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C. 
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C. 
You cannot add more items, though only $9 for 2A ,2B and 1C.

Note:

There are at most 6 kinds of items, 100 special offers.
For each item, you need to buy at most 6 of them.
You are not allowed to buy more items than you want, even if that would lower the overall price.

Solution: Search

Try all combinations.

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {

int with_offer = INT_MAX;

for (const auto& offer : special) {

vector<int> new_needs(needs);

bool valid_offer = true;

for (int i = 0; i < price.size(); ++i)

if (!(valid_offer &= ((new_needs[i] -= offer[i]) >= 0)))

break;

if (!valid_offer) continue;

with_offer = min(with_offer, shoppingOffers(price, special, new_needs) + offer.back());

}

int without_offer = inner_product(begin(price), end(price), begin(needs), 0);

return min(with_offer, without_offer);

}

};

花花酱 LeetCode 592. Fraction Addition and Subtraction

By zxi on August 6, 2018

Problem

Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result should be irreducible fraction. If your final result is an integer, say 2, you need to change it to the format of fraction that has denominator 1. So in this case, 2 should be converted to 2/1.

Example 1:

Input:"-1/2+1/2"
Output: "0/1"

Example 2:

Input:"-1/2+1/2+1/3"
Output: "1/3"

Example 3:

Input:"1/3-1/2"
Output: "-1/6"

Example 4:

Input:"5/3+1/3"
Output: "2/1"

Note:

The input string only contains '0' to '9', '/', '+' and '-'. So does the output.
Each fraction (input and output) has format ±numerator/denominator. If the first input fraction or the output is positive, then '+' will be omitted.
The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1,10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.
The number of given fractions will be in the range [1,10].
The numerator and denominator of the final result are guaranteed to be valid and in the range of 32-bit int.

Solution: Math

a/b+c/d = (a*d + b * c) / (b * d)

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string fractionAddition(string expression) {

int a = 0;

int b = 1;

int c;

int d;

char slash;

istringstream in(expression);

while (in >> c >> slash >> d) {

a = a * d + b * c;

b *= d;

int gcd = abs(__gcd(a, b));

a /= gcd;

b /= gcd;

}

return to_string(a) + "/" + to_string(b);

}

};

C++/class

// Author: Huahua

// Running time: 0 ms

class Fraction {

public:

Fraction(int a, int b): a_(a), b_(b) {}

Fraction& operator+=(const Fraction& f) {

a_ = a_ * f.b_ + b_ * f.a_;

b_ = b_ * f.b_;

int d = abs(__gcd(a_, b_));

a_ /= d;

b_ /= d;

return *this;

}

string toString() {

return to_string(a_) + "/" + to_string(b_);

}

private:

int a_; // hold the sign, e.g. can be +-.

int b_; // always > 0.

};

class Solution {

public:

string fractionAddition(string expression) {

Fraction f(0, 1);

int a;

int b;

char op;

istringstream in(expression);

while (in >> a >> op >> b)

f += Fraction(a, b);

return f.toString();

}

};

花花酱 LeetCode 885. Boats to Save People

By zxi on August 4, 2018

Problem

The i-th person has weight people[i], and each boat can carry a maximum weight of limit.

Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person. (It is guaranteed each person can be carried by a boat.)

Example 1:

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

Example 2:

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

Example 3:

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

Note:

1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000

Solution: Greedy + Two Pointers

Time complexity: O(nlogn)

Space complexity: O(1)

Put one heaviest guy and put the lightest guy if not full.

// Author: Huahua

// Running time: 80 ms

class Solution {

public:

int numRescueBoats(vector<int>& people, int limit) {

sort(people.rbegin(), people.rend());

int i = 0;

int j = people.size() - 1;

int ans = 0;

while (i <= j) {

++ans;

if (i == j) break;

if (people[i++] + people[j] <= limit) --j;

}

return ans;

}

};

花花酱 LeetCode 808. Soup Servings

By zxi on August 1, 2018

Problem

There are two types of soup: type A and type B. Initially we have N ml of each type of soup. There are four kinds of operations:

Serve 100 ml of soup A and 0 ml of soup B
Serve 75 ml of soup A and 25 ml of soup B
Serve 50 ml of soup A and 50 ml of soup B
Serve 25 ml of soup A and 75 ml of soup B

When we serve some soup, we give it to someone and we no longer have it. Each turn, we will choose from the four operations with equal probability 0.25. If the remaining volume of soup is not enough to complete the operation, we will serve as much as we can. We stop once we no longer have some quantity of both types of soup.

Note that we do not have the operation where all 100 ml’s of soup B are used first.

Return the probability that soup A will be empty first, plus half the probability that A and B become empty at the same time.

Example:
Input: N = 50
Output: 0.625
Explanation: 
If we choose the first two operations, A will become empty first. For the third operation, A and B will become empty at the same time. For the fourth operation, B will become empty first. So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.25 * (1 + 1 + 0.5 + 0) = 0.625.

Notes:

0 <= N <= 10^9.
Answers within 10^-6 of the true value will be accepted as correct.

Solution 1: Recursion with Memorization

Time complexity: O(N^2) N ~ 5000 / 25 = 200

Space complexity: O(N^2)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

double soupServings(int N) {

if (N >= 5000) return 1.0;

return prob(N, N);

}

private:

unordered_map<int, unordered_map<int, double>> m_;

double prob(int A, int B) {

static int ops[][2] = {{100, 0}, {75, 25}, {50, 50}, {25, 75}};

if (A <= 0 && B <= 0) return 0.5;

if (A <= 0) return 1.0;

if (B <= 0) return 0.0;

if (m_.count(A) && m_[A].count(B)) return m_[A][B];

m_[A][B] = 0.0;

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

m_[A][B] += 0.25 * prob(A - ops[i][0], B - ops[i][1]);

return m_[A][B];

}

};

花花酱 LeetCode 881. Random Flip Matrix

By zxi on July 31, 2018

Problem

You are given the number of rows n_rows and number of columns n_cols of a 2D binary matrix where all values are initially 0. Write a function flip which chooses a 0 value uniformly at random, changes it to 1, and then returns the position [row.id, col.id] of that value. Also, write a function reset which sets all values back to 0. Try to minimize the number of calls to system’s Math.random() and optimize the time and space complexity.

Note:

1 <= n_rows, n_cols <= 10000
0 <= row.id < n_rows and 0 <= col.id < n_cols
flip will not be called when the matrix has no 0 values left.
the total number of calls to flip and reset will not exceed 1000.

Example 1:

Input: 
["Solution","flip","flip","flip","flip"]
[[2,3],[],[],[],[]]
Output: [null,[0,1],[1,2],[1,0],[1,1]]

Example 2:

Input: 
["Solution","flip","flip","reset","flip"]
[[1,2],[],[],[],[]]
Output: [null,[0,0],[0,1],null,[0,0]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution‘s constructor has two arguments, n_rows and n_cols. flip and reset have no arguments. Arguments are always wrapped with a list, even if there aren’t any.

Solution 1: Hashtable + Resample

Time complexity: O(|flip|) = O(1000) = O(1)

Space complexity: O(|flip|) = O(1000) = O(1)

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

Solution(int n_rows, int n_cols):

rows_(n_rows), cols_(n_cols), n_(rows_ * cols_) {}

vector<int> flip() {

int index = rand() % n_;

while (m_.count(index))

index = rand() % n_;

m_.insert(index);

return {index / cols_, index % cols_};

}

void reset() {

m_.clear();

n_ = rows_ * cols_;

}

private:

const int rows_;

const int cols_;

int n_;

unordered_set<int> m_;

};

Solution 2: Fisher–Yates shuffle

Generate a random shuffle of 0 to n – 1, one number at a time.

Time complexity: flip: O(1)

Space complexity: O(|flip|) = O(1000) = O(1)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

Solution(int n_rows, int n_cols):

rows_(n_rows), cols_(n_cols), n_(rows_ * cols_) {}

vector<int> flip() {

int s = rand() % (n_--);

int index = s;

if (m_.count(s))

index = m_[s];

m_[s] = m_.count(n_) ? m_[n_] : n_;

return {index / cols_, index % cols_};

}

void reset() {

m_.clear();

n_ = rows_ * cols_;

}

private:

const int rows_;

const int cols_;

int n_;

unordered_map<int, int> m_;

};