704.二分查找我先去查了一下什么是二分法一、一句话理解把一堆已经排好序的数据不断分成两半只在可能存在答案的那一半继续找直到找到或确定不存在。二、核心条件数据必须有序从小到大或从大到小可以随机访问比如数组、列表三、时间复杂度最坏O(log n)然后开始学习写二分法需要注意的问题就是关于区间区间的定义一般为两种左闭右闭即[left, right]或者左闭右开即[left, right)。看了视频感觉很清晰现在就简单写一下伪代码的版本左闭右闭left0 rightnumsize-1 while(leftright)://因为左闭右闭左边是可能等于右边可以画等号 middle(leftright)/2 if num[middle]target://那我们要找的数就在左边更新right rightmiddle-1//我们已经确定middle位置不是要找的而且右边闭合所以不加上middle而是使用middle-1 elif num[middle]target: leftmiddle1//这个和之前的同理就是左边闭合我们不加上已经确定不在区间的数 else: return middle return -1左闭右开left0 rightnumsize//因为右开不包含右边界 while(leftright)//左右边界不会有相等的时候 middle(leftright)/2 if num[middle]target: rightmiddle//要找的在左边更新右边界。右开那就可以直接赋值middle elif num[middle]target: leftmiddle1//要找的在右边更新左边界但是左闭要把middle弄在区间外面middle1 else: return middle return -1写力扣704二分查找看第一排报错是索引要整数不是浮点型是我middle计算这里出了问题用的是leftright/2,应该是整除leftright//2修改后第二次提交通过相关推荐27.移除元素删除数组中等于这个目标值的元素并返回新数组的大小库函数使用如果这个题目用库函数一下子就解决了不建议用库函数补充数组理论知识双指针思路复杂度O(n)伪代码slow0 fast0 for(fast0;fastnumsize;fast): if(nums[fast]!val): //删去不是val的值那么就是只处理不等于val的 //快指针用来获取新数组中的元素 //慢指针获取新数组中需要更新的位置 nums[slow]nums[fast] slow //如果等于val那么不会进去if里面slow也不会进行更新 //这里有一个点是当最后一次更新slow还是进行了操作那么slow的大小就是数组的大小1.slow在python中不允许使用slowslow11.2.边界越界问题977.有序数组的平方给你一个按非递减顺序排序的整数数组nums返回每个数字的平方组成的新数组要求也按非递减顺序排序。这里我是完全想不到双指针的比较容易想到的应该就是先全部平方再排序。但是这样时间复杂度好像比较大所以引出了这个双指针法比较重要的点在于最小的负数平方之后可能变成最大的有序数组的两边大逐渐往中间收拢这样一个趋势伪代码result[]//用来保存结果 knumsize-1 for(i0,jnumsize-1;ij;)//ij的话ij的情况会退出循环就是会少处理一个元素 if(nums[i]*nums[i]nums[j]*nums[j]): result[k]nums[i]*nums[i] k-- i else://包含小于和等于的情况 result[k]nums[j]*nums[j] k-- j-- return result好了我发现是我赋值给了nums应该给res但是修改之后又出现了边界问题不会改问了AInums[-4,-1,0,3,10] # 仅修改这一行把空列表改为和nums长度相同的初始列表 res [0] * len(nums) # 原代码是 res []唯一的修改点将res []改为res [0] * len(nums)。原代码中res是空列表直接通过下标res[k]赋值会触发「索引超出范围」错误而[0] * len(nums)会创建一个和nums长度相同、初始值全为 0 的列表这样就能正常通过下标赋值了。欧克啊今天也是做完了题其实我以前做过但是忘了然后重新看视频思路清晰了很多前两题的报错也是自己看然后修改的最后一个报错确实不会改继续学习吧
测开准备-day01数据结构力扣
704.二分查找我先去查了一下什么是二分法一、一句话理解把一堆已经排好序的数据不断分成两半只在可能存在答案的那一半继续找直到找到或确定不存在。二、核心条件数据必须有序从小到大或从大到小可以随机访问比如数组、列表三、时间复杂度最坏O(log n)然后开始学习写二分法需要注意的问题就是关于区间区间的定义一般为两种左闭右闭即[left, right]或者左闭右开即[left, right)。看了视频感觉很清晰现在就简单写一下伪代码的版本左闭右闭left0 rightnumsize-1 while(leftright)://因为左闭右闭左边是可能等于右边可以画等号 middle(leftright)/2 if num[middle]target://那我们要找的数就在左边更新right rightmiddle-1//我们已经确定middle位置不是要找的而且右边闭合所以不加上middle而是使用middle-1 elif num[middle]target: leftmiddle1//这个和之前的同理就是左边闭合我们不加上已经确定不在区间的数 else: return middle return -1左闭右开left0 rightnumsize//因为右开不包含右边界 while(leftright)//左右边界不会有相等的时候 middle(leftright)/2 if num[middle]target: rightmiddle//要找的在左边更新右边界。右开那就可以直接赋值middle elif num[middle]target: leftmiddle1//要找的在右边更新左边界但是左闭要把middle弄在区间外面middle1 else: return middle return -1写力扣704二分查找看第一排报错是索引要整数不是浮点型是我middle计算这里出了问题用的是leftright/2,应该是整除leftright//2修改后第二次提交通过相关推荐27.移除元素删除数组中等于这个目标值的元素并返回新数组的大小库函数使用如果这个题目用库函数一下子就解决了不建议用库函数补充数组理论知识双指针思路复杂度O(n)伪代码slow0 fast0 for(fast0;fastnumsize;fast): if(nums[fast]!val): //删去不是val的值那么就是只处理不等于val的 //快指针用来获取新数组中的元素 //慢指针获取新数组中需要更新的位置 nums[slow]nums[fast] slow //如果等于val那么不会进去if里面slow也不会进行更新 //这里有一个点是当最后一次更新slow还是进行了操作那么slow的大小就是数组的大小1.slow在python中不允许使用slowslow11.2.边界越界问题977.有序数组的平方给你一个按非递减顺序排序的整数数组nums返回每个数字的平方组成的新数组要求也按非递减顺序排序。这里我是完全想不到双指针的比较容易想到的应该就是先全部平方再排序。但是这样时间复杂度好像比较大所以引出了这个双指针法比较重要的点在于最小的负数平方之后可能变成最大的有序数组的两边大逐渐往中间收拢这样一个趋势伪代码result[]//用来保存结果 knumsize-1 for(i0,jnumsize-1;ij;)//ij的话ij的情况会退出循环就是会少处理一个元素 if(nums[i]*nums[i]nums[j]*nums[j]): result[k]nums[i]*nums[i] k-- i else://包含小于和等于的情况 result[k]nums[j]*nums[j] k-- j-- return result好了我发现是我赋值给了nums应该给res但是修改之后又出现了边界问题不会改问了AInums[-4,-1,0,3,10] # 仅修改这一行把空列表改为和nums长度相同的初始列表 res [0] * len(nums) # 原代码是 res []唯一的修改点将res []改为res [0] * len(nums)。原代码中res是空列表直接通过下标res[k]赋值会触发「索引超出范围」错误而[0] * len(nums)会创建一个和nums长度相同、初始值全为 0 的列表这样就能正常通过下标赋值了。欧克啊今天也是做完了题其实我以前做过但是忘了然后重新看视频思路清晰了很多前两题的报错也是自己看然后修改的最后一个报错确实不会改继续学习吧
