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.

---

给定一系列课程，每门课有持续时间以及该课程关闭时间。从0时刻开始，问最多能完成多少门课程。注意不能同时上多门课程。 使用贪心的思路， 首先根据经验，越早结束的课程，越早选修并结束该课程越好，因为这样可以留出更多的时间选修其他课程。所以我们首先对所有课程按关闭时间从小到大排序，每次我们贪心的选择最早关闭的课程。 如果now+duration<=closed，即当前时间加该课程的持续时间不超过课程的关闭时间，则贪心选修该课程，并且把该课程的持续时间插入到一个优先队列中（最大堆）。 如果不能选修该课程，且优先队列中堆顶的持续时间比当前课程还大，则可以把堆顶课程删掉，换成该门课程，这样该门课程肯定可以选修并完成，同时使得新的now比之前的now要小，更有利于选修更多的课程。 举个例子，假设已经按关闭时间排序了[3,8],[7,10],[5,14],[8,17]，now=0。

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。

完整代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时162MS。]]>

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,10⁴] 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.

---

给定一个整数数组，选出三个数，使得乘积最大。 整数数组中可能有负数，所以我们先对数组从小到大排序。如果最小值都大于0，说明没有负数，则三数乘积最大就是最大的前3个数的乘积。 如果有负数，且至少有两个负数，则还需要判断一下最小的两个负数乘以最大的正数的乘积，这个数和前一种情况的大小关系。 代码如下： [cpp] 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); } }; [/cpp] 本代码提交AC，用时73MS。]]>

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

---

给定m个已从小到大排序的数组，要求从两个不同的数组中取出两个数，使得这两个数的差的绝对值最大，问最大的差的绝对值是多少。 因为数组已排序，所以最大的差值肯定等于某个数组的最大值和另一个数组的最小值的差。这里唯一需要注意的是两个数必须选自两个不同的数组。 我开始的做法是这样的，把所有数组的最大值和最小值都拿出来，然后重新排个序。在新数组中，如果最大值和最小值来自不同的数组，则他们的差就是最终结果。加入最大值和最小值是来自同一个数组的，则求最大值和次小值的差以及次大值和最小值的差中的最大值。因为最大值和最小值来自同一个数组，所以最大值和次小值以及次大值和最小值肯定不是来自同一个数组的。 代码如下： [cpp] 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)); } }; [/cpp] 本代码提交AC，用时26MS。因为要对m个数组的最大值和最小值排序，所以时间复杂度为O((2m)lg(2m))。 讨论区还有一种解法，只需要O(m)的复杂度。我们遍历每个数组，记录之前所有数组的最小值的最小值以及最大值的最大值，然后用当前数组的最大值和最小值减去之前所有数组中的最小值的最小值以及最大值的最大值，求绝对值，更新结果。这样就作差的两个数肯定来自不同的数组，避免了之前的问题。 代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时22MS。]]>

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

---

给定一个数组，问最短对多长的子数组排序之后，整个数组都会是升序的。比如样例对中间的[6,4,8,10,9]这个子数组排序之后，放回到原数组，原数组也是升序排列的。 第一种解法是，直接对数组排序，然后把已排序数组和未排序数组分别从首位对比，遇到第一个不相等的位置就跳出，然后需要排序的子数组长度就是j-i+1了。 代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时52MS，时间复杂度是O(nlgn)。 还有一种O(n)的方法，参考这个题解。 基本思想是这样：

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

