# 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

class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
vector<int> ans;
int n = arr.size();
auto it = lower_bound(arr.begin(), arr.end(), x);
if (it == arr.begin()) {
while (ans.size() < k) {
ans.push_back(*it++);
}
return ans;
}
else if (it == arr.end()) {
while (ans.size() < k) {
ans.push_back(*--it);
}
return ans;
}
else {
int right = it - arr.begin();
int left = right - 1;
int left_diff = INT_MAX, right_diff = INT_MAX;
while (ans.size() < k) {
if (left >= 0)left_diff = abs(arr[left] - x);
else left_diff = INT_MAX;
if (right < n)right_diff = abs(arr[right] - x);
else right_diff = INT_MAX;
if (left_diff <= right_diff) {
ans.push_back(arr[left]);
--left;
}
else {
ans.push_back(arr[right]);
++right;
}
}
}
sort(ans.begin(), ans.end());
return ans;
}
};


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

bool cmp(const vector<int>& p1, const vector<int>& p2) {
return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]);
}
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), cmp);
int n = pairs.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = 0;
dp[0][1] = 1;
int ans = 1;
for (int i = 1; i < n; ++i) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = 1;
int j = i - 1;
while (j >= 0 && pairs[i][0] <= pairs[j][1]) {
--j;
}
if (j >= 0) {
dp[i][1] = max(dp[i][1], dp[j][1] + 1);
}
ans = max(ans, dp[i][0]);
ans = max(ans, dp[i][1]);
}
return ans;
}
};


class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]); });
int n = pairs.size(), ans = 1;
vector<int> dp(n, 1);
for (int i = 1; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (pairs[i][0] > pairs[j][1]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
};


class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[1] < p2[1]; });
int ans = 0;
for (int i = 0, j = 0; j < pairs.size(); ++j) {
if (j == 0 || pairs[j][0] > pairs[i][1]) {
++ans;
i = j;
}
}
return ans;
}
};


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

retrieve的时候，根据粒度，重新设置start和end，比如样例中粒度为Year时，把start改为Year固定，其他时间最小

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

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

class LogSystem {
private:
struct Node {
int id;
string timestamp;
Node(int i, string t) :id(i), timestamp(t) {};
};
list<Node> log;
string start, end;
public:
LogSystem() {
start = "2000:00:00:00:00:00";
end = "2017:12:31:23:59:59";
}
void put(int id, string timestamp) {
Node node(id, timestamp);
if (log.empty())log.push_back(node);
else {
auto it = log.begin();
while (it != log.end() && (*it).timestamp <= timestamp)++it;
log.insert(it, node);
}
}
vector<int> retrieve(string s, string e, string gra) {
if (gra == "Year") {
s = s.substr(0, 4) + start.substr(4);
e = e.substr(0, 4) + end.substr(4);
}
else if (gra == "Month") {
s = s.substr(0, 7) + start.substr(7);
e = e.substr(0, 7) + end.substr(7);
}
else if (gra == "Day") {
s = s.substr(0, 10) + start.substr(10);
e = e.substr(0, 10) + end.substr(10);
}
else if (gra == "Hour") {
s = s.substr(0, 13) + start.substr(13);
e = e.substr(0, 13) + end.substr(13);
}
else if (gra == "Minute") {
s = s.substr(0, 16) + start.substr(16);
e = e.substr(0, 16) + end.substr(16);
}
vector<int> ans;
auto it = log.begin();
while (it != log.end() && (*it).timestamp < s)++it;
while (it != log.end() && (*it).timestamp <= e) {
ans.push_back((*it).id);
++it;
}
return ans;
}
};


# 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.
Can you do it in O(n) time and/or in-place with O(1) extra space?

class Solution {
private:
//自己实现的快排程序
void my_quick_sort(vector<int>& nums, int s, int t) {
int i = s, j = t, pivot = s;
if (i >= j)return;
while (i <= j) {
while (i <= j&&nums[i] <= nums[pivot])++i;
if (i > j)break;
while (i <= j&&nums[j] >= nums[pivot])--j;
if (i > j)break;
swap(nums[i++], nums[j--]);
}
swap(nums[pivot], nums[j]);
my_quick_sort(nums, s, j - 1);
my_quick_sort(nums, j + 1, t);
}
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
my_quick_sort(nums, 0, n - 1);
int i = (n & 1) == 0 ? n / 2 - 1 : n / 2, j = n - 1;
vector<int> ans(n, 0);
for (int k = 0; k < n; ++k) {
ans[k] = (k & 1) == 0 ? nums[i--] : nums[j--];
}
nums = ans;
}
};


