973. K Closest Points to Origin

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)

Note:

1. 1 <= K <= points.length <= 10000
2. -10000 < points[i][0] < 10000
3. -10000 < points[i][1] < 10000

给定二维平面上的若干个点，求距离原点最近的K个点。

看总结： https://leetcode-cn.com/problems/k-closest-points-to-origin/solution/cyu-yan-san-chong-jie-fa-han-zong-jie-by-gan-cui-j/

事实上，诸如此类的，要在一个数组中寻找第K大的数（或者第K小的数），前K大的数，前K小的数，一般来说的方法有：

1.先排序（快排）时间复杂度为nlogn
2.建堆，堆的大小为K，建立大根堆或者小根堆，时间复杂度为nlogK(如果要求出前K个较大的，那么就建立小根堆，一旦比堆顶大，那么就入堆)；
3.结合快速排序划分的方法，不断减小问题的规模

对于这一题，采用解法3，即快排划分的思路。采用标准快排思路，每次选区间最右边的元素作为pivot，然后划分，看看划分后的pivot位置和K的大小关系，递归在左右区间进行划分。完整代码如下：

class Solution {
private:
	vector<int> origin;

	int CalDist(vector<int> &p1, vector<int> &p2) {
		return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
	}

	void MySwap(vector<vector<int>>& points, int u, int v) {
		swap(points[u][0], points[v][0]);
		swap(points[u][1], points[v][1]);
	}

	void Work(vector<vector<int>>& points, int l, int r, int K) {
		if (l >= r) return;

		int pivot = r;
		int pdist = CalDist(points[pivot], origin);
		int i = l;
		for (int j = l; j < r; ++j) {
			int idist = CalDist(points[j], origin);
			if (idist < pdist) {
				MySwap(points, i++, j);
			}
		}
		MySwap(points, i, pivot);

		if (K == i)return;
		else if (K < i)Work(points, l, i - 1, K);
		else Work(points, i + 1, r, K);
	}
public:
	vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
		origin = { 0, 0 }; // 求与该点距离最近的top-k个点，本题中该点是原点

		for (int i = 0; i < points.size(); ++i) {
			printf("x=%d,y=%d,dist=%d\n", points[i][0], points[i][1], CalDist(points[i], origin));
		}

		Work(points, 0, points.size() - 1, K - 1);

		vector<vector<int>> ans;
		for (int i = 0; i < K; ++i) ans.push_back(points[i]);
		return ans;
	}
};

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

5452. Can Make Arithmetic Progression From Sequence

Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Return true if the array can be rearranged to form an arithmetic progression, otherwise, return false.

Example 1:

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

Example 2:

Input: arr = [1,2,4]
Output: false
Explanation: There is no way to reorder the elements to obtain an arithmetic progression.

Constraints:

• 2 <= arr.length <= 1000
• -10^6 <= arr[i] <= 10^6

给一个数组，问能否通过排列组合让这个数组变成等差数列。

直接排序，看看是否是等差数列即可：

class Solution {
public:
	bool canMakeArithmeticProgression(vector<int>& arr) {
		sort(arr.begin(), arr.end());
		int diff = arr[1] - arr[0];
		for (int i = 2; i < arr.size(); ++i) {
			if (arr[i] - arr[i - 1] != diff)return false;
		}
		return true;
	}
};

本代码提交AC。

1424. Diagonal Traverse II

Given a list of lists of integers, nums, return all elements of nums in diagonal order as shown in the below images.

Example 1:

Input: nums = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,4,2,7,5,3,8,6,9]

Example 2:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

Example 3:

Input: nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]]
Output: [1,4,2,5,3,8,6,9,7,10,11]

Example 4:

Input: nums = [[1,2,3,4,5,6]]
Output: [1,2,3,4,5,6]

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i].length <= 10^5
• 1 <= nums[i][j] <= 10^9
• There at most 10^5 elements in nums.

如上图所示，给定一个残缺矩阵，要求遍历每个对角线，输出所有元素的值。

朴素解法会TLE，特别是如果有某一行或某一列比其他行列长特别多的情况。

提示解法：观察规律发现，处于同一对角线的元素的行列下标之和相等。所以我们可以把所有元素的行列下标进行排序，如果下标和相等，则处于同一对角线，按行下标从大到小排序；如果下标和不相等，则按下标和从小到大排序。完整代码如下：

bool cmp(const pair<int, int> &p1, const pair<int, int> &p2) {
	int sum1 = p1.first + p1.second, sum2 = p2.first + p2.second;
	if (sum1 == sum2) {
		return p1.first > p2.first;
	}
	else {
		return sum1 < sum2;
	}
}
class Solution {
public:
	vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
		vector<pair<int, int>> idxs;
		for (int i = 0; i < nums.size(); ++i) {
			for (int j = 0; j < nums[i].size(); ++j) {
				idxs.push_back(make_pair(i, j));
			}
		}
		sort(idxs.begin(), idxs.end(), cmp);
		vector<int> ans;
		for (int i = 0; i < idxs.size(); ++i) {
			ans.push_back(nums[idxs[i].first][idxs[i].second]);
		}
		return ans;
	}
};

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

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。

1366. Rank Teams by Votes

In a special ranking system, each voter gives a rank from highest to lowest to all teams participated in the competition.

The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.

Given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.

