# 剑指 Offer 11. 旋转数组的最小数字

LeetCode Find Minimum in Rotated Sorted Array II相同，即旋转有序数组中包含重复元素，求最小值。考虑nums[m]==nums[r]的情况，退化为线性查找，完整代码如下：

class Solution {
public:
int minArray(vector<int>& numbers) {
int n = numbers.size();
int l = 0, r = n - 1;
while(l <= r) {
if(r - l <= 1) return min(numbers[l], numbers[r]);
int m = l + (r - l) / 2;
if(numbers[m] > numbers[r]) l = m;
else if(numbers[m] == numbers[r]) --r;
else r = m;
}
return 0;
}
};

# 剑指 Offer 04. 二维数组中的查找

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

0 <= n <= 1000

0 <= m <= 1000

class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
if(matrix.empty() || matrix[0].empty()) return false;
int n = matrix.size(), m = matrix[0].size();
int i = 0, j = m - 1;
while(i < n && j >= 0) {
if(matrix[i][j] == target) return true;
if(target > matrix[i][j]) ++i;
else --j;
}
return false;
}
};

# LeetCode Minimum Number of Days to Make m Bouquets

5455. Minimum Number of Days to Make m Bouquets

Given an integer array bloomDay, an integer m and an integer k.

We need to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.

The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.

Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.

Example 1:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.


Example 2:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.


Example 3:

Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output: 12
Explanation: We need 2 bouquets each should have 3 flowers.
Here's the garden after the 7 and 12 days:
After day 7: [x, x, x, x, _, x, x]
We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent.
After day 12: [x, x, x, x, x, x, x]
It is obvious that we can make two bouquets in different ways.


Example 4:

Input: bloomDay = [1000000000,1000000000], m = 1, k = 1
Output: 1000000000
Explanation: You need to wait 1000000000 days to have a flower ready for a bouquet.


Example 5:

Input: bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
Output: 9


Constraints:

• bloomDay.length == n
• 1 <= n <= 10^5
• 1 <= bloomDay[i] <= 10^9
• 1 <= m <= 10^6
• 1 <= k <= n

class Solution {
bool IsValid(vector<int>& bloomDay, int day, int m, int k) {
int bouquets = 0, n = bloomDay.size();
int i = 0, good = 0;
while (i < n) {
while (i<n&&bloomDay[i]>day)++i;
if (i >= n)break;

int j = i;
while (j < n&&bloomDay[j] <= day)++j;
// [i,j) 都开花了

good += (j - i) / k;

i = j;
}
return good >= m;
}
public:
int minDays(vector<int>& bloomDay, int m, int k) {
int n = bloomDay.size();
if (m*k > n)return -1;

map<int, int> hash;
for (int i = 0; i < n; ++i)++hash[bloomDay[i]];
if (m*k == n)return (--hash.end())->first; // 最后一天

int unique_day = hash.size();
vector<int> days(unique_day, 0);
vector<int> num_bloomed(unique_day, 0);

int d = 0, nb = 0;
int left = 0, right = unique_day - 1, found_left = false;
for (map<int, int>::iterator it = hash.begin(); it != hash.end(); ++it) {
nb += it->second;
if (nb >= m * k && !found_left) {
left = d;
found_left = true;
}

days[d] = it->first;
num_bloomed[d] = nb;

++d;
}

while (left <= right) {
int mid = left + (right - left) / 2;
bool valid = IsValid(bloomDay, days[mid], m, k);
if (valid)right = mid - 1;
else left = mid + 1;
}

return days[right + 1];
}
};

# LeetCode Leftmost Column with at Least a One

LeetCode Leftmost Column with at Least a One

(This problem is an interactive problem.)

A binary matrix means that all elements are 0 or 1. For each individual row of the matrix, this row is sorted in non-decreasing order.

Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a 1 in it. If such index doesn’t exist, return -1.

You can’t access the Binary Matrix directly.  You may only access the matrix using a BinaryMatrix interface:

• BinaryMatrix.get(x, y) returns the element of the matrix at index (x, y) (0-indexed).
• BinaryMatrix.dimensions() returns a list of 2 elements [m, n], which means the matrix is m * n.

Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer.  Also, any solutions that attempt to circumvent the judge will result in disqualification.

For custom testing purposes you’re given the binary matrix mat as input in the following four examples. You will not have access the binary matrix directly.

Example 1:

Input: mat = [[0,0],[1,1]]
Output: 0


Example 2:

Input: mat = [[0,0],[0,1]]
Output: 1


Example 3:

Input: mat = [[0,0],[0,0]]
Output: -1

Example 4:

Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1


Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 100
• mat[i][j] is either 0 or 1.
• mat[i] is sorted in a non-decreasing way.

class Solution {
public:
int LeftMost(BinaryMatrix &binaryMatrix, int row, int m, int n) {
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
int midv = binaryMatrix.get(row, mid);
if (midv == 0)l = mid + 1;
else r = mid - 1;
}
return r + 1;
}
int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
vector<int> dim = binaryMatrix.dimensions();
int m = dim[0], n = dim[1];
int ans = n;
for (int i = 0; i < m; ++i) {
ans = min(ans, LeftMost(binaryMatrix, i, m, n));
}
if (ans == n)return -1;
else return ans;
}
};

