# LeetCode Design Underground System

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 t1 at some station, then it gets out at time t2 with t2 > t1. All events happen in chronological order.

Example 1:

Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]

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(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.

class UndergroundSystem {
private:
map<string, map<string, pair<int, int>>> system_; // start->end, total time, #travels
map<int, pair<string, int>> starts_; // travel start station
public:
UndergroundSystem() {

}

void checkIn(int id, string stationName, int t) {
starts_[id] = make_pair(stationName, t);
}

void checkOut(int id, string stationName, int t) {
string start_station = starts_[id].first;
int start_time = starts_[id].second;
starts_.erase(id);
if (system_.find(start_station) == system_.end()
|| system_[start_station].find(stationName) == system_[start_station].end()) {
system_[start_station][stationName] = make_pair(0, 0);
}
system_[start_station][stationName].first += (t - start_time);
system_[start_station][stationName].second += 1;
}

double getAverageTime(string startStation, string endStation) {
return system_[startStation][endStation].first / double(system_[startStation][endStation].second);
}
};

# LeetCode Count Number of Teams

1395. Count Number of Teams

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

• Choose 3 soldiers with index (ijk) with rating (rating[i]rating[j]rating[k]).
• A team is valid if:  (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).


Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.


Example 3:

Input: rating = [1,2,3,4]
Output: 4


Constraints:

• n == rating.length
• 1 <= n <= 200
• 1 <= rating[i] <= 10^5

class Solution {
public:
int numTeams(vector<int>& rating) {
int ans = 0, n = rating.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
for (int k = j + 1; k < n; ++k) {
if (rating[i] < rating[j] && rating[j] < rating[k])++ans;
else if (rating[i] > rating[j] && rating[j] > rating[k])++ans;
}
}
}
return ans;
}
};

class Solution {
public:
int numTeams(vector<int>& rating) {
int ans = 0, n = rating.size();
for (int i = 1; i < n - 1; ++i) {
vector<int> less_num(2, 0), greater_num(2, 0);
for (int j = 0; j < n; ++j) {
if (rating[j] < rating[i])++less_num[j < i];
else if (rating[j] > rating[i])++greater_num[j > i];
}
ans += less_num * greater_num + less_num * greater_num;
}
return ans;
}
};


# LeetCode Find Lucky Integer in an Array

5368. Find Lucky Integer in an Array

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.


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 = 
Output: -1


Example 5:

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


Constraints:

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

class Solution {
public:
int findLucky(vector<int>& arr) {
map<int, int> lucky;
for (int i = 0; i < arr.size(); ++i) {
++lucky[arr[i]];
}
int max_lucky = -1;
for (map<int, int>::iterator it = lucky.begin(); it != lucky.end(); ++it) {
if (it->first == it->second) {
max_lucky = max(max_lucky, it->first);
}
}
return max_lucky;
}
};

# LeetCode Check if There is a Valid Path in a Grid

Given a m x ngrid. Each cell of the grid represents a street. The street of grid[i][j] can be:

• 1 which means a street connecting the left cell and the right cell.
• 2 which means a street connecting the upper cell and the lower cell.
• 3 which means a street connecting the left cell and the lower cell.
• 4 which means a street connecting the right cell and the lower cell.
• 5 which means a street connecting the left cell and the upper cell.
• 6 which means a street connecting the right cell and the upper cell.

You will initially start at the street of the upper-left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1)The path should only follow the streets.

Notice that you are not allowed to change any street.

Return true if there is a valid path in the grid or false otherwise.

Example 1:

Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).


Example 2:

Input: grid = [[1,2,1],[1,2,1]]
Output: false
Explanation: As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)


Example 3:

Input: grid = [[1,1,2]]
Output: false
Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).


Example 4:

Input: grid = [[1,1,1,1,1,1,3]]
Output: true


Example 5:

Input: grid = [,,,,,,]
Output: true


Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• 1 <= grid[i][j] <= 6

class Solution {
public:
bool hasValidPath(vector<vector<int>>& grid) {
int m = grid.size(), n = grid.size();
vector<vector<int>> flag(m, vector<int>(n, 0));
vector<vector<int>> dirs = { {0,-1},{0,1},{-1,0},{1,0} };//左右上下
queue<pair<int, int>> q;
q.push(make_pair(0, 0));
while (!q.empty()) {
pair<int, int> p = q.front();
int u = p.first, v = p.second;
int src = grid[u][v];
if (u == m - 1 && v == n - 1)return true;
q.pop();
flag[u][v] = 1;
for (int i = 0; i < dirs.size(); ++i) {
int x = u + dirs[i], y = v + dirs[i];
if (x >= 0 && x < m&&y >= 0 && y < n && flag[x][y] == 0) {
int dest = grid[x][y];
if (grid[u][v] == 1) {
if ((i == 0 && (dest == 1 || dest == 4 || dest == 6)) ||
(i == 1 && (dest == 1 || dest == 3 || dest == 5))) {
q.push(make_pair(x, y));
}
}
else if (grid[u][v] == 2) {
if ((i == 2 && (dest == 2 || dest == 3 || dest == 4)) ||
(i == 3 && (dest == 2 || dest == 5 || dest == 6))) {
q.push(make_pair(x, y));
}
}
else if (grid[u][v] == 3) {
if ((i == 0 && (dest == 1 || dest == 4 || dest == 6)) ||
(i == 3 && (dest == 2 || dest == 5 || dest == 6))) {
q.push(make_pair(x, y));
}
}
else if (grid[u][v] == 4) {
if ((i == 1 && (dest == 1 || dest == 3 || dest == 5)) ||
(i == 3 && (dest == 2 || dest == 5 || dest == 6))) {
q.push(make_pair(x, y));
}
}
else if (grid[u][v] == 5) {
if ((i == 0 && (dest == 1 || dest == 4 || dest == 6)) ||
(i == 2 && (dest == 2 || dest == 3 || dest == 4))) {
q.push(make_pair(x, y));
}
}
else if (grid[u][v] == 6) {
if ((i == 1 && (dest == 1 || dest == 3 || dest == 5)) ||
(i == 2 && (dest == 2 || dest == 3 || dest == 4))) {
q.push(make_pair(x, y));
}
}
}
}
}
return false;
}
};


