Posts tagged as “medium”

花花酱 LeetCode 787. Cheapest Flights Within K Stops

By zxi on February 22, 2018

题目大意：给你一些城市之间的机票价格，问从src到dst的最少需要花多少钱，最多可以中转k个机场。

There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.

Now given all the cities and fights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

Example 1:

Input:

n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]

src = 0, dst = 2, k = 1

Output: 200

Explanation:

The graph looks like this:

The cheapest price from city <code>0</code> to city <code>2</code> with at most 1 stop costs 200, as marked red in the picture.

Example 2:

Input:

n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]

src = 0, dst = 2, k = 0

Output: 500

Explanation:

The graph looks like this:

The cheapest price from city <code>0</code> to city <code>2</code> with at most 0 stop costs 500, as marked blue in the picture.

Note:

The number of nodes n will be in range [1, 100], with nodes labeled from 0 to n - 1.
The size of flights will be in range [0, n * (n - 1) / 2].
The format of each flight will be (src, dst, price).
The price of each flight will be in the range [1, 10000].
k is in the range of [0, n - 1].
There will not be any duplicated flights or self cycles.

Solution 1: DFS

w/o prunning TLE

w/ prunning Accepted

C++

// Author: Huahua

// Running time: 36 ms

class Solution {

public:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

g_.clear();

for (const auto& e : flights)

g_[e[0]].emplace_back(e[1], e[2]);

vector<int> visited(n, 0);

visited[src] = 1;

int ans = INT_MAX;

dfs(src, dst, K + 1, 0, visited, ans);

return ans == INT_MAX ? - 1 : ans;

}

private:

unordered_map<int, vector<pair<int,int>>> g_;

void dfs(int src, int dst, int k, int cost, vector<int>& visited, int& ans) {

if (src == dst) {

ans = cost;

return;

}

if (k == 0) return;

for (const auto& p : g_[src]) {

if (visited[p.first]) continue; // do not visit the same city twice.

if (cost + p.second > ans) continue; // IMPORTANT!!! prunning

visited[p.first] = 1;

dfs(p.first, dst, k - 1, cost + p.second, visited, ans);

visited[p.first] = 0;

}

};

Solution 2: BFS

C++

// Author: Huahua

// Running time: 20 ms

class Solution {

public:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

unordered_map<int, vector<pair<int,int>>> g;

for (const auto& e : flights)

g[e[0]].emplace_back(e[1], e[2]);

int ans = INT_MAX;

queue<pair<int,int>> q;

q.push({src, 0});

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int curr = q.front().first;

int cost = q.front().second;

q.pop();

if (curr == dst)

ans = min(ans, cost);

for (const auto& p : g[curr]) {

if (cost + p.second > ans) continue; // Important: prunning

q.push({p.first, cost + p.second});

}

if (steps++ > K) break;

}

return ans == INT_MAX ? - 1 : ans;

}

};

Solution 3: Bellman-Ford algorithm

dp[k][i]: min cost from src to i taken up to k flights (k-1 stops)

init: dp[0:k+2][src] = 0

transition: dp[k][i] = min(dp[k-1][j] + price[j][i])

ans: dp[K+1][dst]

Time complexity: O(k * |flights|) / O(k*n^2)

Space complexity: O(k*n) -> O(n)

w/o space compression O(k*n)

C++ O(k*n)

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

constexpr int kInfCost = 1e9;

vector<vector<int>> dp(K + 2, vector<int>(n, kInfCost));

dp[0][src] = 0;

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

dp[i][src] = 0;

for (const auto& p : flights)

dp[i][p[1]] = min(dp[i][p[1]], dp[i-1][p[0]] + p[2]);

}

return dp[K + 1][dst] >= kInfCost ? -1 : dp[K + 1][dst];

}

};

C++ O(n)

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

constexpr int kInfCost = 1e9;

vector<int> cost(n, kInfCost);

cost[src] = 0;

for (int i = 0; i <= K; ++i) {

vector<int> tmp(cost);

for (const auto& p : flights)

tmp[p[1]] = min(tmp[p[1]], cost[p[0]] + p[2]);

cost.swap(tmp);

}

return cost[dst] >= kInfCost ? -1 : cost[dst];

}

};

Java

// Author: Huahua

// Running time: 11 ms

