花花酱 LeetCode 959. Regions Cut By Slashes

By zxi on December 18, 2018

In a N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of a /, \, or blank space. These characters divide the square into contiguous regions.

(Note that backslash characters are escaped, so a \ is represented as "\\".)

Return the number of regions.

Example 1:

Input:[  " /",  "/ "]
Output: 2
Explanation: The 2x2 grid is as follows:

Example 2:

Input:[  " /",  "  "]
Output: 1
Explanation: The 2x2 grid is as follows:

Example 3:

Input:[  "\\/",  "/\\"]
Output: 4
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)The 2x2 grid is as follows:

Example 4:

Input:[  "/\\",  "\\/"]
Output: 5
Explanation: (Recall that because \ characters are escaped, "/\\" refers to /\, and "\\/" refers to \/.)The 2x2 grid is as follows:

Example 5:

Input:[  "//",  "/ "]
Output: 3
Explanation: The 2x2 grid is as follows:

Note:

1 <= grid.length == grid[0].length <= 30
grid[i][j] is either '/', '\', or ' '.

Solution 1: Split grid into 4 triangles and Union Find Faces

Divide each grid into 4 triangles and union them if not split.
Time complexity: O(n^2*alphn(n^2))
Space complexity: O(n^2)

C++

class Solution {

public:

int regionsBySlashes(vector<string>& grid) {

int n = grid.size();

DSU dsu(4 * n * n);

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

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

int index = 4 * (r * n + c);

switch (grid[r][c]) {

case '/':

dsu.merge(index + 0, index + 3);

dsu.merge(index + 1, index + 2);

break;

case '\\':

dsu.merge(index + 0, index + 1);

dsu.merge(index + 2, index + 3);

break;

case ' ':

dsu.merge(index + 0, index + 1);

dsu.merge(index + 1, index + 2);

dsu.merge(index + 2, index + 3);

break;

default: break;

}

if (r + 1 < n)

dsu.merge(index + 2, index + 4 * n + 0);

if (c + 1 < n)

dsu.merge(index + 1, index + 4 + 3);

}

int ans = 0;

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

if (dsu.find(i) == i) ++ans;

return ans;

}

private:

class DSU {

public:

DSU(int n): parent_(n) {

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

parent_[i] = i;

}

int find(int x) {

if (parent_[x] != x) parent_[x] = find(parent_[x]);

return parent_[x];

}

void merge(int x, int y) {

parent_[find(x)] = find(y);

}

private:

vector<int> parent_;

};

Solution 2: Euler’s Formula / Union-Find vertices

C++

class Solution {

public:

int regionsBySlashes(vector<string>& grid) {

int n = grid.size();

p_ = vector<int>((n + 1) * (n + 1));

// All vertices on the boundaries are merged into root(0).

for (int r = 0; r < n + 1; ++r)

for (int c = 0; c < n + 1; ++c)

p_[getIndex(n, r, c)] = (r == 0 || r == n || c == 0 || c == n) ? 0 : getIndex(n, r, c);

int f = 1;

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

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

if (grid[r][c] == ' ') continue;

// A new face will created if two vertices are already in the same group.

if (grid[r][c] == '/') {

f += merge(getIndex(n, r, c + 1),

getIndex(n, r + 1, c));

} else {

f += merge(getIndex(n, r, c),

getIndex(n, r + 1, c + 1));

}

return f;

}

private:

vector<int> p_;

int getIndex(int n, int r, int c) { return r * (n + 1) + c; }

int find(int x) {

if (p_[x] != x) p_[x] = find(p_[x]);

return p_[x];

}

int merge(int x, int y) {

int rx = find(x);

int ry = find(y);

if (rx == ry) return 1;

p_[ry] = rx;

return 0;

}

};

Solution 3: Pixelation (Upscale 3 times)

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

C++

// Author: Huahua, running time: 20 ms

class Solution {

public:

int regionsBySlashes(vector<string>& grid) {

const int n = grid.size();

vector<vector<int>> g(n * 3, vector<int>(n * 3));

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

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

if (grid[i][j] == '/') {

g[i * 3 + 0][j * 3 + 2] = 1;

g[i * 3 + 1][j * 3 + 1] = 1;

g[i * 3 + 2][j * 3 + 0] = 1;

} else if (grid[i][j] == '\\') {

g[i * 3 + 0][j * 3 + 0] = 1;

g[i * 3 + 1][j * 3 + 1] = 1;

g[i * 3 + 2][j * 3 + 2] = 1;

}

int ans = 0;

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

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

if (g[i][j]) continue;

visit(g, j, i, n * 3);

++ans;

}

return ans;

}

