Problem

题目大意：给你四个点判断能否构成正方形。

https://leetcode.com/problems/valid-square/description/

Given the coordinates of four points in 2D space, return whether the four points could construct a square.

The coordinate (x,y) of a point is represented by an integer array with two integers.

Example:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: True

Note:

All the input integers are in the range [-10000, 10000].
A valid square has four equal sides with positive length and four equal angles (90-degree angles).
Input points have no order.

Solution

Time complexity: O(1)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {

set<int> s{distSqr(p1, p2), distSqr(p1, p3), distSqr(p1, p4), distSqr(p2, p3), distSqr(p2, p4), distSqr(p3, p4)};

return !s.count(0) && s.size() == 2;

}

private:

static inline int distSqr(const vector<int>& p1, const vector<int>& p2) {

return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);

}

};

Problem:

link: https://leetcode.com/problems/my-calendar-iii/description/

Implement a MyCalendarThree class to store your events. A new event can always be added.

Your class will have one method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A K-booking happens when K events have some non-empty intersection (ie., there is some time that is common to all K events.)

For each call to the method MyCalendar.book, return an integer K representing the largest integer such that there exists a K-booking in the calendar.

Your class will be called like this: MyCalendarThree cal = new MyCalendarThree();MyCalendarThree.book(start, end)

Example 1:

MyCalendarThree();
MyCalendarThree.book(10, 20); // returns 1
MyCalendarThree.book(50, 60); // returns 1
MyCalendarThree.book(10, 40); // returns 2
MyCalendarThree.book(5, 15); // returns 3
MyCalendarThree.book(5, 10); // returns 3
MyCalendarThree.book(25, 55); // returns 3
Explanation: 
The first two events can be booked and are disjoint, so the maximum K-booking is a 1-booking.
The third event [10, 40) intersects the first event, and the maximum K-booking is a 2-booking.
The remaining events cause the maximum K-booking to be only a 3-booking.
Note that the last event locally causes a 2-booking, but the answer is still 3 because
eg. [10, 20), [10, 40), and [5, 15) are still triple booked.

Note:

The number of calls to MyCalendarThree.book per test case will be at most 400.
In calls to MyCalendarThree.book(start, end), start and end are integers in the range [0, 10^9].

Idea:

Similar to LeetCode 731 My Calendar II Use an ordered / tree map to track the number of event at current time.

For a new book event, increase the number of events at start, decrease the number of events at end.

Scan the timeline to find the maximum number of events.

Solution 1: Count Boundaries

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Runtime: 116 ms

class MyCalendarThree {

public:

MyCalendarThree() {}

int book(int start, int end) {

++deltas_[start];

--deltas_[end];

int ans = 0;

int curr = 0;

for (const auto& kv : deltas_)

ans = max(ans, curr += kv.second);

return ans;

}

private:

map<int, int> deltas_;

};

Solution 2

C++

// Author: Huahua

// Runtime: 66 ms

class MyCalendarThree {

public:

MyCalendarThree() {

counts_[INT_MIN] = 0;

counts_[INT_MAX] = 0;

max_count_ = 0;

}

int book(int start, int end) {

auto l = prev(counts_.upper_bound(start)); // l->first < start

auto r = counts_.lower_bound(end); // r->first >= end

for (auto curr = l, next = curr; curr != r; curr = next) {

++next;

if (next->first > end)

counts_[end] = curr->second;

if (curr->first <= start && next->first > start)

max_count_ = max(max_count_, counts_[start] = curr->second + 1);

else

max_count_ = max(max_count_, ++curr->second);

}

return max_count_;

}

private:

map<int, int> counts_;

int max_count_;

};

Solution 3: Segment Tree

C++

// Author: Huahua

// Runtime: 63 ms (<95.65%)

class MyCalendarThree {

public:

MyCalendarThree(): max_count_(0) {

root_.reset(new Node(0, 100000000, 0));

}

int book(int start, int end) {

Add(start, end, root_.get());

return max_count_;

}

private:

struct Node {

Node(int l, int r, int count):l(l), m(-1), r(r), count(count){}

int l;

int m;

int r;

int count;

std::unique_ptr<Node> left;

std::unique_ptr<Node> right;

};

void Add(int start, int end, Node* root) {

if (root->m != -1) {

if (end <= root->m)

Add(start, end, root->left.get());

else if(start >= root->m)

Add(start, end, root->right.get());

else {

Add(start, root->m, root->left.get());

Add(root->m, end, root->right.get());

}

return;

}

if (start == root->l && end == root->r)

max_count_ = max(max_count_, ++root->count);

else if (start == root->l) {

root->m = end;

root->left.reset(new Node(start, root->m, root->count + 1));

root->right.reset(new Node(root->m, root->r, root->count));

max_count_ = max(max_count_, root->count + 1);

} else if(end == root->r) {

root->m = start;

root->left.reset(new Node(root->l, root->m, root->count));

root->right.reset(new Node(root->m, root->r, root->count + 1));

max_count_ = max(max_count_, root->count + 1);

} else {

root->m = start;

root->left.reset(new Node(root->l, root->m, root->count));

root->right.reset(new Node(root->m, root->r, root->count));

Add(start, end, root->right.get());

}

std::unique_ptr<Node> root_;

int max_count_;

};

Python3

"""

Author: Huahua

Runtime: 436 ms (<88.88%)

"""

class Node:

def __init__(self, l, r, count):

self.l = l

self.m = -1

self.r = r

self.count = count

self.left = None

self.right = None

class MyCalendarThree:

def __init__(self):

self.root = Node(0, 10**9, 0)

self.max = 0

def book(self, start, end):

self.add(start, end, self.root)

return self.max

def add(self, start, end, root):

if root.m != -1:

if end <= root.m: self.add(start, end, root.left)

elif start >= root.m: self.add(start, end, root.right)

else:

self.add(start, root.m, root.left)

self.add(root.m, end, root.right)

return

if start == root.l and end == root.r:

root.count += 1

self.max = max(self.max, root.count)

elif start == root.l:

root.m = end

root.left = Node(start, root.m, root.count + 1)

root.right = Node(root.m, root.r, root.count)

self.max = max(self.max, root.count + 1)

elif end == root.r:

root.m = start;

root.left = Node(root.l, root.m, root.count)

root.right = Node(root.m, root.r, root.count + 1)

self.max = max(self.max, root.count + 1)

else:

root.m = start

root.left = Node(root.l, root.m, root.count)

root.right = Node(root.m, root.r, root.count)

self.add(start, end, root.right)

Related Problems:

Posts tagged as “geometry”

花花酱 LeetCode 593. Valid Square

Problem

Solution

花花酱 LeetCode 732. My Calendar III

Solution 1: Count Boundaries

C++

Solution 2

C++

Solution 3: Segment Tree

C++

Python3