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

}

};

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

}

Huahua's Tech Road

花花酱 LeetCode 728. Self Dividing Numbers

花花酱 LeetCode 639. Decode Ways II

花花酱 LeetCode 720. Longest Word in Dictionary

花花酱 LeetCode 726. Number of Atoms

花花酱 LeetCode 321. Create Maximum Number

Idea: Greedy + DP

Solution:

C++

Java