花花酱 LeetCode 864. Shortest Path to Get All Keys

By zxi on July 8, 2018

Problem

We are given a 2-dimensional grid. "." is an empty cell, "#" is a wall, "@" is the starting point, ("a", "b", …) are keys, and ("A", "B", …) are locks.

We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions. We cannot walk outside the grid, or walk into a wall. If we walk over a key, we pick it up. We can’t walk over a lock unless we have the corresponding key.

For some 1 <= K <= 6, there is exactly one lowercase and one uppercase letter of the first K letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.

Return the lowest number of moves to acquire all keys. If it’s impossible, return -1.

Example 1:

Input: ["@.a.#","###.#","b.A.B"]
Output: 8

Example 2:

Input: ["@..aA","..B#.","....b"]
Output: 6

Note:

1 <= grid.length <= 30
1 <= grid[0].length <= 30
grid[i][j] contains only '.', '#', '@', 'a'-'f' and 'A'-'F'
The number of keys is in [1, 6]. Each key has a different letter and opens exactly one lock.

Solution: BFS

Time complexity: O(m*n*64)

Space complexity: O(m*n*64)

C++

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int shortestPathAllKeys(vector<string>& grid) {

int m = grid.size();

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

int all_keys = 0;

queue<int> q;

vector<vector<vector<int>>> seen(m, vector<vector<int>>(n, vector<int>(64, 0)));

// Init

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

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

const char c = grid[i][j];

if (c == '@') {

q.push((j << 16) | (i << 8));

seen[i][j][0] = 1;

} else if (c >= 'a' && c <= 'f') {

all_keys |= (1 << (c - 'a'));

}

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

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int s = q.front(); q.pop();

int x = s >> 16;

int y = (s >> 8) & 0xFF;

int keys = s & 0xFF;

if (keys == all_keys) return steps;

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

int nkeys = keys;

int nx = x + dirs[i];

int ny = y + dirs[i + 1];

if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

const char c = grid[ny][nx];

if (c == '#') continue; // Wall

// Do not have the key.

if (c >= 'A' && c <= 'F' && !(keys & (1 << (c - 'A')))) continue;

// Update the keys we have.

if (c >= 'a' && c <= 'f') nkeys |= (1 << (c - 'a'));

if (seen[ny][nx][nkeys]) continue;

q.push((nx << 16) | (ny << 8) | nkeys);

seen[ny][nx][nkeys] = 1;

}

++steps;

}

return -1;

}

};

Python3

# Author: Huahua, 390 ms

class Solution:

def shortestPathAllKeys(self, grid):

m, n = len(grid), len(grid[0])

all_keys = 0

seen = [[[None]* 64 for _ in range(n)] for _ in range(m)]

q = collections.deque()

for i in range(m):

for j in range(n):

c = grid[i][j]

if c == '@':

q.append((j << 16) | (i << 8))

seen[i][j][0] = 1

elif c >= 'a' and c <= 'f':

all_keys |= (1 << (ord(c) - ord('a')))

dirs = [-1, 0, 1, 0, -1]

steps = 0

while q:

size = len(q)

while size > 0:

size -= 1

s = q.popleft()

x = s >> 16

y = (s >> 8) & 0xff

keys = s & 0xff

if keys == all_keys: return steps

for i in range(4):

nx, ny, nkeys = x + dirs[i], y + dirs[i + 1], keys

if nx < 0 or nx >= n or ny < 0 or ny >= m: continue

c = grid[ny][nx]

if c == '#': continue

if c in string.ascii_uppercase and keys & (1 << (ord(c) - ord('A'))) == 0: continue

if c in string.ascii_lowercase: nkeys |= (1 << (ord(c) - ord('a')))

if seen[ny][nx][nkeys]: continue

q.append((nx << 16) | (ny << 8) | nkeys)

seen[ny][nx][nkeys] = 1

steps += 1

return -1

Problem

Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y.

For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".

Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}. Notice that "tars" and "arts" are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list A of strings. Every string in A is an anagram of every other string in A. How many groups are there?

Example 1:

Input: ["tars","rats","arts","star"]
Output: 2

Note:

A.length <= 2000
A[i].length <= 1000
A.length * A[i].length <= 20000
All words in A consist of lowercase letters only.
All words in A have the same length and are anagrams of each other.
The judging time limit has been increased for this question.

Solution: Brute Force + Union Find

Time Complexity: O(n^2 * L)

Space Complexity: O(n)

C++

// Author: Huahua

// Running time: 230 ms (<99.08%)

class DSU {

public:

DSU(int size):size_(size), parent_(size), rank_(size) {

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

}

int Find(int n) {

if (parent_[n] != n)

parent_[n] = Find(parent_[n]);

return parent_[n];

}

void Union(int x, int y) {

int px = Find(x);

int py = Find(y);

if (px == py) return;

if (rank_[py] > rank_[px])

swap(px, py);

else if (rank_[py] == rank_[px])

++rank_[px];

parent_[py] = px;

--size_;

}

int Size() const {

return size_;

}

private:

int size_;

vector<int> ranks_;

vector<int> parent_;

};

class Solution {

public:

int numSimilarGroups(vector<string>& A) {

DSU dsu(A.size());

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

for (int j = i + 1; j < A.size(); ++j)

if (similar(A[i], A[j]))

dsu.Union(i, j);

return dsu.Size();

}

private:

bool similar(const string& a, const string& b) {

int diff = 0;

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

if (a[i] != b[i] && ++diff > 2) return false;

return true;

}

};

花花酱 LeetCode 840. Magic Squares In Grid

By zxi on July 8, 2018

Problem

A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given an grid of integers, how many 3 x 3 “magic square” subgrids are there? (Each subgrid is contiguous).

