花花酱 LeetCode 726. Number of Atoms

By zxi on November 15, 2017

Problem:

Given a chemical formula (given as a string), return the count of each atom.

An atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.

1 or more digits representing the count of that element may follow if the count is greater than 1. If the count is 1, no digits will follow. For example, H2O and H2O2 are possible, but H1O2 is impossible.

Two formulas concatenated together produce another formula. For example, H2O2He3Mg4 is also a formula.

A formula placed in parentheses, and a count (optionally added) is also a formula. For example, (H2O2) and (H2O2)3 are formulas.

Given a formula, output the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.

Example 1:

Input:

formula = "H2O"

Output: "H2O"

Explanation:

The count of elements are {'H': 2, 'O': 1}.

Example 2:

Input:

formula = "Mg(OH)2"

Output: "H2MgO2"

Explanation:

The count of elements are {'H': 2, 'Mg': 1, 'O': 2}.

Example 3:

Input:

formula = "K4(ON(SO3)2)2"

Output: "K4N2O14S4"

Explanation:

The count of elements are {'K': 4, 'N': 2, 'O': 14, 'S': 4}.

Note:

All atom names consist of lowercase letters, except for the first character which is uppercase.
The length of formula will be in the range [1, 1000].
formula will only consist of letters, digits, and round parentheses, and is a valid formula as defined in the problem.

Idea:

Recursion

Time complexity: O(n)

Space complexity: O(n)

Solution:

C++

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

string countOfAtoms(const string& formula) {

int i = 0;

string ans;

for (const auto& kv : countOfAtoms(formula, i)) {

ans += kv.first;

if (kv.second > 1) ans += std::to_string(kv.second);

}

return ans;

}

private:

map<string, int> countOfAtoms(const string& formula, int& i) {

map<string, int> counts;

while (i != formula.length()) {

if (formula[i] == '(') {

const auto& tmp_counts = countOfAtoms(formula, ++i);

const int count = getCount(formula, i);

for (const auto& kv : tmp_counts)

counts[kv.first] += kv.second * count;

} else if (formula[i] == ')') {

++i;

return counts;

} else {

const string& name = getName(formula, i);

counts[name] += getCount(formula, i);

}

return counts;

}

string getName(const string& formula, int& i) {

string name;

while (isalpha(formula[i])

&& (name.empty() || islower(formula[i]))) name += formula[i++];

return name;

}

int getCount(const string& formula, int& i) {

string count_str;

while (isdigit(formula[i])) count_str += formula[i++];

return count_str.empty() ? 1 : std::stoi(count_str);

}

};

Java

// Author: Huahua

// Runtime: 13 ms

