Posts published in “Easy”

花花酱 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 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 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 169. Majority Element

By zxi on November 4, 2017

题目大意：给你一个数组，其中一个数出现超过n/2次，问你出现次数最多的那个数是什么？

Problem:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Ideas:

Solution 1:

Hash table O(n) / O(n)

// Author: Huahua

// Runtime : 23 ms

class Solution {

public:

int majorityElement(vector<int>& nums) {

unordered_map<int, int> count;

const int n = nums.size();

for (const int num : nums)

if (++count[num] > n / 2) return num;

return -1;

}

};

Solution 2:

BST O(nlogk) / O(n)

// Author: Huahua

// Runtime : 19 ms

class Solution {

public:

int majorityElement(vector<int>& nums) {

map<int, int> count;

const int n = nums.size();

for (const int num : nums)

if (++count[num] > n / 2) return num;

return -1;

}

};

Solution 3:

Randomization O(n) / O(1)

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

int majorityElement(vector<int>& nums) {

srand(time(nullptr));

const int n = nums.size();

while (true) {

const int index = rand() % n;

const int majority = nums[index];

int count = 0;

for (const int num : nums)

if (num == majority && ++count > n/2) return num;

}

return -1;

}

};

Solution 4:

Bit voting O(n) / O(1)

class Solution {

public:

int majorityElement(vector<int>& nums) {

const int n = nums.size();

int majority = 0;

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

int mask = 1 << i;

int count = 0;

for (const int num : nums)

if ((num & mask) && (++count > n /2)) {

majority |= mask;

break;

}

return majority;

}

};

Solution 5:

Moore Voting O(n) / O(1)

class Solution {

public:

int majorityElement(vector<int>& nums) {

int majority = nums.front();

int count = 0;

for (const int num : nums) {

if (num == majority) ++count;

else if (--count == 0) {

count = 1;

majority = num;

}

return majority;

}

};

Solution 6:

Full sorting O(nlogn) / O(1)

class Solution {

public:

int majorityElement(vector<int>& nums) {

std::sort(nums.begin(), nums.end());

return nums[nums.size()/2];

}

};

Solution 7:

Partial sorting O(n) / O(1)

class Solution {

public:

int majorityElement(vector<int>& nums) {

nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());

return nums[nums.size() / 2];

}

};

Solution 8:

Divide and conquer O(nlogn) / O(logn)

class Solution {

public:

int majorityElement(vector<int>& nums) {

return majorityElement(nums, 0, nums.size() - 1);

}

private:

int majorityElement(const vector<int>& nums, int l, int r) {

if (l == r) return nums[l];

const int m = l + (r - l) / 2;

const int ml = majorityElement(nums, l, m);

const int mr = majorityElement(nums, m + 1, r);

if (ml == mr) return ml;

return count(nums.begin() + l, nums.begin() + r + 1, ml) >

count(nums.begin() + l, nums.begin() + r + 1, mr)

? ml : mr;

}

};

Divide and conquer O(nlogn) / O(logn)

class Solution {

public:

int majorityElement(vector<int>& nums) {

return majorityElement(nums, 0, nums.size() - 1).first;

}

private:

pair<int, int> majorityElement(const vector<int>& nums, int l, int r) {

if (l == r) return {nums[l], 1};

int mid = l + (r - l) / 2;

auto ml = majorityElement(nums, l, mid);

auto mr = majorityElement(nums, mid + 1, r);

if (ml.first == mr.first) return { ml.first, ml.second + mr.second };

if (ml.second > mr.second)

return { ml.first, ml.second + count(nums.begin() + mid + 1, nums.begin() + r + 1, ml.first) };

else

return { mr.first, mr.second + count(nums.begin() + l, nums.begin() + mid + 1, mr.first) };

}

};