花花酱 LeetCode 791. Custom Sort String

By zxi on February 24, 2018

题目大意：给你字符的顺序，让你排序一个字符串。

S and T are strings composed of lowercase letters. In S, no letter occurs more than once.

S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.

Return any permutation of T (as a string) that satisfies this property.

Example :

Input:

S = "cba"

T = "abcd"

Output: "cbad"

Explanation:

"a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a".

Since "d" does not appear in S, it can be at any position in T. "dcba", "cdba", "cbda" are also valid outputs.

Note:

S has length at most 26, and no character is repeated in S.
T has length at most 200.
S and T consist of lowercase letters only.

Solution 1: HashTable + Sorting

Store the order of char in a hashtable
Sort the string based on the order

Time complexity: O(nlogn)

Space complexity: O(128)

// Author: Huahua

// Running time: 2 ms

class Solution {

public:

string customSortString(string S, string T) {

vector<int> order(128, INT_MAX);

int i = 0;

for (char c: S)

if (order[c] == INT_MAX) order[c] = ++i;

std::sort(T.begin(), T.end(), [&order](const char c1, const char c2){

return order[c1] < order[c2];

});

return T;

}

};

花花酱 LeetCode 789. Escape The Ghosts

By zxi on February 24, 2018

题目大意：给你目的地坐标以及幽灵的坐标，初始点在(0,0)，每次你和幽灵都可以移动一步。问你是否可以安全到达终点。

You are playing a simplified Pacman game. You start at the point (0, 0), and your destination is (target[0], target[1]). There are several ghosts on the map, the i-th ghost starts at (ghosts[i][0], ghosts[i][1]).

Each turn, you and all ghosts simultaneously *may* move in one of 4 cardinal directions: north, east, west, or south, going from the previous point to a new point 1 unit of distance away.

You escape if and only if you can reach the target before any ghost reaches you (for any given moves the ghosts may take.) If you reach any square (including the target) at the same time as a ghost, it doesn’t count as an escape.

Return True if and only if it is possible to escape.

Example 1:

Input:

ghosts = [[1, 0], [0, 3]]

target = [0, 1]

Output: true

Explanation:

You can directly reach the destination (0, 1) at time 1, while the ghosts located at (1, 0) or (0, 3) have no way to catch up with you.

Example 2:

Input:

ghosts = [[1, 0]]

target = [2, 0]

Output: false

Explanation:

You need to reach the destination (2, 0), but the ghost at (1, 0) lies between you and the destination.

Example 3:

Input:

ghosts = [[2, 0]]

target = [1, 0]

Output: false

Explanation:

The ghost can reach the target at the same time as you.

Note:

All points have coordinates with absolute value <= 10000.
The number of ghosts will not exceed 100.

Solution: Greedy / Math

You can escape if and only if no ghosts can reach target before you. Just need to compare the Manhattan distance.

如果所有的幽灵都无法在你之前到达target，那么你可以逃脱。只要比较曼哈顿距离即可。

C++

Time complexity: O(|ghost|)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {

const int steps = abs(target[0]) + abs(target[1]);

for (const auto& g: ghosts)

if (abs(g[0] - target[0]) + abs(g[1] - target[1]) <= steps)

return false;

return true;

}

};

Java

// Author: Huahua

// Running time: 4 ms

class Solution {

public boolean escapeGhosts(int[][] ghosts, int[] target) {

final int steps = Math.abs(target[0]) + Math.abs(target[1]);

for (int[] g : ghosts)

if (Math.abs(g[0] - target[0]) + Math.abs(g[1] - target[1]) <= steps)

return false;

return true;

}

Python3

"""

Author: Huahua

Running time: 40 ms

"""

class Solution:

def escapeGhosts(self, ghosts, target):

steps = abs(target[0]) + abs(target[1])

return not any(abs(x - target[0]) + abs(y - target[1]) <= steps for x, y in ghosts)

花花酱 LeetCode 788 Rotated Digits

By zxi on February 24, 2018

题目大意：

给一个字符串，独立旋转每个数字180°，判断得到的新字符串是否合法。

出现数字3,4,7一定不合法
新字符串 == 原来字符串不合法

X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X. A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other; 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number.

Now given a positive number N, how many numbers X from 1 to N are good?

Example:

Input: 10

Output: 4

Explanation:

There are four good numbers in the range [1, 10] : 2, 5, 6, 9.

Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.

Note:

N will be in range [1, 10000].

Solution 1: Brute Force

Time complexity: O(nlogn)

C++

// Author: Huahua

// Running time: 21 ms

class Solution {

public:

int isValid(int n) {

string s = to_string(n);

string t(s);

for (int i = 0; i < s.length(); ++i) {

if (s[i] == '3' || s[i] == '4' || s[i] == '7')

return 0;

else if (s[i] == '2') t[i] = '5';

else if (s[i] == '5') t[i] = '2';

else if (s[i] == '6') t[i] = '9';

else if (s[i] == '9') t[i] = '6';

}

return t != s;

}

int rotatedDigits(int N) {

int ans = 0;

for (int i = 1; i <= N; ++i)

ans += isValid(i);

return ans;

}

};

Bit Operation

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int isValid(int n) {

constexpr int kInValidMask = (1 << 3) | (1 << 4) | (1 << 7);

constexpr int kValidMask = (1 << 2) | (1 << 5) | (1 << 6) | (1 << 9);

int valid = 0;

while (n > 0) {

int r = 1 << (n % 10);

if (r & kInValidMask)

return 0;

else if (r & kValidMask)

valid = 1;

n /= 10;

}

return valid;

}

int rotatedDigits(int N) {

int ans = 0;

for (int i = 1; i <= N; ++i)

ans += isValid(i);

return ans;

}

};

花花酱 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 "";

}

};

Huahua's Tech Road

花花酱 LeetCode 791. Custom Sort String

花花酱 LeetCode 789. Escape The Ghosts

花花酱 LeetCode 788 Rotated Digits

花花酱 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