花花酱 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)

花花酱 LeetCode 836. Rectangle Overlap

By zxi on July 19, 2018

Problem

A rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) are the coordinates of its bottom-left corner, and (x2, y2) are the coordinates of its top-right corner.

Two rectangles overlap if the area of their intersection is positive. To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two (axis-aligned) rectangles, return whether they overlap.

Example 1:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

Example 2:

Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: false

Notes:

Both rectangles rec1 and rec2 are lists of 4 integers.
All coordinates in rectangles will be between -10^9 and 10^9.

Solution: Geometry

Time complexity: O(1)

Space complexity: O(1)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {

return rec1[0] < rec2[2] && rec2[0] < rec1[2] &&

rec1[1] < rec2[3] && rec2[1] < rec1[3];

}

};

花花酱 LeetCode 345. Reverse Vowels of a String

By zxi on July 19, 2018

Problem

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = “hello”, return “holle”.

Example 2:
Given s = “leetcode”, return “leotcede”.

Note:
The vowels does not include the letter “y”.

Solution

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

string reverseVowels(string s) {

int i = 0;

int j = s.size() - 1;

while (i < j) {

while (!isVowel(s[i]) && i < j) ++i;

while (!isVowel(s[j]) && i < j) --j;

swap(s[i++], s[j--]);

}

return s;

}

private:

bool isVowel(char c) {

c = tolower(c);

return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';

}

};

花花酱 LeetCode 427. Construct Quad Tree

By zxi on July 17, 2018

Problem

We want to use quad trees to store an N x N boolean grid. Each cell in the grid can only be true or false. The root node represents the whole grid. For each node, it will be subdivided into four children nodes until the values in the region it represents are all the same.

Each node has another two boolean attributes : isLeaf and val. isLeaf is true if and only if the node is a leaf node. The val attribute for a leaf node contains the value of the region it represents.

Your task is to use a quad tree to represent a given grid. The following example may help you understand the problem better:

Given the 8 x 8 grid below, we want to construct the corresponding quad tree:

It can be divided according to the definition above:

The corresponding quad tree should be as following, where each node is represented as a (isLeaf, val)pair.

For the non-leaf nodes, val can be arbitrary, so it is represented as *.

Note:

N is less than 1000 and guaranteened to be a power of 2.
If you want to know more about the quad tree, you can refer to its wiki.

Solution: Recursion

Time complexity: O(n^2*logn)

Space complexity: O(n^2)

C++

// Author: Huahua

// Running time: 44 ms

class Solution {

public:

Node* construct(vector<vector<int>>& grid) {

return construct(grid, 0, 0, grid.size());

}

private:

Node* construct(const vector<vector<int>>& grid, int x, int y, int n) {

if (n == 0) return nullptr;

bool all_zeros = true;

bool all_ones = true;

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

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

if (grid[i][j] == 0)

all_ones = false;

else

all_zeros = false;

if (all_zeros || all_ones)

return new Node(all_ones, true, nullptr, nullptr, nullptr, nullptr);

return new Node(true, false,

construct(grid, x, y, n/2), // topLeft

construct(grid, x + n/2, y, n/2), // topRight

construct(grid, x, y + n/2, n/2), // bottomLeft

construct(grid, x + n/2, y + n/2, n/2)); // bottomRight

}

};

Time complexity: O(n^2)

Space complexity: O(n^2)

// Author: Huahua

// Running time: 56 ms

class Solution {

public:

Node* construct(vector<vector<int>>& grid) {

return construct(grid, 0, 0, grid.size());

}

private:

Node* construct(const vector<vector<int>>& grid, int x, int y, int n) {

if (n == 0) return nullptr;

if (n == 1) return new Node(grid[y][x], true, nullptr, nullptr, nullptr, nullptr);

auto tl = construct(grid, x, y, n/2); // topLeft

auto tr = construct(grid, x + n/2, y, n/2); // topRight

auto bl = construct(grid, x, y + n/2, n/2); // bottomLeft

auto br = construct(grid, x + n/2, y + n/2, n/2); // bottomRight

if (tl->isLeaf && tr->isLeaf && bl->isLeaf && br->isLeaf

&& tl->val == tr->val && tl->val == bl->val && tl->val == br->val) {

auto root = new Node(tl->val, true, nullptr, nullptr, nullptr, nullptr);

delete tl;

delete tr;

delete bl;

delete br;

return root;

}

return new Node(true, false, tl, tr, bl, br);

}

};

花花酱 LeetCode 643. Maximum Average Subarray I

By zxi on July 16, 2018

Problem

题目大意：找出k长度的子数组的平均值的最大值。

https://leetcode.com/problems/maximum-average-subarray-i/description/

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

1 <= k <= n <= 30,000.
Elements of the given array will be in the range [-10,000, 10,000].

Solution: Sliding Window

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 124 ms

class Solution {

public:

double findMaxAverage(vector<int>& nums, int k) {

const int n = nums.size();

int sum = 0;

int ans = INT_MIN;

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

if (i >= k) sum -= nums[i - k];

sum += nums[i];

if (i + 1 >= k) ans = max(ans, sum);

}

return static_cast<double>(ans) / k;

}

};

Posts tagged as “easy”

花花酱 LeetCode 872. Leaf-Similar Trees

Problem

Solution: Recursion

花花酱 LeetCode 836. Rectangle Overlap

Problem

Solution: Geometry

花花酱 LeetCode 345. Reverse Vowels of a String

Problem

Solution

花花酱 LeetCode 427. Construct Quad Tree

Problem

Solution: Recursion

花花酱 LeetCode 643. Maximum Average Subarray I

Problem

Solution: Sliding Window

Related Problems