LeetCode之——双指针
双指针
双指针有的又叫快慢指针，有的也分细为快慢指针和左右指针，主要用来解决数组、字符串、链表等问题。今天的题涉及的比较浅，主要是解决简单的数组和字符串的问题。
题1：leetcode27. 移除元素
给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示：
- 0 <= nums.length <= 100
- 0 <= nums[i] <= 50
- 0 <= val <= 100
解题思路：
题干中强调了“原地”，因此我们不能重新新建另一个数组来解题。这道题我们采用快慢指针，先来理解一下快慢指针的过程：
令 slowIdx(慢指针) 指向下标 0，fastIdx(快指针) 也指向下标0, fastIdx往前移动，如果对应的数值与所删除的元素不等，则把当前数值赋值给slowIdx对应位置的值。fastIdx 其实就是 for 循环中自增的 i, 遍历一遍后 slowIdx+1 就是我们所需的长度。具体过程leetcode的官方题解以及评论区有视频和图解，不理解的可以去好好看看。
接下来上代码：
public static void main(String[] args) {
int[] nums = new int[]{0,1,2,2,3,0,4,2};
int val = 2;
int len = removeElement(nums, val);
for (int i = 0; i < len; i++) {
System.out.print(nums[i]+" ");
}
}
// 区区几行代码就不多作注解了
private static int removeElement(int[] nums, int val) {
int slowIdx = 0;
for (int fastIdx = 0; fastIdx < nums.length; fastIdx++) {
if (nums[fastIdx] != val){
nums[slowIdx] = nums[fastIdx];
slowIdx++;
}
}
return slowIdx;
与上题类似的还有leetcode26. 删除有序数组中的重复项以及leetcode283. 移动0，这里就不做具体的分析，直接给大家上代码吧（懒了）：
leetcode26：
public static void main(String[] args) {
int[] nums = new int[]{};
int len = removeDuplicates(nums);
for (int i = 0; i < len; i++) {
System.out.print(nums[i]+" ");
}
}
private static int removeDuplicates(int[] nums) {
if (nums.length == 0)
return 0; //leetcode里return -1 会出错；
// 这里slowIdx从1开始是因为一开始将第一个数作为双指针中的val值
int slowIdx = 1;
int val = nums[0];
for (int fastIdx = 0; fastIdx < nums.length; fastIdx++) {
if (nums[fastIdx] != val){
val = nums[fastIdx];
nums[slowIdx++] = val;
}
}
return slowIdx;
}
leetcode283:
public static void main(String[] args) {
int[] nums = new int[]{0,1,0,3,12};
moveZeroes(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i]+" ");
}
}
// 思路就是想将0作为移除的val，计算有多少个0，然后最后将这些0插入到数组后面
private static void moveZeroes(int[] nums) {
int val = 0;
int slowIdx = 0;
int zeroNum = 0;
for (int fastIdx = 0; fastIdx < nums.length; fastIdx++) {
if (nums[fastIdx] != val){
nums[slowIdx++] = nums[fastIdx];
}
else
zeroNum++;
}
// 往后插入0
for (int i = nums.length - zeroNum; i 题2：leetcode844. 比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
如果相等，返回 true ；否则，返回 false 。
注意：如果对空文本输入退格字符，文本继续为空
示例1：
输入：s = "ab#c", t = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。
示例2：
输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 “”。
示例3：
输入：s = "a##c", t = "#a#c"
输出：true
解释：s 和 t 都会变成 “c”。
示例4：
输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。
提示：
- 1 <= s.length, t.length <= 200
- s 和 t 只含有小写字母以及字符 '#'
解题思路：
这道题相信很多人不会立刻想到双指针(没错就是我自己)，一般都是将字符串中该删除的删除，对重构后的两个字符串进比较。不过它标签之一既然有双指针，那就是能用双指针来求解。看了官方的双指针求解，采用逆序遍历比较的方法，可怎么感觉比一般双指针麻烦了很多，当然官方还有动图解释，大家可以去看看。
这道题其实不用官方那么麻烦，跟之前的套路一样，当然我们首先是将字符串变为数组，然后就是将'#'作为val值，如果fastIdx搜寻到val，那么按照题目意思需要删除前一个数据，那么只需要把slowIdx-1就可以了。最后就可以得到删除后的字符串片段(竟然是利用双指针来重构字符串，有被惊到)，话不多说，上代码：
public static void main(String[] args) {
String s = "a#c", t = "b";
boolean out = backspaceCompare(s, t);
System.out.println(out);
}
private static boolean backspaceCompare(String s, String t) {
// 双指针最好是对数组进行操作，因此这里将字符串转为数组
String ss = getStr(s.toCharArray());
String tt = getStr(t.toCharArray());
return ss.equals(tt);
}
private static String getStr(char[] str) {
// 使用时slowIdx先+1，再赋值，便于else if里-1
int slowIdx = -1;
char space = '#';
for (int fastIdx = 0; fastIdx < str.length; fastIdx++) {
if (str[fastIdx] != space){
slowIdx++;
str[slowIdx] = str[fastIdx];
}
else if (slowIdx >= 0){
slowIdx--;
}
}
// copyOfRange方法截取数组
char[] result = Arrays.copyOfRange(str,0,slowIdx+1);
// 返回值转为String
return new String(result);
}
题3：leetcode977. 有序数组的平方
给你一个按非递减顺序 排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
示例1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
提示：
- $1 <= nums.length <= 10^4$
- $-10^4 <= nums[i] <= 10^4$
- nums 以按非递减顺序排序
解题思路：
这道题其实很简单，数组中逐个平方后再排序就行，当然，排序方法的不同效率也不同，也可以直接调用java自带的Arrays.sort()方法，它用了一种名为TimSort的排序算法，是归并排序的优化版本。而官方有一个解就是双指针+归并排序的，有兴趣的可以去学习。
这里不直接调用java自带的排序, 根据题目可以知道，数组里如果存在负数，平方后数值是先减少后增大的(数组非递减)，故我们可以直接比较首尾数值平方后的大小，然后利用首尾双指针将最大值插入最后一位，下面看代码：
public static void main(String[] args) {
int[] nums = new int[]{-7,-3,2,3,11};
int[] result = sortedSquares(nums);
for (int i = 0; i < result.length; i++) {
System.out.print(result[i]+" ");
}
}
private static int[] sortedSquares(int[] nums) {
// 新建长度与nums一样的数组，作为返回数组
int[] res = new int[nums.length];
// 初始化头尾指针
int leftIdx = 0, rightIdx = nums.length-1;
int idx = nums.length-1; //这是插入值的顺序
while (leftIdx <= rightIdx){
// 比较首尾平方的大小，然后更新对应的首尾指针
if (nums[leftIdx] * nums[leftIdx] >= nums[rightIdx] * nums[rightIdx]){
res[idx--] = nums[leftIdx] * nums[leftIdx];
leftIdx++;
}
else{
res[idx--] = nums[rightIdx] * nums[rightIdx];
rightIdx--;
}
}
return res;
}
刷题参考路线：代码随想录(微信公众号)