Posts published in “Medium”

花花酱 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 725. Split Linked List in Parts

By zxi on November 13, 2017

Problem:

Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list “parts”.

The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null.

The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.

Return a List of ListNode’s representing the linked list parts that are formed.

Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]

Example 1:

Input:

root = [1, 2, 3], k = 5

Output: [[1],[2],[3],[],[]]

Explanation:

The input and each element of the output are ListNodes, not arrays.

For example, the input root has root.val = 1, root.next.val = 2, \root.next.next.val = 3, and root.next.next.next = null.

The first element output[0] has output[0].val = 1, output[0].next = null.

The last element output[4] is null, but it's string representation as a ListNode is [].

Example 2:

Input:

root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3

Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]

Explanation:

The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

Note:

The length of root will be in the range [0, 1000].
Each value of a node in the input will be an integer in the range [0, 999].
k will be an integer in the range [1, 50].

Idea:

List + Simulation

Solution:

C++

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

vector<ListNode*> splitListToParts(ListNode* root, int k) {

int len = 0;

for (ListNode* head = root; head; head = head->next) ++len;

vector<ListNode*> ans(k, nullptr);

int l = len / k;

int r = len % k;

ListNode* head = root;

ListNode* prev = nullptr;

for (int i = 0; i < k; ++i, --r) {

ans[i] = head;

for (int j = 0; j < l + (r > 0); ++j) {

prev = head;

head = head->next;

}

if (prev) prev->next = nullptr;

}

return ans;

}

};

Java

// Author: Huahua

// Runtime: 4 ms

class Solution {

public ListNode[] splitListToParts(ListNode root, int k) {

ListNode[] ans = new ListNode[k];

int len = 0;

for (ListNode head = root; head != null; head = head.next) ++len;

int l = len / k;

int r = len % k;

ListNode prev = null;

ListNode head = root;

for (int i = 0; i < k; ++i, --r) {

ans[i] = head;

int part_len = l + ((r > 0) ? 1 : 0);

for (int j = 0; j < part_len; ++j) {

prev = head;

head = head.next;

}

if (prev != null) prev.next = null;

}

return ans;

}

Python

"""

Author: Huahua

Runtime: 79 ms

"""

class Solution:

def splitListToParts(self, root, k):

total_len = 0

head = root

while head:

total_len += 1

head = head.next

ans = [None for _ in range(k)]

l, r = total_len // k, total_len % k

prev, head = None, root

for i in range(k):

ans[i] = head

for j in range(l + (1 if r > 0 else 0)):

prev, head = head, head.next

if prev: prev.next = None

r -= 1

return ans

花花酱 LeetCode 98. Validate Binary Search Tree

By zxi on November 11, 2017

Problem:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Example 1:

/ \

1 3

Binary tree [2,1,3], return true.

Example 2:

/ \

2 3

Binary tree [1,2,3], return false.

Solution 1

Traverse the tree and limit the range of each subtree and check whether root’s value is in the range.

Time complexity: O(n)

Space complexity: O(n)

Note: in order to cover the range of -2^31 ~ 2^31-1, we need to use long or nullable integer.

C++/long

class Solution {

public:

bool isValidBST(TreeNode* root) {

return isValidBST(root, LLONG_MIN, LLONG_MAX);

}

private:

bool isValidBST(TreeNode* root, long min_val, long max_val) {

if (!root) return true;

if (root->val <= min_val || root->val >= max_val)

return false;

return isValidBST(root->left, min_val, root->val)

&& isValidBST(root->right, root->val, max_val);

}

};

C++/nullable

class Solution {

public:

bool isValidBST(TreeNode* root) {

return isValidBST(root, nullptr, nullptr);

}

private:

bool isValidBST(TreeNode* root, int* min_val, int* max_val) {

if (!root) return true;

if ((min_val && root->val <= *min_val)

||(max_val && root->val >= *max_val))

return false;

return isValidBST(root->left, min_val, &root->val)

&& isValidBST(root->right, &root->val, max_val);

}

};

Java/nullable

// Author: Huahua

// Running time: 1 ms

class Solution {

public boolean isValidBST(TreeNode root) {

return isValidBST(root, null, null);

}

private boolean isValidBST(TreeNode root, Integer min, Integer max) {

if (root == null) return true;

if ((min != null && root.val <= min)

||(max != null && root.val >= max))

return false;

return isValidBST(root.left, min, root.val)

&& isValidBST(root.right, root.val, max);

}

Solution 2

Do an in-order traversal, the numbers should be sorted, thus we only need to compare with the previous number.

Time complexity: O(n)

Space complexity: O(n)

C++

class Solution {

public:

bool isValidBST(TreeNode* root) {

prev_ = nullptr;

return inOrder(root);

}

private:

TreeNode* prev_;

bool inOrder(TreeNode* root) {

if (!root) return true;

if (!inOrder(root->left)) return false;

if (prev_ && root->val <= prev_->val) return false;

prev_ = root;

return inOrder(root->right);

}

};

Java

// Author: Huahua

// Running time: 1 ms

class Solution {

private TreeNode prev;

public boolean isValidBST(TreeNode root) {

prev = null;

return inOrder(root);

}

private boolean inOrder(TreeNode root) {

if (root == null) return true;

if (!inOrder(root.left)) return false;

if (prev != null && root.val <= prev.val) return false;

prev = root;

return inOrder(root.right);

}

Related Problem

花花酱 LeetCode 530. Minimum Absolute Difference in BST

花花酱 LeetCode 91. Decode Ways

By zxi on November 9, 2017

题目大意：

给你一个加密的数字字符串，问你一共有多少种不同的解密方式。

Problem:

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

‘A’ -> 1

‘B’ -> 2

…

‘Z’ -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Idea:

Dynamic Programming

Solution:

C++

Time complexity: O(n^2)

Space complexity: O(n^2)

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int numDecodings(string s) {

if(s.length() == 0) return 0;

m_ways[""] = 1;

return ways(s);

}

private:

int ways(const string& s) {

if (m_ways.count(s)) return m_ways[s];

if (s[0] == '0') return 0;

if (s.length() == 1) return 1;

int w = ways(s.substr(1));

const int prefix = stoi(s.substr(0, 2));

if (prefix <= 26)

w += ways(s.substr(2));

m_ways[s] = w;

return w;

}

unordered_map<string, int> m_ways;

};

C++

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

int numDecodings(string s) {

if(s.length() == 0) return 0;

return ways(s, 0, s.length() - 1);

}

private:

int ways(const string& s, int l, int r) {

if (m_ways.count(l)) return m_ways[l];

if (s[l] == '0') return 0;

if (l >= r) return 1; // Single digit or empty.

int w = ways(s, l + 1, r);

const int prefix = (s[l] - '0') * 10 + (s[l + 1] - '0');

if (prefix <= 26)

w += ways(s, l + 2, r);

m_ways[l] = w;

return w;

}

// Use l as key.

unordered_map<int, int> m_ways;

};

C++

Time complexity: O(n)

Space complexity: O(1)

class Solution {

public:

int numDecodings(string s) {

if (s.empty() || s[0] == '0') return 0;

if (s.length() == 1) return 1;

const int n = s.length();

int w1 = 1;

int w2 = 1;

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

int w = 0;

if (!isValid(s[i]) && !isValid(s[i - 1], s[i])) return 0;

if (isValid(s[i])) w = w1;

if (isValid(s[i - 1], s[i])) w += w2;

w2 = w1;

w1 = w;

}

return w1;

}

private:

bool isValid(const char c) { return c != '0'; }

bool isValid(const char c1, const char c2) {

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

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

}

};

