按照https://leetcode.cn/circle/discuss/RvFUtj/顺序刷题

零、经验记录

1. 学会画图分析

2. 学会找终止条件

3. 做一道就高质量完成

一、二分算法

0. 总结：大于某个数的第一个数的位置有固定模板，其中要讨论最后一个数小于等于目标数的情况

1. 二分查找：在升序数组中查找某数，如果存在则返回下标，不存在则返回-1

a. 自己的想法：left、mid、right三个指针迭代，注意终止条件，一是mid对应的元素为该数，二是到了只剩两个元素时，那么此时mid=left，如果right对应元素为该数，则返回下表right，如果不是，则代表数组中没有该数，返回-1

b. 存在的问题：判断条件复杂，原因是边界不好，每次判断完大小后，实际上mid对应的元素就可以被排除了。如果nums[mid] > target: right = mid-1。如果nums[mid]<target:left=mid+1。

c. 一点点的疏忽会带来极大的麻烦，要求逻辑足够严谨，充分利用已有信息。

2. 寻找比目标字母大的最小字母：找到一个非递减字符数组中比目标字母大的最小字母

a. 自己的想法：三指针迭代，迭代方式为： if letters[mid] <= target: left= mid+1; if letters[mid] > target: right = mid

b. 存在的问题：没考虑到字母之间可以直接比较（上面是改正后的），没有搞清终止条件。如下图，首先排除target不在该字符数组的两种情况，然后递推即可。

3. 正整数和负整数的最大计数：统计非递减数组的正整数数量和负整数数量中的最大值

a. 自己的想法：需要计算pos和neg的数量，首先如果第一个数大于0或者最后一个数小于0，那么该数组全正或全负，返回数组长度即可。然后分别找到大于0的第一个数的位置和小于0的最后一个数的位置。这里需要注意避免陷入死循环，需要考虑遍历尽头。

b.存在的问题：小于0的最后一个数容易陷入死循环，可以转换为大于等于-1的第一个数，然后这个数的前一个数就必然是最后一个负整数。

4. 两个数组间的距离值：数组1中的元素与数组2中的所有元素距离大于d的数量

a. 自己的想法：

     遍历arr1，其中每个数字作为target，去寻找arr2中大于等于和小于target的最后一个数

     最小的那个如果距离满足大于d，那么该数字满足距离要求

b.存在的问题：arr1不需要排序，找到了大于等于target的第一个数之后，前一个数即为小于target的最后一个数

c. 时间复杂度分为两部分，arr2排序为n2logn2，后面的二分查找为n1logn2，空间复杂度为n1