private:

void visit(vector<vector<int>>& g, int x, int y, int n) {

if (x < 0 || x >= n || y < 0 || y >= n) return;

if (g[y][x]) return;

g[y][x] = 1;

visit(g, x + 1, y, n);

visit(g, x, y + 1, n);

visit(g, x - 1, y, n);

visit(g, x, y - 1, n);

}

};

花花酱 LeetCode 958. Check Completeness of a Binary Tree

By zxi on December 18, 2018

Given a binary tree, determine if it is a complete binary tree.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Example 1:

Input: [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2:

Input: [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

Note:

The tree will have between 1 and 100 nodes.

Solution:

Level order traversal, if any nodes appears after a missing node then the tree is not a perfect binary tree.

Time complexity: O(n)

Space complexity: O(n)

C++

class Solution {

public:

bool isCompleteTree(TreeNode* root) {

if (!root) return true;

queue<TreeNode> q;

q.push(root);

bool missing = false;

while (!q.empty()) {

auto size = q.size();

while (size--) {

auto node = q.front(); q.pop();

if (node) {

if (missing) return false;

q.push(node->left);

q.push(node->right);

} else {

missing = true;

}

return true;

}

};

Python3

class Solution:

def isCompleteTree(self, root):

if not root: return True

q = collections.deque([root])

missing = False

while q:

size = len(q)

while size > 0:

size -= 1

node = q.popleft()

if node:

if missing: return False

q.append(node.left)

q.append(node.right)

else:

missing = True

return True

花花酱 LeetCode Binary Trees 二叉树 SP12

By zxi on December 16, 2018

Binary tree is one of the most frequently asked question type during interview.

二叉树是面试中经常会问到的问题。

The candidate needs to understand the recursively defined TreeNode and solve the problem through recursion.

面试者需要理解递归定义的TreeNode数据类型，并且通过使用递归的方式来解决问题。

花花酱 LeetCode 111. Minimum Depth of Binary Tree

By zxi on December 15, 2018

Problem

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

return its minimum depth = 2.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 4 ms

class Solution {

public:

int minDepth(TreeNode* root) {

if (!root) return 0;

if (!root->left && !root->right) return 1;

int l = root->left ? minDepth(root->left) : INT_MAX;

int r = root->right ? minDepth(root->right) : INT_MAX;

return min(l, r) + 1;

}

};

Python3

class Solution:

def minDepth(self, root):

if not root: return 0

if not root.left and not root.right: return 1

l = self.minDepth(root.left)

r = self.minDepth(root.right)

if not root.left: return 1 + r

if not root.right: return 1 + l

return 1 + min(l, r)

Problem

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

return its depth = 3.

Solution: Recursion

maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 4 ms

class Solution {

public:

int maxDepth(TreeNode* root) {

if (!root) return 0;

int l = maxDepth(root->left);

int r = maxDepth(root->right);

return max(l, r) + 1;

}

};

Python3

# Author: Huahua, 80 ms

class Solution:

def maxDepth(self, root):

if not root: return 0

l = self.maxDepth(root.left)

r = self.maxDepth(root.right)

return max(l, r) + 1

花花酱 LeetCode 959. Regions Cut By Slashes

Solution 1: Split grid into 4 triangles and Union Find Faces

C++

Solution 2: Euler’s Formula / Union-Find vertices

C++

Solution 3: Pixelation (Upscale 3 times)

C++

花花酱 LeetCode 958. Check Completeness of a Binary Tree

Solution:

C++

Python3

花花酱 LeetCode Binary Trees 二叉树 SP12

花花酱 LeetCode 111. Minimum Depth of Binary Tree

Problem

Solution: Recursion

C++

Python3

Related Problem

花花酱 LeetCode 104. Maximum Depth of Binary Tree

Problem

Solution: Recursion

C++

Python3

Huahua's Tech Road

花花酱 LeetCode 959. Regions Cut By Slashes

Solution 1: Split grid into 4 triangles and Union Find Faces

C++

Solution 2: Euler’s Formula / Union-Find vertices

C++

Solution 3: Pixelation (Upscale 3 times)

C++

花花酱 LeetCode 958. Check Completeness of a Binary Tree

Solution:

C++

Python3

花花酱 LeetCode Binary Trees 二叉树 SP12

花花酱 LeetCode 111. Minimum Depth of Binary Tree

Problem

Solution: Recursion

C++

Python3

Related Problem

花花酱 LeetCode 104. Maximum Depth of Binary Tree

Problem

Solution: Recursion

C++

Python3