class Solution {

private int i;

public String countOfAtoms(String formula) {

StringBuilder ans = new StringBuilder();

i = 0;

Map<String, Integer> counts = countOfAtoms(formula.toCharArray());

for (String name: counts.keySet()) {

ans.append(name);

int count = counts.get(name);

if (count > 1) ans.append("" + count);

}

return ans.toString();

}

private Map<String, Integer> countOfAtoms(char[] f) {

Map<String, Integer> ans = new TreeMap<String, Integer>();

while (i != f.length) {

if (f[i] == '(') {

++i;

Map<String, Integer> tmp = countOfAtoms(f);

int count = getCount(f);

for (Map.Entry<String, Integer> entry : tmp.entrySet())

ans.put(entry.getKey(),

ans.getOrDefault(entry.getKey(), 0)

+ entry.getValue() * count);

} else if (f[i] == ')') {

++i;

return ans;

} else {

String name = getName(f);

ans.put(name, ans.getOrDefault(name, 0) + getCount(f));

}

return ans;

}

private String getName(char[] f) {

String name = "" + f[i++];

while (i < f.length && 'a' <= f[i] && f[i] <= 'z') name += f[i++];

return name;

}

private int getCount(char[] f) {

int count = 0;

while (i < f.length && '0' <= f[i] && f[i] <= '9') {

count = count * 10 + (f[i] - '0');

++i;

}

return count == 0 ? 1 : count;

}

花花酱 LeetCode 321. Create Maximum Number

By zxi on November 14, 2017

Problem:

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]

题目大意：给你两个数字数组和k，返回从两个数组中选取k个数字能够组成的最大值。

Idea: Greedy + DP

Solution:

Time complexity: O(k * (n1+n2)^2)

Space complexity: O(n1+n2)

C++

// Author: Huahua

// Runtime: 26 ms

class Solution {

public:

vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {

vector<int> ans;

const int n1 = nums1.size();

const int n2 = nums2.size();

for (int i = max(0, k - n2); i <= min(k, n1); ++i)

ans = max(ans, maxNumber(maxNumber(nums1, i),

maxNumber(nums2, k - i)));

return ans;

}

private:

vector<int> maxNumber(const vector<int>& nums, int k) {

vector<int> ans(k);

int j = 0;

for (int i = 0; i < nums.size(); ++i) {

while (j > 0 && nums[i] > ans[j - 1]

&& nums.size() - i > k - j) --j;

if (j < k) ans[j++] = nums[i];

}

return ans;

}

vector<int> maxNumber(const vector<int>& nums1, const vector<int>& nums2) {

vector<int> ans(nums1.size() + nums2.size());

auto s1 = nums1.cbegin();

auto e1 = nums1.cend();

auto s2 = nums2.cbegin();

auto e2 = nums2.cend();

int index = 0;

while (s1 != e1 || s2 != e2)

ans[index++] =

lexicographical_compare(s1, e1, s2, e2) ? *s2++ : *s1++;

return ans;

}

};

Java

// Author: Huahua

// Runtime: 18 ms

class Solution {

public int[] maxNumber(int[] nums1, int[] nums2, int k) {

int[] best = new int[0];

for (int i = Math.max(0, k - nums2.length);

i <= Math.min(k, nums1.length); ++i)

best = max(best, 0,

maxNumber(maxNumber(nums1, i),

maxNumber(nums2, k - i)), 0);

return best;

}

private int[] maxNumber(int[] nums, int k) {

int[] ans = new int[k];

int j = 0;

for (int i = 0; i < nums.length; ++i) {

while (j > 0 && nums[i] > ans[j - 1]

&& nums.length - i > k - j) --j;

if (j < k)

ans[j++] = nums[i];

}

return ans;

}

private int[] maxNumber(int[] nums1, int[] nums2) {

int[] ans = new int[nums1.length + nums2.length];

int s1 = 0;

int s2 = 0;

int index = 0;

while (s1 != nums1.length || s2 != nums2.length)

ans[index++] = max(nums1, s1, nums2, s2) == nums1 ?

nums1[s1++] : nums2[s2++];

return ans;

}

private int[] max(int[] nums1, int s1, int[] nums2, int s2) {

for (int i = s1; i < nums1.length; ++i) {

int j = s2 + i - s1;

if (j >= nums2.length) return nums1;

if (nums1[i] < nums2[j]) return nums2;

if (nums1[i] > nums2[j]) return nums1;

}

return nums2;

}

花花酱 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 724. Find Pivot Index

By zxi on November 13, 2017

Problem:

Given an array of integers nums, write a method that returns the “pivot” index of this array.

We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.

If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example 1:

Input:

nums = [1, 7, 3, 6, 5, 6]

Output: 3

Explanation:

The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.

Also, 3 is the first index where this occurs.

Example 2:

Input:

nums = [1, 2, 3]

Output: -1

Explanation:

There is no index that satisfies the conditions in the problem statement.

Note:

The length of nums will be in the range [0, 10000].
Each element nums[i] will be an integer in the range [-1000, 1000].

Idea:

Solution:

C++

// Author: Huahua

// Runtime: 43 ms

class Solution {

public:

int pivotIndex(vector<int>& nums) {

const int sum = accumulate(nums.begin(), nums.end(), 0);

int l = 0;

int r = sum;

for (int i = 0; i < nums.size(); ++i) {

r -= nums[i];

if (l == r) return i;

l += nums[i];

}

return -1;

}

};

Java

// Author: Huahua

// Runtime: 133 ms

class Solution {

public int pivotIndex(int[] nums) {

int sum = IntStream.of(nums).sum();

int l = 0;

int r = sum;

for (int i = 0; i < nums.length; ++i) {

r -= nums[i];

if (l == r) return i;

l += nums[i];

}

return -1;

}

Python

"""

Author: Huahua

Runtime: 112 ms

"""

class Solution:

def pivotIndex(self, nums):

l, r = 0, sum(nums)

for i in range(len(nums)):

r -= nums[i]

if l == r: return i

l += nums[i]

return -1

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

}

Huahua's Tech Road

花花酱 LeetCode 726. Number of Atoms

花花酱 LeetCode 321. Create Maximum Number

Idea: Greedy + DP

Solution:

C++

Java

花花酱 LeetCode 725. Split Linked List in Parts

花花酱 LeetCode 724. Find Pivot Index

花花酱 LeetCode 98. Validate Binary Search Tree

Solution 1

C++/long

C++/nullable

Java/nullable

Solution 2

C++

Java

Related Problem