Return a string of all teams sorted by the ranking system.

Example 1:

Input: votes = ["ABC","ACB","ABC","ACB","ACB"]
Output: "ACB"
Explanation: Team A was ranked first place by 5 voters. No other team was voted as first place so team A is the first team.
Team B was ranked second by 2 voters and was ranked third by 3 voters.
Team C was ranked second by 3 voters and was ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team and team B is the third.

Example 2:

Input: votes = ["WXYZ","XYZW"]
Output: "XWYZ"
Explanation: X is the winner due to tie-breaking rule. X has same votes as W for the first position but X has one vote as second position while W doesn't have any votes as second position. 

Example 3:

Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"
Explanation: Only one voter so his votes are used for the ranking.

Example 4:

Input: votes = ["BCA","CAB","CBA","ABC","ACB","BAC"]
Output: "ABC"
Explanation: 
Team A was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team B was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team C was ranked first by 2 voters, second by 2 voters and third by 2 voters.
There is a tie and we rank teams ascending by their IDs.

Example 5:

Input: votes = ["M","M","M","M"]
Output: "M"
Explanation: Only team M in the competition so it has the first rank.

Constraints:

• 1 <= votes.length <= 1000
• 1 <= votes[i].length <= 26
• votes[i].length == votes[j].length for 0 <= i, j < votes.length.
• votes[i][j] is an English upper-case letter.
• All characters of votes[i] are unique.
• All the characters that occur in votes[0] also occur in votes[j] where 1 <= j < votes.length.

给定很多人对很多team的打分排序列表，如果一个队排在前面的名次越多，则其最终名次越高，据此输出最终排序列表。

规则很复杂，其实很简单。设计一个Team的类，它有一个scores数组，scores[i]表示这个队被多少人投票排在了第i名。由于最多只有26个队，所以scores的维度为26。对Team自定义排序函数，排序规则是依次比较scores的每个元素大小，如果都相等的话，最后比较name的大小。

完整代码如下：

const int MAXN = 26;
class Team {
public:
	char name;
	vector<int> scores;

	Team() :name(0) {
		scores.resize(MAXN, 0);
	};

	bool operator<(const Team& t) {
		for (int i = 0; i < MAXN; ++i) {
			if (scores[i] > t.scores[i]) {
				return true;
			}
			else if (scores[i] < t.scores[i]) {
				return false;
			}
		}
		return name < t.name;
	}
};

class Solution {
public:
	string rankTeams(vector<string>& votes) {
		vector<Team> teams(MAXN, Team());
		for (int j = 0; j < votes[0].size(); ++j) {
			int idx = votes[0][j] - 'A';
			teams[idx].name = votes[0][j]; // 出现的team name
		}
		for (int i = 0; i < votes.size();++i) {
			for (int j = 0; j < votes[i].size(); ++j) {
				int idx = votes[i][j] - 'A';
				++teams[idx].scores[j];
			}
		}
		vector<Team> showups;
		for (int i = 0; i < MAXN; ++i) {
			if (teams[i].name != 0) {
				showups.push_back(teams[i]);
			}
		}
		sort(showups.begin(), showups.end());
		string ans = "";
		for (int i = 0; i < showups.size(); ++i) {
			ans += showups[i].name;
		}
		return ans;
	}
};

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

LeetCode Find K Closest Elements Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred. Example 1:

Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]

Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]

1. The value k is positive and will always be smaller than the length of the sorted array.
2. Length of the given array is positive and will not exceed 10⁴
3. Absolute value of elements in the array and x will not exceed 10⁴

LeetCode Design Log Storage System You are given several logs that each log contains a unique id and timestamp. Timestamp is a string that has the following format: Year:Month:Day:Hour:Minute:Second, for example, 2017:01:01:23:59:59. All domains are zero-padded decimal numbers. Design a log storage system to implement the following functions: void Put(int id, string timestamp): Given a log’s unique id and timestamp, store the log in your storage system. int[] Retrieve(String start, String end, String granularity): Return the id of logs whose timestamps are within the range from start to end. Start and end all have the same format as timestamp. However, granularity means the time level for consideration. For example, start = “2017:01:01:23:59:59”, end = “2017:01:02:23:59:59”, granularity = “Day”, it means that we need to find the logs within the range from Jan. 1st 2017 to Jan. 2nd 2017. Example 1:

put(1, "2017:01:01:23:59:59");
put(2, "2017:01:01:22:59:59");
put(3, "2016:01:01:00:00:00");
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Year"); // return [1,2,3], because you need to return all logs within 2016 and 2017.
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Hour"); // return [1,2], because you need to return all logs start from 2016:01:01:01 to 2017:01:01:23, where log 3 is left outside the range.

1. There will be at most 300 operations of Put or Retrieve.
2. Year ranges from [2000,2017]. Hour ranges from [00,23].
3. Output for Retrieve has no order required.

"2016:00:00:00:00:00"

"2017:12:31:23:59:59"

LeetCode Wiggle Sort II Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3].... Example: (1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6]. (2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2]. Note: You may assume all input has valid answer. Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

LeetCode K-diff Pairs in an Array Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k. Example 1:

Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

1. The pairs (i, j) and (j, i) count as the same pair.
2. The length of the array won’t exceed 10,000.
3. All the integers in the given input belong to the range: [-1e7, 1e7].