# LeetCode K Closest Points to Origin

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

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

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

# LeetCode Can Make Arithmetic Progression From Sequence

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

# LeetCode Diagonal Traverse II

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.

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

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

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

# LeetCode Find K Closest Elements

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]

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

Note:
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 104
3. Absolute value of elements in the array and x will not exceed 104

# LeetCode Maximum Length of Pair Chain

LeetCode Maximum Length of Pair Chain You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion. Given a set of pairs, find the length longest chain which can be formed. You needn’t use up all the given pairs. You can select pairs in any order. Example 1:

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

Note:
1. The number of given pairs will be in the range [1, 1000].

# LeetCode Design Log Storage System

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.

Note:
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

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

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.

Example 2:
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).

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

Note:
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].