intlower_bound(vector<int>& nums, int target){
int n = nums.size();
int l = -1, r = n;
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid;
}
}
return r;
}
根据题意,正确的调用函数:
classSolution {
public:
vector<int> searchRange(vector<int>& nums, int target){
// start 求得是大于等于 target 的第一个数int start = lower_bound(nums, target);
if (start == nums.size() || nums[start] != target) {
return {-1, -1};
}
// end 求得是大于 target 的左边的数int end = lower_bound(nums, target + 1) - 1;
return {start, end};
}
private:
intlower_bound(vector<int>& nums, int target){
int n = nums.size();
int l = -1, r = n;
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid;
}
}
return r;
}
};
classSolution {
public:
intsearch(vector<int>& nums, int target){
int n = nums.size();
int l = -1, r = n;
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (nums[mid] >= target) {
r = mid;
} else {
l = mid;
}
}
if (r < n && nums[r] == target) return r;
return-1;
}
};
classSolution {
public:
charnextGreatestLetter(vector<char>& letters, char target){
int n = letters.size();
int l = -1, r = n;
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (letters[mid] >= target + 1) {
r = mid;
} else {
l = mid;
}
}
return r == n ? letters[0] : letters[r];
}
};
第二种:
classSolution {
public:
charnextGreatestLetter(vector<char>& letters, char target){
int n = letters.size();
int l = -1, r = n;
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (letters[mid] <= target) {
l = mid;
} else {
r = mid;
}
}
return l == n - 1 ? letters[0] : letters[l + 1]; // 或者是把 l+1 换成 r
}
};
classSolution {
public:
intmaximumCount(vector<int>& nums){
int n1 = 0, n2 = 0;
for (int num : nums) {
if (num < 0) n1++;
if (num > 0) n2++;
}
returnmax(n1, n2);
}
};
方法二(二分):
classSolution {
public:
intmaximumCount(vector<int>& nums){
int n = nums.size();
int n1 = lower_bound(nums, 0);
int n2 = lower_bound(nums, -1);
returnmax(n - n1, n2);
}
private:
intlower_bound(vector<int>& nums, int target){
int l = -1, r = nums.size();
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (nums[mid] > target) r = mid;
else l = mid;
}
return r;
}
};
1170. 比较字符串中最小字母的出现频次(medium)
定义一个函数 f(s),统计 s 中(按字典序比较)最小字母的出现频次,其中 s 是一个非空字符串。
例如,若 s = 'dcce',那么 f(s) = 2,因为字典序最小字母是'c',它出现了 2 次。
现在,给你两个字符串数组待查表 queries 和词汇表 words。对于每次查询 queries[i],需统计 words 中满足 f(queries[i]) < f(W) 的词的数目,W 表示词汇表 words 中的每个词。