LeetCode刷题打卡第一天（数组I、II）

二分查找（5）——二分法

• 704（二分查找）

• 给定一个n个元素有序的（升序）整型数组 nums 和一个目标值 target,写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1

1. 使用：int mid = (right – left) / 2 + left，而不是：int mid = (right + left) / 2——防止数据过大（大于INT_MAX）越界
2. 初始化right = nums.length – 1
3. while 的循环条件应该是 left <= right
4. while循环 或者 递归方法

• 35（搜索插入位置）

• 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

1. 直接返回left

• 34（在排序数组中查找元素的第一个和最后一个位置）

• 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

 （暴力查找不可行）

1. 返回一个匿名数组的方法：return new int [] {-1, -1};
2. 法一：分别寻找左右边界
3. 法二：用两个while循环判断左右边界，while (l – 1 >= 0 && nums[l – 1] == target) {l–};
   • 出现的问题：

     ①没有想到用while循环;

     ②while循环的条件，r + 1 后不能= nums.length;

     ③二分法条件写错了导致出现所谓的“超时”

• 69（X的平方根）

• 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

1. 法一：数学公式

• 写成x=x12=(elnx)12= e12lnx
• int ans = exp(0.5 * log(x));
• A？B : C —— A为真，执行B；A为假，执行C
• return ((long long) (ans + 1) * (ans + 1) <= x  ?  ans + 1 : ans);

1. 法二：二分查找k值   
   • left = 0, right = x ；
   • 学习if条件，无需那么复杂

• 367（有效的完全平方数）

• 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false
  • 注意转换类型：(long) mid * mid < num

移除元素（5）——双指针

• 27（移除元素）

• 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

1. 法一：快慢指针法
2. 法二：双指针法优化，左右两个指针，避免需要保留的元素重复赋值

根据题意，我们可以将数组分成「前后」两段：前半段是有效部分，存储的是不等于 val 的元素；后半段是无效部分，存储的是等于 val 的元素。

• 26（删除排序数组中的重复项）

• 给你一个升序排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该保持一致。

双指针遍历法 注意返回的slow的值，                                                          此时应该返回slow + 1

• 283（移动零）

• 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序

为了让后面的数组元素为零（自己写的）                                     官方解法，让快慢指针互换

• 844（比较含退格的字符串）

• 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。注意：如果对空文本输入退格字符，文本继续为空

1. 法一：双指针遍历（从后往前）（记录跳过的个数）

找到s中第一个比较的字符

找到T中第一个比较的字符

说明长度不等，即不能匹配上

1. 法二：重构字符串（用栈）—— 如果它是退格符，将栈顶弹出；如果是普通字符，将其压入栈中（时空复杂度均为O（m + n） (m 、n 为字符串s 、t 的长度)）
   1. String的charAt(i)方法     
   2. 用的StringBuilder()类（不是线程安全，不可同步访问，但有速度优势）
   3. StringBuffer()类：  

                append(char ch)——追加到序列中；

                deleteCharAt(int index)——按此顺序删除制定位置的char；

                toString():——以与此序列相同的顺序返回包含此序列中字符的字符串，

                                        字符串的长度将是该序列的长度

• 977（有序数组的平方）
• 给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
  • 法二：双指针遍历I（找到两个有序子数组（正、负））
  • 法三：双指针遍历II（从左右两端开始比较，较大的逆序放入新数组中）