算法day01

发布于:2024-05-09 ⋅ 阅读:(18) ⋅ 点赞:(0)

1、[283.移动零](https://leetcode.cn/problems/move-zeroes/)

        给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。请注意 ,必须在不复制数组的情况下原地对数组进行操作。

        解题思路:

        双指针算法:由于数组划分,数组滑块,采用数组下标来充当指针;

        依题意,需将数组划分为非零区域和零区域,且非零区域的数字排列顺序与之前相对不变;

         定义cur和dest两个指针:

cur:从数组的0的下标开始扫描,一直到nums.length-1的位置;

dest:从下标为-1的位置开始扫描,将整个数组分为已处理区和未处理区;

        举例说明:

        此时如下图所示:

        cur向前一步,

        判断,如果当前cur所指为零,则接着向前一步,如果所指非零,则dest指针往前一步,此时的两个位置的数值进行交换,如下所示,持续上述步骤;

综上所述,代码如下:

class Solution {
    public void moveZeroes(int[] nums) {
       for(int cur=0,dest = -1;cur < nums.length;cur ++){
            if(nums[cur] != 0){
                dest ++;
                //交换cur和dest
                int temp = nums[cur];
                nums[cur] = nums[dest];
                nums[dest] = temp;

            }
       }
    }
}

2、[1089. 复写零](https://leetcode.cn/problems/duplicate-zeros/)

        给你一个长度固定的整数数组 arr ,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。

        注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改,不要从函数返回任何东西。

        由题意可得,需要采用双指针的方法;

        因为是要保持原数组长度的前提下,从前往后需要进行改写数组,所以我们需要找到最后一个被复写的数字,从后往前按照规则复写;

步骤一:先找到最后一个复写的数

        1、先判断cur位置上的数值是否为0;

                如果为0,dest指针先前移动两步;

                如果不为0,dest指针先前移动一步;

        2、找到当前循环的结束点;

                dest指针在(0,n-1)范围内是,该循环继续,所以当dest指针>=n-1时,当前循环结束;

        3、所以在循环未结束前,dest指针向前移动后,不能结束终止循环,则cur指针向前一步;

        综上所述,cur指针最后所指的位置的数字就是我们要复写的最后一个数字;

步骤二:处理关于dest指针在上述循环结束后的边界条件;

        在找到最后一个复写数字的时候莫过于两种情况;

情况一:dest指针在n-1位置上,此为正常状态;

情况二:dest指针由于规则,+2之后回停在n+1位置上,此为非正常状态,需要特殊处理;

        我们需要在dest+2,cur+1,操作(此时存在数组越界)的情况下,dest-2,cur-1,arr【n-1】=0操作处理;

步骤三:从后往前复写0操作;

        

代码如下:

class Solution {
    public void duplicateZeros(int[] arr) {
       int cur = 0,dest = -1,n = arr.length;
 // 1. 先找到最后⼀个需要复写的数
       while(cur < n ){
        if(arr[cur] != 0){
            dest +=1;
        }else{
            dest +=2;
        }
        if(dest >= n-1){
            break;
        }
        cur ++;
       }
 // 2. 处理⼀下边界情况
        if(dest == n) {
            arr[n-1] = 0;
            dest -=2;
            cur--;
            }
 // 3. 从后向前完成复写操作
 while(cur >= 0){
    if(arr[cur] != 0) {
        arr[dest--] = arr[cur--];
    } else {
      arr[dest--] = 0;
      arr[dest--] = 0;
      cur--;
 }
 }
    
}
}

 ps:如果对你有所帮助的话就请意见三连哦!!!