69.x的平方根
给你一个非负整数 x
,计算并返回 x
的 算术平方根 。由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5)
或者 x ** 0.5
。
示例 1:
输入:x = 4 输出:2示例 2:
输入:x = 8 输出:2 解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
解题思路:
① 第一种就是暴力解法,因为 x 开方之后的值肯定是小于等于其本身的,所以定义一个变量 i 让它从 0~i 遍历并比较i*i 和 x 的大小,注意返回的值是 i 还是 i+1 。代码如下
class Solution {
public:
int mySqrt(int x) {
//这里使用long long int是防止i*i的计算结果产生溢出
long long int i ;
//这样解法的复杂度是O(根号x)
while((i*i) <= x){
i++ ;
}
return i-1 ;
}
};
② 第二种是二分查找法,二分查找的下界设置为 0 ,上界设置为 x ,定义一个中间变量 mid ,然后将 mid 做如下定义,这样定义的目的是防止越界,如果直接定义为 (right + left) / 2 在计算过程中,(right + left) 的结果可能会超出 int 所能表达的最大数字。
int mid = left + (right - left) / 2 ;
当然可以直接将 min 定义成 long long int 型,个人感觉这样更好一点,后面计算 mid * mid 的时候也不用在前面加上 long long 了。代码如下:
class Solution {
public:
int mySqrt(int x) {
int left = 0 ;
int right = x ;
int ans = -1 ;
while(left<=right){
long long int mid = left + (right - left) / 2 ;
if(mid * mid == x){
ans = mid ;
break ;//没有break就会超时,因为这里后面的语句没有执行也就没有更新left和right
}else if(mid * mid > x){
right = mid-1 ;
}else{
left = mid+1 ;
ans = mid;
}
}
return ans ;
}
};
③ 官方题解中还有一个牛顿迭代法,大概看了一下,涉及了函数求零点问题,还要求导啥的感觉太麻烦了。正常估计也想不到要用这个方法。
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
是一个小写字母
解题思路:
① 同样可以使用二分查找,思路和上一个题目基本一模一样。
代码如下:
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int right = letters.size() - 1 ;
int left = 0;
if(target >= letters[right]){
return letters[0] ;
}
while(left < right){
int mid = (left + right) / 2 ;
if(letters[mid] > target){
//这里下标为mid的字符已经比target大了
//所以可能是目标字符也可能不是(因为不保证它是第一个比它大的)
//所以更新时不能将它直接跳过,要以它为有边界
right = mid ;
}else{
//这里为什么是mid+1,因为这里else的潜在条件是letters[mid] <= target
//而我们要找的是第一个‘大于’target的字符,所以下标为mid的字符一定不会是目标字符
//因此更新left时就可以跳过这一个,直接将mid+1作为左边界重新寻找
left = mid + 1;
}
}
return letters[left] ;
}
};
另外还有一个版本的代码,和上一个区别就是while的条件不一样了,然后right的更新情况不一样。emmm...其实感觉很费解,有点转不过来弯儿,为什么是这个样子。
【好好意会一下其实也能想通,就是不知道以后遇到了能不能想起来,哈哈】
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int right = letters.size() - 1 ;
int left = 0;
if(target >= letters[right]){
return letters[0] ;
}
while(left <= right){
int mid = (left + right) / 2 ;
if(letters[mid] > target){
right = mid - 1 ;
}else{
left = mid + 1;
}
}
return letters[left] ;
}
};
② 还有一种就是直接解咯,当然上面用二分查找法是为了练习一下这个算法,直接解就非常easy,遍历一下就完事了,毫无技巧。
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int len = letters.size() ;
int i = 0;
for( ; i<len ;i++){
if(letters[i] > target){
return letters[i] ;
}
}
return letters[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
解题思路:
① 刚开始在想这怎么用二分查找来做呢,想了一下感觉不是很友好,然后就先用自己的想法做了,每个元素都会成对出现,唯有一个数只会出现一次。那么只需要遍历下标 i 是奇数的数据,然后比较 nums[i-1] 和 nums[i] 是否相等,相等时执行 i = i + 2 ,继续遍历,不相等时就可以直接返回 nums[i-1] 了,个人感觉这个非常好理解,但是时间复杂度🤔是多少,看起来应该是不满足题目要求的。
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int len = nums.size() ;
int i ;
for(i = 1 ;i<len; i=i+2){
int key = nums[i] ;
if(nums[i-1] == nums[i]){
continue ;
}else {
return nums[i-1];
}
}
return nums[len-1] ;
}
};
问了一下GPT,时间复杂度是O(n)【我还以为是O(n/2)】。
![](https://i-blog.csdnimg.cn/direct/20c5e67cf7be42eda28077cda4510749.jpeg)
② 尝试使用二分查找,二分查找的时间复杂度是 O(log n) ,只能从数据的个数下手了【奇数偶数】,因为数据都是成对出现,单独的数据出现的时候,它前面和后面的数据个数一定是偶数个,由于下标是从 0 开始的,所以目标数据 key 的下标 i 一定是偶数!那我们就来看下标是偶数的数据。解释写在代码注释里了。
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int right = nums.size() - 1 ;
int left = 0 ;
while(left<right){
int mid = ( right + left )/2 ;
if(mid % 2 == 0){
//mid是偶数 且mid和mid+1指向的数相同,说明key还没有出现
//更新左边界,在数据的右半部分继续查找
if(nums[mid] == nums[mid+1]){
left = mid + 2 ;
}else {
//mid和mid+1指向的数不相同,说明key已经出现
//key出现之后两个相同数据的索引才会由“偶奇”变为“奇偶”
//更新右边界,在数据的左半部分继续查找
//因为要找的Key也有可能就是下标为mid的数据,故right = mid
right = mid ;
}
}else{
//mid是奇数时同理,比较“偶奇”指向的数,相同则说明key还未出现
//此时更新左边界为下一个偶数 即 mid+1
if(nums[mid-1] == nums[mid]){
left = mid + 1 ;
}else {
//若是不相同 说明key已经出现 操作同上一部分
right = mid ;
}
}
}
return nums[left] ;
}
};
278.第一个错误的版本
你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。假设你有 n
个版本 [1, 2, ..., n]
,你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用 bool isBadVersion(version)
接口来判断版本号 version
是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1:
输入:n = 5, bad = 4 输出:4 解释:调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true 所以,4 是第一个错误的版本。
示例 2:
输入:n = 1, bad = 1 输出:1提示:
1 <= bad <= n <= 231 - 1
解题思路: