Huahua’s Tech Road

花花酱 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 1390. Four Divisors

By zxi on March 22, 2020

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors.

If there is no such integer in the array, return 0.

Example 1:

Input: nums = [21,4,7]
Output: 32
Explanation:
21 has 4 divisors: 1, 3, 7, 21
4 has 3 divisors: 1, 2, 4
7 has 2 divisors: 1, 7
The answer is the sum of divisors of 21 only.

Constraints:

1 <= nums.length <= 10^4
1 <= nums[i] <= 10^5

Solution: Math

If a number is a perfect square (e.g. 9 = 3 * 3), it will have odd number of divisors. (9: 1, 3, 9).

Time complexity: O(sum(sqrt(num_i))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int sumFourDivisors(vector<int>& nums) {

int ans = 0;

for (int n : nums) {

int r = sqrt(n);

if (n <= 4 || r * r == n) continue;

int count = 2;

int sum = 1 + n;

for (int d = 2; d <= r; ++d)

if (n % d == 0) {

count += 2;

sum += n / d + d;

}

if (count == 4) ans += sum;

}

return ans;

}

};

花花酱 LeetCode 1389. Create Target Array in the Given Order

By zxi on March 22, 2020

Given two arrays of integers nums and index. Your task is to create target array under the following rules:

Initially target array is empty.
From left to right read nums[i] and index[i], insert at index index[i] the value nums[i] in target array.
Repeat the previous step until there are no elements to read in nums and index.

Return the target array.

It is guaranteed that the insertion operations will be valid.

Example 1:

Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]
Output: [0,4,1,3,2]
Explanation:
nums       index     target
0            0        [0]
1            1        [0,1]
2            2        [0,1,2]
3            2        [0,1,3,2]
4            1        [0,4,1,3,2]

Example 2:

Input: nums = [1,2,3,4,0], index = [0,1,2,3,0]
Output: [0,1,2,3,4]
Explanation:
nums       index     target
1            0        [1]
2            1        [1,2]
3            2        [1,2,3]
4            3        [1,2,3,4]
0            0        [0,1,2,3,4]

Example 3:

Input: nums = [1], index = [0]
Output: [1]

Constraints:

1 <= nums.length, index.length <= 100
nums.length == index.length
0 <= nums[i] <= 100
0 <= index[i] <= i

Solution: Simulation

Time complexity: O(n) ~ O(n^2)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {

vector<int> target;

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

target.insert(begin(target) + index[i], nums[i]);

return target;

}

};

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

}

};

花花酱 LeetCode 1387. Sort Integers by The Power Value

By zxi on March 22, 2020

The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps:

if x is even then x = x / 2
if x is odd then x = 3 * x + 1

For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1).

Given three integers lo, hi and k. The task is to sort all integers in the interval [lo, hi] by the power value in ascending order, if two or more integers have the same power value sort them by ascending order.

Return the k-th integer in the range [lo, hi] sorted by the power value.

Notice that for any integer x (lo <= x <= hi) it is guaranteed that x will transform into 1 using these steps and that the power of x is will fit in 32 bit signed integer.

Example 1:

Input: lo = 12, hi = 15, k = 2
Output: 13
Explanation: The power of 12 is 9 (12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)
The power of 13 is 9
The power of 14 is 17
The power of 15 is 17
The interval sorted by the power value [12,13,14,15]. For k = 2 answer is the second element which is 13.
Notice that 12 and 13 have the same power value and we sorted them in ascending order. Same for 14 and 15.

Example 2:

Input: lo = 1, hi = 1, k = 1
Output: 1

Example 3:

Input: lo = 7, hi = 11, k = 4
Output: 7
Explanation: The power array corresponding to the interval [7, 8, 9, 10, 11] is [16, 3, 19, 6, 14].
The interval sorted by power is [8, 10, 11, 7, 9].
The fourth number in the sorted array is 7.

Example 4:

Input: lo = 10, hi = 20, k = 5
Output: 13

Example 5:

Input: lo = 1, hi = 1000, k = 777
Output: 570

Constraints:

1 <= lo <= hi <= 1000
1 <= k <= hi - lo + 1

Solution: Precompute + quick select

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

C++

// Author: Huahua

class Solution {

public:

int getKth(int lo, int hi, int k) {

vector<pair<int, int>> vals;

for (int n = lo; n <= hi; ++n) {

int p = 0;

int x = n;

while (x != 1) {

if (x & 1) x = 3 * x + 1;

else x /= 2;

++p;

}

vals.emplace_back(p, n);

}

nth_element(begin(vals), begin(vals) + k - 1, end(vals));

return vals[k - 1].second;

}

};

Huahua's Tech Road

花花酱 LeetCode 1396. Design Underground System

Solution: Hashtable

C++

花花酱 LeetCode 1390. Four Divisors

Solution: Math

C++

花花酱 LeetCode 1389. Create Target Array in the Given Order

Solution: Simulation

C++

花花酱 LeetCode 1386. Cinema Seat Allocation

Solution: HashTable + Greedy

C++

花花酱 LeetCode 1387. Sort Integers by The Power Value

Solution: Precompute + quick select

C++