首页 > 其他分享 >给自己复盘的随想录笔记-移除元素

给自己复盘的随想录笔记-移除元素

时间:2024-08-22 19:24:23浏览次数:13  
标签:right nums int 随想录 数组 移除 left 复盘 指针

双指针法

双指针法(快慢指针法): 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

  • 快指针:寻找新数组的元素 ,新数组就是不含有目标元素的数组
  • 慢指针:指向更新 新数组下标的位置

相关题目

删除有序数组中的重复项

解题思路:
解法: 双指针

首先注意数组是有序的,那么重复的元素一定会相邻。

要求删除重复元素,实际上就是将不重复的元素移到数组的左侧。

考虑用 2 个指针,一个在前记作 p,一个在后记作 q,算法流程如下:

1.比较 p 和 q 位置的元素是否相等。

如果相等,q 后移 1 位
如果不相等,将 q 位置的元素复制到 p+1 位置上,p 后移一位,q 后移 1 位
重复上述过程,直到 q 等于数组长度。

返回 p + 1,即为新数组长度。

class Solution {
    public int removeDuplicates(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int p = 0;
    int q = 1;
    while(q < nums.length){
        if(nums[p] != nums[q]){
            nums[p + 1] = nums[q];
            p++;
        }
        q++;
    }
    return p + 1;
}


}

移动零

有一个比较凑巧的思路,那就是知道后面是0 ,那么就去补0

class Solution {
    public void moveZeroes(int[] nums) {
     int slow=0;
     for(int fast=0;fast<nums.length;fast++){
        if(nums[fast]!=0){
            nums[slow++]=nums[fast];
        }
    
     }
     
     for( int num=slow;num<nums.length;num++){
        nums[num]=0;
     }
    }
}

另一种思路就是今天讲的双指针法,一个快指针指要交换的元素,一个满指针指元素接下来位置的下标,设计到元素的交换

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
    }

    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

比较含退格的字符串

思路:双指针: 遇到字母两指针都向前一位,遇到#号快指针向前一位,慢指针后退一位(注意0位置) 就行了。

这个思路好理解,我自己也想出来了,就是灵活运用双指针的思路,一定记住加上i>0的判断之后然后后移,避免出现第一个字符量就是#,不加上就会数组越界

class Solution {
    public boolean backspaceCompare(String s, String t) {
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();

        return helper(ss).equals(helper(tt));
    }

    String helper(char[] c){
        int i = 0,j = 0;
        while(j < c.length){
            if(c[j] != '#'){ //遇到字母 两个指针都往前走
                c[i++] = c[j++];
            }else {
                j++;
                if(i > 0) i--;  // 遇到 #, i 指针向后退
            }
        }
        return new String(c).substring(0,i);
    }
}

这个地方数组字符串之间的转换要熟练把握。

有序数组的平方

这个题目不使用双指针的思路去做

class Solution {
    public int[] sortedSquares(int[] nums) {
   
for(int i=0;i<nums.length;i++){
nums[i]=nums[i]*nums[i];
    }
    Arrays.sort(nums);
    return nums;
}
    }

使用双指针的思路去做,

977. 有序数组的平方 - 力扣(LeetCode)

在评论区看到一个这道题用双指针的解法分析的很清晰的,

class Solution {
        public int[] sortedSquares(int[] nums) {
        // 左指针,指向原数组最左边
        int left = 0;
        // 有指针,指向原数组最右边
        int right = nums.length - 1;
        // 创建一个新数组,存储平方值
        int[] result = new int[nums.length];
        // 得到元素值平方值,从新数组最后位置开始写
        int write = nums.length - 1;
        // 左右指针相遇(逐渐靠拢的过程)之后不再循环
        while (left <= right){
            // 如果原数组的左指针对应的平方值大于右指针,那么往新数组最后位置写入左指针对应的平方值
            if (nums[left] * nums[left] > nums[right] * nums[right]){
                result[write] = nums[left] * nums[left];
                // 左指针右移
                left ++;
                // 移动新数组待写入的位置
                write --;
            }
            else {
                result[write] = nums[right] * nums[right];
                right --;
                write --;
            }
        }
        return result;
    }

}

