Huahua's Tech Road

花花酱 LeetCode 1318. Minimum Flips to Make a OR b Equal to c

By zxi on January 13, 2020

Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation).
Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.

Example 1:

Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)

Example 2:

Input: a = 4, b = 2, c = 7
Output: 1

Example 3:

Input: a = 1, b = 2, c = 3
Output: 0

Constraints:

1 <= a <= 10^9
1 <= b <= 10^9
1 <= c <= 10^9

Solution: Bit operation

If the bit of c is 1, a / b at least has one 1. cost = 1 – ((a | b) & 1)
If the bit of c is 0, a / b must be 0, cost = (a & 1) + (b & 1)

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

C++

// Author: Huahua

class Solution {

public:

int minFlips(int a, int b, int c) {

int count = 0;

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

if (c & 1) count += 1 - ((a | b) & 1);

else count += (a & 1) + (b & 1);

a >>= 1;

b >>= 1;

c >>= 1;

}

return count;

}

};

花花酱 LeetCode 1317. Convert Integer to the Sum of Two No-Zero Integers

By zxi on January 13, 2020

Given an integer n. No-Zero integer is a positive integer which doesn’t contain any 0 in its decimal representation.

Return a list of two integers [A, B] where:

A and B are No-Zero integers.
A + B = n

It’s guarateed that there is at least one valid solution. If there are many valid solutions you can return any of them.

Example 1:

Input: n = 2

Output: [1,1]

Explanation: A = 1, B = 1. A + B = n and both A and B don't contain any 0 in their decimal representation.

Example 2:

1 2	<strong>Input:</strong> n = 11 <strong>Output:</strong> [2,9]

Example 3:

1 2	<strong>Input:</strong> n = 10000 <strong>Output:</strong> [1,9999]

Example 4:

1 2	<strong>Input:</strong> n = 69 <strong>Output:</strong> [1,68]

Example 5:

1 2	<strong>Input:</strong> n = 1010 <strong>Output:</strong> [11,999]

Constraints:

2 <= n <= 10^4

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

vector<int> getNoZeroIntegers(int n) {

auto valid = [](int x) {

if (!x) return false;

while (x) {

if (x % 10 == 0) return false;

x /= 10;

}

return true;

};

for (int i = 1; i <= n / 2; ++i)

if (valid(i) && valid(n - i))

return {i, n - i};

return {};

}

};

花花酱 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 1319. Number of Operations to Make Network Connected

By zxi on January 11, 2020

There are n computers numbered from 0 to n-1 connected by ethernet cables connections forming a network where connections[i] = [a, b] represents a connection between computers a and b. Any computer can reach any other computer directly or indirectly through the network.

Given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected. Return the minimum number of times you need to do this in order to make all the computers connected. If it’s not possible, return -1.

Example 1:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

Example 2:

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
Output: 2

Example 3:

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
Output: -1
Explanation: There are not enough cables.

Example 4:

Input: n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
Output: 0

Constraints:

1 <= n <= 10^5
1 <= connections.length <= min(n*(n-1)/2, 10^5)
connections[i].length == 2
0 <= connections[i][0], connections[i][1] < n
connections[i][0] != connections[i][1]
There are no repeated connections.
No two computers are connected by more than one cable.

Solution 1: Union-Find

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

C++

// Author: Huahua

class Solution {

public:

int makeConnected(int n, vector<vector<int>>& connections) {

if (connections.size() < n - 1) return -1;

vector<int> p(n);

iota(begin(p), end(p), 0);

function<int(int)> find = [&](int x) {

return p[x] == x ? x : p[x] = find(p[x]);

};

for (const auto& c : connections)

p[find(c[0])] = find(c[1]);

unordered_set<int> s;

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

s.insert(find(i));

return s.size() - 1;

}

};

Solution 2: DFS

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

C++

// Author: Huahua

class Solution {

public:

int makeConnected(int n, vector<vector<int>>& connections) {

if (connections.size() < n - 1) return -1;

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

for (const auto& c : connections) {

g[c[0]].push_back(c[1]);

g[c[1]].push_back(c[0]);

}

vector<int> seen(n);

int count = 0;

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

for (int nxt : g[cur])

if (!seen[nxt]++) dfs(nxt);

};

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

if (!seen[i]++ && ++count)

dfs(i);

return count - 1;

}

};

花花酱 LeetCode 1313. Decompress Run-Length Encoded List

By zxi on January 11, 2020

We are given a list nums of integers representing a list compressed with run-length encoding.

Consider each adjacent pair of elements [a, b] = [nums[2*i], nums[2*i+1]] (with i >= 0). For each such pair, there are a elements with value b in the decompressed list.

Return the decompressed list.

Example 1:

Input: nums = [1,2,3,4]
Output: [2,4,4,4]

Constraints:

2 <= nums.length <= 100
nums.length % 2 == 0
1 <= nums[i] <= 100

Solution: Simulation

Time complexity: O(sum(n_i))
Space complexity: O(sum(n_i)) or O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> decompressRLElist(vector<int>& nums) {

vector<int> ans;

for (int i = 0; i < nums.size(); i += 2)

for (int j = 0; j < nums[i]; ++j)

ans.push_back(nums[i + 1]);

return ans;

}

};