刷题笔记--一丶数组类型--双指针法

目录

• 前言
• 系列文章目录
• 题录--同向双指针
• • 27.移除元素
  • 26.删除有序数组中的重复项
  • 283.移动零
  • 844.比较含退格的字符串
• 题录--异向双指针
• • 977.有序数组的平方
• 双指针总结

前言

这里的话新增一个“系列文章目录”，以后随着系列的增多会慢慢一点点增加。

系列文章目录

刷题笔记–一丶数组类型–二分法

题录–同向双指针 27.移除元素

27.移除元素

在leetcode中的题目如下：

这一题有两种解法。

第一种就是暴力解法：双层for循环嵌套，外面的for循环用来遍历数组，里面的for循环用来更新数组。

如果一旦发现要删除的元素，那么所有的元素都往前移一位，当然移完之后也要判断一下移动之后的当前下标是否还是待删除元素。

class Solution {
    public int removeElement(int[] nums, int val) {
        int size = nums.length;
        //1.注意双层for循环的临界判断条件都是size，不能使用nums.length
        for (int i = 0; i < size; i++) {
            if(nums[i] == val){
                for (int j = i+1; j < size; j++) {
                        nums[j - 1] = nums[j];
                }
                i--;//2.注意这里一定要i--，防止连续两个都是要删除的元素
                size--;
            }
        }
        return size;
    }
}

第二种就是我们的双指针解法，当然包括这里和下面属于我们这部分的题都属于我们的同向双指针法。

class Solution {
    public int removeElement(int[] nums, int val) {
        int size = nums.length;
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] != val){
                nums[index] = nums[i];
                index++;
            }else{
                size--;
            }
        }
        return size;
    }
}

26.删除有序数组中的重复项

26.删除有序数组中的重复项
对应题目截图如下：

对应解题思路如下：

class Solution {
    public int removeDuplicates(int[] nums) {
        int cur = 0;
        for(int i = 0;i < nums.length;i++){
            if(nums[i] != nums[cur]){
                cur++;
                nums[cur] = nums[i];
            }
        }
        cur++;
        return cur;
    }
}

这是一个很经典的同向双指针入门题目，所以不做过多思路解释。

283.移动零

283.移动零

题目如下：

对应解题步骤如下

class Solution {
     public void moveZeroes(int[] nums) {
        int cur = 0;
        int index = 0;
        int size = nums.length;
        while(index < size){
            if(nums[index] != 0){
                swap(nums,index,cur);
                cur++;
            }
            //不论怎样index都是要往前走的
            index++;
        }
    }
    public void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

整体思路也很简单，就是我们要确保所有的index下标都是不等于0的。

而cur所有经历过的下标都是非零，这样就可以造成一个什么情况呢？没错，index和cur的下标中间都是0！是不是有点难以理解？没关系，看后面的“总结”部分就行。

844.比较含退格的字符串

844.比较含退格的字符串

看原题

真的就是一个简单题，但是还是挺考验细节的。

如果我一开始用栈来做可以方便很多。

但是毕竟是属于同向双指针的问题，所以还是用双指针的模板来做。

[0,left）是已经处理好的元素，[left,right]是处理好但是不需要的元素，(right,arr.length - 1]是还未处理的元素。

class Solution {
   public boolean backspaceCompare(String s, String t) {
        return  fun1(s).equals(fun1(t));
    }
    public String fun1(String s){
        char[] arr = s.toCharArray();
        int left = 0;
        int right = 0;
        while(right < arr.length){
            if(arr[right] != '#'){
                arr[left] = arr[right];
                left++;
            }else{
                if(left > 0){
                    left--;
                }
            }
            right++;
        };
        if(left == -1){
            return "";
        }
        StringBuffer mys = new StringBuffer();
        for (int i = 0; i < left; i++) {
            mys.append(arr[i]);
        }
        return mys.toString();
    }
}

题录–异向双指针 977.有序数组的平方

977.有序数组的平方

异向双指针，这里浅提一下，解题模板是[0,left]和[right,nums.length - 1]是已经处理好的元素，而中间的(left,right)是没有处理的元素。

这一题没有对空间复杂度有要求，所以就创建一个新的数组来接收值就好了。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0;//定义左指针
        int right = nums.length - 1;//定义右指针
        //处理数组中的平方项
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        //用一个新的数组来接收顺序大小的值
        int[] arr = new int[nums.length];
        //要求非递减，所以index是从后往前走
        int index = nums.length - 1;
        while(index >= 0 && left <= right){
            //如果左指针下标对应值的大于右指针下标对应的值，那就把大的值赋值给新数组的index下标
            if(nums[left] > nums[right]){
                arr[index] = nums[left];
                left++;
            }else{//这里注意了，除了右指针大于左指针的下标外还有等于，他和上面的 left == right联合起来处理left和right下标相同的情况
                arr[index] = nums[right];
                right--;
            }
            index--;
        }
        return arr;
    }
}

双指针总结

<1>首先我发现了一个很严重的问题，我写算法题不加注释，这不是个好习惯，所以以后写算法题我会加上注释，就是我每一步干了什么。

<2>我本来这个时候应该总结一下双指针的做题模板的，但是我发现我的这篇博客写的其实挺到位的，所以我这里就不再重新写一遍了。

（PS：我这么说是不是有点不太好？）

所以，看这里，双指针题型的解题模板。

点击这里观看我以前写的一篇关于双指针解题模板的题型~