Huahua’s Tech Road

花花酱 LeetCode 731. My Calendar II – 花花酱

By zxi on November 19, 2017

Problem:

Implement a MyCalendarTwo class to store your events. A new event can be added if adding the event will not cause a triple booking.

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 triple booking happens when three events have some non-empty intersection (ie., there is some time that is common to all 3 events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.

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

Example 1:

MyCalendar();

MyCalendar.book(10, 20); // returns true

MyCalendar.book(50, 60); // returns true

MyCalendar.book(10, 40); // returns true

MyCalendar.book(5, 15); // returns false

MyCalendar.book(5, 10); // returns true

MyCalendar.book(25, 55); // returns true

Explanation<b>:</b>

The first two events can be booked. The third event can be double booked.

The fourth event (5, 15) can't be booked, because it would result in a triple booking.

The fifth event (5, 10) can be booked, as it does not use time 10 which is already double booked.

The sixth event (25, 55) can be booked, as the time in [25, 40) will be double booked with the third event;

the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

Note:

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

Idea:

Brute Force

Solution1:

Brute Force

Time Complexity: O(n^2)

Space Complexity: O(n)

// Author: Huahua

// Runtime: 82 ms

class MyCalendarTwo {

public:

MyCalendarTwo() {}

bool book(int start, int end) {

for (const auto& kv : overlaps_)

if (max(start, kv.first) < min(end, kv.second)) return false;

for (const auto& kv : booked_) {

const int ss = max(start, kv.first);

const int ee = min(end, kv.second);

if (ss < ee) overlaps_.emplace_back(ss, ee);

}

booked_.emplace_back(start, end);

return true;

}

private:

vector<pair<int, int>> booked_;

vector<pair<int, int>> overlaps_;

};

Java

// Author: Huahua

// Runtime: 156 ms

class MyCalendarTwo {

private List<int[]> booked_;

private List<int[]> overlaps_;

public MyCalendarTwo() {

booked_ = new ArrayList<>();

overlaps_ = new ArrayList<>();

}

public boolean book(int start, int end) {

for (int[] range : overlaps_)

if (Math.max(range[0], start) < Math.min(range[1], end))

return false;

for (int[] range : booked_) {

int ss = Math.max(range[0], start);

int ee = Math.min(range[1], end);

if (ss < ee) overlaps_.add(new int[]{ss, ee});

}

booked_.add(new int[]{start, end});

return true;

}

Python

"""

Author: Huahua

Runtime: 638 ms

"""

class MyCalendarTwo:

def __init__(self):

self.booked_ = []

self.overlaps_ = []

def book(self, start, end):

for s, e in self.overlaps_:

if start < e and end > s: return False

for s, e in self.booked_:

if start < e and end > s:

self.overlaps_.append([max(start, s), min(end, e)])

self.booked_.append([start, end])

return True

Solution 2:

Counting

Time Complexity: O(n^2logn)

Space Complexity: O(n)

// Author: Huahua

// Runtime: 212 ms

class MyCalendarTwo {

public:

MyCalendarTwo() {}

bool book(int start, int end) {

++delta_[start];

--delta_[end];

int count = 0;

for (const auto& kv : delta_) {

count += kv.second;

if (count == 3) {

--delta_[start];

++delta_[end];

return false;

}

if (kv.first > end) break;

}

return true;

}

private:

map<int, int> delta_;

};

Related Problems:

花花酱 LeetCode 729. My Calendar I

By zxi on November 19, 2017

Problem:

Implement a MyCalendar class to store your events. A new event can be added if adding the event will not cause a double booking.

Your class will have the 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 double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

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

Example 1:

MyCalendar();

MyCalendar.book(10, 20); // returns true

MyCalendar.book(15, 25); // returns false

MyCalendar.book(20, 30); // returns true

Explanation:

The first event can be booked. The second can't because time 15 is already booked by another event.

The third event can be booked, as the first event takes every time less than 20, but not including 20.

Note:

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

Idea:

Binary Search

Solution1:

Brute Force: O(n^2)

C++

// Author: Huahua

// Runtime: 99 ms

class MyCalendar {

public:

MyCalendar() {}

bool book(int start, int end) {

for (const auto& event : booked_) {

int s = event.first;

int e = event.second;

if (max(s, start) < min(e, end)) return false;

}

booked_.emplace_back(start, end);

return true;

}

private:

vector<pair<int, int>> booked_;

};

Solution 2:

Binary Search O(nlogn)

C++

// Author: Huahua

// Runtime: 82 ms

class MyCalendar {

public:

MyCalendar() {}

bool book(int start, int end) {

auto it = booked_.lower_bound(start);

if (it != booked_.cend() && it->first < end)

return false;

if (it != booked_.cbegin() && (--it)->second > start)

return false;

booked_[start] = end;

return true;

}

private:

map<int, int> booked_;

};

Java

// Author: Huahua

// Runtime: 170 ms

class MyCalendar {

TreeMap<Integer, Integer> booked_;

public MyCalendar() {

booked_ = new TreeMap<>();

}

public boolean book(int start, int end) {

Integer lb = booked_.floorKey(start);

if (lb != null && booked_.get(lb) > start) return false;

Integer ub = booked_.ceilingKey(start);

if (ub != null && ub < end) return false;

booked_.put(start, end);

return true;

}

Related Problems:

花花酱 LeetCode 728. Self Dividing Numbers

By zxi on November 19, 2017

Problem:

A self-dividing number is a number that is divisible by every digit it contains.

For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.

Also, a self-dividing number is not allowed to contain the digit zero.

Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.

Example 1:

Input:

left = 1, right = 22

Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

Note:

The boundaries of each input argument are 1 <= left <= right <= 10000.

Idea:

Brute Force

Time Complexity: O(n)

Space Complexity: O(1)

Solution:

C++

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

vector<int> selfDividingNumbers(int left, int right) {

vector<int> ans;

for (int n = left; n <= right; ++n) {

int t = n;

bool valid = true;

while (t && valid) {

const int r = t % 10;

if (r == 0 || n % r)

valid = false;

t /= 10;

}

if (valid) ans.push_back(n);

}

return ans;

}

};

String

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

vector<int> selfDividingNumbers(int left, int right) {

vector<int> ans;

for (int n = left; n <= right; ++n) {

const string t = std::to_string(n);

bool valid = true;

for (const char c : t) {

if (c == '0' || n % (c - '0')) {

valid = false;

break;

}

if (valid) ans.push_back(n);

}

return ans;

}

};

Related Problems:

[解题报告] LeetCode 611. Valid Triangle Number

花花酱 LeetCode 639. Decode Ways II

By zxi on November 18, 2017

Problem:

A message containing letters from A-Z is being encoded to numbers using the following mapping way:

'A' -> 1

'B' -> 2

...

'Z' -> 26

Beyond that, now the encoded string can also contain the character ‘*’, which can be treated as one of the numbers from 1 to 9.

Given the encoded message containing digits and the character ‘*’, return the total number of ways to decode it.

Also, since the answer may be very large, you should return the output mod 10⁹ + 7.

Example 1:

Input: "*"

Output: 9

Explanation: The encoded message can be decoded to the string:

"A", "B", "C", "D", "E", "F", "G", "H", "I".

Example 2:

1 2	Input: "1*" Output: 9 + 9 = 18

Note:

The length of the input string will fit in range [1, 10⁵].
The input string will only contain the character ‘*’ and digits ‘0’ – ‘9’.

Idea:

Time complexity: O(n)

Space complexity: O(1)

Solution:

C++

// Author: Huahua

// Runtime: 58 ms

class Solution {

public:

int numDecodings(string s) {

if (s.empty()) return 0;

// dp[-1] dp[0]

long dp[2] = {1, ways(s[0])};

for (int i = 1; i < s.length(); ++i) {

long dp_i = ways(s[i]) * dp[1] + ways(s[i - 1], s[i]) * dp[0];

dp_i %= kMod;

dp[0] = dp[1];

dp[1] = dp_i;

}

return dp[1];

}

private:

static constexpr int kMod = 1000000007;

int ways(char c) {

if (c == '0') return 0;

if (c == '*') return 9;

return 1;

}

int ways(char c1, char c2) {

if (c1 == '*' && c2 == '*')

return 15;

if (c1 == '*') {

return (c2 >= '0' && c2 <= '6') ? 2 : 1;

} else if (c2 == '*') {

switch (c1) {

case '1': return 9;

case '2': return 6;

default: return 0;

}

} else {

int prefix = (c1 - '0') * 10 + (c2 - '0');

return prefix >= 10 && prefix <= 26;

}

};

Related Problems:

[解题报告] LeetCode 91. Decode Ways

花花酱 LeetCode 720. Longest Word in Dictionary

By zxi on November 16, 2017

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.

Example 1:

Input:

words = ["w","wo","wor","worl", "world"]

Output: "world"

Explanation:

The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

Input:

words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]

Output: "apple"

Explanation:

Both "apply" and "apple" can be built from other words in the dictionary.

However, "apple" is lexicographically smaller than "apply".

Note:

All the strings in the input will only contain lowercase letters.
The length of words will be in the range [1, 1000].
The length of words[i] will be in the range [1, 30].

Idea:

Brute force

Trie

Solution:

C++

// Author: Huahua

// Runtime: 39 ms (better than 97.85%)

class Solution {

public:

string longestWord(vector<string>& words) {

string best;

unordered_set<string> dict(words.begin(), words.end());

for (const string& word : words) {

if (word.length() < best.length()

|| (word.length() == best.length() && word > best))

continue;

string prefix;

bool valid = true;

for (int i = 0; i < word.length() - 1 && valid; ++i) {

prefix += word[i];

if (!dict.count(prefix)) valid = false;

}

if (valid) best = word;

}

return best;

}

};

// Author: Huahua

// Runtime: 46 ms

class Solution {

public:

string longestWord(vector<string>& words) {

// Sort by length DESC, if there is a tie, sort by lexcial order.

std::sort(words.begin(), words.end(),

[](const string& w1, const string& w2){

if (w1.length() != w2.length())

return w1.length() > w2.length();

return w1 < w2;

});

unordered_set<string> dict(words.begin(), words.end());

for (const string& word : words) {

string prefix;

bool valid = true;

for (int i = 0; i < word.length() - 1 && valid; ++i) {

prefix += word[i];

if (!dict.count(prefix)) valid = false;

}

if (valid) return word;

}

return "";

}

};

Trie + Sorting

// Author: Huahua

// Runtime: 49 ms

class Trie {

public:

Trie(): root_(new TrieNode()) {}

void insert(const string& word) {

TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a'])

p->children[c - 'a'] = new TrieNode();

p = p->children[c - 'a'];

}

p->is_word = true;

}

bool hasAllPrefixes(const string& word) {

const TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a']) return false;

p = p->children[c - 'a'];

if (!p->is_word) return false;

}

return true;

}

private:

struct TrieNode {

TrieNode():is_word(false), children(26, nullptr){}

~TrieNode() {

for (auto node : children)

delete node;

}

bool is_word;

vector<TrieNode*> children;

};

std::unique_ptr<TrieNode> root_;

};