Related Problems:

[解题报告] LeetCode 639. Decode Ways II – 花花酱

花花酱 LeetCode 216. Combination Sum III

By zxi on November 3, 2017

题目大意：输出所有用k个数的和为n的组合。可以使用的元素是1到9。

Problem:

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

1	[[1,2,6], [1,3,5], [2,3,4]]

Idea:

DFS + backtracking

bit

Solution:

C++

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

vector<vector<int>> combinationSum3(int k, int n) {

vector<vector<int>> ans;

vector<int> cur;

dfs(k, n, 1, cur, ans);

return ans;

}

private:

// Use k numbers (>= s) to sum up to n

void dfs(int k, int n, int s,

vector<int>& cur, vector<vector<int>>& ans) {

if (k == 0) {

if (n == 0) ans.push_back(cur);

return;

}

for (int i = s; i <= 9; ++i) {

if (i > n) return;

cur.push_back(i);

dfs(k - 1, n - i, i + 1, cur, ans);

cur.pop_back();

}

};

C++ / binary

class Solution {

public:

vector<vector<int>> combinationSum3(int k, int n) {

vector<vector<int>> ans;

// 2^9, generate all combinations of [1 .. 9]

for (int i = 0; i < (1 << 9); ++i) {

vector<int> cur;

int sum = 0;

// Use j if (j - 1)-th bit is 1

for (int j = 1; j <= 9; ++j)

if (i & (1 << (j - 1))) {

sum += j;

cur.push_back(j);

}

if (sum == n && cur.size() == k)

ans.push_back(cur);

}

return ans;

}

};

Python

class Solution:

def combinationSum3(self, k, n):

def dfs(k, n, s, cur, ans):

if k == 0 and n == 0:

ans.append(list(cur))

for i in range(s, min(n + 1, 10)):

dfs(k - 1, n - i, i + 1, cur + [i], ans)

ans = []

dfs(k, n, 1, [], ans)

return ans

Related problems: