Huahua’s Tech Road

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

}

花花酱 LeetCode 1105. Filling Bookcase Shelves

By zxi on June 29, 2019

We have a sequence of books: the i-th book has thickness books[i][0] and height books[i][1].

We want to place these books in order onto bookcase shelves that have total width shelf_width.

We choose some of the books to place on this shelf (such that the sum of their thickness is <= shelf_width), then build another level of shelf of the bookcase so that the total height of the bookcase has increased by the maximum height of the books we just put down. We repeat this process until there are no more books to place.

Note again that at each step of the above process, the order of the books we place is the same order as the given sequence of books. For example, if we have an ordered list of 5 books, we might place the first and second book onto the first shelf, the third book on the second shelf, and the fourth and fifth book on the last shelf.

Return the minimum possible height that the total bookshelf can be after placing shelves in this manner.

Example 1:

Input: books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width = 4
Output: 6
Explanation:
The sum of the heights of the 3 shelves are 1 + 3 + 2 = 6.
Notice that book number 2 does not have to be on the first shelf.

Constraints:

1 <= books.length <= 1000
1 <= books[i][0] <= shelf_width <= 1000
1 <= books[i][1] <= 1000

Solution: DP

dp[i] := min height of placing books[0] ~ books[i]
dp[-1] = 0
dp[j] = min{dp[i-1] + max(h[i] ~ h[j])}, 0 < i <= j, sum(w[i] ~ w[j]) <= shelf_width

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

C++

// Author: Huahua, running time: 0 ms

class Solution {

public:

int minHeightShelves(vector<vector<int>>& books, int sw) {

int n = books.size();

vector<int> dp(n, INT_MAX / 2);

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

int w = 0;

int h = 0;

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

if ((w += books[j][0]) > sw) break;

h = max(h, books[j][1]);

dp[j] = min(dp[j], (i == 0 ? 0 : dp[i - 1]) + h);

}

return dp.back();

}

};

Huahua's Tech Road

花花酱 LeetCode 1108. Defanging an IP Address

Solution: String

C++

花花酱 LeetCode 391. Perfect Rectangle

Solution: Counting corner points

C++

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

Solution: Math

C++

花花酱 LeetCode 1106. Parsing A Boolean Expression

Solution: Recursion

C++

Java

花花酱 LeetCode 1105. Filling Bookcase Shelves

Solution: DP

C++