花花酱 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 214. Shortest Palindrome

By zxi on February 20, 2018

题目大意：给你一个字符串你可以在它的前面添加一些字符，返回最短的回文字符串。

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

Solution 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(n)

C++ w/ copy

// Author: Huahua

// Running time: 102 ms (<25.74%)

class Solution {

public:

string shortestPalindrome(string s) {

const string r(s.rbegin(), s.rend());

const int n = s.size();

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

if (s.substr(0, n - i) == r.substr(i))

return r.substr(0, i) + s;

return "";

}

};

C++ w/o copy

// Author: Huahua

// Running time: 13 ms (<49.74%)

class Solution {

public:

string shortestPalindrome(string s) {

const string r(s.rbegin(), s.rend());

const int n = s.size();

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

if (s.compare(0, n - i, r, i, n - i) == 0)

return r.substr(0, i) + s;

return "";

}

};

花花酱 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 786. K-th Smallest Prime Fraction

By zxi on February 20, 2018

题目大意：给你一些互质数字，求出它们组成的分数中第K小的分数。

A sorted list A contains 1, plus some number of primes. Then, for every p < q in the list, we consider the fraction p/q.

What is the K-th smallest fraction considered? Return your answer as an array of ints, where answer[0] = p and answer[1] = q.

Examples:

Input: A = [1, 2, 3, 5], K = 3

Output: [2, 5]

Explanation:

The fractions to be considered in sorted order are:

1/5, 1/3, 2/5, 1/2, 3/5, 2/3.

The third fraction is 2/5.

Input: A = [1, 7], K = 1

Output: [1, 7]

Note:

A will have length between 2 and 2000.
Each A[i] will be between 1 and 30000.
K will be between 1 and A.length * (A.length + 1) / 2.

Solution 1: Binary Search

Binary search m, 0 < m < 1, such that there are exact k pairs of (i, j) that A[i] / A[j] < m

Time complexity: O(n*C) C <= 31

C++

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

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

const int n = A.size();

double l = 0;

double r = 1.0;

while (l < r) {

double m = (l + r) / 2;

double max_f = 0.0;

int total = 0;

int p, q = 0;

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

while (j < n && A[i] > m * A[j]) ++j;

if (n == j) break;

total += (n - j);

const double f = static_cast<double>(A[i]) / A[j];

if (f > max_f) {

p = i;

q = j;

max_f = f;

}

if (total == K)

return {A[p], A[q]};

else if (total > K)

r = m;

else

l = m;

}

return {};

}

};

Java

// Author: Huahua

// Running time: 16 ms

class Solution {

public int[] kthSmallestPrimeFraction(int[] A, int K) {

final int n = A.length;

double l = 0;

double r = 1.0;

while (l < r) {

double m = (l + r) / 2;

double max_f = 0.0;

int total = 0;

int p = 0;

int q = 0;

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

while (j < n && A[i] > m * A[j]) ++j;

if (n == j) break;

total += (n - j);

final double f = (double)A[i] / A[j];

if (f > max_f) {

p = i;

q = j;

max_f = f;

}

if (total == K)

return new int[]{A[p], A[q]};

else if (total > K)

r = m;

else

l = m;

}

return new int[] {};

}

Python3

"""

Author: Huahua

Running time: 172 ms

"""

class Solution:

def kthSmallestPrimeFraction(self, A, K):

n = len(A)

l = 0.0

r = 1.0

while l < r:

m = (l + r) / 2

max_f = 0.0

total = 0

j = 1

for i in range(n - 1):

while j < n and A[i] > m * A[j]: j += 1

if j == n: break

total += n - j

f = A[i] / A[j]

if f > max_f:

p, q, max_f = i, j, f

if total == K:

return [A[p], A[q]]

elif total > K:

r = m

else:

l = m

return []

Related Problems:

花花酱 LeetCode 784. Letter Case Permutation

By zxi on February 20, 2018

题目大意：给你一个字符串，每个字母可以变成大写也可以变成小写。让你输出所有可能字符串。

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

Examples:

Input: S = "a1b2"

Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4"

Output: ["3z4", "3Z4"]

Input: S = "12345"

Output: ["12345"]

Note:

S will be a string with length at most 12.
S will consist only of letters or digits.

Solution 1: DFS

Time complexity: O(n*2^l), l = # of letters in the string

Space complexity: O(n) + O(n*2^l)

C++

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

vector<string> letterCasePermutation(string S) {

vector<string> ans;

dfs(S, 0, ans);

return ans;

}

private:

void dfs(string& S, int s, vector<string>& ans) {

if (s == S.length()) {

ans.push_back(S);

return;

}

dfs(S, s + 1, ans);

if (!isalpha(S[s])) return;

S[s] ^= (1 << 5);

dfs(S, s + 1, ans);

S[s] ^= (1 << 5);

}

};

Java

// Author: Huahua

// Running time: 8 ms

class Solution {

public List<String> letterCasePermutation(String S) {

List<String> ans = new ArrayList<>();

dfs(S.toCharArray(), 0, ans);

return ans;

}

private void dfs(char[] S, int i, List<String> ans) {

if (i == S.length) {

ans.add(new String(S));

return;

}

dfs(S, i + 1, ans);

if (!Character.isLetter(S[i])) return;

S[i] ^= 1 << 5;

dfs(S, i + 1, ans);

S[i] ^= 1 << 5;

}

Python 3

"""

Author: Huahua

Running time: 92 ms

"""

class Solution:

def letterCasePermutation(self, S):

ans = []

def dfs(S, i, n):

if i == n:

ans.append(''.join(S))

return

dfs(S, i + 1, n)

if not S[i].isalpha(): return

S[i] = chr(ord(S[i]) ^ (1<<5))

dfs(S, i + 1, n)

S[i] = chr(ord(S[i]) ^ (1<<5))

dfs(list(S), 0, len(S))

return ans

Huahua's Tech Road

花花酱 LeetCode 787. Cheapest Flights Within K Stops

Solution 1: DFS

C++

Solution 2: BFS

C++

Solution 3: Bellman-Ford algorithm

C++ O(k*n)

C++ O(n)

Java

Python3

花花酱 LeetCode 214. Shortest Palindrome

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

Solution 1: Binary Search

花花酱 LeetCode 786. K-th Smallest Prime Fraction

Solution 1: Binary Search

C++

Java

Python3

花花酱 LeetCode 784. Letter Case Permutation

Solution 1: DFS

C++

Java

Python 3