class Solution {
public:
void wiggleSort(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size(), i = (n + 1) / 2, j = n;
vector<int> ans(n, 0);
for (int k = 0; k < n; ++k) {
ans[k] = (k & 1) == 0 ? nums[--i] : nums[--j];
}
nums = ans;
}
};


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

class Solution {
public:
int findPairs(vector<int>& nums, int k) {
if (k < 0)return 0;
int repeated = 0;
map<int, int> count;
for (const auto& num : nums) {
++count[num];
if (count[num] == 2)++repeated;
}
if (k == 0)return repeated;
vector<int> sorted;
for (const auto& it : count) {
sorted.push_back(it.first);
}
int ans = 0;
for (const auto& num : sorted) {
if (count.find(num + k) != count.end())++ans;
}
return ans;
}
};


# LeetCode Course Schedule III

LeetCode Course Schedule III
There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dth day. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day.
Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.
Example:

Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
Output: 3
Explanation:
There're totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day.
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day.
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.


Note:

1. The integer 1 <= d, t, n <= 10,000.
2. You can't take two courses simultaneously.

1. 选修第一门课程，now=3<8，优先队列堆顶为3
2. 选修第二门课程，now=3+7=10<=10，优先队列堆顶为7
3. 选修第三门课程，now=10+5=15>14，失败；发现堆顶课程的持续时间是7，大于当前课程的持续时间5，所以可以把堆顶课程换成该门课程，则新的now=10-7+5=8，堆顶为5。因为该门课程的持续时间比堆顶短，且关闭时间已排序，所以大于堆顶的关闭时间，所以把堆顶课程换成该课程，该课程肯定能过完成。且新的now=8比先前的now=10要小，使得可以完成第四门课程。
4. 选修第四门课，now=8+8=16<17，优先队列为8。

class Solution {
public:
int scheduleCourse(vector<vector<int>>& courses) {
auto cmp = [](vector<int>& c1, vector<int>& c2) {return c1[1] < c2[1]; };
sort(courses.begin(), courses.end(), cmp);
int now = 0, ans = 0;
priority_queue<int> pq;
for (const auto& c : courses) {
if (now + c[0] <= c[1]) {
++ans;
now += c[0];
pq.push(c[0]);
}
else if (!pq.empty() && c[0] < pq.top()) {
now = now - pq.top() + c[0];
pq.pop();
pq.push(c[0]);
}
}
return ans;
}
};


# LeetCode Maximum Product of Three Numbers

LeetCode Maximum Product of Three Numbers
Given an integer array, find three numbers whose product is maximum and output the maximum product.
Example 1:

Input: [1,2,3]
Output: 6


Example 2:

Input: [1,2,3,4]
Output: 24


Note:

1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
2. Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

class Solution {
public:
int maximumProduct(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
int ans1 = nums[n - 1] * nums[n - 2] * nums[n - 3], ans2 = 0;
if (nums[0] > 0)return ans1;
if (nums[0] < 0 && nums[1] < 0)ans2 = nums[0] * nums[1] * nums[n - 1];
return max(ans1, ans2);
}
};


# LeetCode Maximum Distance in Arrays

LeetCode Maximum Distance in Arrays
Given m arrays, and each array is sorted in ascending order. Now you can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a and b to be their absolute difference |a-b|. Your task is to find the maximum distance.
Example 1:

Input:
[[1,2,3],
[4,5],
[1,2,3]]
Output: 4
Explanation:
One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array.


Note:

1. Each given array will have at least 1 number. There will be at least two non-empty arrays.
2. The total number of the integers in all the m arrays will be in the range of [2, 10000].
3. The integers in the m arrays will be in the range of [-10000, 10000].

