704.二分查找
文档讲解:代码随想录(programmercarl.com)
视频讲解:手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法
状态:ac
用时:1.5h
思路:经典的二分法思路,将target和中间数进行对比,大的话在中间数右边,小的话在左边,相等的话返回位置。是一种通过不断缩小查找范围来搜寻目标元素的方法。
遇到的问题:思路是非常简单的,但是边界条件的设置是这个问题的难度所在,而对于循环变量的理解是影响做这题的关键要素。
我的理解:关键不在于区间里的元素具有什么性质,而是区间外面的元素具有什么性质!
如果是[left, right],就是你在一次循环后,新的left或者right外一定是排除的,因此mid被排除后,left或right一定是没被排除的,即left = mid+1或者right = mid - 1,保证了[left, right]的闭区间性质。while的条件是left<=right,这在闭区间内有意义。
如果是[left, right),对于right开区间,right和right外都是排除的,循环后mid是排除的,mid-1是未被排除的,right = mid,保证了right一侧的开区间性质。while的条件是left<right,left==right在左闭右开区间内有意义。
27.移除元素
文档讲解:代码随想录(programmercarl.com)
视频讲解:数组中移除元素并不容易! | LeetCode:27. 移除元素
状态:ac
用时:1h
思路:(1) 暴力解法:每一次查找到一个要移除的元素后,将后面的元素依次往前面移动,来覆盖该元素。
(2) 双指针:一个指针作为快指针,扫描数组中不用移除的元素;一个指针作慢指针,作为新的数组的索引。只需要执行一次for循环,快指针指的元素如果需要被移除,则慢指针不动,快指针往前移动;如果需要被移除,则将快指针指向的值覆盖慢指针指向的值。
暴力解法:要注意如果用j从i开始,使用,会导致数组越界问题。
快慢指针: