Posts tagged as “dp”

花花酱 LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

By zxi on January 26, 2020

There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [from_i, to_i, weight_i] represents a bidirectional and weighted edge between cities from_i and to_i, and given the integer distanceThreshold.

Return the city with the smallest numberof cities that are reachable through some path and whose distance is at most distanceThreshold, If there are multiple such cities, return the city with the greatest number.

Notice that the distance of a path connecting cities i and j is equal to the sum of the edges’ weights along that path.

Example 1:

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 4 for each city are:
City 0 -> [City 1, City 2] 
City 1 -> [City 0, City 2, City 3] 
City 2 -> [City 0, City 1, City 3] 
City 3 -> [City 1, City 2] 
Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.

Example 2:

Input: n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
Output: 0
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 2 for each city are:
City 0 -> [City 1] 
City 1 -> [City 0, City 4] 
City 2 -> [City 3, City 4] 
City 3 -> [City 2, City 4]
City 4 -> [City 1, City 2, City 3] 
The city 0 has 1 neighboring city at a distanceThreshold = 2.

Constraints:

2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= from_i < to_i < n
1 <= weight_i, distanceThreshold <= 10^4
All pairs (from_i, to_i) are distinct.

Solution1: Floyd-Warshall

All pair shortest path

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

C++

// Author: Huahua

class Solution {

public:

int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {

vector<vector<int>> dp(n, vector<int>(n, INT_MAX / 2));

for (const auto& e : edges)

dp[e[0]][e[1]] = dp[e[1]][e[0]] = e[2];

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

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

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

dp[u][v] = min(dp[u][v], dp[u][k] + dp[k][v]);

int ans = -1;

int min_nb = INT_MAX;

for (int u = 0; u < n; ++u) {

int nb = 0;

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

if (v != u && dp[u][v] <= distanceThreshold)

++nb;

if (nb <= min_nb) {

min_nb = nb;

ans = u;

}

return ans;

}

};

Solution 2: Dijkstra’s Algorithm

Time complexity: O(V * ElogV) / worst O(n^3*logn), best O(n^2*logn)
Space complexity: O(V + E)

C++

// Author: Huahua

class Solution {

public:

int findTheCity(int n, vector<vector<int>>& edges, int t) {

vector<vector<pair<int, int>>> g(n);

for (const auto& e : edges) {

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

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

}

// Returns the number of nodes within t from s.

auto dijkstra = [&](int s) {

vector<int> dist(n, INT_MAX / 2);

set<pair<int, int>> q; // <dist, node>

vector<set<pair<int, int>>::const_iterator> its(n);

dist[s] = 0;

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

its[i] = q.emplace(dist[i], i).first;

while (!q.empty()) {

auto it = cbegin(q);

int d = it->first;

int u = it->second;

q.erase(it);

if (d > t) break; // pruning

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

int v = p.first;

int w = p.second;

if (dist[v] <= d + w) continue;

// Decrease key

q.erase(its[v]);

its[v] = q.emplace(dist[v] = d + w, v).first;

}

return count_if(begin(dist), end(dist), [t](int d) { return d <= t; });

};

int ans = -1;

int min_nb = INT_MAX;

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

int nb = dijkstra(i);

if (nb <= min_nb) {

min_nb = nb;

ans = i;

}

return ans;

}

};

花花酱 LeetCode 42. Trapping Rain Water

By zxi on January 15, 2020

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

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

Solution 1: Brute Force

r[i] = min(max(h[0:i+1]), max(h[i:n]))
ans = sum(r[i])

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

C++

// Author: Huahua

class Solution {

public:

int trap(vector<int>& height) {

const int n = height.size();

int ans = 0;

auto sit = cbegin(height);

auto eit = cend(height);

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

int l = *max_element(sit, sit + i + 1);

int r = *max_element(sit + i, eit);

ans += min(l, r) - height[i];

}

return ans;

}

};

Solution 2: DP

l[i] := max(h[0:i+1])
r[i] := max(h[i:n])
ans = sum(min(l[i], r[i]) – h[i])

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

C++

// Author: Huahua

