花花酱 LeetCode 432. All O`one Data Structure

By zxi on April 6, 2018

Problem

题目大意：设计一种数据结构，支持inc/dec/getmaxkey/getminkey操作，必须都在O(1)时间内完成。

https://leetcode.com/problems/all-oone-data-structure/description/

Implement a data structure supporting the following operations:

Inc(Key) – Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
Dec(Key) – If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
GetMaxKey() – Returns one of the keys with maximal value. If no element exists, return an empty string "".
GetMinKey() – Returns one of the keys with minimal value. If no element exists, return an empty string "".

Challenge: Perform all these in O(1) time complexity.

Solution

Time complexity: O(1)

Space complexity: O(n), n = # of unique keys

// Author: Huahua

// Running time: 32 ms

class AllOne {

public:

/** Initialize your data structure here. */

AllOne() {}

/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */

void inc(string key) {

auto it = m_.find(key);

if (it == m_.end()) {

if (l_.empty() || l_.front().value != 1)

l_.push_front({1, {key}});

else

l_.front().keys.insert(key);

m_[key] = l_.begin();

return;

}

auto lit = it->second;

auto nit = next(lit);

if (nit == l_.end() || nit->value != lit->value + 1)

nit = l_.insert(nit, {lit->value + 1, {}});

nit->keys.insert(key);

m_[key] = nit;

remove(lit, key);

}

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */

void dec(string key) {

auto it = m_.find(key);

if (it == m_.end()) return;

auto lit = it->second;

if (lit->value > 1) {

auto pit = prev(lit);

if (lit == l_.begin() || pit->value != lit->value - 1)

pit = l_.insert(lit, {lit->value - 1, {}});

pit->keys.insert(key);

m_[key] = pit;

} else {

// value == 1, remove from the data structure

m_.erase(key);

}

remove(lit, key);

}

/** Returns one of the keys with maximal value. */

string getMaxKey() {

return l_.empty() ? "" : *l_.back().keys.cbegin();

}

/** Returns one of the keys with Minimal value. */

string getMinKey() {

return l_.empty() ? "" : *l_.front().keys.cbegin();

}

private:

struct Node {

int value;

unordered_set<string> keys;

};

list<Node> l_;

unordered_map<string, list<Node>::iterator> m_;

// Remove from old node.

void remove(list<Node>::iterator it, const string& key) {

it->keys.erase(key);

if (it->keys.empty())

l_.erase(it);

}

};

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

Huahua's Tech Road

花花酱 LeetCode 432. All O`one Data Structure

Problem

Solution

Related Problems

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