leetcode老问题新发现（更新ing）
重刷Leetcode
- [704. 二分查找](https://leetcode.cn/problems/binary-search/description/)
- [27. 移除元素](https://leetcode.cn/problems/remove-element/description/)
- 977.有序数组的平方
前言：之前用C++把代码随想录写的差不多了，近期在学Java，写着重写一遍题目，在复习算法的同时，顺便掌握一下Java的语法。 本贴打算作为一个长期贴，并且每道题只做提示，不会发详细的题解。旨在快速复习题目，看有没有考虑一些特殊情况。
704. 二分查找
- 注意到
int mid = (left + right)/2中加法会溢出的问题。于是我写成了int mid = low + (high - low) >> 1;。错误，优先级错误，因为位移操作符 >> 的优先级比加法 + 低。 - 注意闭、开区间的写法。判断条件，赋值都会有所不同。
27. 移除元素
每次太久没做这道题，回来做总会写成
class Solution {public int removeElement(int[] nums, int val) {int p = 0, q = 0;while(q < nums.length) {while(q < nums.length && nums[q] == val) {q++;}if(q >= nums.length) {break;}nums[p++] = nums[q++];}return p;}
}
虽然思路是一样的，时间复杂度一样。但是明显比下面答案冗长的多。
class Solution {public int removeElement(int[] nums, int val) {int fast = 0, slow = 0;while(fast < nums.length) {if(nums[fast] == val) {fast++;continue;}nums[slow++] = nums[fast++];}return slow;}
}
反思了一下，写成第一种是因为总是把一个过程看太复杂了，即一个循环内完成一次找到合适元素的过程。而第二种写法是一步一步找的过程。
所以如果遇到写的过程发现思路是对的，但是代码很冗余。这种情况可以想一下是不是可以简化一次循环过程。
977.有序数组的平方
1.最简单的方法就是先平方后排序，时间复杂度为O(N logN)（因为快排）。这种方法没有利用到有序的信息。可以先用二分查找找出正负分界点（这一部分是检测能否熟练掌握二分查找的技能），然后再使用类似归并的思想处理。时间复杂度为O(N)。
2. 除了上面两种方法，官方答案（法三）还给出不用一开始查找分界点的方法。自己思考回忆一下…
3. leetcode官方给出的空间复杂度我不太赞同，他是开答案的空间就不算入空间复杂度。这样看的话原地处理（法一）并没有优势。
4. 在写归并时，最后两个while循环中，我写了下面代码，然后报错了，原因是超出数组范围。
while(q<nums.length) {res[index++] = nums[q++] * nums[q];}
原因：q++放前面了，所以两个q并不是一个值。正确代码为：res[index++] = nums[q] * nums[q++];
（待更新。。）