如果违反1，那么该数右边还有比该数小的数，所以需要把这个更小的数放到该数前面，也就是说该数不在其最终的位置；违反2也是类似的。 所以我们维护两个数组，分别存储从左往右的最大值和从右往左的最小值，然后和原数组比较即可。 代码如下： [cpp] /** * /————\ * 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; } }; [/cpp] 本代码提交AC，用时72MS，时间复杂度是O(n)，但是为啥比第一种方法还慢呀。]]>

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.
4. All the heaters follow your radius standard and the warm radius will the same.

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.

---

给定房子和加热器的位置，问加热器的最小半径是所少才能使所有房子都在加热的范围之内。一个加热器的加热范围是一个圆，所有加热器的加热半径都是一样的。 要保证每个房子都在加热范围之内，且加热器的半径最小，则房子i肯定被紧邻i前后的两个加热器之一覆盖，其他加热器距离i的距离肯定比紧邻i前后的两个加热器远。比如x, i, y，i表示房子坐标，x和y分别表示紧邻i的两个加热器坐标，则覆盖i的最小半径应该是min(i-x,y-i)。 所以问题就转换为对每个房子坐标i，去加热器坐标数组中找到紧邻i前后的两个加热器坐标x和y，然后根据上述公式更新结果。为了便于查找，先对加热器坐标排序，然后直接二分查找就好了。 代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时89MS。 还可以自己写二分查找代码，如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时76MS。]]>

LeetCode Longest Word in Dictionary through Deleting Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string. Example 1:

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
Output:
"apple"

Example 2:

Input:
s = "abpcplea", d = ["a","b","c"]
Output:
"a"

Note:

1. All the strings in the input will only contain lower-case letters.
2. The size of the dictionary won’t exceed 1,000.
3. The length of all the strings in the input won’t exceed 1,000.

---

给定一个字典d和字符串s，问d中哪些字符串可以通过s删除若干个字符得到，要求输出满足条件的最长字符串，如果有多个，则输出字典序最小的。 本题有两个考点，一是判断t是否能通过删除s中的若干个字符得到。使用两个指向s,t的指针i,j，j不断后移找t[i]，找到之后i,j都后移。最终如果找到t中所有字符，则成功，否则失败。 另一个考点是，找出所有满足条件的字符串之后，怎样找到长度最长且字典序最小的字符串。这可以通过自定义string的比较函数，然后sort得到。具体看代码： [cpp] bool comp(const string& s1, const string& s2) { return s1.size() > s2.size() || (s1.size() == s2.size() && s1 < s2); } class Solution { private: bool convert(const string& src, const string& dest){ int m = src.size(), n = dest.size(); if (m < n)return false; int i = 0, j = 0; while (i < m) { while (i < m && src[i] != dest[j])++i; if (i >= m)break; ++i; ++j; if (j == n)break; } return j == n; } public: string findLongestWord(string s, vector<string>& d) { vector<string> cand; for (int i = 0; i < d.size(); ++i) { if (convert(s, d[i]))cand.push_back(d[i]); } sort(cand.begin(), cand.end(), comp); if (cand.size() > 0)return cand[0]; else return ""; } }; [/cpp] 本代码提交AC，用时135MS。]]>

LeetCode Non-overlapping Intervals Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping. Note:

1. You may assume the interval’s end point is always bigger than its start point.
2. Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

Example 1:

Input: [ [1,2], [2,3], [3,4], [1,3] ]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [ [1,2], [1,2], [1,2] ]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

Input: [ [1,2], [2,3] ]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

---

给定一系列区间，问最少删除多少个区间能使得剩余区间没有重叠。区间[i,j]和[u,v]重叠是指u<j或者i<v，如果两个区间只是边界重叠比如j==u，则不算重叠。 我们可以使用贪心的策略求最多能保存多少个区间，然后用总数一减就得到最少删除的区间数。 首先对区间先后按start和end从小到大排序，然后从头开始遍历。假设我们上一次保留的区间的end是last_end，如果当前区间的intervals[i].start>=last_end，则说明区间i可以保留，更新last_end=intervals[i].end。如果intervals[i].start<last_end，则当前区间会和上一个区间重叠，需要删除一个区间，为了使留下来的区间更多，肯定要删除end大的区间，令last_end=min(last_end,intervals[i].end)，通过保留end小的区间来间接模拟删除end大的区间。 当得到保留下来的不重叠区间个数ans后，用n-ans就是需要删除的区间数。完整代码如下： [cpp] bool comp(const Interval &i1, const Interval &i2){ return i1.start < i2.start || (i1.start == i2.start && i1.end < i2.end); } class Solution { public: int eraseOverlapIntervals(vector<Interval>& intervals) { if(intervals.empty()) return 0; sort(intervals.begin(), intervals.end(), comp); int ans = 1, n = intervals.size(), last_end = intervals[0].end; for(int i = 1; i < n; ++i){ if(intervals[i].start >= last_end){ ++ans; last_end = intervals[i].end; } else { last_end = min(last_end, intervals[i].end); } } return n – ans; } }; [/cpp] 本代码提交AC，用时9MS。]]>

LeetCode Find Right Interval Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the “right” of i. For any interval i, you need to store the minimum interval j’s index, which means that the interval j has the minimum start point to build the “right” relationship for interval i. If the interval j doesn’t exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array. Note:

1. You may assume the interval’s end point is always bigger than its start point.
2. You may assume none of these intervals have the same start point.

Example 1:

Input: [ [1,2] ]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

Input: [ [3,4], [2,3], [1,2] ]
Output: [-1, 0, 1]
Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.

Example 3:

Input: [ [1,4], [2,3], [3,4] ]
Output: [-1, 2, -1]
Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.

---

给定一系列区间[start,end]，定义区间[i,j]的“右区间”为[u,v]使得u是第一个不小于j的数。要求输出每个区间的右区间下标，如果不存在右区间，则输出-1。 我的解法。因为要输出右区间在原数组中的下标，所以得保留每个区间在原数组中的下标。定义一个新的结构体MyInterval，用来保存区间以及该区间在原数组中的下标。对所有区间按start排序，然后遍历每一个区间[i,j]，在已排序区间数组中找第一个start大于j的区间，取出它的下标作为区间[i,j]的结果。 代码如下： [cpp] typedef struct MyInterval { Interval inter; int idx; MyInterval(Interval inter_, int idx_) :inter(inter_), idx(idx_) {}; bool operator<(const MyInterval& myi) const{ return this->inter.start < myi.inter.start; // 所有start不相同 } }; class Solution2 { public: vector<int> findRightInterval(vector<Interval>& intervals) { int n = intervals.size(); vector<MyInterval> myvs; for (int i = 0; i < n; ++i) { MyInterval myint(intervals[i], i); myvs.push_back(myint); } sort(myvs.begin(), myvs.end()); vector<int> ans(n, -1); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { // 线性查找 if (myvs[j].inter.start >= myvs[i].inter.end) { ans[myvs[i].idx] = myvs[j].idx; break; } } } return ans; } }; [/cpp] 本代码提交AC，用时299MS。 上述代码还可优化，在已排序区间数组中找第一个start大于j的区间时，可以用二分搜索。 另外因为所有区间的start不相同，所以事先用hash记录start和原数组下标。这样只需要把所有区间的start抽出来排序，然后二分查找每一个end。代码如下： [cpp] class Solution { private: int binsearch(const vector<int>& starts, int target) { int l = 0, r = starts.size() – 1; while (l <= r) { int m = l + (r – l) / 2; if (starts[m] == target)return starts[m]; if (starts[m] < target)l = m + 1; else r = m – 1; } return starts[l]; } public: vector<int> findRightInterval(vector<Interval>& intervals) { int n = intervals.size(); vector<int> starts; unordered_map<int, int> hash; for (int i = 0; i < n; ++i) { starts.push_back(intervals[i].start); hash[intervals[i].start] = i; } sort(starts.begin(), starts.end()); vector<int> ans(n, -1); for (int i = 0; i < n; ++i) { if (intervals[i].end <= starts[n – 1]) { int t = binsearch(starts, intervals[i].end); ans[i] = hash[t]; } } return ans; } }; [/cpp] 本代码提交AC，用时96MS，快了不少。]]>

LeetCode Minimum Time Difference Given a list of 24-hour clock time points in “Hour:Minutes” format, find the minimum minutes difference between any two time points in the list. Example 1:

Input: ["23:59","00:00"]
Output: 1

Note:

1. The number of time points in the given list is at least 2 and won’t exceed 20000.
2. The input time is legal and ranges from 00:00 to 23:59.

---

给定一个时间字符串数组，问数组中任意两个时间之差最小是多少分钟。 本题的基本思路是把数组中所有的时间表示转换为分钟，然后排序求相邻两个分钟之间的最小差。 本题的一个小难点是时间是循环的，比如01:30和06:30差5小时，但01:30和23:30差几小时呢？如果顺着看差22小时，好像比前一个差要大，但是逆着看，实际上只差2小时。所以分立0点两边的两个时间差其实有两个。处理办法是把0~12点之间的时间转换为两个分钟数，一个是0~12以内的，另一个是12~24以内的。 代码如下： [cpp] class Solution { private: void convertToMinutes(const string& s, vector<int>& minutes) { int pos = s.find(‘:’); int hour = atoi(s.substr(0, pos).c_str()), minute = atoi(s.substr(pos + 1).c_str()); int m = hour * 60 + minute; minutes.push_back(m); if (hour < 12)minutes.push_back(m + 24 * 60); } public: int findMinDifference(vector<string>& timePoints) { vector<int> minutes; for (int i = 0; i < timePoints.size(); ++i) { convertToMinutes(timePoints[i], minutes); } sort(minutes.begin(), minutes.end()); int ans = INT_MAX; for (int i = 1; i < minutes.size(); ++i) { ans = min(ans, minutes[i] – minutes[i – 1]); } return ans; } }; [/cpp] 本代码提交AC，用时19MS。]]>