hint还提示了另一种解法，从矩阵的右上角开始，遇到0则往下走，遇到1则往左走。因为如果是1的话，至少当前所在列是包含1的，也许还可以再往左试探一下，而如果是0的话，只能往下走了。这种方法极端情况下可能从矩阵的右上角走到左下角，时间复杂度为O(m+n)。完整代码如下：

class Solution {
public:

int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
vector<int> dim = binaryMatrix.dimensions();
int m = dim[0], n = dim[1];
int x = 0, y = n - 1;
int ans = n;
while (x < m&&y >= 0) {
int val = binaryMatrix.get(x, y);
if (val == 0)++x;
else if (val == 1) {
ans = y;
if (y - 1 >= 0 && binaryMatrix.get(x, y - 1) == 1) {
--y;
ans = y;
}
else ++x;
}
}
if (ans == n)return -1;
else return ans;
}
};


# LCP 08. 剧情触发时间

LCP 08. 剧情触发时间

• 1 <= increase.length <= 10000
• 1 <= requirements.length <= 100000
• 0 <= increase[i] <= 10
• 0 <= requirements[i] <= 100000

class Solution {
public:
vector<int> getTriggerTime(vector<vector<int>>& increase, vector<vector<int>>& requirements) {
int m = increase.size(), n = requirements.size();
vector<int> cs(m + 1, 0), rs(m + 1, 0), hs(m + 1, 0);

for (int i = 0; i < m; ++i) {
cs[i + 1] = cs[i] + increase[i][0];
rs[i + 1] = rs[i] + increase[i][1];
hs[i + 1] = hs[i] + increase[i][2];
}

vector<int> ans(n, -1);

for (int i = 0; i < n; ++i) {
int minc = lower_bound(cs.begin(), cs.end(), requirements[i][0]) - cs.begin();
int minr = lower_bound(rs.begin(), rs.end(), requirements[i][1]) - rs.begin();
int minh = lower_bound(hs.begin(), hs.end(), requirements[i][2]) - hs.begin();
int cur = max(max(minc, minr), minh);
if (cur <= m)ans[i] = cur;
}

return ans;
}
};

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

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

# 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 Minimum Size Subarray Sum

209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums)
{
int n = nums.size(), left = 0, right = 0, sum = 0, ans = INT_MAX;
while (right < n) {
while (right < n && sum < s)
sum += nums[right++];
while (left <= right && sum >= s) {
ans = min(ans, right – left);
sum -= nums[left++];
}
}
return ans == INT_MAX ? 0 : ans;
}
};

class Solution {
private:
int searchRight(vector<int>& accuSum, int l, int r, int target)
{
while (l <= r) {
int m = l + (r – l) / 2;
if (accuSum[m] == target)
return m;
else if (accuSum[m] > target)
r = m – 1;
else
l = m + 1;
}
return l;
}
public:
int minSubArrayLen(int s, vector<int>& nums)
{
int n = nums.size(), ans = INT_MAX;
vector<int> accuSum(n + 1, 0);
for (int i = 1; i <= n; ++i)
accuSum[i] = accuSum[i – 1] + nums[i – 1];
for (int left = 0; left < n; ++left) {
int right = searchRight(accuSum, left, accuSum.size() – 1, accuSum[left] + s);
if (right == n + 1)
break;
ans = min(ans, right – left);
}
return ans == INT_MAX ? 0 : ans;
}
};

# LeetCode Kth Smallest Element in a Sorted Matrix

378. Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
[ 1,  5,  9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,

return 13.


Note:
You may assume k is always valid, 1 ≤ k ≤ n2.

class Solution {
private:
struct Node {
int val, row, col;
Node(int v = 0, int r = 0, int c = 0)
: val(v)
, row(r)
, col(c){};
friend bool operator<(const Node& n1, const Node& n2) { return n1.val > n2.val; }
};
public:
int kthSmallest(vector<vector<int> >& matrix, int k)
{
int n = matrix.size();
priority_queue<Node> pn;
for (int i = 0; i < n; ++i)
pn.push(Node(matrix[i][0], i, 0));
Node t;
while (k–) {
t = pn.top();
pn.pop();
if (t.col < n – 1)
pn.push(Node(matrix[t.row][t.col + 1], t.row, t.col + 1));
}
return t.val;
}
};

class Solution {
public:
int kthSmallest(vector<vector<int> >& matrix, int k)
{
int n = matrix.size(), left = matrix[0][0], right = matrix[n – 1][n – 1];
while (left <= right) {
int mid = left + (right – left) / 2;
int cnt = 0;
for (int i = 0; i < n; ++i) {
cnt += upper_bound(matrix[i].begin(), matrix[i].end(), mid) – matrix[i].begin();
}
if (cnt < k)
left = mid + 1;
else
right = mid – 1;
}
return left;
}
};

class Solution {
private:
int count_less_equal(vector<vector<int> >& matrix, int num)
{
int n = matrix.size(), i = n – 1, j = 0, cnt = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] <= num) {
cnt += i + 1;
++j;
}
else
–i;
}
return cnt;
}
public:
int kthSmallest(vector<vector<int> >& matrix, int k)
{
int n = matrix.size(), left = matrix[0][0], right = matrix[n – 1][n – 1];
while (left <= right) {
int mid = left + (right – left) / 2;
int cnt = count_less_equal(matrix, mid);
if (cnt < k)
left = mid + 1;
else
right = mid – 1;
}
return left;
}
};

# 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.
Input: [1,2,3],[2]

Input: [1,2,3,4],[1,4]
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.