class Solution {

public:

string longestWord(vector<string>& words) {

std::sort(words.begin(), words.end(),

[](const string& w1, const string& w2){

if (w1.length() != w2.length())

return w1.length() > w2.length();

return w1 < w2;

});

Trie trie;

for (const string& word : words)

trie.insert(word);

for (const string& word : words)

if (trie.hasAllPrefixes(word)) return word;

return "";

}

};

Trie + No sorting

// Author: Huahua

// Runtime: 56 ms

class Trie {

public:

Trie(): root_(new TrieNode()) {}

void insert(const string& word) {

TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a'])

p->children[c - 'a'] = new TrieNode();

p = p->children[c - 'a'];

}

p->is_word = true;

}

bool hasAllPrefixes(const string& word) {

const TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a']) return false;

p = p->children[c - 'a'];

if (!p->is_word) return false;

}

return true;

}

private:

struct TrieNode {

TrieNode():is_word(false), children(26, nullptr){}

~TrieNode() {

for (auto node : children)

delete node;

}

bool is_word;

vector<TrieNode*> children;

};

std::unique_ptr<TrieNode> root_;

};

class Solution {

public:

string longestWord(vector<string>& words) {

Trie trie;

for (const string& word : words)

trie.insert(word);

string best;

for (const string& word : words) {

if (word.length() < best.length()

|| (word.length() == best.length() && word > best))

continue;

if (trie.hasAllPrefixes(word))

best = word;

}

return best;

}

};

Huahua's Tech Road

花花酱 LeetCode 731. My Calendar II – 花花酱

花花酱 LeetCode 729. My Calendar I

花花酱 LeetCode 728. Self Dividing Numbers

花花酱 LeetCode 639. Decode Ways II

花花酱 LeetCode 720. Longest Word in Dictionary