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

设计一个地铁记录系统。完整代码如下，使用system记录每条线路的用时和乘坐次数，使用starts记录每个人旅行起点。不用记录终点，因为checkout的时候，把起点取出计算用时即可。

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);
	}
};

本代码提交AC，用时744MS。

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 (i, j, k) 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

给定一个数组，要求找出这样的升序或者降序的三元组数目。

竞赛阶段，由于n的范围较小，首先尝试暴力O(n^3)解法，代码如下：

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;
	}
};

本代码提交AC，用时204MS。

还有更优的O(n^2)的解法。对于每个士兵，统计其左边小于它的数目，和右边大于它的数目，则这两个数相乘即为该士兵能组成的升序数目，类似的可以算到该士兵能组成的降序数目。代码如下：

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[1] * greater_num[1] + less_num[0] * greater_num[0];
		}
		return ans;
	}
};

本代码提交AC，用时12MS。

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] == 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

给定一个数组，定义幸运数字是它的值与它在数组中出现的次数相等的数，问数组中最大的幸运数字是哪个。

简单题，用一个map计数即可，代码如下：

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;
	}
};

本代码提交AC，用时12MS。

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

给定一个数组，问其中哪些数只有4个因子，把只有4个因子的数对应的所有因子加起来。

也是很无聊的一个题，按题意照做即可，注意求解因子的时候只需要循环到sqrt(v)即可，因为如果一个因子大于sqrt(v)的话，其对应的另一个因子肯定小于sqrt(v)，也就是之前已经遍历过了。

完整代码如下：

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;
	}
};

本代码提交AC，用时440MS。

1389. 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        [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

很无聊的一个题。给定一个值数组nums，和一个下标数组index，表示数nums[i]插入到index[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;
	}
};

本代码提交AC，用时0MS。

34. 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]

给定一个有序数组，里面可能有重复元素，要求找出某个元素所有出现位置的起始位置和终止位置。

由于是有序数组，所以直接二分搜索，需要注意的是如果是找起始位置，则找到目标元素后还应该继续往左找，可以想象mid一直遇到target，则要不断执行r=mid-1，直到退出while循环，此时老的mid是等于target的最小下标，所以要返回r+1。类似的，如果找终止位置，则遇到相等后还要继续往右找，即l=mid+1，失败的时候返回上一个mid，即l-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) };
	}
};

本代码提交AC，用时4MS。

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

给定n个工程师，每个工程师有自己的速度值speed和效率值efficiency，一个包含k个工程师的团队的总体performance等于所有工程师的速度之和乘以最小效率：sum(speed)*min(efficiency)。问最多选k个工程师，最大的performance是多少。

我一开始被“最多k个”迷惑了，一直以为是一个DP题，后来看题解发现不是。

由于performance=sum(speed)*min(efficiency)，所以首先对n个工程师按efficiency从大到小排序，然后对于前m个工程师，他们的最小efficiency就是当前遍历到的第m个工程师的efficiency。如果m已经超过k，则需要从m个工程师中剔除掉速度最小的工程师，因为此时的min(efficiency)固定是第m个工程师的efficiency，所以只需要剔除速度低的工程师。

那么，如果最优解是少于k个人，这种方法能否找到最优解呢？其实是可以的，因为对于每加入一个工程师，我们都会和当前最优解对比，刚开始的时候，队列中的人数肯定少于k。

完整代码如下：

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);
	}
};

本代码提交AC，用时108MS。