Posts tagged as “medium”

花花酱LeetCode 983. Minimum Cost For Tickets

By zxi on January 27, 2019

In a country popular for train travel, you have planned some train travelling one year in advance. The days of the year that you will travel is given as an array days. Each day is an integer from 1 to 365.

Train tickets are sold in 3 different ways:

a 1-day pass is sold for costs[0] dollars;
a 7-day pass is sold for costs[1] dollars;
a 30-day pass is sold for costs[2] dollars.

The passes allow that many days of consecutive travel. For example, if we get a 7-day pass on day 2, then we can travel for 7 days: day 2, 3, 4, 5, 6, 7, and 8.

Return the minimum number of dollars you need to travel every day in the given list of days.

Example 1:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: 
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total you spent $11 and covered all the days of your travel.

Example 2:

Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation: 
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total you spent $17 and covered all the days of your travel.

Note:

1 <= days.length <= 365
1 <= days[i] <= 365
days is in strictly increasing order.
costs.length == 3
1 <= costs[i] <= 1000

Solution: DP

dp[i] := min cost to cover the i-th day
dp[0] = 0
dp[i] = min(dp[i – 1] + costs[0], dp[i – 7] + costs[1], dp[i – 30] + costs[2])

C++

// Author: Huahua, running time: 0 ms

class Solution {

public:

int mincostTickets(vector<int>& days, vector<int>& costs) {

vector<int> req(days.back() + 1);

vector<int> dp(days.back() + 1);

for (int day : days) req[day] = 1;

dp[0] = 0;

for (int i = 1; i < dp.size(); ++i) {

if (!req[i]) {

dp[i] = dp[i - 1];

continue;

}

dp[i] = dp[i - 1] + costs[0];

dp[i] = min(dp[i], dp[max(0, i - 7)] + costs[1]);

dp[i] = min(dp[i], dp[max(0, i - 30)] + costs[2]);

}

return dp.back();

}

};

Python

// Author: Huahua, running time: 60 ms

class Solution:

def mincostTickets(self, days: 'List[int]', costs: 'List[int]') -> 'int':

req = set(days)

dp = [0] * (days[-1] + 1)

for i in range(1, len(dp)):

if not i in req:

dp[i] = dp[i - 1]

continue

dp[i] = min(dp[max(0, i - 1)] + costs[0],

dp[max(0, i - 7)] + costs[1],

dp[max(0, i - 30)] + costs[2])

return dp[-1]

花花酱 LeetCode 981. Time Based Key-Value Store

By zxi on January 26, 2019

Create a timebased key-value store class TimeMap, that supports two operations.

1. set(string key, string value, int timestamp)

Stores the key and value, along with the given timestamp.

2. get(string key, int timestamp)

Returns a value such that set(key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp.
If there are multiple such values, it returns the one with the largest timestamp_prev.
If there are no values, it returns the empty string ("").

Example 1:

Input: inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,null,"bar","bar",null,"bar2","bar2"]
Explanation:   
TimeMap kv;   
kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1   
kv.get("foo", 1);  // output "bar"   
kv.get("foo", 3); // output "bar" since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ie "bar"   
kv.set("foo", "bar2", 4);   
kv.get("foo", 4); // output "bar2"   
kv.get("foo", 5); //output "bar2"

Example 2:

Input: inputs = ["TimeMap","set","set","get","get","get","get","get"], inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]]
Output: [null,null,null,"","high","high","low","low"]

Note:

All key/value strings are lowercase.
All key/value strings have length in the range [1, 100]
The timestamps for all TimeMap.set operations are strictly increasing.
1 <= timestamp <= 10^7
TimeMap.set and TimeMap.get functions will be called a total of 120000 times (combined) per test case.

Solution: HashTable + Map

C++

// Author: Huahua, running time: 200 ms

class TimeMap {

public:

/** Initialize your data structure here. */

TimeMap() {}

void set(string key, string value, int timestamp) {

s_[key].emplace(timestamp, std::move(value));

}

string get(string key, int timestamp) {

auto m = s_.find(key);

if (m == s_.end()) return "";

auto it = m->second.upper_bound(timestamp);

if (it == begin(m->second)) return "";

return prev(it)->second;

}

private:

unordered_map<string, map<int, string>> s_;

};

花花酱 LeetCode 979. Distribute Coins in Binary Tree

By zxi on January 20, 2019

Given the root of a binary tree with N nodes, each node in the tree has node.valcoins, and there are N coins total.

In one move, we may choose two adjacent nodes and move one coin from one node to another. (The move may be from parent to child, or from child to parent.)

Return the number of moves required to make every node have exactly one coin.

Example 1:

Input: [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

Example 2:

Input: [0,3,0]
Output: 3
Explanation: From the left child of the root, we move two coins to the root [taking two moves].  Then, we move one coin from the root of the tree to the right child.

Example 3:

Input: [1,0,2]
Output: 2

Example 4:

Input: [1,0,0,null,3]
Output: 4

Note:

1<= N <= 100
0 <= node.val <= N

Solution: Recursion

Compute the balance of left/right subtree, ans += abs(balance(left)) + abs(balance(right))
balance(root) = balance(left) + balance(right) + root.val – 1

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

C++

class Solution {

public:

int distributeCoins(TreeNode* root) {

int ans = 0;

balance(root, ans);

return ans;

}

private:

int balance(TreeNode* root, int& ans) {

if (!root) return 0;

int l = balance(root->left, ans);

int r = balance(root->right, ans);

ans += abs(l) + abs(r);

return l + r + root->val - 1;

}

};

花花酱 LeetCode 974. Subarray Sums Divisible by K

By zxi on January 17, 2019

Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.

Example 1:

Input: A = [4,5,0,-2,-3,1], K = 5 
Output: 7 
Explanation: There are 7 subarrays with a sum divisible by K = 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Note:

1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000

Solution: Count prefix sums

let c[i] denotes the counts of prefix_sum % K init: c[0] = 1
Whenever we end up with the same prefix sum (after modulo), which means there are subarrys end with current element that is divisible by K (0 modulo).

e.g. A = [4,5,0,-2,-3,1], K = 5
[4,5] has prefix sum of 4, which happens at index 0 [4], and index 1, [4,5]
[4,5,0] also has a prefix sum of 4, which means [4, {5,0}], [4,5, {0}] are divisible by K.

ans += (c[prefix_sum] – 1)
i = 0, prefix_sum = 0, c[(0+4)%5] = c[4] = 1, ans = 0
i = 1, prefix_sum = 4+5, c[(4+5)%5] = c[4] = 2, ans = 0+2-1=0 => [5]
i = 2, prefix_sum = 4+0, c[(4+0)%5] = c[4] = 3, ans = 1+3-1=3 => [5], [5,0], [0]
i = 3, prefix_sum = 4-2, c[(4-2)%5] = c[2] = 1, ans = 3
i = 4, prefix_sum = 2-3, c[(2-3+5)%5] = c[4] = 4, ans = 3+4-1=6 => [5],[5,0],[0],[5,0,-2,-3], [0,-2,-3],[-2,-3]
i = 5, prefix_sum = 4+1, c[(4+1)%5] = c[0] = 2, ans = 6 + 2 – 1 =>
[5],[5,0],[0],[5,0,-2,-3], [0,-2,-3],[-2,-3], [4,5,0,-2,-3,1]

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

C++

class Solution {

public:

int subarraysDivByK(vector<int>& A, int K) {

vector<int> c(K);

c[0] = 1;

int ans = 0;

int sum = 0;

for (int a : A) {

sum = (sum + a % K + K) % K;

ans += c[sum]++;

}

return ans;

}

};

Python3

class Solution:

def subarraysDivByK(self, A, K):

c = [0] * K

c[0] = 1

s = 0

ans = 0

for a in A:

s = (s + a % K + K) % K

ans += c[s]

c[s] += 1

return ans

花花酱 LeetCode 971. Flip Binary Tree To Match Preorder Traversal

By zxi on January 5, 2019

Given a binary tree with N nodes, each node has a different value from {1, ..., N}.

A node in this binary tree can be flipped by swapping the left child and the right child of that node.

Consider the sequence of N values reported by a preorder traversal starting from the root. Call such a sequence of N values the voyage of the tree.

(Recall that a preorder traversal of a node means we report the current node’s value, then preorder-traverse the left child, then preorder-traverse the right child.)

Our goal is to flip the least number of nodes in the tree so that the voyage of the tree matches the voyagewe are given.

If we can do so, then return a list of the values of all nodes flipped. You may return the answer in any order.

If we cannot do so, then return the list [-1].

Example 1:

Input: root = [1,2], voyage = [2,1]
Output: [-1]

Example 2:

Input: root = [1,2,3], voyage = [1,3,2]
Output: [1]

Example 3:

Input: root = [1,2,3], voyage = [1,2,3]
Output: []

Note:

1 <= N <= 100

Solution: Pre-order traversal

if root->val != v[pos] return [-1]
if root->left?->val != v[pos + 1], swap the nodes

c++

class Solution {

public:

vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {

vector<int> flips;

int pos = 0;

solve(root, voyage, pos, flips);

return flips;

}

private:

void solve(TreeNode* root, const vector<int>& voyage, int& pos, vector<int>& flips) {

if (!root) return;

if (root->val != voyage.at(pos)) {

flips.clear();

flips.push_back(-1);

return;

}

if (root->left && root->left->val != voyage.at(pos + 1)) {

swap(root->left, root->right);

flips.push_back(root->val);

}

++pos;

solve(root->left, voyage, pos, flips);

solve(root->right, voyage, pos, flips);

}

};

Python3

# Author: Huahua, 60 ms

class Solution:

def flipMatchVoyage(self, root, voyage):

self.pos = 0

self.flips = []

def solve(root):

if not root: return

if root.val != voyage[self.pos]:

self.flips = [-1]

return

if root.left and root.left.val != voyage[self.pos + 1]:

root.left, root.right = root.right, root.left

self.flips.append(root.val)

self.pos += 1

solve(root.left)

solve(root.right)

solve(root)

return self.flips