Example 1:

Input: [[4,3,8,4],
        [9,5,1,9],
        [2,7,6,2]]
Output: 1
Explanation: 
The following subgrid is a 3 x 3 magic square:
438
951
276

while this one is not:
384
519
762

In total, there is only one magic square inside the given grid.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
0 <= grid[i][j] <= 15

Solution

Time complexity: O(m*n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int numMagicSquaresInside(vector<vector<int>>& grid) {

int m = grid.size();

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

int ans = 0;

for (int i = 0; i < m - 2; ++i)

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

ans += magic(grid, j, i);

return ans;

}

private:

int magic(const vector<vector<int>>& grid, int x, int y) {

vector<int> rows(3);

vector<int> cols(3);

vector<int> exps{15, 15, 15};

int dig = 0;

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

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

int v = grid[y + i][x + j];

if (v <= 0 || v > 9) return 0; // must between 1 and 9

rows[i] += v;

cols[j] += v;

if (i == j) dig += v;

}

return rows == exps && cols == exps && dig == 15;

}

};

花花酱 LeetCode 865. Smallest Subtree with all the Deepest Nodes

By zxi on July 8, 2018

Problem

Given a binary tree rooted at root, the depth of each node is the shortest distance to the root.

A node is deepest if it has the largest depth possible among any node in the entire tree.

The subtree of a node is that node, plus the set of all descendants of that node.

Return the node with the largest depth such that it contains all the deepest nodes in it’s subtree.

Example 1:

Input: [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation:



We return the node with value 2, colored in yellow in the diagram.
The nodes colored in blue are the deepest nodes of the tree.
The input "[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]" is a serialization of the given tree.
The output "[2, 7, 4]" is a serialization of the subtree rooted at the node with value 2.
Both the input and output have TreeNode type.

Note:

The number of nodes in the tree will be between 1 and 500.
The values of each node are unique.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

TreeNode* subtreeWithAllDeepest(TreeNode* root) {

return depth(root).second;

}

private:

pair<int, TreeNode*> depth(TreeNode* root) {

if (root == nullptr)

return {-1, nullptr};

auto l = depth(root->left);

auto r = depth(root->right);

int dl = l.first;

int dr = r.first;

return { max(dl, dr) + 1,

dl == dr ? root : (dl > dr) ? l.second : r.second};

}

};

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

TreeNode* subtreeWithAllDeepest(TreeNode* root) {

TreeNode* ans;

depth(root, &ans);

return ans;

}

private:

int depth(TreeNode* root, TreeNode** s) {

if (root == nullptr)

return -1;

TreeNode* sl;

TreeNode* sr;

int l = depth(root->left, &sl);

int r = depth(root->right, &sr);

*s = (l == r) ? root : ((l > r) ? sl : sr);

return max(l, r) + 1;

}

};

Python3

"""

Author: Huahua

Running time: 40 ms

"""

class Solution:

def subtreeWithAllDeepest(self, root):

def solve(root):

if not root: return (-1, None)

dl, sl = solve(root.left)

dr, sr = solve(root.right)

if dl == dr: return (dl + 1, root)

return (dl + 1, sl) if dl > dr else (dr + 1, sr)

return solve(root)[1]

花花酱 LeetCode 867. Prime Palindrome

By zxi on July 8, 2018

Problem

Find the smallest prime palindrome greater than or equal to N.

Recall that a number is prime if it’s only divisors are 1 and itself, and it is greater than 1.

For example, 2,3,5,7,11 and 13 are primes.

Recall that a number is a palindrome if it reads the same from left to right as it does from right to left.

For example, 12321 is a palindrome.

Example 1:

Input: 6
Output: 7

Example 2:

Input: 8
Output: 11

Example 3:

Input: 13
Output: 101

Note:

1 <= N <= 10^8
The answer is guaranteed to exist and be less than 2 * 10^8.

Solution: Math

All odd digits palindromes have a factor 11, they are not prime except 11 itself.

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int primePalindrome(int N) {

if (N <= 2) return 2;

if (N % 2 == 0) ++N;

while (true) {

if (reverse(N) == N && isPrime(N))

return N;

N += 2;

if (N > 11 & (int)log10(N) % 2 == 1)

// 13 -> 101

// 1001 -> 10001

N = pow(10, (int)log10(N) + 1) + 1;

}

return -1;

}

private:

int reverse(int n) {

int r = 0;

while (n) {

r = 10 * r + n % 10;

n /= 10;

}

return r;

}

bool isPrime(int n) {

if (n <= 1) return false;

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

if (n % i == 0) return false;

return true;

}

};

花花酱 LeetCode 864. Shortest Path to Get All Keys

Problem

Solution: BFS

C++

Python3

Related Problems

花花酱 LeetCode 839. Similar String Groups

Problem

Solution: Brute Force + Union Find

花花酱 LeetCode 840. Magic Squares In Grid

Problem

Solution

花花酱 LeetCode 865. Smallest Subtree with all the Deepest Nodes

Problem

Solution: Recursion

花花酱 LeetCode 867. Prime Palindrome

Problem

Solution: Math

Huahua's Tech Road

花花酱 LeetCode 864. Shortest Path to Get All Keys

Problem

Solution: BFS

C++

Python3

Related Problems

花花酱 LeetCode 839. Similar String Groups

Problem

Solution: Brute Force + Union Find

花花酱 LeetCode 840. Magic Squares In Grid

Problem

Solution

花花酱 LeetCode 865. Smallest Subtree with all the Deepest Nodes

Problem

Solution: Recursion

花花酱 LeetCode 867. Prime Palindrome

Problem

Solution: Math