【剑指offer】搜索篇-含题目代码思路解析
【剑指offer】搜索篇-含题目代码思路解析
1.JZ53 数字在升序数组中出现的次数
在这里插入图片描述
C++【二分法】
class Solution {
public:
int bisearch(vector<int>& data,float k){
int left=0;
int right=data.size()-1;
while(left<=right){
int mid=(left+right)/2;
if(data[mid]<k){
left=mid+1;
}else if(data[mid]>k){
right=mid-1;
}
}
return left;
}
int GetNumberOfK(vector<int> data ,int k) {
return bisearch(data,k+0.5)-bisearch(data, k-0.5);
}
};注意
在这里插入图片描述
在这里插入图片描述
2.JZ4 二维数组中的查找
在这里插入图片描述
C++【二分】
class Solution {
public:
bool binary_search(int target,vector<int>array){
int left=0;
int right=array.size()-1;
while(left<=right){
int mid=(left+right)/2;
if(array[mid] == target)return true;
else if(array[mid]<target){left=mid+1;}
else if(array[mid]>target){right=mid-1;}
}
return false;
}
bool Find(int target, vector<vector<int> > array) {
for(auto i:array){
if(binary_search(target, i))return true;
}
return false;
}
};注意
- 逐行遍历，C++11语法auto使用
int arr[] = {1, 2, 3};
for(auto i : arr) {
std::cout<< i << std::endl;
} - 二分查找函数的参数bool binary_search(int target,vectorarray) 里是单维数组，所以外面调用再加一层逐行遍历auto i:array，从而实现对二维数组的整体遍历查找。
3. JZ11 旋转数组的最小数字
在这里插入图片描述
C++
class Solution {
public:
int binary_search(vector<int> array){
int left=0;
int right=array.size()-1;
while(left<right){
int mid=(left+right)/2;
if(array[mid]>array[right]){left=mid+1;}
else if(array[mid]<array[right]){right=mid;}
else if(array[mid]==array[right]){right--;}
}
return array[right];
}
int minNumberInRotateArray(vector<int> rotateArray) {
return binary_search(rotateArray);
}
};注意
在这里插入图片描述
4. JZ38 字符串的排列
在这里插入图片描述
在这里插入图片描述
5.JZ44 数字序列中某一位的数字
在这里插入图片描述
C++
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @return int整型
*/
int findNthDigit(int n) {
int digits=1;
long long sum=9;
while(n>sum){
n-=sum;
sum=pow(10,digits-1);
digits++;
sum=9*sum;
}
int num =pow(10,digits-1)+ (n - 1) / digits;
printf("%lld hhhh",sum);
//定位n在数字的哪一位上
int index = (n - 1) % digits;
return to_string(num)[index] - '0';
}
};注意
在这里插入图片描述
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022-10-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录