Posts published in “Hashtable”

花花酱 LeetCode 1400. Construct K Palindrome Strings

By zxi on April 4, 2020

Given a string s and an integer k. You should construct k non-empty palindrome strings using all the characters in s.

Return True if you can use all the characters in s to construct k palindrome strings or False otherwise.

Example 1:

Input: s = "annabelle", k = 2
Output: true
Explanation: You can construct two palindromes using all characters in s.
Some possible constructions "anna" + "elble", "anbna" + "elle", "anellena" + "b"

Example 2:

Input: s = "leetcode", k = 3
Output: false
Explanation: It is impossible to construct 3 palindromes using all the characters of s.

Example 3:

Input: s = "true", k = 4
Output: true
Explanation: The only possible solution is to put each character in a separate string.

Example 4:

Input: s = "yzyzyzyzyzyzyzy", k = 2
Output: true
Explanation: Simply you can put all z's in one string and all y's in the other string. Both strings will be palindrome.

Example 5:

Input: s = "cr", k = 7
Output: false
Explanation: We don't have enough characters in s to construct 7 palindromes.

Constraints:

1 <= s.length <= 10^5
All characters in s are lower-case English letters.
1 <= k <= 10^5

Solution: HashTable

Compute the frequency of each characters.

Count the # of characters with odd frequency |odd|, each palindrome can consume at most one char with odd frequency. thus k must >= |odd|.
ans = k <= len(s) and k >= odd

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool canConstruct(string s, int k) {

if (k > s.length()) return false;

vector<int> f(26);

for (char c : s) f[c - 'a'] ^= 1;

int odd = accumulate(begin(f), end(f), 0);

return k >= odd;

}

};

花花酱 LeetCode 1399. Count Largest Group

By zxi on April 4, 2020

Given an integer n. Each number from 1 to n is grouped according to the sum of its digits.

Return how many groups have the largest size.

Example 1:

Input: n = 13
Output: 4
Explanation: There are 9 groups in total, they are grouped according sum of its digits of numbers from 1 to 13:
[1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9]. There are 4 groups with largest size.

Example 2:

Input: n = 2
Output: 2
Explanation: There are 2 groups [1], [2] of size 1.

Example 3:

Input: n = 15
Output: 6

Example 4:

Input: n = 24
Output: 5

Constraints:

1 <= n <= 10^4

Solution: HashTable

Time complexity: O(nlogn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

int countLargestGroup(int n) {

vector<int> c(37); // max sum is 9+9+9+9 = 36

for (int i = 1; i <= n; ++i) {

int x = i;

int sum = 0;

while (x) {

sum += x % 10;

x /= 10;

}

++c[sum];

}

return count(begin(c), end(c), *max_element(begin(c), end(c)));

}

};

花花酱 LeetCode 1394. Find Lucky Integer in an Array

By zxi on March 28, 2020

Given an array of integers arr, a lucky integer is an integer which has a frequency in the array equal to its value.

Return a lucky integer in the array. If there are multiple lucky integers return the largest of them. If there is no lucky integer return -1.

Example 1:

Input: arr = [2,2,3,4]
Output: 2
Explanation: The only lucky number in the array is 2 because frequency[2] == 2.

Example 2:

Input: arr = [1,2,2,3,3,3]
Output: 3
Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.

Example 3:

Input: arr = [2,2,2,3,3]
Output: -1
Explanation: There are no lucky numbers in the array.

Example 4:

Input: arr = [5]
Output: -1

Example 5:

Input: arr = [7,7,7,7,7,7,7]
Output: 7

Constraints:

1 <= arr.length <= 500
1 <= arr[i] <= 500

Solution: Hashtable

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int findLucky(vector<int>& arr) {

unordered_map<int, int> freq;

for (int x : arr) ++freq[x];

int ans = -1;

for (const auto& [key, count] : freq)

if (key == count) ans = max(ans, key);

return ans;

}

};

花花酱 LeetCode 1396. Design Underground System

By zxi on March 28, 2020

Implement the class UndergroundSystem that supports three methods:

1. checkIn(int id, string stationName, int t)

A customer with id card equal to id, gets in the station stationName at time t.
A customer can only be checked into one place at a time.

2. checkOut(int id, string stationName, int t)

A customer with id card equal to id, gets out from the station stationName at time t.

3. getAverageTime(string startStation, string endStation)