# LeetCode Four Divisors

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

class Solution {
public:
void FindDivisors(int v, vector<int>& ans) {
int mid = sqrt(v);
for (int i = 1; i <= mid; ++i) {
if (v%i == 0) {
ans.push_back(i);
if (v / i != i)ans.push_back(v / i);
}
}
}
int sumFourDivisors(vector<int>& nums) {
int ans = 0;
for (int i = 0; i < nums.size(); ++i) {
vector<int> divs;
FindDivisors(nums[i], divs);
if (divs.size() == 4) {
for (int j = 0; j < divs.size(); ++j)ans += divs[j];
}
}
return ans;
}
};

# LeetCode Create Target Array in the Given Order

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        
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        
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 = , index = 
Output: 


Constraints:

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

class Solution {
public:
vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
int n = nums.size();
vector<int> ans;
for (int i = 0; i < n; ++i) {
ans.insert(ans.begin() + index[i], nums[i]);
}
return ans;
}
};

# LeetCode Longest Happy Prefix

A string is called a happy prefix if is a non-empty prefix which is also a suffix (excluding itself).

Given a string s. Return the longest happy prefix of s .

Return an empty string if no such prefix exists.

Example 1:

Input: s = "level"
Output: "l"
Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".


Example 2:

Input: s = "ababab"
Output: "abab"
Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.


Example 3:

Input: s = "leetcodeleet"
Output: "leet"


Example 4:

Input: s = "a"
Output: ""


Constraints:

• 1 <= s.length <= 10^5
• s contains only lowercase English letters.

class Solution {
public:
string longestPrefix(string s) {
s = s + ".";
int n = s.size();
vector<int> next(n, 0);
next = -1;
int i = 0, j = -1;
while (i < n - 1) {
if (j == -1 || s[i] == s[j]) {
++i;
++j;
next[i] = j;
}
else {
j = next[j];
}
}
return s.substr(0, next[n - 1]);
}
};

# LeetCode Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

class Solution {
public:
int FindFirstIndex(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (target <= nums[mid])r = mid - 1;
else l = mid + 1;
}
if (r + 1 < nums.size() && nums[r + 1] == target)return r + 1;
else return -1;
}
int FindLastIndex(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (target >= nums[mid])l = mid + 1;
else r = mid - 1;
}
if (l - 1 >= 0 && nums[l - 1] == target)return l - 1;
else return -1;
}
vector<int> searchRange(vector<int>& nums, int target) {
return { FindFirstIndex(nums,target),FindLastIndex(nums,target) };
}
};

# LeetCode Maximum Performance of a Team

There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.

The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers.

Example 1:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation:
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.


Example 2:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.


Example 3:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72


Constraints:

• 1 <= n <= 10^5
• speed.length == n
• efficiency.length == n
• 1 <= speed[i] <= 10^5
• 1 <= efficiency[i] <= 10^8
• 1 <= k <= n

class Solution {
public:
int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
vector<pair<int, int>> workers;
for (int i = 0; i < n; ++i) {
workers.push_back(make_pair(efficiency[i], speed[i]));
}
sort(workers.begin(), workers.end()); // 默认对pair.first升序排列
priority_queue <int, vector<int>, greater<int> > pq; // pq默认是最大堆，这是构建最小堆
long long ans = 0;
long long sum_speed = 0;
for (int i = n - 1; i >= 0; --i) {
sum_speed += workers[i].second;
pq.push(workers[i].second);
if (pq.size() > k) {
sum_speed -= pq.top();
pq.pop();
}
ans = max(ans, sum_speed*workers[i].first);
}
return ans % (int)(1e9 + 7);
}
};

# LeetCode Balance a Binary Search Tree

Given a binary search tree, return a balanced binary search tree with the same node values.

A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.

If there is more than one answer, return any of them.

Example 1:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct.


Constraints:

• The number of nodes in the tree is between 1 and 10^4.
• The tree nodes will have distinct values between 1 and 10^5.

class Solution {
public:
void preIter(TreeNode* root, vector<int> &nums) {
if (root == NULL)return;
preIter(root->left, nums);
nums.push_back(root->val);
preIter(root->right, nums);
}
TreeNode* constructBST(vector<int> &nums, int l, int r) {
if (l > r)return NULL;
if (l == r)return new TreeNode(nums[l]);

int mid = l + (r - l) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = constructBST(nums, l, mid - 1);
root->right = constructBST(nums, mid + 1, r);
return root;
}
TreeNode* balanceBST(TreeNode* root) {
vector<int> nums;
preIter(root, nums);
int n = nums.size();
return constructBST(nums, 0, n - 1);
}
};