704.二分查找模板题题目链接https://leetcode.cn/problems/binary-search/代码随想录题解 704. 二分查找 | 代码随想录状态完全掌握三种模板“一只会code的小金鱼”的分界线思路左开右开和卡哥的思路左闭右开左闭右闭这题是模板题用卡哥的思路很快就写出来了而且很好记忆我给二分模板定了三要素进行记忆1.左右初始化2.while()条件3.mid是否±1。以前自己写二分老是会忘记while的条件是leftright还是leftright什么时候用leftmiddle1还是leftmiddlerightmiddle-1还是rightmiddle?初始化该用left0还是left-1rightnums.size()还是rightnums.size()-1理解二分的边界是最容易记忆二分的理解方法是区间不变量原则小金鱼的思路也可以归到区间不变量原则里。为了方便我现在定义的数组都是从小到大顺序排序并且数组从0开始。区间不变量是指将二分的Left和Right当成区间同时固定为闭区间还是开区间的不变量。简单来说举个例子左闭右开Left是闭区间Right是开区间Left的值是可以取到的但Right的值无法取到。首先看1.左右初始化左闭left时数组可以取到left值所以left0等于原数组的下标下限右开right取不到所以rightnums.size()比原数组的下标上限多1个2.while()条件左闭left时数组可以取到left值右开right时数组取值不到right不能left值所以while(leftright)3.mid是否±1左闭left时数组可以取值此时midleftright1nums[mid]targetleft更新因为mid此时的值已经不符合target了并且是左闭left是可以取到的所以left不取mid而是从mid1开始所以左闭mid1。同理右开right时数组取不到right的值nums[mid]targetright更新mid此时的值不符合target并且右开right的值是取不到的所以right是可以取到mid。那左闭右闭则leftmid1rightmid-1以此类推左开右开leftmidrightmid。我做了个表格以此类推我的理解原则区间不变量左右初始化while()条件mid是否±1左闭右开left0 | rightnums.size()leftrightleftmid1rightmid左闭右闭left0 | rightnums.size()-1leftrightleftmid1rightmid-1左开右开left-1 | rightnum.size()left1!rightleftmidrightmid最后一行是小金鱼的模板我记忆为两边都是开的情况是符合我们的区间不变量原则的同时没有左开右闭这种情况是因为日常开发中都是用的左闭的多。下面用左闭右开手撕模板题模板题是默认了从小到大排列同时没有重复元素的class Solution { public: int search(vectorint nums, int target) { int left0,rightnums.size(),middle; while(leftright) { middleleft(right-left)/2;//防止两个int相加爆int if(nums[middle]target)return middle; else if(nums[middle]target)rightmiddle; else leftmiddle1; } return -1; } };备战gxcpc时看acwing提高课的心得yxc y总的模板他用的是左闭右闭我把他的两个模板的精髓提取出到我的左闭右闭总结里他是把整个区间分成两半whileLR循环结束之后 R 1 L 的即L与R差了一位前半边符合check的true右半边符合false一半是0到 R 另一半就是 L 到nums.size()-1根据题意返回L或者R就行了在下面找数字出现的第一位和最后一位的题里最有体现。不用在关注mid的左半边还是右半边。35.搜索插入位置题目链接35. 搜索插入位置 - 力扣LeetCode【二分查找 | 妈妈再也不怕我写错二分啦 | 五点七边二分视频补充】 https://www.bilibili.com/video/BV1fA411z7ru/?share_sourcecopy_webvd_source7a3599e572d9e56d7bbfb1f44a9b852d这题和上面的模板题变化的地方在于找不到target不是输出-1了而是插入到原数组去我这里使用左开右开来写使用小金鱼的分界线理论可以看小金鱼的视频当作卡哥的模板的衍生我的个人详细理解在下一道题。class Solution { public: int searchInsert(vectorint nums, int target) { int left-1,rightnums.size(),middle; while(left1!right) { middleleftright1; if(nums[middle]target)rightmiddle; else if(nums[middle]target)leftmiddle; } return right; } };34.在排序数组中查找元素出现第一次的位置和最后一次的位置题目链接34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode思路【二分查找 | 妈妈再也不怕我写错二分啦 | 五点七边二分视频补充】 https://www.bilibili.com/video/BV1fA411z7ru/?share_sourcecopy_webvd_source7a3599e572d9e56d7bbfb1f44a9b852d我的个人思路把mid当成分界线左边left都是小于target右边right都是大于等于target的所以分界线右边第一个元素就是target第一次出现的位置即此时right的下标同理当我的左边都是小于等于target的数右边都是大于target的数那分界线左边第一个元素就是target最后一次出现的位置即此时left的下标手撕代码如下用的左开右开class Solution { public: vectorint searchRange(vectorint nums, int target) { if(nums.empty())return{-1,-1};//当数组是空的时候直接结束输出-1-1 int l1,r1,l2,r2; int ans1,ans2; l1-1;l2-1;r1nums.size();r2nums.size(); while(l11!r1) { int midl1(r1-l1)/2; if(nums[mid]target)r1mid; else l1mid; } if(r1nums.size()nums[r1]target)ans1 r1; else return{-1,-1}; while(l2!r2-1) { int midl2(r2-l2)/2; if(nums[mid]target)r2mid; else l2mid; } if(nums[l2]target)ans2l2; // else ans2 -1; 这行可写可不写因为第一个出现位置找不到就肯定找不到最后一个出现位置 return {ans1,ans2}; } };27.移除元素题目链接https://leetcode.cn/problems/remove-element/代码随想录27. 移除元素 | 代码随想录思路双指针快、慢指针这题在力扣是可以暴力写的但时间复杂度是O(n*n)用双指针可以只用一层for循环时间复杂度到O(n)由于数组在内存上是一段连续的地址所以是不存在删除的只能用后面的元素覆盖掉实现“删除”。所以我们可以用两个指针进行更新数组快指针fast用于指向不删除的元素慢指针slow指向我们的新数组将fast指向的值给slow即可完成更新。具体代码如下class Solution { public: int removeElement(vectorint nums, int val) { int size nums.size(); for(int fast0,slow0;fastnums.size();fast) { if(nums[fast]!val) { nums[slow]nums[fast]; } else size--; } return size; } };Tips力扣上的超过百分之多少的人当玩具就行了多交几次一样的代码也可超过百分百977.有序数组的平方题目链接977. 有序数组的平方 - 力扣LeetCode代码随想录题解977.有序数组的平方 | 代码随想录思路双指针头、尾指针暴力写法可以直接全部平方之后再sort排序但因为sort复杂度是O(nlogn)的还能再优化。用空间换时间再开一个新数组因为存在负数的平方是大于正数的而且原数组是有序排列的所以可以头尾各设计一个指针平方值大的更新在新数组的末尾这样只用一次循环代码时间复杂度O(n)代码如下class Solution { public: vectorint sortedSquares(vectorint nums) { int left0,rightnums.size()-1; int knums.size()-1; vectorintnum(nums.size()); while(leftright) { if(pow(nums[left],2)pow(nums[right],2)) { num[k--]pow(nums[right],2); right--; } else { num[k--]pow(nums[left],2); left; } } return num; } };太忙了第二天才完成第一天的内容二分还是很建议大家琢磨透再写的很重要的算法。
代码随想录算法训练营Day 1 | 二分：LeetCode704二分查找、35搜索插入位置、34查找元素第一个和最后一个位置 | 双指针：27移除元素、977有序数组的平方
704.二分查找模板题题目链接https://leetcode.cn/problems/binary-search/代码随想录题解 704. 二分查找 | 代码随想录状态完全掌握三种模板“一只会code的小金鱼”的分界线思路左开右开和卡哥的思路左闭右开左闭右闭这题是模板题用卡哥的思路很快就写出来了而且很好记忆我给二分模板定了三要素进行记忆1.左右初始化2.while()条件3.mid是否±1。以前自己写二分老是会忘记while的条件是leftright还是leftright什么时候用leftmiddle1还是leftmiddlerightmiddle-1还是rightmiddle?初始化该用left0还是left-1rightnums.size()还是rightnums.size()-1理解二分的边界是最容易记忆二分的理解方法是区间不变量原则小金鱼的思路也可以归到区间不变量原则里。为了方便我现在定义的数组都是从小到大顺序排序并且数组从0开始。区间不变量是指将二分的Left和Right当成区间同时固定为闭区间还是开区间的不变量。简单来说举个例子左闭右开Left是闭区间Right是开区间Left的值是可以取到的但Right的值无法取到。首先看1.左右初始化左闭left时数组可以取到left值所以left0等于原数组的下标下限右开right取不到所以rightnums.size()比原数组的下标上限多1个2.while()条件左闭left时数组可以取到left值右开right时数组取值不到right不能left值所以while(leftright)3.mid是否±1左闭left时数组可以取值此时midleftright1nums[mid]targetleft更新因为mid此时的值已经不符合target了并且是左闭left是可以取到的所以left不取mid而是从mid1开始所以左闭mid1。同理右开right时数组取不到right的值nums[mid]targetright更新mid此时的值不符合target并且右开right的值是取不到的所以right是可以取到mid。那左闭右闭则leftmid1rightmid-1以此类推左开右开leftmidrightmid。我做了个表格以此类推我的理解原则区间不变量左右初始化while()条件mid是否±1左闭右开left0 | rightnums.size()leftrightleftmid1rightmid左闭右闭left0 | rightnums.size()-1leftrightleftmid1rightmid-1左开右开left-1 | rightnum.size()left1!rightleftmidrightmid最后一行是小金鱼的模板我记忆为两边都是开的情况是符合我们的区间不变量原则的同时没有左开右闭这种情况是因为日常开发中都是用的左闭的多。下面用左闭右开手撕模板题模板题是默认了从小到大排列同时没有重复元素的class Solution { public: int search(vectorint nums, int target) { int left0,rightnums.size(),middle; while(leftright) { middleleft(right-left)/2;//防止两个int相加爆int if(nums[middle]target)return middle; else if(nums[middle]target)rightmiddle; else leftmiddle1; } return -1; } };备战gxcpc时看acwing提高课的心得yxc y总的模板他用的是左闭右闭我把他的两个模板的精髓提取出到我的左闭右闭总结里他是把整个区间分成两半whileLR循环结束之后 R 1 L 的即L与R差了一位前半边符合check的true右半边符合false一半是0到 R 另一半就是 L 到nums.size()-1根据题意返回L或者R就行了在下面找数字出现的第一位和最后一位的题里最有体现。不用在关注mid的左半边还是右半边。35.搜索插入位置题目链接35. 搜索插入位置 - 力扣LeetCode【二分查找 | 妈妈再也不怕我写错二分啦 | 五点七边二分视频补充】 https://www.bilibili.com/video/BV1fA411z7ru/?share_sourcecopy_webvd_source7a3599e572d9e56d7bbfb1f44a9b852d这题和上面的模板题变化的地方在于找不到target不是输出-1了而是插入到原数组去我这里使用左开右开来写使用小金鱼的分界线理论可以看小金鱼的视频当作卡哥的模板的衍生我的个人详细理解在下一道题。class Solution { public: int searchInsert(vectorint nums, int target) { int left-1,rightnums.size(),middle; while(left1!right) { middleleftright1; if(nums[middle]target)rightmiddle; else if(nums[middle]target)leftmiddle; } return right; } };34.在排序数组中查找元素出现第一次的位置和最后一次的位置题目链接34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode思路【二分查找 | 妈妈再也不怕我写错二分啦 | 五点七边二分视频补充】 https://www.bilibili.com/video/BV1fA411z7ru/?share_sourcecopy_webvd_source7a3599e572d9e56d7bbfb1f44a9b852d我的个人思路把mid当成分界线左边left都是小于target右边right都是大于等于target的所以分界线右边第一个元素就是target第一次出现的位置即此时right的下标同理当我的左边都是小于等于target的数右边都是大于target的数那分界线左边第一个元素就是target最后一次出现的位置即此时left的下标手撕代码如下用的左开右开class Solution { public: vectorint searchRange(vectorint nums, int target) { if(nums.empty())return{-1,-1};//当数组是空的时候直接结束输出-1-1 int l1,r1,l2,r2; int ans1,ans2; l1-1;l2-1;r1nums.size();r2nums.size(); while(l11!r1) { int midl1(r1-l1)/2; if(nums[mid]target)r1mid; else l1mid; } if(r1nums.size()nums[r1]target)ans1 r1; else return{-1,-1}; while(l2!r2-1) { int midl2(r2-l2)/2; if(nums[mid]target)r2mid; else l2mid; } if(nums[l2]target)ans2l2; // else ans2 -1; 这行可写可不写因为第一个出现位置找不到就肯定找不到最后一个出现位置 return {ans1,ans2}; } };27.移除元素题目链接https://leetcode.cn/problems/remove-element/代码随想录27. 移除元素 | 代码随想录思路双指针快、慢指针这题在力扣是可以暴力写的但时间复杂度是O(n*n)用双指针可以只用一层for循环时间复杂度到O(n)由于数组在内存上是一段连续的地址所以是不存在删除的只能用后面的元素覆盖掉实现“删除”。所以我们可以用两个指针进行更新数组快指针fast用于指向不删除的元素慢指针slow指向我们的新数组将fast指向的值给slow即可完成更新。具体代码如下class Solution { public: int removeElement(vectorint nums, int val) { int size nums.size(); for(int fast0,slow0;fastnums.size();fast) { if(nums[fast]!val) { nums[slow]nums[fast]; } else size--; } return size; } };Tips力扣上的超过百分之多少的人当玩具就行了多交几次一样的代码也可超过百分百977.有序数组的平方题目链接977. 有序数组的平方 - 力扣LeetCode代码随想录题解977.有序数组的平方 | 代码随想录思路双指针头、尾指针暴力写法可以直接全部平方之后再sort排序但因为sort复杂度是O(nlogn)的还能再优化。用空间换时间再开一个新数组因为存在负数的平方是大于正数的而且原数组是有序排列的所以可以头尾各设计一个指针平方值大的更新在新数组的末尾这样只用一次循环代码时间复杂度O(n)代码如下class Solution { public: vectorint sortedSquares(vectorint nums) { int left0,rightnums.size()-1; int knums.size()-1; vectorintnum(nums.size()); while(leftright) { if(pow(nums[left],2)pow(nums[right],2)) { num[k--]pow(nums[right],2); right--; } else { num[k--]pow(nums[left],2); left; } } return num; } };太忙了第二天才完成第一天的内容二分还是很建议大家琢磨透再写的很重要的算法。
