二分专题
704. 二分查找
给定一个 n
个元素有序的(升序)整型数组
nums
和一个目标值 target
,写一个函数搜索
nums
中的
target
,如果目标值存在返回下标,否则返回
-1
。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示:
- 你可以假设
nums
中的所有元素是不重复的。 n
将在[1, 10000]
之间。nums
的每个元素都将在[-9999, 9999]
之间。
Code
240301
class Solution {
public:
int search(vector<int>& nums, int target) {
auto it=lower_bound(nums.begin(),nums.end(),target);
if(it!=nums.end() && *it==target){
int len=it-nums.begin();
return len;
}else return -1;
}
};
35. 搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n)
的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums
为 无重复元素 的 升序 排列数组-104 <= target <= 104
Code
240301
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
auto it=lower_bound(nums.begin(),nums.end(),target);
int len=it-nums.begin();
return len;
}
};
744. 寻找比目标字母大的最小字母
给你一个字符数组
letters
,该数组按非递减顺序排序,以及一个字符
target
。letters
里至少有两个不同的字符。
返回 letters
中大于 target
的最小的字符。如果不存在这样的字符,则返回 letters
的第一个字符。
示例 1:
输入: letters = ["c", "f", "j"],target = "a"
输出: "c"
解释:letters 中字典上比 'a' 大的最小字符是 'c'。
示例 2:
输入: letters = ["c","f","j"], target = "c"
输出: "f"
解释:letters 中字典顺序上大于 'c' 的最小字符是 'f'。
示例 3:
输入: letters = ["x","x","y","y"], target = "z"
输出: "x"
解释:letters 中没有一个字符在字典上大于 'z',所以我们返回 letters[0]。
提示:
2 <= letters.length <= 104
letters[i]
是一个小写字母letters
按非递减顺序排序letters
最少包含两个不同的字母target
是一个小写字母
Code
240301
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
auto it=upper_bound(letters.begin(),letters.end(),target);
if(it!=letters.end()) return *it;
else return letters.front();
}
};
33. 搜索旋转排序数组
整数数组 nums
按升序排列,数组中的值
互不相同 。
在传递给函数之前,nums
在预先未知的某个下标
k
(0 <= k < nums.length
)上进行了
旋转,使数组变为
[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(下标
从 0 开始 计数)。例如, [0,1,2,4,5,6,7]
在下标 3
处经旋转后可能变为 [4,5,6,7,0,1,2]
。
给你 旋转后 的数组 nums
和一个整数
target
,如果 nums
中存在这个目标值
target
,则返回它的下标,否则返回 -1
。
你必须设计一个时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
示例 2:
输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
示例 3:
输入:nums = [1], target = 0
输出:-1
提示:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums
中的每个值都 独一无二- 题目数据保证
nums
在预先未知的某个下标上进行了旋转 -104 <= target <= 104
Code
240301
class Solution {
public:
vector<int> num;
int tar;
int left(int begin,int end){
if(begin>end) return -1;
int mid=(begin+end)/2;
if(num[mid]==tar) return mid;
if(num[mid]>tar) return left(begin,mid-1);
if(num[mid]<num[0]) return left(begin,mid-1);
return left(mid+1,end);
}
int right(int begin,int end){
if(begin>end) return -1;
int mid=(begin+end)/2;
if(num[mid]==tar) return mid;
if(num[mid]<tar) return right(mid+1,end);
if(num[mid]>num.back()) return right(mid+1,end);
return right(begin,mid-1);
}
int search(vector<int>& nums, int target) {
num=nums;
tar=target;
int n=nums.size();
if(nums.back()<target) return left(0,n-1);
else return right(0,n-1);
}
};
153. 寻找旋转排序数组中的最小值
已知一个长度为 n
的数组,预先按照升序排列,经由
1
到 n
次 旋转
后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7]
在变化后可能得到:
- 若旋转
4
次,则可以得到[4,5,6,7,0,1,2]
- 若旋转
7
次,则可以得到[0,1,2,4,5,6,7]
注意,数组 [a[0], a[1], a[2], ..., a[n-1]]
旋转一次 的结果为数组
[a[n-1], a[0], a[1], a[2], ..., a[n-2]]
。
给你一个元素值 互不相同 的数组 nums
,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的
最小元素 。
你必须设计一个时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。
示例 2:
输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 3 次得到输入数组。
示例 3:
输入:nums = [11,13,15,17]
输出:11
解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。
提示:
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums
中的所有整数 互不相同nums
原来是一个升序排序的数组,并进行了1
至n
次旋转
Code
240301
class Solution {
public:
vector<int> num;
int find(int begin,int end){
if(begin==end) return begin;
int mid=(begin+end)/2;
if(num[mid]>num.back()) return find(mid+1,end);
// if(num[mid]<num.front())
return find(begin,mid);
}
int findMin(vector<int>& nums) {
if(nums.front()<nums.back()) return nums.front();
num=nums;
return nums[find(0,nums.size()-1)];
}
};
154. 寻找旋转排序数组中的最小值 II
已知一个长度为 n
的数组,预先按照升序排列,经由
1
到 n
次 旋转
后,得到输入数组。例如,原数组 nums = [0,1,4,4,5,6,7]
在变化后可能得到:
- 若旋转
4
次,则可以得到[4,5,6,7,0,1,4]
- 若旋转
7
次,则可以得到[0,1,4,4,5,6,7]
注意,数组 [a[0], a[1], a[2], ..., a[n-1]]
旋转一次 的结果为数组
[a[n-1], a[0], a[1], a[2], ..., a[n-2]]
。
给你一个可能存在 重复 元素值的数组 nums
,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的
最小元素 。
你必须尽可能减少整个过程的操作步骤。
示例 1:
输入:nums = [1,3,5]
输出:1
示例 2:
输入:nums = [2,2,2,0,1]
输出:0
提示:
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums
原来是一个升序排序的数组,并进行了1
至n
次旋转
进阶:这道题与 寻找旋转排序数组中的最小值
类似,但 nums
可能包含重复元素。允许重复会影响算法的时间复杂度吗?会如何影响,为什么?
Code1
240301
class Solution {
public:
int find(vector<int>& nums,int begin,int end){
cout<<"begin="<<begin<<",end="<<end<<endl;
if(begin>end) return -1;
if(begin==end) return begin;
int mid=(begin+end)/2;
cout<<"mid="<<mid<<endl;
if(nums[mid]>nums.front()) return find(nums,mid+1,end);
else if(nums[mid]<nums.front()) return find(nums,begin,mid);
else{
cout<<"##"<<endl;
int temp1=find(nums,begin,mid-1);
int temp2=find(nums,mid+1,end);
cout<<"temp1="<<temp1<<",temp2="<<temp2<<endl;
if(temp1==-1 && temp2==-1) return -1;
if(temp1==-1) return temp2;
if(temp2==-1) return temp1;
return (nums[temp1]<nums[temp2])?temp1:temp2;
// if(temp1!=-1) return temp1;
// else return temp2;
}
}
int findMin(vector<int>& nums) {
if(nums.front()<nums.back()) return nums.front();
int begin=0,end=nums.size()-1;
if(nums.front()>nums.back()){
while(begin<end){
int mid=(begin+end)/2;
if(nums[mid]>=nums.front()){
begin=mid+1;
}else if(nums[mid]<=nums.back()){
end=mid;
}
cout<<"begin="<<begin<<",end="<<end<<endl;
}
}else{
begin=find(nums,begin,end);
}
return nums[begin];
}
};
Code2
240302
class Solution {
public:
int findMin(vector<int>& nums) {
if(nums.front()<nums.back()) return nums.front();
int begin=0,end=nums.size()-1;
while(begin<end){
int mid=(begin+end)/2;
if(nums[mid]<nums[end]){
end=mid;
}else if(nums[mid]>nums[end]){
begin=mid+1;
}else{
end--;
}
}
return nums[begin];
}
};
74. 搜索二维矩阵
给你一个满足下述两条属性的 m x n
整数矩阵:
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target
,如果 target
在矩阵中,返回 true
;否则,返回 false
。
示例 1:
![img](https://assets.leetcode.com/uploads/2020/10/05/mat.jpg)
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true
示例 2:
![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/25/mat2.jpg)
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出:false
提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
Code
240302
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int begin=0,end=matrix.size()-1;
while(begin<end){
cout<<"begin="<<begin<<",end="<<end<<endl;
int mid=(begin+end+1)/2;
if(matrix[mid][0]>target) end=mid-1;
else if(matrix[mid][0]<=target) begin=mid;
}
int row=begin;
cout<<"row="<<row<<endl;
begin=0,end=matrix[row].size()-1;
while(begin<end){
cout<<"begin="<<begin<<",end="<<end<<endl;
int mid=(begin+end+1)/2;
if(matrix[row][mid]>target) end=mid-1;
else if(matrix[row][mid]<=target) begin=mid;
}
return target==matrix[row][begin];
}
};
代码
测试用例
测试用例
测试结果
已解答
中等
相关标签
相关企业
提示
给你一个整数数组 citations
,其中
citations[i]
表示研究者的第 i
篇论文被引用的次数,citations
已经按照
升序排列 。计算并返回该研究者的 h 指数。
h
指数的定义:h 代表“高引用次数”(high citations),一名科研人员的
h
指数是指他(她)的 (n
篇论文中)至少 有 h
篇论文分别被引用了至少 h
次。
请你设计并实现对数时间复杂度的算法解决此问题。
示例 1:
输入:citations = [0,1,3,5,6]
输出:3
解释:给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
由于研究者有3篇论文每篇 至少 被引用了 3 次,其余两篇论文每篇被引用 不多于 3 次,所以她的 h 指数是 3 。
示例 2:
输入:citations = [1,2,100]
输出:2
提示:
n == citations.length
1 <= n <= 105
0 <= citations[i] <= 1000
citations
按 升序排列
Code
240302
class Solution {
public:
int hIndex(vector<int>& citations) {
int n=citations.size();
// if(n==1 && citations[0]==0) return 0;
int begin=0,end=n-1;
while(begin<end){
cout<<"begin="<<begin<<",end="<<end<<endl;
int mid=begin+(end-begin)/2;
if(citations[mid]>=n-mid) end=mid;
else begin=mid+1;
}
if(n-begin<=citations[begin]) return n-begin;
return 0;
}
};
540. 有序数组中的单一元素
给你一个仅由整数组成的有序数组,其中每个元素都会出现两次,唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n)
时间复杂度和
O(1)
空间复杂度。
示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: nums = [3,3,7,7,10,11,11]
输出: 10
提示:
1 <= nums.length <= 105
0 <= nums[i] <= 105
Code
230302
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int n=nums.size();
int begin=0,end=n-1;
while(begin<end){
cout<<begin<<" "<<end<<endl;
int mid=begin+(end-begin)/2;
if(nums[mid+1]==nums[mid]){
if(mid%2==0) begin=mid+2;
else end=mid-1;
}else if(nums[mid-1]==nums[mid]){
if((mid-1)%2==0) begin=mid+1;
else end=mid-2;
}else begin=end=mid;
}
return nums[begin];
}
};
852. 山脉数组的峰顶索引
符合下列属性的数组 arr
称为 山脉数组
:
arr.length >= 3
存在
i
(
0 < i < arr.length - 1
)使得:
arr[0] < arr[1] < ... arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给你由整数组成的山脉数组 arr
,返回满足
arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
的下标 i
。
你必须设计并实现时间复杂度为 O(log(n))
的解决方案。
示例 1:
输入:arr = [0,1,0]
输出:1
示例 2:
输入:arr = [0,2,1,0]
输出:1
示例 3:
输入:arr = [0,10,5,2]
输出:1
提示:
3 <= arr.length <= 105
0 <= arr[i] <= 106
- 题目数据保证
arr
是一个山脉数组
Code
240302
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int n=arr.size();
int begin=0,end=n-1;
while(begin<end){
int mid=(begin+end)/2;
if(arr[mid]>arr[mid+1] && arr[mid]>arr[mid-1]) begin=end=mid;
else if(arr[mid]>arr[mid+1]) end=mid;
else begin=mid;
}
return begin;
}
};
658. 找到 K 个最接近的元素
给定一个 排序好 的数组 arr
,两个整数
k
和 x
,从数组中找到最靠近
x
(两数之差最小)的 k
个数。返回的结果必须要是按升序排好的。
整数 a
比整数 b
更接近 x
需要满足:
|a - x| < |b - x|
或者|a - x| == |b - x|
且a < b
示例 1:
输入:arr = [1,2,3,4,5], k = 4, x = 3
输出:[1,2,3,4]
示例 2:
输入:arr = [1,2,3,4,5], k = 4, x = -1
输出:[1,2,3,4]
提示:
1 <= k <= arr.length
1 <= arr.length <= 104
arr
按 升序 排列-104 <= arr[i], x <= 104
Code
230302
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int n=arr.size();
int begin=0,end=n-1;
while(begin<end){
int mid=(begin+end)/2;
if(arr[mid]==x) begin=end=mid;
else if(arr[mid]<x) begin=mid+1;
else end=mid;
}
vector<int> v;
int left=begin-1,right=begin;
while(k && right<n && left>=0){
if(x-arr[left]>arr[right]-x) v.push_back(arr[right++]);
else v.push_back(arr[left--]);
k--;
}
while(k && left>=0){
v.push_back(arr[left--]);
k--;
}
while(k && right<n){
v.push_back(arr[right++]);
k--;
}
sort(v.begin(),v.end());
return v;
}
};
611. 有效三角形的个数
给定一个包含非负整数的数组 nums
,返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
示例 2:
输入: nums = [4,2,3,4]
输出: 4
提示:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
Code
230302
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(),nums.end());
int sum=0;
for(auto i=nums.begin();i<nums.end();i++){
for(auto j=i+1;j<nums.end();j++){
auto it_begin=upper_bound(i+1,j,*j-*i);
sum+=j-it_begin;
}
}
return sum;
}
};
2300. 咒语和药水的成功对数
给你两个正整数数组 spells
和 potions
,长度分别为 n
和 m
,其中
spells[i]
表示第 i
个咒语的能量强度,potions[j]
表示第 j
瓶药水的能量强度。
同时给你一个整数 success
。一个咒语和药水的能量强度
相乘 如果 大于等于
success
,那么它们视为一对 成功
的组合。
请你返回一个长度为 n
的整数数组 pairs
,其中
pairs[i]
是能跟第 i
个咒语成功组合的
药水 数目。
示例 1:
输入:spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出:[4,0,3]
解释:
- 第 0 个咒语:5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
- 第 1 个咒语:1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
- 第 2 个咒语:3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
所以返回 [4,0,3] 。
示例 2:
输入:spells = [3,1,2], potions = [8,5,8], success = 16
输出:[2,0,2]
解释:
- 第 0 个咒语:3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
- 第 1 个咒语:1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
- 第 2 个咒语:2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
所以返回 [2,0,2] 。
提示:
n == spells.length
m == potions.length
1 <= n, m <= 105
1 <= spells[i], potions[i] <= 105
1 <= success <= 1010
Code
240302
class Solution {
public:
vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success){
int n=spells.size();
int m=potions.size();
sort(potions.begin(),potions.end());
vector<int> v(n);
for(int i=0;i<n;i++){
int begin=0,end=m-1;
while(begin<end){
int mid=begin+(end-begin)/2;
if((long long)spells[i]*potions[mid]<success) begin=mid+1;
else end=mid;
}
if((long long)spells[i]*potions[begin]<success) v[i]=0;
else v[i]=m-begin;
}
return v;
}
};
1498. 满足条件的子序列数目
已解答
中等
相关标签
相关企业
提示
给你一个整数数组 nums
和一个整数 target
。
请你统计并返回 nums
中能满足其最小元素与最大元素的
和 小于或等于 target
的
非空 子序列的数目。
由于答案可能很大,请将结果对 109 + 7
取余后返回。
示例 1:
输入:nums = [3,5,6,7], target = 9
输出:4
解释:有 4 个子序列满足该条件。
[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)
示例 2:
输入:nums = [3,3,6,8], target = 10
输出:6
解释:有 6 个子序列满足该条件。(nums 中可以有重复数字)
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]
示例 3:
输入:nums = [2,3,3,4,6,7], target = 12
输出:61
解释:共有 63 个非空子序列,其中 2 个不满足条件([6,7], [7])
有效序列总数为(63 - 2 = 61)
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 106
1 <= target <= 106
Code
230303
class Solution {
public:
const int MOD=1000000007;
// 快速幂
// unordered_map<int,int> ump;
// int fastPow(int exp){
// int result=1;
// int base=2;
// while(exp>0){
// if (exp & 1) result = (long long)result * base % MOD;
// base = (long long)base * base % MOD;
// exp >>= 1;
// }
// return result;
// }
int numSubseq(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
vector<int> powers(nums.size(),1);
for(int i=1;i<nums.size();i++){
powers[i]=(powers[i-1]*2)%MOD;
}
int sum=0;
for(auto i=nums.begin();i!=nums.end();i++){
if(target<=*i) break;
auto it=upper_bound(nums.begin(),i,target-*i);
// int len=min(it-nums.begin(),i-nums.begin());
sum=(sum+powers[i-nums.begin()]-powers[i-it])%MOD;
// for(auto j=nums.begin();j<min(it,i);j++){
// sum=(sum+powers[i-j-1])%MOD;
// // 快速幂
// // if(!ump[i-j-1]) ump[i-j-1]=fastPow(i-j-1);
// // sum=(sum+ump[i-j-1])%MOD;
// }
if(*i*2<=target) sum++;
// Old Version(WA)
// it--;
// cout<<endl;
// cout<<i-nums.begin()<<endl;
// if(*i*2>target) while(it>=nums.begin()){
// sum=(sum+(int)pow(2,i-it)-1)%1000000007;
// cout<<(int)pow(2,i-it)-1<<endl;
// it--;
// }else while(it>=nums.begin()){
// sum=(sum+(int)pow(2,i-it))%1000000007;
// cout<<(int)pow(2,i-it)<<endl;
// it--;
// }
}
if(sum<0)sum+=MOD;
return sum%MOD;
}
};
34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums
,和一个目标值
target
。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回
[-1, -1]
。
你必须设计并实现时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0
输出:[-1,-1]
提示:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums
是一个非递减数组-109 <= target <= 109
Code1
240324
传统写法
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n=nums.size();
if(n==0) return vector<int>{-1,-1};
int res_l,res_r;
int left=0,right=n-1;
while(left<right){
int mid=left+(right-left)/2;
if(nums[mid]<target) left=mid+1;
else right=mid;
}
if(nums[left]==target) res_l=left;
else return vector<int>{-1,-1};
left=0,right=n-1;
while(left<right){
int mid=left+(right-left+1)/2;
if(nums[mid]>target) right=mid-1;
else left=mid;
}
res_r=left;
return vector<int>{res_l,res_r};
}
};
Code2
240324
用了STL
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size()==0) return vector<int>{-1,-1};
int res_l,res_r;
auto it=lower_bound(nums.begin(),nums.end(),target);
if(it==nums.end() || *it!=target) return vector<int>{-1,-1};
res_l=it-nums.begin();
it=upper_bound(it,nums.end(),target);
res_r=it-nums.begin()-1;
return vector<int>{res_l,res_r};
}
};
69. x 的平方根
给你一个非负整数 x
,计算并返回 x
的
算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如
pow(x, 0.5)
或者 x ** 0.5
。
示例 1:
输入:x = 4
输出:2
示例 2:
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
提示:
0 <= x <= 231 - 1
Code
240324
class Solution {
public:
int mySqrt(int x) {
long long left=0,right=x;
while(left<right){
long long mid=left+(right-left+1)/2;
if(mid*mid>x) right=mid-1;
else left=mid;
}
return (int)left;
}
};
81. 搜索旋转排序数组 II
已知存在一个按非降序排列的整数数组 nums
,数组中的值不必互不相同。
在传递给函数之前,nums
在预先未知的某个下标
k
(0 <= k < nums.length
)上进行了
旋转 ,使数组变为
[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(下标
从 0 开始 计数)。例如,
[0,1,2,4,4,4,5,6,6,7]
在下标 5
处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4]
。
给你 旋转后 的数组 nums
和一个整数
target
,请你编写一个函数来判断给定的目标值是否存在于数组中。如果
nums
中存在这个目标值 target
,则返回
true
,否则返回 false
。
你必须尽可能减少整个操作步骤。
示例 1:
输入:nums = [2,5,6,0,0,1,2], target = 0
输出:true
示例 2:
输入:nums = [2,5,6,0,0,1,2], target = 3
输出:false
提示:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
- 题目数据保证
nums
在预先未知的某个下标上进行了旋转 -104 <= target <= 104
进阶:
- 这是 搜索旋转排序数组
的延伸题目,本题中的
nums
可能包含重复元素。 - 这会影响到程序的时间复杂度吗?会有怎样的影响,为什么?
Code
240324
class Solution {
public:
bool search(vector<int>& nums, int target) {
if(nums.size()==0) return false;
if(nums.size()==1) return nums.front()==target;
if(nums.front()==target) return true;
if(nums.front()==nums.back()){
while(nums.size() && nums.back()==nums.front()) nums.pop_back();
if(!nums.size()) return false;
}
// if(nums.back()==target) return true;
int left=0,right=nums.size()-1;
if(target>=nums[left])
while(left<=right){
cout<<"1:"<<left<<","<<right<<"\n";
int mid=(left+right)/2;
if(nums[mid]==target) return true;
else if(nums[mid]<nums.front()) right=mid-1;
else if(nums[mid]>target) right=mid-1;
else left=mid+1;
}else while(left<=right){
cout<<"2:"<<left<<","<<right<<"\n";
int mid=left+(right-left)/2;
if(nums[mid]==target) return true;
else if(nums[mid]>nums.back()) left=mid+1;
else if(nums[mid]<target) left=mid+1;
else right=mid-1;
}
return false;
}
};
162. 寻找峰值
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组
nums
,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回
任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞
。
你必须实现时间复杂度为 O(log n)
的算法来解决此问题。
示例 1:
输入:nums = [1,2,3,1]
输出:2
解释:3 是峰值元素,你的函数应该返回其索引 2。
示例 2:
输入:nums = [1,2,1,3,5,6,4]
输出:1 或 5
解释:你的函数可以返回索引 1,其峰值元素为 2;
或者返回索引 5, 其峰值元素为 6。
提示:
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
- 对于所有有效的
i
都有nums[i] != nums[i + 1]
Code1
240324
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int Max=INT_MIN,Max_index=0;
for(int i=0;i<nums.size();i++){
if(nums[i]>Max){
Max=nums[i];
Max_index=i;
}
}
return Max_index;
}
};
Code2
240324
这个二分的速度居然没有直接遍历快
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int n=nums.size();
if(n==1) return 0;
if(n==2) return (nums[0]>nums[1])?0:1;
int left=0,right=n-1;
while(left<=right){
int mid=(left+right)/2;
cout<<left<<","<<right<<"\n";
if(mid==0){
if(nums[0]>nums[1]) return 0;
else left++;
}else if(mid==n-1){
if(nums[n-1]>nums[n-2]) return n-1;
else right--;
}else{
if(nums[mid-1]>nums[mid] && nums[mid]>nums[mid+1]) right=mid-1;
else if(nums[mid-1]<nums[mid] && nums[mid]>nums[mid+1]) return mid;
else if(nums[mid-1]<nums[mid] && nums[mid]<nums[mid+1]) left=mid+1;
else left=mid+1;
}
}
return -1;
}
};
167. 两数之和 II - 输入有序数组
给你一个下标从 1 开始的整数数组 numbers
,该数组已按 非递减顺序排列
,请你从数组中找出满足相加之和等于目标数 target
的两个数。如果设这两个数分别是 numbers[index1]
和
numbers[index2]
,则
1 <= index1 < index2 <= numbers.length
。
以长度为 2 的整数数组 [index1, index2]
的形式返回这两个整数的下标 index1
和
index2
。
你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1:
输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2:
输入:numbers = [2,3,4], target = 6
输出:[1,3]
解释:2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3:
输入:numbers = [-1,0], target = -1
输出:[1,2]
解释:-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
提示:
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers
按 非递减顺序 排列-1000 <= target <= 1000
- 仅存在一个有效答案
Code
240324
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int n=numbers.size();
for(int i=0;i<n;i++){
auto it=upper_bound(numbers.begin(),numbers.end(),target-numbers[i])-1;
if(*it+numbers[i]==target && it-numbers.begin()!=i) return vector<int>{i+1,(int)(it-numbers.begin())+1};
}
return vector<int>{-1,-1};
}
};
209. 长度最小的子数组
给定一个含有 n
个正整数的数组和一个正整数
target
。
找出该数组中满足其总和大于等于 target
的长度最小的
连续
子数组
[numsl, numsl+1, ..., numsr-1, numsr]
,并返回其长度。如果不存在符合条件的子数组,返回
0
。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2:
输入:target = 4, nums = [1,4,4]
输出:1
示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0
提示:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
进阶:
- 如果你已经实现
O(n)
时间复杂度的解法, 请尝试设计一个O(n log(n))
时间复杂度的解法。
Code
240324
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n=nums.size();
vector<int> prefix_sum(n+1);
for(int i=1;i<=n;i++){
prefix_sum[i]=prefix_sum[i-1]+nums[i-1];
}
long minLen=INT_MAX;
for(int i=0;i<=n;i++){
auto it=lower_bound(prefix_sum.begin(),prefix_sum.end(),target+prefix_sum[i]);
if(it!=prefix_sum.end()){
minLen=min(minLen,it-prefix_sum.begin()-i);
}
}
return (minLen==INT_MAX)?0:minLen;
}
};
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n=nums.size();
for(int i=1;i<n;i++){
nums[i]+=nums[i-1];
}
auto it=lower_bound(nums.begin(),nums.end(),target);
if(it==nums.end()) return 0;
long minLen=it-nums.begin()+1;
for(int i=0;i<n;i++){
it=lower_bound(nums.begin()+i,nums.end(),target+nums[i]);
if(it==nums.end()) break;
minLen=min(minLen,it-nums.begin()-i);
}
return minLen;
}
};
222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root
,求出该树的节点个数。
完全二叉树
的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第
h
层,则该层包含 1~ 2h
个节点。
示例 1:
![img](https://assets.leetcode.com/uploads/2021/01/14/complete.jpg)
输入:root = [1,2,3,4,5,6]
输出:6
示例 2:
输入:root = []
输出:0
示例 3:
输入:root = [1]
输出:1
提示:
- 树中节点的数目范围是
[0, 5 * 104]
0 <= Node.val <= 5 * 104
- 题目数据保证输入的树是 完全二叉树
进阶:遍历树来统计节点是一种时间复杂度为
O(n)
的简单解决方案。你可以设计一个更快的算法吗?
Code
240325
class Solution {
public:
int countNodes(TreeNode* root) {
if(root==NULL) return 0;
int depth=1;
TreeNode* cur=root;
while(cur->left){
cur=cur->left;
depth++;
}
// cout<<depth<<"\n";
int left=1<<(depth-1),right=(1<<depth)-1;
while(left<right){
// cout<<"\n"<<left<<","<<right<<"\n\n";
int mid=(left+right+1)/2;
cur=root;
for(int i=2;i<depth;i++){
// cout<<depth-i<<","<<((mid>>(depth-i))&1)<<"\n";
if((mid>>(depth-i))&1){
cur=cur->right;
}else{
cur=cur->left;
}
}
if((mid&1)==1 && cur->right) left=mid;
else if((mid&1)==0 && cur->left) left=mid;
else right=mid-1;
}
return left;
}
};
34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums
,和一个目标值
target
。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回
[-1, -1]
。
你必须设计并实现时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0
输出:[-1,-1]
提示:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums
是一个非递减数组-109 <= target <= 109
Code
240716
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res={-1,-1};
int size=nums.size();
if(size==0) return res;
if(size==1){
if(nums[0]==target){
return {0,0};
}else{
return res;
}
}
int l=0,r=size-1,m;
while(l<r){
m=(l+r+1)>>1;
if(nums[m]>=target) r=m-1;
else l=m;
}
if(nums[l]==target) res[0]=l;
else if(l+1<size && nums[l+1]==target) res[0]=l+1;
else return res;
l=0,r=size-1;
while(l<r){
m=(l+r)>>1;
if(nums[m]<=target) l=m+1;
else r=m;
}
if(nums[l]==target) res[1]=l;
else res[1]=l-1;
return res;
}
};