Huahua's Tech Road

花花酱 LeetCode 1109. Corporate Flight Bookings

By zxi on July 11, 2019

There are n flights, and they are labeled from 1 to n.

We have a list of flight bookings. The i-th booking bookings[i] = [i, j, k] means that we booked kseats from flights labeled i to j inclusive.

Return an array answer of length n, representing the number of seats booked on each flight in order of their label.

Example 1:

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]

Constraints:

1 <= bookings.length <= 20000
1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000
1 <= bookings[i][2] <= 10000

Solution: Marking start and end

Time complexity: O(|bookings|)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {

vector<int> ans(n + 1);

for (const auto& b : bookings) {

ans[b[0] - 1] += b[2];

ans[b[1]] -= b[2];

}

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

ans[i] += ans[i - 1];

ans.pop_back();

return ans;

}

};

花花酱 LeetCode 1108. Defanging an IP Address

By zxi on July 11, 2019

Given a valid (IPv4) IP address, return a defanged version of that IP address.

A defanged IP address replaces every period "." with "[.]".

Example 1:

Input: address = "1.1.1.1"
Output: "1[.]1[.]1[.]1"

Example 2:

Input: address = "255.100.50.0"
Output: "255[.]100[.]50[.]0"

Constraints:

The given address is a valid IPv4 address.

Solution: String

Time complexity: O(n)
Space complexity: O(n)

C++

class Solution {

public:

string defangIPaddr(string address) {

string output;

for (const char c : address) {

if (c == '.') output += "[.]";

else output += c;

}

return output;

}

};

花花酱 LeetCode 391. Perfect Rectangle

By zxi on July 11, 2019

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1:

rectangles = [

[1,1,3,3],

[3,1,4,2],

[3,2,4,4],

[1,3,2,4],

[2,3,3,4]

]

Return true. All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

rectangles = [

[1,1,2,3],

[1,3,2,4],

[3,1,4,2],

[3,2,4,4]

]

Return false. Because there is a gap between the two rectangular regions.

Example 3:

rectangles = [

[1,1,3,3],

[3,1,4,2],

[1,3,2,4],

[3,2,4,4]

]

Return false. Because there is a gap in the top center.

Example 4:

rectangles = [

[1,1,3,3],

[3,1,4,2],

[1,3,2,4],

[2,2,4,4]

]

Return false. Because two of the rectangles overlap with each other.

Solution: Counting corner points

C++

// Author: Huahua

class Solution {

public:

bool isRectangleCover(vector<vector<int>>& rectangles) {

set<pair<int, int>> corners;

int area = 0;

for (const auto& rect : rectangles) {

pair<int, int> p1{rect[0], rect[1]};

pair<int, int> p2{rect[2], rect[1]};

pair<int, int> p3{rect[2], rect[3]};

pair<int, int> p4{rect[0], rect[3]};

for (const auto& p : {p1, p2, p3, p4}) {

const auto& ret = corners.insert(p);

if (!ret.second) corners.erase(ret.first);

}

area += (p3.first - p1.first) * (p3.second - p1.second);

}

if (corners.size() != 4) return false;

const auto& p1 = *begin(corners);

const auto& p3 = *rbegin(corners);

return area == (p3.first - p1.first) * (p3.second - p1.second);

}

};

花花酱 LeetCode 1104. Path In Zigzag Labelled Binary Tree

By zxi on July 1, 2019

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,…), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,…), the labelling is right to left.

Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output: [1,2,6,10,26]

Constraints:

1 <= label <= 10^6

Solution: Math

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

vector<int> pathInZigZagTree(int label) {

deque<int> ans;

while (label) {

ans.push_front(label);

int h = 31 - __builtin_clz(label);

label = ((1 << h) + (1 << (h + 1)) - 1 - label) / 2;

}

return {begin(ans), end(ans)};

}

};

花花酱 LeetCode 1106. Parsing A Boolean Expression

By zxi on June 30, 2019

Return the result of evaluating a given boolean expression, represented as a string.

An expression can either be:

"t", evaluating to True;
"f", evaluating to False;
"!(expr)", evaluating to the logical NOT of the inner expression expr;
"&(expr1,expr2,...)", evaluating to the logical AND of 2 or more inner expressions expr1, expr2, ...;
"|(expr1,expr2,...)", evaluating to the logical OR of 2 or more inner expressions expr1, expr2, ...

Example 1:

Input: expression = "!(f)"
Output: true

Example 2:

Input: expression = "|(f,t)"
Output: true

Example 3:

Input: expression = "&(t,f)"
Output: false

Example 4:

Input: expression = "|(&(t,f,t),!(t))"
Output: false

Solution: Recursion

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool parseBoolExpr(string expression) {

int s = 0;

return parse(expression, s);

}

private:

bool parse(const string& exp, int& s) {

char ch = exp[s++];

if (ch == 't') return true;

if (ch == 'f') return false;

if (ch == '!') {

bool ans = !parse(exp, ++s);

++s;

return ans;

}

bool is_and = (ch == '&');

bool ans = is_and;

++s;

while (true) {

if (is_and) ans &= parse(exp, s);

else ans |= parse(exp, s);

if (exp[s++] == ')') break;

}

return ans;

}

};

Java

class Solution {

private int s;

private char[] exp;

public boolean parseBoolExpr(String expression) {

exp = expression.toCharArray();

s = 0;

return parse() == 1;

}

private int parse() {

char ch = exp[s++];

if (ch == 't') return 1;

if (ch == 'f') return 0;

if (ch == '!') {

++s;

int ans = 1 - parse();

++s;

return ans;

}

boolean is_and = (ch == '&');

int ans = is_and ? 1 : 0;

++s;

while (true) {

if (is_and) ans &= parse();

else ans |= parse();

if (exp[s++] == ')') break;

}

return ans;

}