标签:right,nums,int,随想录,数组,移除,left,复盘,指针
From: https://blog.csdn.net/weixin_46321761/article/details/141364041

相关文章

  • 给自己复盘用的随想录笔记day1-二分查找
    二分法使用情景数组为有序数组,同时题目还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件,当大家看到题目描述满足如上条件的时候,可要想一想是不是可以用二分法了。求某一个整数的平方根边界条件写二分法......
  • 代码随想录 -- 数组 -- 螺旋矩阵II
    59.螺旋矩阵II-力扣(LeetCode)每画一条边都要坚持一致的左闭右开注意处理n为奇数时的矩阵中心点classSolution(object):defgenerateMatrix(self,n):res=[[0]*nforainrange(n)]startX=0startY=0loop=mid=n/2c......
  • 代码随想录 -- 数组 -- 区间和
    58.区间和(第九期模拟笔试)(kamacoder.com)暴力解法大概率超时,应采用前缀和解法p[i] 表示vec[0]到vec[i]的累加和求vec[m] 到vec[n] 的和只需要 p[n]-p[m] 即可知识点input函数Python3 中raw_input()和input()进行了整合,去除了raw_input(),仅保留了i......
  • 代码随想录day37 || 518 零钱兑换,377 组合总和iv,70 爬楼梯
    0-1背包问题在0-1背包问题中,每种物品只能选择一次,因此一旦选择某个物品后,剩余的容量只能放入前面的物品。这就是为什么状态转移方程是:dp[i][j]=max(dp[i-1][j],dp[i-1][j-w(i)]+v(i))这里的dp[i-1][j-w(i)]+v(i)表示选择第(i)个物品后,剩余的容量只能放入前(......
  • 代码随想录Day22
    77.组合给定两个整数n和k,返回范围[1,n]中所有可能的k个数的组合。你可以按任何顺序返回答案。示例1:输入:n=4,k=2输出:[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]示例2:输入:n=1,k=1输出:[[1]]提示:1<=n<=201<=k<=n正解......
  • 代码随想录day36 || 1049 最后一筐石头重量||, 494 目标和,474 一和零
    1049最后一块石头重量||funclastStoneWeightII(stones[]int)int{ //本题思路在于要想得到最小差,就要尽可能将石头分割为两堆相近的重量,然后转换为背包问题 //dp[i]表示容量i背包能装的石头总价值,其中重量和价值相等 //递推公式dp[j]=max(dp[j],dp[j-w(i)]+v[i]......
  • 「代码随想录算法训练营」第四十三天 | 图论 part1
    797.所有可能的路径题目链接:https://leetcode.cn/problems/all-paths-from-source-to-target/description/文章讲解:https://programmercarl.com/kamacoder/0098.所有可达路径.html题目难度:中等题目状态:看题解思路一:DFSvoiddfs(vector<vector<int>>&graph,intx,intn......
  • 代码随想录Day21
    669.修剪二叉搜索树给你二叉搜索树的根节点root,同时给定最小边界low和最大边界high。通过修剪二叉搜索树,使得所有节点的值在[low,high]中。修剪树不应该改变保留在树中的元素的相对结构(即,如果没有被移除,原有的父代子代关系都应当保留)。可以证明,存在唯一的答案。所......
  • 「代码随想录算法训练营」第四十二天 | 单调栈 part2
    42.接雨水题目链接:https://leetcode.cn/problems/trapping-rain-water/文章讲解:https://programmercarl.com/0042.接雨水.html题目难度:困难视频讲解:https://www.bilibili.com/video/BV1uD4y1u75P/题目状态:这道题目在LeetCodeTop100中做过,使用两种方法,再回顾一下思路一:单......
  • 代码随想录day35 || 416 分割等和子集
    背包问题有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i],得到的价值是value[i]。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。//pake//// @Description:// @paramweights:物品i对应重量// @paramvalue:物品i对应价值// @......