Huahua’s Tech Road

花花酱 LeetCode 693. Binary Number with Alternating Bits

By zxi on October 7, 2017

Problem:

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

Example 1:

Input: 5

Output: True

Explanation:

The binary representation of 5 is: 101

Example 2:

Input: 7

Output: False

Explanation:

The binary representation of 7 is: 111.

Example 3:

Input: 11

Output: False

Explanation:

The binary representation of 11 is: 1011.

Example 4:

Input: 10

Output: True

Explanation:

The binary representation of 10 is: 1010.

Idea:

Bit operation

Solution

C++

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

bool hasAlternatingBits(int n) {

int r = n & 1;

while ((n >>= 1) > 0) {

int t = n & 1;

if (t == r) return false;

r = t;

}

return true;

}

};

花花酱 LeetCode 695. Max Area of Island

By zxi on October 7, 2017

Problem:

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1‘s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],

[0,0,0,0,0,0,0,1,1,1,0,0,0],

[0,1,1,0,1,0,0,0,0,0,0,0,0],

[0,1,0,0,1,1,0,0,1,0,1,0,0],

[0,1,0,0,1,1,0,0,1,1,1,0,0],

[0,0,0,0,0,0,0,0,0,0,1,0,0],

[0,0,0,0,0,0,0,1,1,1,0,0,0],

[0,0,0,0,0,0,0,1,1,0,0,0,0]]

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

1	[[0,0,0,0,0,0,0,0]]

Given the above grid, return 0.

Note: The length of each dimension in the given grid does not exceed 50.

Idea:

Use DFS to find the connected components

Solution:

C++

// Author: Huahua

// Runtime: 32 ms

class Solution {

public:

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

int h = grid.size();

if (h == 0) return 0;

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

int ans = 0;

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

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

ans = max(ans, area(grid, j, i, w, h));

return ans;

}

private:

int area(vector<vector<int>>& grid, int x, int y, int w, int h) {

if (x < 0 || y < 0 || x >= w || y >= h || grid[y][x] == 0) return 0;

grid[y][x] = 0;

return area(grid, x - 1, y, w, h)

+ area(grid, x + 1, y, w, h)

+ area(grid, x, y - 1, w, h)

+ area(grid, x, y + 1, w, h)

+ 1;

}

};

Related problems:

花花酱 LeetCode 685. Redundant Connection II

By zxi on October 7, 2017

Problem:

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, …, N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] that represents a directed edge connecting nodes u and v, where u is a parent of child v.

Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

Example 1:

Input: [[1,2], [1,3], [2,3]]

Output: [2,3]

Explanation: The given directed graph will be like this:

/ \

v v

2-->3

Example 2:

Input: [[1,2], [2,3], [3,4], [4,1], [1,5]]

Output: [4,1]

Explanation: The given directed graph will be like this:

5 <- 1 -> 2

^ |

| v

4 <- 3

Note:

The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

Idea:

Union Find

Time complexity: O(nlog*n) ~ O(n)

Space complexity: O(n)

Solution:

C++

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {

vector<int> parents(edges.size() + 1, 0);

vector<int> roots(edges.size() + 1, 0);

vector<int> sizes(edges.size() + 1, 1);

vector<int> ans1;

vector<int> ans2;

for(auto& edge: edges) {

int u = edge[0];

int v = edge[1];

// A node has two parents

if (parents[v] > 0) {

ans1 = {parents[v], v};

ans2 = edge;

// Delete the later edge

edge[0] = edge[1] = -1;

}

parents[v] = u;

}

for(const auto& edge: edges) {

int u = edge[0];

int v = edge[1];

// Invalid edge (we deleted in step 1)

if (u < 0 || v < 0) continue;

if (!roots[u]) roots[u] = u;

if (!roots[v]) roots[v] = v;

int pu = find(u, roots);

int pv = find(v, roots);

// Both u and v are already in the tree

if (pu == pv)

return ans1.empty() ? edge : ans1;

// Unoin, always merge smaller set (pv) to larger set (pu)

if (sizes[pv] > sizes[pu])

swap(pu, pv);

roots[pv] = pu;

sizes[pu] += sizes[pv];

}

return ans2;

}

private:

int find(int node, vector<int>& roots) {

while (roots[node] != node) {

roots[node] = roots[roots[node]];

node = roots[node];

}

return node;

}

};

C++ / without using Union find

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {

vector<int> parents(edges.size() + 1, 0);

vector<int> ans1;

vector<int> ans2;

bool dup_parents = false;

for(auto& edge: edges) {

int u = edge[0];

int v = edge[1];

// A node has two parents

if (parents[v] > 0) {

ans1 = {parents[v], v};

ans2 = edge;

dup_parents = true;

// Delete the later edge

edge[0] = edge[1] = -1;

} else {

parents[v] = u;

}

// Reset parents

parents = vector<int>(edges.size() + 1, 0);

for(const auto& edge: edges) {

int u = edge[0];

int v = edge[1];

// Invalid edge (we deleted in step 1)

if (u < 0 || v < 0) continue;

parents[v] = u;

if (cycle(v, parents))

return dup_parents ? ans1 : edge;

}

return ans2;

}

private:

bool cycle(int v, const vector<int>& parents) {

int u = parents[v];

while (u) {

if (u == v) return true;

u = parents[u];

}

return false;

}

};

Python