class Solution {

public:

int trap(vector<int>& height) {

const int n = height.size();

vector<int> l(n);

vector<int> r(n);

int ans = 0;

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

l[i] = i == 0 ? height[i] : max(l[i - 1], height[i]);

for (int i = n - 1; i >= 0; --i)

r[i] = i == n - 1 ? height[i] : max(r[i + 1], height[i]);

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

ans += min(l[i], r[i]) - height[i];

return ans;

}

};

Solution 3: Two Pointers

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

C++

// Author: Huahua, 4 ms, 9.1 MB

class Solution {

public:

int trap(vector<int>& height) {

const int n = height.size();

if (n == 0) return 0;

int l = 0;

int r = n - 1;

int max_l = height[l];

int max_r = height[r];

int ans = 0;

while (l < r) {

if (max_l < max_r) {

ans += max_l - height[l];

max_l = max(max_l, height[++l]);

} else {

ans += max_r - height[r];

max_r = max(max_r, height[--r]);

}

return ans;

}

};

花花酱 LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers

By zxi on January 12, 2020

You have a keyboard layout as shown above in the XY plane, where each English uppercase letter is located at some coordinate, for example, the letter A is located at coordinate (0,0), the letter B is located at coordinate (0,1), the letter P is located at coordinate (2,3) and the letter Z is located at coordinate (4,1).

Given the string word, return the minimum total distance to type such string using only two fingers. The distance between coordinates (x₁,y₁) and (x₂,y₂) is |x₁ – x₂| + |y₁ – y₂|.

Note that the initial positions of your two fingers are considered free so don’t count towards your total distance, also your two fingers do not have to start at the first letter or the first two letters.

Example 1:

Input: word = "CAKE"
Output: 3
Explanation: 
Using two fingers, one optimal way to type "CAKE" is: 
Finger 1 on letter 'C' -> cost = 0 
Finger 1 on letter 'A' -> cost = Distance from letter 'C' to letter 'A' = 2 
Finger 2 on letter 'K' -> cost = 0 
Finger 2 on letter 'E' -> cost = Distance from letter 'K' to letter 'E' = 1 
Total distance = 3

Example 2:

Input: word = "HAPPY"
Output: 6
Explanation: 
Using two fingers, one optimal way to type "HAPPY" is:
Finger 1 on letter 'H' -> cost = 0
Finger 1 on letter 'A' -> cost = Distance from letter 'H' to letter 'A' = 2
Finger 2 on letter 'P' -> cost = 0
Finger 2 on letter 'P' -> cost = Distance from letter 'P' to letter 'P' = 0
Finger 1 on letter 'Y' -> cost = Distance from letter 'A' to letter 'Y' = 4
Total distance = 6

Example 3:

Input: word = "NEW"
Output: 3

Example 4:

Input: word = "YEAR"
Output: 7

Constraints:

2 <= word.length <= 300
Each word[i] is an English uppercase letter.

Solution: DP

Top down: O(n*27^2)

C++

// Author: Huahua, 64 ms, 46.6 MB

class Solution {

public:

int minimumDistance(string word) {

constexpr int kRest = 26;

const int n = word.length();

vector<vector<vector<int>>> mem(n, vector<vector<int>>(27, vector<int>(27, -1)));

auto cost = [](int c1, int c2) {

if (c1 == kRest) return 0;

return abs(c1 / 6 - c2 / 6) + abs(c1 % 6 - c2 % 6);

};

// min cost to type word[i:n]. l, r are the last finger positions.

function<int(int, int, int)> dp = [&](int i, int l, int r) {

if (i == n) return 0;

if (mem[i][l][r] >= 0) return mem[i][l][r];

int c = word[i] - 'A';

return mem[i][l][r] = min(dp(i + 1, c, r) + cost(l, c),

dp(i + 1, l, c) + cost(r, c));

};

return dp(0, kRest, kRest);

}

};

C++

// Author: Huahua, 12 ms, 10.1 MB

class Solution {

public:

int minimumDistance(string word) {

constexpr int kRest = 26;

const int n = word.length();

vector<vector<int>> mem(n, vector<int>(27));

auto cost = [](int c1, int c2) {

if (c1 == kRest) return 0;

return abs(c1 / 6 - c2 / 6) + abs(c1 % 6 - c2 % 6);

};

// min cost to type word[i:n]. o is the last position of the other finger.

// the current finger is at word[i - 1].

function<int(int, int)> dp = [&](int i, int o) {

if (i == n) return 0;

if (mem[i][o]) return mem[i][o];

int p = i == 0 ? kRest : word[i - 1] - 'A';

int c = word[i] - 'A';

return mem[i][o] = min(dp(i + 1, o) + cost(p, c), // same finger

dp(i + 1, p) + cost(o, c)); // other finger

};

return dp(0, kRest);

}

};

C++

// Author: Huahua, 8 ms, 10.1 MB

class Solution {

public:

int minimumDistance(string word) {

constexpr int kRest = 26;

const int n = word.length();

// dp[i][j] : min cost to type word[0:i]

// one finger is at word[i - 1], another finger is at j.

vector<vector<int>> dp(n + 1, vector<int>(27, INT_MAX / 2));

dp[0][kRest] = 0;

auto cost = [](int c1, int c2) {

if (c1 == kRest) return 0;

return abs(c1 / 6 - c2 / 6) + abs(c1 % 6 - c2 % 6);

};

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

int p = i == 0 ? kRest : word[i - 1] - 'A';

int c = word[i] - 'A';

for (int j = 0; j <= 26; ++j) {

dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + cost(p, c)); // same finger

dp[i + 1][p] = min(dp[i + 1][p], dp[i][j] + cost(j, c)); // other finger

}

return *min_element(begin(dp[n]), end(dp[n]));

}

};

