花花酱 LeetCode 599. Minimum Index Sum of Two Lists

By zxi on April 2, 2018

Problem

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

Example 1:

Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".

Example 2:

Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
Output: ["Shogun"]
Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).

Note:

The length of both lists will be in the range of [1, 1000].
The length of strings in both lists will be in the range of [1, 30].
The index is starting from 0 to the list length minus 1.
No duplicates in both lists.

Solution

Time complexity: O(n+m)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 103 ms

class Solution {

public:

vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {

unordered_map<string, int> indices;

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

indices[list1[i]] = i;

vector<string> ans;

int best_index = INT_MAX;

string best;

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

if (!indices.count(list2[i])) continue;

int index = indices[list2[i]] + i;

if (index < best_index) ans.clear();

if (index <= best_index) {

best_index = index;

ans.push_back(list2[i]);

}

return ans;

}

};

花花酱 LeetCode 596. Classes More Than 5 Students

By zxi on April 2, 2018

Problem

There is a table courses with columns: student and class

Please list out all classes which have more than or equal to 5 students.

For example, the table:

+---------+------------+
| student | class      |
+---------+------------+
| A       | Math       |
| B       | English    |
| C       | Math       |
| D       | Biology    |
| E       | Math       |
| F       | Computer   |
| G       | Math       |
| H       | Math       |
| I       | Math       |
+---------+------------+

Should output:

+---------+
| class   |
+---------+
| Math    |
+---------+

Note:
The students should not be counted duplicate in each course.

Solution

SQL

# Author: Huahua

# Running time: 1756 ms

select class from courses group by class having count(distinct student) >= 5

花花酱 LeetCode 811. Subdomain Visit Count

By zxi on April 1, 2018

Problem

A website domain like “discuss.leetcode.com” consists of various subdomains. At the top level, we have “com”, at the next level, we have “leetcode.com”, and at the lowest level, “discuss.leetcode.com”. When we visit a domain like “discuss.leetcode.com”, we will also visit the parent domains “leetcode.com” and “com” implicitly.

Now, call a “count-paired domain” to be a count (representing the number of visits this domain received), followed by a space, followed by the address. An example of a count-paired domain might be “9001 discuss.leetcode.com”.

We are given a list cpdomains of count-paired domains. We would like a list of count-paired domains, (in the same format as the input, and in any order), that explicitly counts the number of visits to each subdomain.

Example 1:
Input: 
["9001 discuss.leetcode.com"]
Output: 
["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]
Explanation: 
We only have one website domain: "discuss.leetcode.com". As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

Example 2:
Input: 
["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
Output: 
["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
Explanation: 
We will visit "google.mail.com" 900 times, "yahoo.com" 50 times, "intel.mail.com" once and "wiki.org" 5 times. For the subdomains, we will visit "mail.com" 900 + 1 = 901 times, "com" 900 + 50 + 1 = 951 times, and "org" 5 times.

Notes:

The length of cpdomains will not exceed 100.
The length of each domain name will not exceed 100.
Each address will have either 1 or 2 “.” characters.
The input count in any count-paired domain will not exceed 10000.

Solution: HashTable

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

vector<string> subdomainVisits(vector<string>& cpdomains) {

unordered_map<string, int> counts;

for (const string& cpdomain : cpdomains) {

size_t index = cpdomain.find(' ');

int count = std::stoi(cpdomain.substr(0, index));

string domain = cpdomain.substr(index + 1);

while (true) {

counts[domain] += count;

size_t i = domain.find('.');

if (i == string::npos) break;

domain = domain.substr(i + 1);

}

vector<string> ans;

for (const auto& kv : counts)

ans.push_back(std::to_string(kv.second) + " " + kv.first);

return ans;

}

};

花花酱 LeetCode 593. Valid Square

By zxi on March 30, 2018

Problem

题目大意：给你四个点判断能否构成正方形。

https://leetcode.com/problems/valid-square/description/

Given the coordinates of four points in 2D space, return whether the four points could construct a square.

The coordinate (x,y) of a point is represented by an integer array with two integers.

Example:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: True

Note:

All the input integers are in the range [-10000, 10000].
A valid square has four equal sides with positive length and four equal angles (90-degree angles).
Input points have no order.

Solution

Time complexity: O(1)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {

set<int> s{distSqr(p1, p2), distSqr(p1, p3), distSqr(p1, p4), distSqr(p2, p3), distSqr(p2, p4), distSqr(p3, p4)};

return !s.count(0) && s.size() == 2;

}

private:

static inline int distSqr(const vector<int>& p1, const vector<int>& p2) {

return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);

}

};

花花酱 LeetCode 192. Word Frequency

By zxi on March 28, 2018

Write a bash script to calculate the frequency of each word in a text file words.txt.

For simplicity sake, you may assume:

words.txt contains only lowercase characters and space ' ' characters.
Each word must consist of lowercase characters only.
Words are separated by one or more whitespace characters.

For example, assume that words.txt has the following content:

the day is sunny the the
the sunny is is

Your script should output the following, sorted by descending frequency:

the 4
is 3
sunny 2
day 1

Note:
Don’t worry about handling ties, it is guaranteed that each word’s frequency count is unique.

Solution

bash

# Author: Huahua

# Running time: 8 ms (beats 99.80%)

cat words.txt | tr -s " " "\n" | sort | uniq -c | sort -r | awk '{print $2, $1}'

Huahua's Tech Road

花花酱 LeetCode 599. Minimum Index Sum of Two Lists

Problem

Solution

花花酱 LeetCode 596. Classes More Than 5 Students

Problem

Solution

花花酱 LeetCode 811. Subdomain Visit Count

Problem

Solution: HashTable

花花酱 LeetCode 593. Valid Square

Problem

Solution

花花酱 LeetCode 192. Word Frequency

Solution

bash