花花酱 LeetCode 453. Minimum Moves to Equal Array Elements

By zxi on April 5, 2018

Problem

题目大意：给你一个数组，每次可以把其中n-1个数加1，问最少需要多少次操作可以使得数组中的元素都相等。

https://leetcode.com/problems/minimum-moves-to-equal-array-elements/description/

Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n – 1 elements by 1.

Example:

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

Idea

Assuming the sum of array is S, the minimum element of the array is min and minimum number of moves is m.

Each move will increase the sum of array by n – 1. Finally, every element becomes x. So we have:

S + (n – 1) * m = x * n
min + m = x

We got: m = S – n * min

Solution: Math

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 51 ms

class Solution {

public:

int minMoves(const vector<int>& a) {

return accumulate(a.begin(), a.end(), 0L) - a.size() * *min_element(a.begin(), a.end());

}

};

Python

"""

Author: Huahua

Running time: 104 ms

"""

class Solution:

def minMoves(self, nums):

return sum(nums) - len(nums) * min(nums)

花花酱 LeetCode 627. Swap Salary

By zxi on April 3, 2018

Problem

https://leetcode.com/problems/swap-salary/description/

Given a table salary, such as the one below, that has m=male and f=female values. Swap all f and m values (i.e., change all f values to m and vice versa) with a single update query and no intermediate temp table.For example:

| id | name | sex | salary |
|----|------|-----|--------|
| 1  | A    | m   | 2500   |
| 2  | B    | f   | 1500   |
| 3  | C    | m   | 5500   |
| 4  | D    | f   | 500    |

After running your query, the above salary table should have the following rows:

| id | name | sex | salary |
|----|------|-----|--------|
| 1  | A    | f   | 2500   |
| 2  | B    | m   | 1500   |
| 3  | C    | f   | 5500   |
| 4  | D    | m   | 500    |

Solution: XOR

# Author: Huahua

# Running time: 309 ms

update salary set sex = char(ascii('f') ^ ascii('m') ^ ascii(sex))

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

}

};

Posts published in April 2018

花花酱 LeetCode 453. Minimum Moves to Equal Array Elements

Problem

Idea

Solution: Math

花花酱 LeetCode 627. Swap Salary

Problem

Solution: XOR

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