"""

Author: Huahua

Runtime: 62 ms

"""

class Solution:

def findRedundantDirectedConnection(self, edges):

def cycle(v, p):

u = p[v]

while u != 0:

if u == v: return True

u = p[u]

return False

n = len(edges)

p = [0] * (n + 1)

ans1 = []

ans2 = []

dup_p = False

for e in edges:

u, v = e

if p[v] > 0:

ans1 = [p[v], v]

ans2 = [u, v]

dup_p = True

e[0] = e[1] = -1

else:

p[v] = u

p = [0] * (n + 1)

for u, v in edges:

if u < 0: continue

p[v] = u

if cycle(v, p):

return ans1 if dup_p else [u, v]

return ans2

花花酱 LeetCode 543. Diameter of Binary Tree

By zxi on October 7, 2017

Problem:

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

/ \

2 3

/ \

4 5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

Idea:

Recursion

Solution1:

C++

class Solution {

public:

int diameterOfBinaryTree(TreeNode* root) {

ans_ = 0;

LP(root);

return ans_;

}

private:

int ans_;

int LP(TreeNode* root) {

if (!root) return -1;

int l = LP(root->left) + 1;

int r = LP(root->right) + 1;

ans_ = max(ans_, l + r);

return max(l, r);

}

};

Solution 2: passed 101/106 TLE

C++ / Floyd-Warshall

// Author: Huahua

// State: 101/106 passed TLE

class Solution {

public:

int diameterOfBinaryTree(TreeNode* root) {

if (!root) return 0;

edges_.clear();

int n = 0;

buildGraph(root, n, -1);

vector<vector<int>> d(n, vector<int>(n, n));

for (int i = 0; i < n; ++i) d[i][i] = 0;

for (const auto& pair : edges_)

d[pair.first][pair.second] = 1;

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

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

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

d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

int ans = INT_MIN;

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

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

if (d[i][j] == n) continue;

ans = max(ans, d[i][j]);

}

return ans;

}

private:

void buildGraph(TreeNode* node, int& id, int pid) {

if (!node) return;

int node_id = id++;

if (pid >= 0) {

edges_.emplace_back(node_id, pid);

edges_.emplace_back(pid, node_id);

}

buildGraph(node->left, id, node_id);

buildGraph(node->right, id, node_id);

}

vector<pair<int,int>> edges_;

};

Solution 3:

Simulate recursion with a stack. We also need to track the return value of each node.

Python

"""

Author: Huahua

Runtime: 82 ms

"""

class Solution:

def diameterOfBinaryTree(self, root):

if not root: return 0

d = {None: -1}

s = [root]

ans = 0

while s:

node = s[-1]

if node.left in d and node.right in d:

s.pop()

l = d[node.left] + 1

r = d[node.right] + 1

ans = max(ans, l + r)

d[node] = max(l, r)

else:

if node.left: s.append(node.left)

if node.right: s.append(node.right)

return ans

C++

// Author: Huahua

// Runtime: 15 ms

class Solution {

public:

int diameterOfBinaryTree(TreeNode* root) {

if (!root) return 0;

int ans = 0;

unordered_map<TreeNode*, int> d{{nullptr, -1}};

stack<TreeNode*> s;

s.push(root);

while (!s.empty()) {

TreeNode* node = s.top();

if (d.count(node->left) && d.count(node->right)) {

int l = d[node->left] + 1;

int r = d[node->right] + 1;

ans = max(ans, l + r);

d[node] = max(l, r);

// children's results will never be used again, safe to delete here.

if (node->left) d.erase(node->left);

if (node->right) d.erase(node->right);

s.pop();

} else {

if (node->left) s.push(node->left);

if (node->right) s.push(node->right);

}

return ans;

}

};

Related Problems:

花花酱 LeetCode 39. Combination Sum

By zxi on October 3, 2017

Problem:

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[

[7],

[2, 2, 3]

]

Idea:

DFS

Solution: C++

class Solution {

public:

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

vector<vector<int>> ans;

vector<int> cur;

std::sort(candidates.begin(), candidates.end());

dfs(candidates, target, 0, cur, ans);

return ans;

}

private:

void dfs(vector<int>& candidates, int target, int s, vector<int>& cur, vector<vector<int>>& ans) {

if (target == 0) {

ans.push_back(cur);

return;

}

for (int i = s; i < candidates.size(); ++i) {

if (candidates[i] > target) break;

cur.push_back(candidates[i]);

dfs(candidates, target - candidates[i], i, cur, ans);

cur.pop_back();

}

};

Python

"""

Author: Huahua

Runtime: 75 ms (batter than 97.04%)

"""

class Solution(object):

def combinationSum(self, candidates, target):

def dfs(candidates, target, s, curr, ans):

if target == 0:

ans.append(curr[:])

return

for i in xrange(s, len(candidates)):

if candidates[i] > target: return

curr.append(candidates[i])

dfs(candidates, target - candidates[i], i, curr, ans)

curr.pop()

ans = []

candidates.sort()

dfs(candidates, target, 0, [], ans);

return ans

Huahua's Tech Road

花花酱 LeetCode 693. Binary Number with Alternating Bits

花花酱 LeetCode 695. Max Area of Island

花花酱 LeetCode 685. Redundant Connection II

花花酱 LeetCode 543. Diameter of Binary Tree

花花酱 LeetCode 39. Combination Sum