常用入门算法

2023-12-27 20:09:33

一:快慢指针

适合原地调换一个数组的元素们的位置,使用for循环,声明两个下标,一个移的快,一个移的慢。

快的指针用来往前走,慢的用来停在目标数据上。典型的案例:283. 移动零

1、给定一个数组?nums,编写一个函数将所有?0?移动到数组的末尾,同时保持非零元素的相对顺序。

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
var moveZeroes = function(nums) {
    let slowIndex = 0;
    for (let fastIndex = 0; fastIndex < nums.length; fastIndex++) {
        if (nums[fastIndex] !== 0) {
            [nums[slowIndex], nums[fastIndex]] = [nums[fastIndex], nums[slowIndex]];
            slowIndex++; // 如果遇到0,慢指针不再往前走
        }
    }
};

二:双指针

双指针适用于获取两个数组中的相同元素,使用while语句。

首先需要把两个数组排序,比较两个指针的值。如果相同将值推进结果数据,并将两个指针都挪动一位;如果不同,将值小的指针挪动一位;

一直到某个数组遍历结束即可,典型实例:349. 两个数组的交集

题目:
给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]

示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
解释:[4,9] 也是可通过的
var intersection = function(nums1, nums2) {
   // 先滤重
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);

    const result = new Set();

    let first = 0, second = 0;

    while (first < nums1.length && second < nums2.length) {
        if(nums1[first] === nums2[second]){
            result.add(nums1[first]);
            first++;
            second++;
        }else if(nums1[first] > nums2[second]){
            second++;
        }else{
            first++;
        }
    }

    return [...result];
};

三:快慢指针跟双指针的区别与相同点?

1、区别

  • 使用场景不同。快慢指针使用于一个数组,双指针适用于两个数组。
  • 适用的遍历方法不同。快慢指针适合for循环,双指针适合while循环。

2、相同点

  • 都属于对数组的操作算法
  • 都是操作两个下标?

PS:实践

理论需要配合实践才能真正掌握,

哥们全栈写了一套个人博客?,代码开源,欢迎大家来玩

文章来源:https://blog.csdn.net/sun_qqq/article/details/135247529
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。