class Solution {

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {

final int kInfCost = 1<<30;

int[] cost = new int[n];

Arrays.fill(cost, kInfCost);

cost[src] = 0;

for (int i = 0; i <= K; ++i) {

int[] tmp = cost.clone();

for(int[] p: flights)

tmp[p[1]] = Math.min(tmp[p[1]], cost[p[0]] + p[2]);

cost = tmp;

}

return cost[dst] >= kInfCost ? -1 : cost[dst];

}

Python3

"""

Author: Huahua

Running time: 132 ms

"""

class Solution:

def findCheapestPrice(self, n, flights, src, dst, K):

kInfCost = 1e9

cost = [kInfCost for _ in range(n)]

cost[src] = 0

for i in range(K + 1):

tmp = list(cost)

for p in flights:

tmp[p[1]] = min(tmp[p[1]], cost[p[0]] + p[2])

cost = tmp

return -1 if cost[dst] >= 1e9 else cost[dst]

花花酱 LeetCode 378. Kth Smallest Element in a Sorted Matrix

By zxi on February 20, 2018

题目大意：给你一个矩阵，每行每列各自排序。找出矩阵中第K小的元素。

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [

[ 1, 5, 9],

[10, 11, 13],

[12, 13, 15]

k = 8,

return 13.

Note:
You may assume k is always valid, 1 ≤ k ≤ n².

Solution 1: Binary Search

Find the smallest x, such that there are k elements that are smaller or equal to x.

Time complexity: O(nlogn*log(max – min))

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 24 ms (beats 97.12%)

class Solution {

public:

int kthSmallest(vector<vector<int>>& matrix, int k) {

const int n = matrix.size();

long l = matrix[0][0];

long r = matrix[n - 1][n - 1] + 1;

while (l < r) {

long m = l + (r - l) / 2;

int total = 0;

int s = n;

for (const auto& row : matrix)

total += (s = distance(begin(row), upper_bound(begin(row), begin(row) + s, m)));

if (total >= k)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 755. Pour Water

By zxi on January 7, 2018

题目大意：

给你地形的高度，有V单位的水会从K位置落下，问你稳定之后水位的高度。

Problem:

We are given an elevation map, heights[i] representing the height of the terrain at that index. The width at each index is 1. After V units of water fall at index K, how much water is at each index?

Water first drops at index K and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:

If the droplet would eventually fall by moving left, then move left.
Otherwise, if the droplet would eventually fall by moving right, then move right.
Otherwise, rise at it’s current position.

Here, “eventually fall” means that the droplet will eventually be at a lower level if it moves in that direction. Also, “level” means the height of the terrain plus any water in that column.

We can assume there’s infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than 1 grid block – each unit of water has to be in exactly one block.

Idea:

Solution 1: Simulation

Time complexity: O(V*n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

vector<int> pourWater(vector<int>& heights, int V, int K) {

while (V--) drop(heights, K);

return heights;

}

private:

void drop(vector<int>& heights, int K) {

int best = K;

for (int d = -1; d <= 1; d += 2) {

int i = K + d;

while (i >= 0 && i < heights.size()

&& heights[i] <= heights[i - d]) {

if (heights[i] < heights[best]) best = i;

i += d;

}

if (best != K) break;

}

++heights[best];

}

};

Java

// Author: Huahua

// Running time: 12 ms

class Solution {

public int[] pourWater(int[] heights, int V, int K) {

while (V-- > 0) {

dropWater(heights, K);

}

return heights;

}

private void dropWater(int[] heights, int K) {

int best = K;

for (int d = -1; d <= 1; d += 2) {

int i = K + d;

while (i >= 0 && i < heights.length && heights[i] <= heights[i - d]) {

if (heights[i] < heights[best]) best = i;

i += d;

}

if (best != K) break;

}

++heights[best];

}

Python3

"""

Author: Huahua

Running time: 207 ms

"""

class Solution:

def pourWater(self, heights, V, K):

def drop(h, K):

best = K

for d in (-1, 1):

i = K + d

while i >= 0 and i < len(h) and h[i] <= h[i - d]:

if h[i] < h[best]:

best = i

i += d

if best != K:

break

heights[best] += 1

for _ in range(V):

drop(heights, K)

return heights

花花酱 LeetCode 322. Coin Change

By zxi on January 2, 2018

题目大意：给你一些不同币值的硬币，问你最少需要多少个硬币才能组成amount，假设每种硬币有无穷多个。

Problem:

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Idea:

DP /knapsack

Solution1:

C++ / DP

Time complexity: O(n*amount^2)

Space complexity: O(amount)

// Author: Huahua

// Running time: 189 ms

class Solution {

public:

int coinChange(vector<int>& coins, int amount) {

vector<int> dp(amount + 1, INT_MAX);

dp[0] = 0;

for (auto coin : coins) {

for (int i = amount - coin; i >= 0; --i)

if (dp[i] != INT_MAX)

for (int k = 1; k * coin + i <= amount; ++k)

dp[i + k * coin] = min(dp[i + k * coin], dp[i] + k);

}

return dp[amount] == INT_MAX ? -1 : dp[amount];

}

};

Solution2:

C++ / DP

Time complexity: O(n*amount)

Space complexity: O(amount)

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int coinChange(vector<int>& coins, int amount) {

// dp[i] = min coins to make up to amount i

vector<int> dp(amount + 1, INT_MAX);

dp[0] = 0;

for (int coin : coins) {

for (int i = coin; i <= amount; ++i)

if (dp[i - coin] != INT_MAX)

dp[i] = min(dp[i], dp[i - coin] + 1);

}

return dp[amount] == INT_MAX ? -1 : dp[amount];

}

};

Python3

"""

Author: Huahua

Running time: 632 ms beats 90.27%

"""

class Solution:

def coinChange(self, coins, amount):

INVALID = 2**32

dp = [INVALID] * (amount + 1)

dp[0] = 0

for coin in coins:

for i in range(coin, amount + 1):

if dp[i - coin] >= dp[i]: continue

dp[i] = dp[i - coin] + 1

return -1 if dp[amount] == INVALID else dp[amount]

Solution3:

C++ / DFS

Time complexity: O(amount^n/(coin_0*coin_1*…*coin_n))

Space complexity: O(n)

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

int coinChange(vector<int>& coins, int amount) {

// Sort coins in desending order

std::sort(coins.rbegin(), coins.rend());

int ans = INT_MAX;

coinChange(coins, 0, amount, 0, ans);

return ans == INT_MAX ? -1 : ans;

}

private:

void coinChange(const vector<int>& coins,

int s, int amount, int count, int& ans) {

if (amount == 0) {

ans = min(ans, count);

return;

}

if (s == coins.size()) return;

const int coin = coins[s];

for (int k = amount / coin; k >= 0 && count + k < ans; k--)

coinChange(coins, s + 1, amount - k * coin, count + k, ans);

}

};

Python3

"""

Author: Huahua

Running time: 200ms

"""

class Solution:

def coinChange(self, coins, amount):

coins.sort(reverse=True)

INVALID = 10**10

self.ans = INVALID

def dfs(s, amount, count):

if amount == 0:

self.ans = count

return

if s == len(coins): return

coin = coins[s]

for k in range(amount // coin, -1, -1):

if count + k >= self.ans: break

dfs(s + 1, amount - k * coin, count + k)

dfs(0, amount, 0)

return -1 if self.ans == INVALID else self.ans

花花酱 LeetCode 652. Find Duplicate Subtrees

By zxi on December 31, 2017

652. Find Duplicate SubtreesMedium730151FavoriteShare

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

Example 1:

The following are two duplicate subtrees:

2
/
4

and

Therefore, you need to return above trees’ root in the form of a list.

Solution 1: Serialization

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

C++

// Author: Huahua

// Runtime: 29 ms

class Solution {

public:

vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {

unordered_map<string, int> counts;

vector<TreeNode*> ans;

serialize(root, counts, ans);

return ans;

}

private:

string serialize(TreeNode* root, unordered_map<string, int>& counts, vector<TreeNode*>& ans) {

if (!root) return "#";

string key = to_string(root->val) + ","

+ serialize(root->left, counts, ans) + ","

+ serialize(root->right, counts, ans);

if (++counts[key] == 2)

ans.push_back(root);

return key;

}

};

Solution 2: int id for each unique subtree

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

C++

// Author: Huahua

// Runtime: 8 ms

class Solution {

public:

vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {

unordered_map<long, pair<int,int>> counts;

vector<TreeNode*> ans;

getId(root, counts, ans);

return ans;

}

private:

int getId(TreeNode* root,

unordered_map<long, pair<int,int>>& counts,

vector<TreeNode*>& ans) {

if (!root) return 0;

long key = (static_cast<long>(static_cast<unsigned>(root->val)) << 32) +

(getId(root->left, counts, ans) << 16) +

getId(root->right, counts, ans);

auto& p = counts[key];

if (p.second++ == 0)

p.first = counts.size();

else if (p.second == 2)

ans.push_back(root);

return p.first;

}

};