Huahua’s Tech Road

花花酱 LeetCode 1734. Decode XORed Permutation

By zxi on January 23, 2021

There is an integer array perm that is a permutation of the first n positive integers, where n is always odd.

It was encoded into another integer array encoded of length n - 1, such that encoded[i] = perm[i] XOR perm[i + 1]. For example, if perm = [1,3,2], then encoded = [2,1].

Given the encoded array, return the original array perm. It is guaranteed that the answer exists and is unique.

Example 1:

Input: encoded = [3,1]
Output: [1,2,3]
Explanation: If perm = [1,2,3], then encoded = [1 XOR 2,2 XOR 3] = [3,1]

Example 2:

Input: encoded = [6,5,4,6]
Output: [2,4,1,5,3]

Constraints:

3 <= n < 10⁵
n is odd.
encoded.length == n - 1

Solution: XOR

The key is to find p[0]. p[i] = p[i – 1] ^ encoded[i – 1]

p[0] ^ p[1] ^ … ^ p[n-1] = 1 ^ 2 ^ … ^ n
encoded[1] ^ encode[3] ^ … ^ encoded[n-2] = (p[1] ^ p[2]) ^ (p[3] ^ p[4]) ^ … ^ (p[n-2] ^ p[n-1])

1) xor 2) = p[0]

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

C++

// Author: Huahua

class Solution {

public:

vector<int> decode(vector<int>& encoded) {

const int n = encoded.size() + 1;

vector<int> perm(n);

// p[0] = (p[0]^p[1]^...^p[n-1] = 1^2^...^n)

// ^ (p[1]^p[2]^...^p[n-1])

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

perm[0] ^= i;

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

perm[0] ^= encoded[i];

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

perm[i] = perm[i - 1] ^ encoded[i - 1];

return perm;

}

};

花花酱 LeetCode 1733. Minimum Number of People to Teach

By zxi on January 23, 2021

On a social network consisting of m users and some friendships between users, two users can communicate with each other if they know a common language.

You are given an integer n, an array languages, and an array friendships where:

There are n languages numbered 1 through n,
languages[i] is the set of languages the i^th user knows, and
friendships[i] = [u_i, v_i] denotes a friendship between the users u_i and v_i.

You can choose one language and teach it to some users so that all friends can communicate with each other. Return the minimum number of users you need to teach.Note that friendships are not transitive, meaning if x is a friend of y and y is a friend of z, this doesn’t guarantee that x is a friend of z.

Example 1:

Input: n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
Output: 1
Explanation: You can either teach user 1 the second language or user 2 the first language.

Example 2:

Input: n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
Output: 2
Explanation: Teach the third language to users 1 and 2, yielding two users to teach.

Constraints:

2 <= n <= 500
languages.length == m
1 <= m <= 500
1 <= languages[i].length <= n
1 <= languages[i][j] <= n
1 <= u_i < v_i <= languages.length
1 <= friendships.length <= 500
All tuples (u_i,v_i) are unique
languages[i] contains only unique values

Solution: Brute Force

Enumerate all languages and see which one is the best.

If two friends speak a common language, we can skip counting them.

Time complexity: O(m*(n+|friendship|))
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {

const int m = languages.size();

vector<unordered_set<int>> langs;

for (auto& l : languages) {

sort(begin(l), end(l));

langs.emplace_back(begin(l), end(l));

}

for (auto& e : friendships) {

const auto& l0 = languages[--e[0]];

const auto& l1 = languages[--e[1]];

vector<int> common;

set_intersection(begin(l0), end(l0), begin(l1), end(l1), back_inserter(common));

if (common.size()) e[0] = e[1] = -1;

}

int ans = INT_MAX;

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

vector<int> users(m);

for (const auto& e : friendships) {

// e[0] and e[1] have a common language, skip this edge

if (e[0] == -1) continue;

if (!langs[e[0]].count(i)) users[e[0]] = 1;

if (!langs[e[1]].count(i)) users[e[1]] = 1;

}

ans = min(ans, accumulate(begin(users), end(users), 0));

}

return ans;

}

};

花花酱 LeetCode1732. Find the Highest Altitude

By zxi on January 23, 2021

There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.

You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.

Example 1:

Input: gain = [-5,1,5,0,-7]
Output: 1
Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.

Example 2:

Input: gain = [-4,-3,-2,-1,4,3,2]
Output: 0
Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.

Constraints:

n == gain.length
1 <= n <= 100
-100 <= gain[i] <= 100

Solution: Running Max

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

C++

// Author: Huahua

class Solution {

public:

int largestAltitude(vector<int>& gain) {

int ans = 0;

int cur = 0;

for (int diff : gain)

ans = max(ans, cur += diff);

return ans;

}

};

花花酱 LeetCode 1728. Cat and Mouse II

By zxi on January 17, 2021

A game is played by a cat and a mouse named Cat and Mouse.

The environment is represented by a grid of size rows x cols, where each element is a wall, floor, player (Cat, Mouse), or food.

Players are represented by the characters 'C'(Cat),'M'(Mouse).
Floors are represented by the character '.' and can be walked on.
Walls are represented by the character '#' and cannot be walked on.
Food is represented by the character 'F' and can be walked on.
There is only one of each character 'C', 'M', and 'F' in grid.

Mouse and Cat play according to the following rules:

Mouse moves first, then they take turns to move.
During each turn, Cat and Mouse can jump in one of the four directions (left, right, up, down). They cannot jump over the wall nor outside of the grid.
catJump, mouseJump are the maximum lengths Cat and Mouse can jump at a time, respectively. Cat and Mouse can jump less than the maximum length.
Staying in the same position is allowed.
Mouse can jump over Cat.

