Posts tagged as “easy”

花花酱 LeetCode 887. Projection Area of 3D Shapes

By zxi on August 4, 2018

Problem

On a N * N grid, we place some 1 * 1 * 1 cubes that are axis-aligned with the x, y, and z axes.

Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).

Now we view the projection of these cubes onto the xy, yz, and zx planes.

A projection is like a shadow, that maps our 3 dimensional figure to a 2 dimensional plane.

Here, we are viewing the “shadow” when looking at the cubes from the top, the front, and the side.

Return the total area of all three projections.

Example 1:

Input: [[2]]
Output: 5

Example 2:

Input: [[1,2],[3,4]]
Output: 17
Explanation: 
Here are the three projections ("shadows") of the shape made with each axis-aligned plane.

Example 3:

Input: [[1,0],[0,2]]
Output: 8

Example 4:

Input: [[1,1,1],[1,0,1],[1,1,1]]
Output: 14

Example 5:

Input: [[2,2,2],[2,1,2],[2,2,2]]
Output: 21

Note:

1 <= grid.length = grid[0].length <= 50
0 <= grid[i][j] <= 50

Solution: Brute Force

Sum of max heights for each cols / rows + # of non-zero-height bars.

Time complexity: O(mn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time : 4 ms

class Solution {

public:

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

int n = grid.size();

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

int ans = 0;

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

int h = 0;

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

h = max(h, grid[i][j]);

if (grid[i][j] != 0) ++ans;

}

ans += h;

}

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

int h = 0;

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

h = max(h, grid[i][j]);

ans += h;

}

return ans;

}

};

花花酱 LeetCode 101. Symmetric Tree

By zxi on July 26, 2018

Problem

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

class Solution {

public:

bool isSymmetric(TreeNode* root) {

return isMirror(root, root);

}

private:

bool isMirror(TreeNode* root1, TreeNode* root2) {

if (!root1 && !root2) return true;

if (!root1 || !root2) return false;

return root1->val == root2->val

&& isMirror(root1->right, root2->left)

&& isMirror(root1->left, root2->right);

}

};

Python

"""

Author: Huahua

Running time: 48 ms

"""

class Solution:

def isSymmetric(self, root):

def isMirror(root1, root2):

if not root1 and not root2: return True

if not root1 or not root2: return False

return root1.val == root2.val \

and isMirror(root1.left, root2.right) \

and isMirror(root2.left, root1.right)

return isMirror(root, root)

Problem

A robot on an infinite grid starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:

-2: turn left 90 degrees
-1: turn right 90 degrees
1 <= x <= 9: move forward x units

Some of the grid squares are obstacles.

The i-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])

If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)

Return the square of the maximum Euclidean distance that the robot will be from the origin.

Example 1:

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: robot will go to (3, 4)

Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)

Note:

0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
The answer is guaranteed to be less than 2 ^ 31.

Solution: Simulation

Time complexity: O(n + sum(x)) = O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 60 ms

class Solution {

public:

int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {

int x = 0;

int y = 0;

int dirs[][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // WNES

int d = 1;

unordered_map<int, unordered_set<int>> o;

for (const auto obstacle : obstacles)

o[obstacle[0]].insert(obstacle[1]);

int ans = 0;

for (int c : commands) {

if (c == -2)

d = (d - 1 + 4) % 4;

else if (c == -1)

d = (d + 1) % 4;

else {

while (c--) {

int tx = x + dirs[d][0];

int ty = y + dirs[d][1];

if (o.count(tx) && o.at(tx).count(ty))

break;

x = tx;

y = ty;

ans = max(ans, x * x + y * y);

}

return ans;

}

};

花花酱 LeetCode 872. Leaf-Similar Trees

By zxi on July 21, 2018

Problem

Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Note:

Both of the given trees will have between 1 and 100 nodes.

Solution: Recursion

Time complexity: O(n1 + n2)

Space complexity: O(n1 + n2)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

bool leafSimilar(TreeNode* root1, TreeNode* root2) {

vector<int> leafs1;

vector<int> leafs2;

getLeafs(root1, leafs1);

getLeafs(root2, leafs2);

return leafs1 == leafs2;

}

private:

void getLeafs(TreeNode* root, vector<int>& leafs) {

if (root == nullptr) return;

if (root->left == nullptr && root->right == nullptr)

leafs.push_back(root->val);

getLeafs(root->left, leafs);

getLeafs(root->right, leafs);

}

};

Python

"""

Author: Huahua

Running time: 24 ms

"""

class Solution(object):

def leafSimilar(self, root1, root2):

def getLeafs(root):

if not root: return []

if not root.left and not root.right: return [root.val]

return getLeafs(root.left) + getLeafs(root.right)

return getLeafs(root1) == getLeafs(root2)

Posts tagged as “easy”

花花酱 LeetCode 887. Projection Area of 3D Shapes

Problem

Solution: Brute Force

花花酱 LeetCode 101. Symmetric Tree

Problem

Solution: Recursion

C++

Python

Related Problems

花花酱 LeetCode 874. Walking Robot Simulation

Problem

Solution: Simulation

花花酱 LeetCode 872. Leaf-Similar Trees

Problem

Solution: Recursion

Posts tagged as “easy”

花花酱 LeetCode 887. Projection Area of 3D Shapes

Problem

Solution: Brute Force

花花酱 LeetCode 876. Middle of the Linked List

Problem

Solution: Slow + Fast Pointers

花花酱 LeetCode 101. Symmetric Tree

Problem

Solution: Recursion

C++

Python

Related Problems

花花酱 LeetCode 874. Walking Robot Simulation

Problem

Solution: Simulation

花花酱 LeetCode 872. Leaf-Similar Trees

Problem

Solution: Recursion