Returns the average time to travel between the startStation and the endStation.
The average time is computed from all the previous traveling from startStation to endStation that happened directly.
Call to getAverageTime is always valid.

You can assume all calls to checkIn and checkOut methods are consistent. That is, if a customer gets in at time t₁ at some station, then it gets out at time t₂ with t₂ > t₁. All events happen in chronological order.

Example 1:

Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

Output
[null,null,null,null,null,null,null,14.0,11.0,null,11.0,null,12.0]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);
undergroundSystem.checkOut(27, "Waterloo", 20);
undergroundSystem.checkOut(32, "Cambridge", 22);
undergroundSystem.getAverageTime("Paradise", "Cambridge");       // return 14.0. There was only one travel from "Paradise" (at time 8) to "Cambridge" (at time 22)
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0. There were two travels from "Leyton" to "Waterloo", a customer with id=45 from time=3 to time=15 and a customer with id=27 from time=10 to time=20. So the average time is ( (15-3) + (20-10) ) / 2 = 11.0
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0
undergroundSystem.checkOut(10, "Waterloo", 38);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 12.0

Constraints:

There will be at most 20000 operations.
1 <= id, t <= 10^6
All strings consist of uppercase, lowercase English letters and digits.
1 <= stationName.length <= 10
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: Hashtable

For each user, store the checkin station and time.
For each trip (startStation + “_” + endStation), store the total time and counts.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class UndergroundSystem {

public:

UndergroundSystem() {}

void checkIn(int id, string stationName, int t) {

m_[id] = {stationName, t};

}

void checkOut(int id, string stationName, int t) {

const auto& [s0, t0] = m_[id];

string key = s0 + "_" + stationName;

times_[key].first += (t - t0);

++times_[key].second;

}

double getAverageTime(string startStation, string endStation) {

const auto& [sum, count] = times_[startStation + "_" + endStation];

return static_cast<double>(sum) / count;

}

private:

unordered_map<int, pair<string, int>> m_; // id -> {station, t}

unordered_map<string, pair<int, int>> times_; // trip -> {sum, count}

};

花花酱 LeetCode 1386. Cinema Seat Allocation

By zxi on March 22, 2020

A cinema has n rows of seats, numbered from 1 to n and there are ten seats in each row, labelled from 1 to 10 as shown in the figure above.

Given the array reservedSeats containing the numbers of seats already reserved, for example, reservedSeats[i]=[3,8] means the seat located in row 3 and labelled with 8 is already reserved.

Return the maximum number of four-person families you can allocate on the cinema seats. A four-person family occupies fours seats in one row, that are next to each other. Seats across an aisle (such as [3,3] and [3,4]) are not considered to be next to each other, however, It is permissible for the four-person family to be separated by an aisle, but in that case, exactly two people have to sit on each side of the aisle.

Example 1:

Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
Output: 4
Explanation: The figure above shows the optimal allocation for four families, where seats mark with blue are already reserved and contiguous seats mark with orange are for one family.

Example 2:

Input: n = 2, reservedSeats = [[2,1],[1,8],[2,6]]
Output: 2

Example 3:

Input: n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
Output: 4

Constraints:

1 <= n <= 10^9
1 <= reservedSeats.length <= min(10*n, 10^4)
reservedSeats[i].length == 2
1 <= reservedSeats[i][0] <= n
1 <= reservedSeats[i][1] <= 10
All reservedSeats[i] are distinct.

Solution: HashTable + Greedy

if both seat[2~5] seat[6~9] are empty, seat two groups.
if any of seat[2~5] seat[4~7] seat[6~9] is empty seat one group.
if there is no one sit in a row, seat two groups.

Time complexity: O(|reservedSeats|)
Space complexity: O(|rows|)

C++

// Author: Huahua

class Solution {

public:

int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {

unordered_map<int, int> rows;

for (auto& seat : reservedSeats)

rows[seat[0]] |= 1 << (seat[1] - 1);

int ans = (n - rows.size()) * 2;

for (const auto& [idx, row] : rows) {

int s2 = row & 0b0000011110;

int s4 = row & 0b0001111000;

int s6 = row & 0b0111100000;

if (s2 == 0 && s6 == 0)

ans += 2;

else if (s2 == 0 || s4 == 0 || s6 == 0)

ans += 1;

}

return ans;

}

};