The game can end in 4 ways:

If Cat occupies the same position as Mouse, Cat wins.
If Cat reaches the food first, Cat wins.
If Mouse reaches the food first, Mouse wins.
If Mouse cannot get to the food within 1000 turns, Cat wins.

Given a rows x cols matrix grid and two integers catJump and mouseJump, return true if Mouse can win the game if both Cat and Mouse play optimally, otherwise return false.

Example 1:

Input: grid = ["####F","#C...","M...."], catJump = 1, mouseJump = 2
Output: true
Explanation: Cat cannot catch Mouse on its turn nor can it get the food before Mouse.

Example 2:

Input: grid = ["M.C...F"], catJump = 1, mouseJump = 4
Output: true

Example 3:

Input: grid = ["M.C...F"], catJump = 1, mouseJump = 3
Output: false

Example 4:

Input: grid = ["C...#","...#F","....#","M...."], catJump = 2, mouseJump = 5
Output: false

Example 5:

Input: grid = [".M...","..#..","#..#.","C#.#.","...#F"], catJump = 3, mouseJump = 1
Output: true

Constraints:

rows == grid.length
cols = grid[i].length
1 <= rows, cols <= 8
grid[i][j] consist only of characters 'C', 'M', 'F', '.', and '#'.
There is only one of each character 'C', 'M', and 'F' in grid.
1 <= catJump, mouseJump <= 8

Solution: MinMax + Memoization

Time complexity: O(m^3 * n^3 * max(n, m))
Space complexity: O(m^3 * n^3)

state: [mouse_pos, cat_pos, turn]

C++

// Author: Huahua

class Solution {

public:

bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {

const int m = grid.size(), n = grid[0].size();

int mouse, cat, food;

for (int pos = 0; pos < m * n; ++pos)

switch (grid[pos / n][ pos % n]) {

case 'M': mouse = pos; break;

case 'C': cat = pos; break;

case 'F': food = pos; break;

default: break;

}

const vector<pair<int, int>> dirs{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

const int limit = m * n * 2;

vector<vector<vector<int>>> seen(m*n,

vector<vector<int>>(m*n, vector<int>(limit + 1, -1)));

function<bool(int, int, int)> dfs =

[&](int mouse, int cat, int d) -> bool {

const bool isCat = d & 1;

if (cat == food || cat == mouse || d >= limit) return isCat;

if (mouse == food) return !isCat;

int& ans = seen[mouse][cat][d];

if (ans != -1) return ans;

const int cur = isCat ? cat : mouse;

const int jumps = isCat ? catJump : mouseJump;

for (const auto& [dx, dy] : dirs)

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

const int x = (cur % n) + dx * j;

const int y = (cur / n) + dy * j;

const int pos = y * n + x;

if (x < 0 || x >= n || y < 0 || y >= m || grid[y][x] == '#') break;

if (!dfs(isCat ? mouse : pos, isCat ? pos : cat, d + 1)) return ans = true;

}

return ans = false;

};

return dfs(mouse, cat, 0);

}

};

花花酱 LeetCode 1727. Largest Submatrix With Rearrangements

By zxi on January 17, 2021

You are given a binary matrix matrix of size m x n, and you are allowed to rearrange the columns of the matrix in any order.

Return the area of the largest submatrix within matrix where every element of the submatrix is 1 after reordering the columns optimally.

Example 1:

Input: matrix = [[0,0,1],[1,1,1],[1,0,1]]
Output: 4
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 4.

Example 2:

Input: matrix = [[1,0,1,0,1]]
Output: 3
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 3.

Example 3:

Input: matrix = [[1,1,0],[1,0,1]]
Output: 2
Explanation: Notice that you must rearrange entire columns, and there is no way to make a submatrix of 1s larger than an area of 2.

Example 4:

Input: matrix = [[0,0],[0,0]]
Output: 0
Explanation: As there are no 1s, no submatrix of 1s can be formed and the area is 0.

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m * n <= 10⁵
matrix[i][j] is 0 or 1.

Solution: DP + Sorting

Preprocess each column, for col j, matrix[i][j] := length consecutive ones of col j.

[0,0,1]    [0,0,1]
[1,1,1] => [1,1,2]
[1,0,1]    [2,0,3]

Then we enumerate ending row, for each ending row i, we sort row[i] in deceasing order

e.g. i = 2

[0,0,1]                  [-,-,-]
[1,1,2] sort by row 2 => [-,-,-]
[2,0,3]                  [3,2,0]

row[2][1] = 3, means there is a 3×1 all ones sub matrix, area = 3
row[2][2] = 2, means there is a 2×2 all ones sub matrix, area = 4.

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

C++

// Author: Huahua

class Solution {

public:

int largestSubmatrix(vector<vector<int>>& matrix) {

const int m = matrix.size();

const int n = matrix[0].size();

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

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

if (matrix[i][j]) matrix[i][j] += matrix[i - 1][j];

int ans = 0;

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

sort(rbegin(matrix[i]), rend(matrix[i]));

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

ans = max(ans, (j + 1) * matrix[i][j]);

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1734. Decode XORed Permutation

Solution: XOR

C++

花花酱 LeetCode 1733. Minimum Number of People to Teach

Solution: Brute Force

C++

花花酱 LeetCode1732. Find the Highest Altitude

Solution: Running Max

C++

花花酱 LeetCode 1728. Cat and Mouse II

Solution: MinMax + Memoization

C++

花花酱 LeetCode 1727. Largest Submatrix With Rearrangements

Solution: DP + Sorting

C++