花花酱 LeetCode 1314. Matrix Block Sum

By zxi on January 11, 2020

Given a m * n matrix mat and an integer K, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for i - K <= r <= i + K, j - K <= c <= j + K, and (r, c) is a valid position in the matrix.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]

Example 2:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
Output: [[45,45,45],[45,45,45],[45,45,45]]

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n, K <= 100
1 <= mat[i][j] <= 100

Solution: 2D range query

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

C++

// Author: Huahua, 20 ms

class Solution {

public:

vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {

const int n = mat.size();

const int m = mat[0].size();

vector<vector<int>> dp(n + 1, vector<int>(m + 1));

for (int y = 1; y <= n; ++y)

for (int x = 1; x <= m; ++x)

dp[y][x] = dp[y - 1][x] + dp[y][x - 1] + mat[y - 1][x - 1] - dp[y - 1][x - 1];

auto ans = mat;

for (int y = 1; y <= n; ++y)

for (int x = 1; x <= m; ++x) {

int x1 = max(1, x - K);

int x2 = min(m, x + K);

int y1 = max(1, y - K);

int y2 = min(n, y + K);

ans[y - 1][x - 1] = dp[y2][x2] - dp[y1 - 1][x2] - dp[y2][x1 - 1] + dp[y1 - 1][x1 - 1];

}

return ans;

}

};

花花酱 LeetCode 1312. Minimum Insertion Steps to Make a String Palindrome

By zxi on January 4, 2020

Given a string s. In one step you can insert any character at any index of the string.

Return the minimum number of steps to make s palindrome.

A Palindrome String is one that reads the same backward as well as forward.

Example 1:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.

Example 2:

Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".

Example 3:

Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

Example 4:

Input: s = "g"
Output: 0

Example 5:

Input: s = "no"
Output: 1

Constraints:

1 <= s.length <= 500
All characters of s are lower case English letters.

Solution: DP

dp[i][j] := min chars to insert
dp[j][j] = dp[i-1][j+1] if s[i] == s[j] else min(dp[i+1][j] , dp[i][j-1]) + 1
base case: dp[i][i] = 0
ans: dp[0][n-1]

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

C++

// Author: Huahua

class Solution {

public:

int minInsertions(string s) {

const int n = s.length();

vector<vector<int>> dp(n, vector<int>(n));

for (int l = 2; l <= n; ++l)

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

dp[i][j] = s[i] == s[j] ? dp[i + 1][j - 1] : min(dp[i + 1][j], dp[i][j - 1]) + 1;

return dp[0][n - 1];

}

};