class Solution {
struct P {
int idx;
int value;
P(int i, int v) :idx(i), value(v) {};
bool operator<(const P& p) {
return this->value < p.value;
}
};
public:
int maxDistance(vector<vector<int>>& arrays) {
vector<P> vp;
for (int i = 0; i < arrays.size(); ++i) {
vp.push_back({ i,arrays[i][0] });
vp.push_back({ i,arrays[i][arrays[i].size() - 1] });
}
sort(vp.begin(), vp.end());
int ans = 0, n = vp.size();
if (vp[0].idx != vp[n - 1].idx)return abs(vp[n - 1].value - vp[0].value);
return max(abs(vp[n - 1].value - vp[1].value), abs(vp[n - 2].value - vp[0].value));
}
};


class Solution {
public:
int maxDistance(vector<vector<int>>& arrays) {
int ans = INT_MIN;
int curMin = arrays[0][0], curMax = arrays[0][arrays[0].size() - 1];
for(int i = 1; i < arrays.size(); ++i) {
ans = max(ans, abs(arrays[i][0] - curMax));
ans = max(ans, abs(arrays[i][arrays[i].size() - 1] - curMin));
curMin = min(curMin, arrays[i][0]);
curMax = max(curMax, arrays[i][arrays[i].size() - 1]);
}
return ans;
}
};


# LeetCode Shortest Unsorted Continuous Subarray

LeetCode Shortest Unsorted Continuous Subarray
Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.
You need to find the shortest such subarray and output its length.
Example 1:

Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.


Note:

1. Then length of the input array is in range [1, 10,000].
2. The input array may contain duplicates, so ascending order here means <=.

class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
vector<int> nums_copy = nums;
sort(nums_copy.begin(), nums_copy.end());
int i = 0, j = nums.size() - 1;
while (i <= j&&nums[i] == nums_copy[i])++i;
while (j >= i&&nums[j] == nums_copy[j])--j;
return j - i + 1;
}
};


1. 从左往右，如果该数已经在最终排序的位置了，那么该数必须小于等于该数右边的最小值
2. 从右往左，如果该数已经在最终排序的位置了，那么该数必须大于等于该数左边的最大值

/**
*            /------------\
* nums:  [2, 6, 4, 8, 10, 9, 15]
* minsf:  2  4  4  8   9  9  15
*         <--------------------
* maxsf:  2  6  6  8  10 10  15
*         -------------------->
*/
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
int n = nums.size();
vector<int> min_so_far(n, 0), max_so_far(n, 0);
for (int i = 0, maxsf = INT_MIN; i < n; ++i)max_so_far[i] = maxsf = max(maxsf, nums[i]);
for (int i = n - 1, minsf = INT_MAX; i >= 0; --i)min_so_far[i] = minsf = min(minsf, nums[i]);
int i = 0, j = n - 1;
while (i <= j&&nums[i] <= min_so_far[i])++i;
while (j >= i&&nums[j] >= max_so_far[j])--j;
return j - i + 1;
}
};


# LeetCode Heaters

LeetCode Heaters
Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.
Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.
So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.
Note:

1. Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
2. Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
3. As long as a house is in the heaters' warm radius range, it can be warmed.

Example 1:

Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.


Example 2:

Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(heaters.begin(), heaters.end());
int ans = 0;
for (int i = 0; i < houses.size(); ++i) {
int &pos = houses[i];
int r = INT_MAX;
auto lb = lower_bound(heaters.begin(), heaters.end(), pos);
if (lb > heaters.begin())r = min(r, pos - *(lb - 1));
auto ub = lower_bound(heaters.begin(), heaters.end(), pos);
if (ub < heaters.end())r = min(r, *ub - pos);
ans = max(ans, r);
}
return ans;
}
};


class Solution {
private:
int my_lower_bound(vector<int>& v, int target) {
int l = 0, r = v.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (target > v[m])l = m + 1;
else r = m - 1;
}
return l;
}
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(heaters.begin(), heaters.end());
int ans = 0, n = houses.size(), m = heaters.size();
for (int i = 0; i < n; ++i) {
int &pos = houses[i];
int r = INT_MAX;
int lb = my_lower_bound(heaters, pos);
if (lb > 0)r = min(r, pos - heaters[lb - 1]);
if (lb < m)r = min(r, heaters[lb] - pos);
ans = max(ans, r);
}
return ans;
}
};