😜 算法双指针
!本篇文章过于久远，其中观点和内容可能已经不准确，请见谅!~
双指针在算法中很常见的一个处理技巧，当然并不是说双指针是一个固定的银弹，只是很多的算法中会使用到两个指针来实现一个更好的算法复杂度。
一般在业务中，如果性能要求没那么变态的场景，基本上一个指针遍历，不行就两个循环，总能解决一般业务。
但是在大数据比如一个超大的数组，遍历一遍的代价已经很大了，能一遍解决最好，所以双指针可能在算法复杂度上更优。
这篇文章也是意识到这样一个方法比较好，目前还并不能总结出一个特别明显的模式，毕竟每个算法的需求不同。
LeetCode 数组中有很多简单题目使用这个方法，所以应该比较容易想到。
[简单难度 70.7%] 2019-10-24 16:15:36
给定一个按非递减顺序排序的整数数组
A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。示例 1：
输入：[-4,-1,0,3,10]输出：[0,1,9,16,100]
示例 2：
输入：[-7,-3,2,3,11]输出：[4,9,9,49,121]
提示：
1 <= A.length <= 10000-10000 <= A[i] <= 10000A 已按非递减顺序排序。
- 最简单的思路是平方后排序，或者取正之后排序然后平方，但是很明显的也就不是题目想要实现的算法；
- 题目本身的特点是原数组已经排列了，需要平方之后再排，平方后的序列肯定是两边大中间小；
- 所以一个比较好的思路是两边比大小，向中间靠拢的过程中排序；
- 这也是算法中比较常见的双指针方法；
- 步骤是两头指针，然后指针数值比大小，较大的确定，较小值的指针的与下一个指针比值的大小，以此递归；
[简单难度 67.8%] 2019-10-28 19:32:30
给定一个非负整数数组
A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。你可以返回满足此条件的任何数组作为答案。
示例：
输入：[3,1,2,4]输出：[2,4,3,1]输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。
提示：
1 <= A.length <= 50000 <= A[i] <= 5000
- 分离数据，不要求排序，将数字放到两端；
- 很容易想到用首尾指针，判断奇偶然后移动指针的值；
- 算法确实是有方法的，如果不了解双指针的方法，可能会花点时间；
[简单难度 73.0%] 2019-10-23 17:55:51
给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。
水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。
反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。
示例 1:
输入: [[1,1,0],[1,0,1],[0,0,0]]输出: [[1,0,0],[0,1,0],[1,1,1]]解释: 首先翻转每一行: [[0,1,1],[1,0,1],[0,0,0]]；然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]
示例 2:
输入: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]输出: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]解释: 首先翻转每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]；然后反转图片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
说明:
1 <= A.length = A[0].length <= 200 <= A[i][j] <= 1
- 题目很简单，主要看效率了；
- 数组逆序的方法不使用自带的数组方法，直接循环就可以，不过可以在原数组上赋值节省空间；
- 1/0 互换，比较容易想到用 1 减来实现，还有一个异或运算
1 ^ 1 = 0; 1 ^ 0 = 1;； - 一行中半行循环即可翻转一行，翻转的时候同时反转；
- 翻转的时候，如果前后对应的两个数字不同，正好是反转的情况，不用赋值；数字相同，同时反转即可；
感谢您的阅读，本文由 Ubug 版权所有。如若转载，请注明出处：Ubug（https://ubug.io/blog/two-pointers）
