算法回忆录

二分法总结

1. 开闭区间，对于可用区间的区别，闭区间中最大值为len()-1，开区间则为len
2. 对于加不加等号则是，需要根据题目的类型，如查找确定值就需要等号，如不然则可能损失值，查找边界则可以为只使用不等号，返回r或者l
3. 对于中间不断mid变量，标准公式为left + (right - left) // 2，这样做首先可以正确找到中间值，二消除溢出的问题如(right-left)//2
4. 对于已经分过的二分法则使用大于目标值，就从大于的那边，减去1，对于已经分过的二分法则使用小于目标值，加上1。使用mid来实现变动可以更快，为什么不使用在left和right的直接加减，原因是在left和right加减，一次性只能加减一个，如果使用mid来实现，则可以使用关于大于或者小于mid直接给屏蔽掉，实现跳跃查找，提升效率
5. 使用两个return返回，则表示查找到就返回正确mid，没有查找到就返回-1
6. 对于查找插入值来说，left则为当前值的插入位置，为什么勒？是因为mid发现大于或者小于，要进行操作加减1，然后再进行循环，再检测，一旦发现检测不了，则证明为已经找到边界值，一般使用left
7. 对于平方数来说，需要注意来说赋值是比较重要的，不能在原值上进行操作，对于平方根来说，检测到不符和的就证明在当前的前一位使用right或者left+1。检测是否为平方根来说，将return返回布尔值就可以
8. 寻找在排序数组中查找元素的第一个和最后一个位置的边界值，需要两个二分法，一个用于最左边的查找，与普通二分法不一样，当左边时等于mid值时，left=mid+1，这为查找是否存在第二个一样的值，当右边时等于mid值时，right=mid-1，这为查找是否存在后面还有一样的值，当left轮询一边时候还没有发现，或者列表的left没有停靠在目标值，都证明当前没有值处于列表中，使用两个二分法找边界最后将初始值清零，重新赋值，最后在两者之间实现 lists[0]和lists[1]的赋值，为什么要在这里使用left <= right 而不是 left < right，则是因为if left >= len(nums) or nums[left] != target:return lists，如果使用<则会漏掉值

   快慢指针总结

9. 使用快慢指针，需要区分谁为处理针，一般来说fast为遍历指针，show为处理指针，且在处理指针是，挑选方向一般为较少的一侧，如当检测一个数组是有相等的值，这时候处理指针方向为当相等的时候，nums[show]==val,在此基础上实现处理指针的变化，后续再加上遍历指针的变化
10. 对于开头快慢指针的设置来说，是需要题目的限制，如检测是否有重复的值，则需要遍历指针设为第二值，处理指针设为第一值，这样节约时间，但是这种就需要将处理指针赋值改变位置，否则就会出现丢失值，返回需要返回长度
11. 对于python中临时交换区间，可以使用多重元素赋值，变量交换
12. 重点– 比较含退格的字符串，这个算法中，有几个需要注意的，1.没有快慢针，两个值都是截取出来长度2.会有一个记录值，这是记录退格，实现增加和减少，使用三个循环，大循环包含两个单独小循环，判段if有#就实现记录值增加，减少长度，最重要一步，当记录值大于零，就在减去1，将边界相减。3.最后判断条件
13. 对于平方和也是这样，将快慢针变为条件限制的值，将异常的条件取出来做比较