Posts tagged as “easy”

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

}

};

Problem

Design your implementation of the circular double-ended queue (deque).
Your implementation should support following operations:

MyCircularDeque(k): Constructor, set the size of the deque to be k.
insertFront(): Adds an item at the front of Deque. Return true if the operation is successful.
insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful.
deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.
deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful.
getFront(): Gets the front item from the Deque. If the deque is empty, return -1.
getRear(): Gets the last item from Deque. If the deque is empty, return -1.
isEmpty(): Checks whether Deque is empty or not.
isFull(): Checks whether Deque is full or not.

Example:

MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
circularDeque.insertLast(1);			// return true
circularDeque.insertLast(2);			// return true
circularDeque.insertFront(3);			// return true
circularDeque.insertFront(4);			// return false, the queue is full
circularDeque.getRear();  				// return 32
circularDeque.isFull();				// return true
circularDeque.deleteLast();			// return true
circularDeque.insertFront(4);			// return true
circularDeque.getFront();				// return 4

Note:

All values will be in the range of [1, 1000].
The number of operations will be in the range of [1, 1000].
Please do not use the built-in Deque library.

Solution

Using head and tail to pointer to the head and the tail in the circular buffer.

// Author: Huahua

// Running time: 20 ms

class MyCircularDeque {

public:

/** Initialize your data structure here. Set the size of the deque to be k. */

MyCircularDeque(int k): k_(k), q_(k), head_(1), tail_(-1), size_(0) {}

/** Adds an item at the front of Deque. Return true if the operation is successful. */

bool insertFront(int value) {

if (isFull()) return false;

head_ = (head_ - 1 + k_) % k_;

q_[head_] = value;

if (size_ == 0) tail_ = head_;

++size_;

return true;

}

/** Adds an item at the rear of Deque. Return true if the operation is successful. */

bool insertLast(int value) {

if (isFull()) return false;

tail_ = (tail_ + 1 + k_) % k_;

q_[tail_] = value;

if (size_ == 0) head_ = tail_;

++size_;

return true;

}

/** Deletes an item from the front of Deque. Return true if the operation is successful. */

bool deleteFront() {

if (isEmpty()) return false;

head_ = (head_ + 1 + k_) % k_;

--size_;

return true;

}

/** Deletes an item from the rear of Deque. Return true if the operation is successful. */

bool deleteLast() {

if (isEmpty()) return false;

tail_ = (tail_ - 1 + k_) % k_;

--size_;

return true;

}

/** Get the front item from the deque. */

int getFront() {

if (isEmpty()) return -1;

return q_[head_];

}

/** Get the last item from the deque. */

int getRear() {

if (isEmpty()) return -1;

return q_[tail_];

}

/** Checks whether the circular deque is empty or not. */

bool isEmpty() {

return size_ == 0;

}

/** Checks whether the circular deque is full or not. */

bool isFull() {

return size_ == k_;

}

private:

const int k_;

int head_;

int tail_;

int size_;

vector<int> q_;

};

Posts tagged as “easy”

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

花花酱 LeetCode 641. Design Circular Deque

Problem

Solution

Related Problems