一 、35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
class Solution {
public:
int searchInsert(vector& nums, int target) {
int l=0,r=nums.size()-1;
int arr=nums.size();
while(l<=r){
int mid=(l+r)>>1;
if(nums[mid]>=target){
arr=mid;
r=mid-1;
}
else {
l=mid+1;
}
}
return arr;
}
};
思路：先建立两个最左l=0 最右下标r=nums.size()-1；每次对半分 找出中间值是否大于 或者小于 target 再次对半分
直到 l>r 为止 。输出所在下标.
二 、704. 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
class Solution {
public:
int search(vector& nums, int target) {
int l=0,r=nums.size()-1;
while(l<=r){
int mid=(-l+r)/2+l;
if(nums[mid]target){
r=mid-1;
}
else return mid;
}
return -1;
}
};
思路 ：最基础的二分.
三 、剑指 Offer 53 - I. 在排序数组中查找数字 I
统计一个数字在排序数组中出现的次数。
class Solution {
public:
int search(vector& nums, int target) {
int l=0,r=nums.size()-1;
int arr=0;
while(l<=r){
int mid=(r-l)/2+l;
if(nums[mid]>=target){
arr=mid;
r=mid-1;
}
else l=mid+1;
}
int ret=0,rr=arr;
for(;rr>0;rr--){
if(nums[rr-1]==target) ret++;
else break;
}
for(;arr
思路 ：因为有序 所以直接二分找到该值 再左右查找 相等的值 并记录.
四 、400. 第 N 位数字
给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。
int findNthDigit(int n){
long long x=n,s=1;int i=0;
for(i=1;i<15;i++){
x=(long long )(x-9*i*s);
if(x<=0){
x+=9*i*s;
break;
}
s*=10;
}
long long t=(long long )(x-1)/i+s;
long long ret=0;
for(int j=(x-1)%i;j
思路：看注释 首先看懂题 例如 11 是两位数 不是一位 所以这里先判断再那个范围 并且减去 前面范围的个数 再用s统计为最小10的几次方 还剩余当前个数 再利用数学方法 每次再这个范围的数的个数都为i 所以t=(x-1)/i+s 就是第n位数字所在数字的位置 再利用余数 找到所在位置.
五、1300. 转变数组后最接近目标值的数组和
给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。
如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。
请注意，答案不一定是 arr 中的数字.
int cmp(const void* c1, const void* c2) {
return *(int*)c1 > *(int*)c2;
}
int findBestValue(int* arr, int arrSize, int target){
if(arr==NULL) return 0;
qsort(arr,arrSize,sizeof(int ),cmp);
double sum=0,n=arrSize;
for(int j=0;j0.5){
return x+1;
}
else return x;
}
sum+=arr[j];
}
return arr[arrSize-1];
}
思路 ：首先进行排序 然后 将target的值进行平均 再遍历 每次进行遍历的时候判断当前值是否大于x 如果大于 那么 x就是可行值 再输入时 先进行判断是否需要四舍五入 进行加1操作 。
当 小于的时 sum+arr[j], 并且再次将target平均（arrsize-i）次。
来自英雄哪里出来
题来自leetcode
