Huahua’s Tech Road

花花酱 LeetCode 1790. Check if One String Swap Can Make Strings Equal

By zxi on March 13, 2021

You are given two strings s1 and s2 of equal length. A string swap is an operation where you choose two indices in a string (not necessarily different) and swap the characters at these indices.

Return true if it is possible to make both strings equal by performing at most one string swap on exactly one of the strings. Otherwise, return false.

Example 1:

Input: s1 = "bank", s2 = "kanb"
Output: true
Explanation: For example, swap the first character with the last character of s2 to make "bank".

Example 2:

Input: s1 = "attack", s2 = "defend"
Output: false
Explanation: It is impossible to make them equal with one string swap.

Example 3:

Input: s1 = "kelb", s2 = "kelb"
Output: true
Explanation: The two strings are already equal, so no string swap operation is required.

Example 4:

Input: s1 = "abcd", s2 = "dcba"
Output: false

Constraints:

1 <= s1.length, s2.length <= 100
s1.length == s2.length
s1 and s2 consist of only lowercase English letters.

Solution: Remember two indices

There needs to be either 0 or 2 indices are different. Otherwise return false.
s1[idx1] == s2[idx2] and s1[idx2] == s2[idx1]

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

C++

// Author: Huahua

class Solution {

public:

bool areAlmostEqual(string s1, string s2) {

vector<int> idx;

for (int i = 0; i < s1.length() && idx.size() <= 2; ++i)

if (s1[i] != s2[i]) idx.push_back(i);

if (idx.size() == 0) return true;

if (idx.size() != 2) return false;

return s1[idx[0]] == s2[idx[1]] && s1[idx[1]] == s2[idx[0]];

}

};

花花酱 LeetCode 1786. Number of Restricted Paths From First to Last Node

By zxi on March 6, 2021

There is an undirected weighted connected graph. You are given a positive integer n which denotes that the graph has n nodes labeled from 1 to n, and an array edges where each edges[i] = [u_i, v_i, weight_i] denotes that there is an edge between nodes u_i and v_i with weight equal to weight_i.

A path from node start to node end is a sequence of nodes [z₀, z₁,z₂, ..., z_k] such that z₀= start and z_k = end and there is an edge between z_i and z_i+1 where 0 <= i <= k-1.

The distance of a path is the sum of the weights on the edges of the path. Let distanceToLastNode(x) denote the shortest distance of a path between node n and node x. A restricted path is a path that also satisfies that distanceToLastNode(z_i) > distanceToLastNode(z_i+1) where 0 <= i <= k-1.

Return the number of restricted paths from node 1 to node n. Since that number may be too large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
Output: 3
Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The three restricted paths are:
1) 1 --> 2 --> 5
2) 1 --> 2 --> 3 --> 5
3) 1 --> 3 --> 5

Example 2:

Input: n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]
Output: 1
Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The only restricted path is 1 --> 3 --> 7.

Constraints:

1 <= n <= 2 * 10⁴
n - 1 <= edges.length <= 4 * 10⁴
edges[i].length == 3
1 <= u_i, v_i <= n
u_i!= v_i
1 <= weight_i <= 10⁵
There is at most one edge between any two nodes.
There is at least one path between any two nodes.

Solution: Dijkstra + DFS w/ memoization

Find shortest path from n to all the nodes.
paths(u) = sum(paths(v)) if dist[u] > dist[v] and (u, v) has an edge
return paths(1)

Time complexity: O(ElogV + V + E)
Space complexity: O(V + E)

C++

// Author: Huahua

class Solution {

public:

int countRestrictedPaths(int n, vector<vector<int>>& edges) {

constexpr int kMod = 1e9 + 7;

using PII = pair<int, int>;

vector<vector<PII>> g(n + 1);

for (const auto& e : edges) {

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

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

}

// Shortest distance from n to x.

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

dist[n] = 0;

priority_queue<PII, vector<PII>, std::greater<PII>> q;

q.emplace(0, n);

while (!q.empty()) {

const auto [d, u] = q.top(); q.pop();

if (dist[u] < d) continue;

for (auto [v, w]: g[u]) {

if (dist[u] + w >= dist[v]) continue;

dist[v] = dist[u] + w;

q.emplace(dist[v], v);

}

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

function<int(int)> dfs = [&](int u) {

if (u == n) return 1;

if (dp[u] != INT_MAX) return dp[u];

int ans = 0;

for (auto [v, w]: g[u])

if (dist[u] > dist[v])

ans = (ans + dfs(v)) % kMod;

return dp[u] = ans;

};

return dfs(1);

}

};

Combined

C++

// Author: Huahua

class Solution {

public:

int countRestrictedPaths(int n, vector<vector<int>>& edges) {

constexpr int kMod = 1e9 + 7;

using PII = pair<int, int>;

vector<vector<PII>> g(n + 1);

for (const auto& e : edges) {

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

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

}

// Shortest distance from n to x.

vector<int> dist(n + 1, INT_MAX);

vector<int> dp(n + 1);

dist[n] = 0;

dp[n] = 1;

priority_queue<PII, vector<PII>, std::greater<PII>> q;

q.emplace(0, n);

while (!q.empty()) {

const auto [d, u] = q.top(); q.pop();

if (d > dist[u]) continue;

if (u == 1) break;

for (auto [v, w]: g[u]) {

if (dist[v] > dist[u] + w)

q.emplace(dist[v] = dist[u] + w, v);

if (dist[v] > dist[u])

dp[v] = (dp[v] + dp[u]) % kMod;

}

return dp[1];

}

};

花花酱 LeetCode 1785. Minimum Elements to Add to Form a Given Sum

By zxi on March 6, 2021

You are given an integer array nums and two integers limit and goal. The array nums has an interesting property that abs(nums[i]) <= limit.

Return the minimum number of elements you need to add to make the sum of the array equal to goal. The array must maintain its property that abs(nums[i]) <= limit.

Note that abs(x) equals x if x >= 0, and -x otherwise.

Example 1:

Input: nums = [1,-1,1], limit = 3, goal = -4
Output: 2
Explanation: You can add -2 and -3, then the sum of the array will be 1 - 1 + 1 - 2 - 3 = -4.

Example 2:

Input: nums = [1,-10,9,1], limit = 100, goal = 0
Output: 1

Constraints:

1 <= nums.length <= 10⁵
1 <= limit <= 10⁶
-limit <= nums[i] <= limit
-10⁹ <= goal <= 10⁹

Solution: Math

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

Compute the diff = abs(sum(nums) – goal)
ans = （diff + limit – 1)) / limit

C++

// Author: Huahua

class Solution {

public:

int minElements(vector<int>& nums, int limit, int goal) {

int64_t diff = abs(goal -

accumulate(begin(nums), end(nums), 0LL));

return (diff + limit - 1) / limit;

}

};

花花酱 LeetCode 1784. Check if Binary String Has at Most One Segment of Ones

By zxi on March 6, 2021

Given a binary string s without leading zeros, return true if s contains at most one contiguous segment of ones. Otherwise, return false.

Example 1:

Input: s = "1001"
Output: false
Explanation: The ones do not form a contiguous segment.

Example 2:

Input: s = "110"
Output: true

Constraints:

1 <= s.length <= 100
s[i] is either '0' or '1'.
s[0] is '1'.

Solution: Counting

increase counter if s[i] == ‘1’ otherwise, reset counter.
increase counts when counter becomes 1.
return counts == 1

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

C++

// Author: Huahua

class Solution {

public:

bool checkOnesSegment(string s) {

int count = 0;

int ones = 0;

for (const char c : s) {

if (c == '1') {

count += (++ones == 1);

} else {

ones = 0;

}

return count == 1;

}

};

花花酱 LeetCode 1782. Count Pairs Of Nodes

By zxi on March 6, 2021

You are given an undirected graph represented by an integer n, which is the number of nodes, and edges, where edges[i] = [u_i, v_i] which indicates that there is an undirected edge between u_i and v_i. You are also given an integer array queries.

The answer to the j^th query is the number of pairs of nodes (a, b) that satisfy the following conditions:

a < b
cnt is strictly greater than queries[j], where cnt is the number of edges incident to a or b.

Return an array answers such that answers.length == queries.length and answers[j] is the answer of the j^th query.

Note that there can be repeated edges.

Example 1:

Input: n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3]
Output: [6,5]
Explanation: The number of edges incident to at least one of each pair is shown above.

Example 2:

Input: n = 5, edges = [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]], queries = [1,2,3,4,5]
Output: [10,10,9,8,6]

Constraints:

2 <= n <= 2 * 10⁴
1 <= edges.length <= 10⁵
1 <= u_i, v_i <= n
u_i!= v_i
1 <= queries.length <= 20
0 <= queries[j] < edges.length

Solution 1: Pre-compute

Pre-compute # of pairs with total edges >= k. where k is from 0 to max_degree * 2 + 1.

Time complexity: (|node_degrees|² + V + E)
Space complexity: O(V+E)

C++

// Author: huahua

class Solution {

public:

vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {

vector<int> node_degrees(n);

unordered_map<int, int> edge_freq;

for (auto& e : edges) {

sort(begin(e), end(e));

++node_degrees[--e[0]];

++node_degrees[--e[1]];

++edge_freq[(e[0] << 16) | e[1]];

}

const int max_degree = *max_element(begin(node_degrees),

end(node_degrees));

// Need pad one more to handle "not found / 0" case.

vector<int> counts(max_degree * 2 + 2);

unordered_map<int, int> degree_count;

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

++degree_count[node_degrees[i]];

for (auto& [d1, c1] : degree_count)

for (auto& [d2, c2] : degree_count)

// Only count once if degrees are different to ensure (a < b)

if (d1 < d2) counts[d1 + d2] += c1 * c2;

// If degrees are the same C(n, 2) to ensure (a < b)

else if (d1 == d2) counts[d1 * 2] += c1 * (c1 - 1) / 2;

for (auto& [key, freq] : edge_freq) {

const int u = key >> 16;

const int v = key & 0xFFFF;

// For a pair of (u, v) their actual edge count is

// d[u] + d[v] - freq[(u, v)] instead of d[u] + d[v]

counts[node_degrees[u] + node_degrees[v]] -= 1;

counts[node_degrees[u] + node_degrees[v] - freq] += 1;

}

// counts[i] = # of pairs whose total edges >= i

for (int i = counts.size() - 2; i >= 0; --i)

counts[i] += counts[i + 1];

vector<int> ans;

for (int q : queries)

ans.push_back(counts[min(q + 1, static_cast<int>(counts.size() - 1))]);

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1790. Check if One String Swap Can Make Strings Equal

Solution: Remember two indices

C++

花花酱 LeetCode 1786. Number of Restricted Paths From First to Last Node

Solution: Dijkstra + DFS w/ memoization

C++

C++

花花酱 LeetCode 1785. Minimum Elements to Add to Form a Given Sum

Solution: Math

C++

花花酱 LeetCode 1784. Check if Binary String Has at Most One Segment of Ones

Solution: Counting

C++

花花酱 LeetCode 1782. Count Pairs Of Nodes

Solution 1: Pre-compute

C++