带你读《图解算法小抄》十九、双指针（4）

带你读《图解算法小抄》十九、双指针（3）https://developer.aliyun.com/article/1348032?groupCode=tech_library

4.移动零

1）问题描述：

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

示例:

输入: [0,1,0,3,12]

输出: [1,3,12,0,0]

注意:

必须在原数组上操作，不能拷贝额外的数组。

尽量减少操作次数。

2）解题步骤：

设置两个指针，一个快指针，一个慢指针。快指针用于遍历数组，慢指针用于标记非零元素的最后一个位置。

当快指针遍历数组时，如果遇到非零元素，将这个元素移到慢指针的位置，然后慢指针向前移动一位。

当快指针遍历完整个数组后，慢指针及其后面的所有位置都应该被赋值为 0。

3）解题框架：

function moveZeroes(nums) {
    let lastNonZeroFoundAt = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== 0) {
            nums[lastNonZeroFoundAt++] = nums[i];
        }
    }
    for (let i = lastNonZeroFoundAt; i < nums.length; i++) {
        nums[i] = 0;
}
}

5.反转字符串

1）问题描述：

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例：

输入：["h","e","l","l","o"]

输出：["o","l","l","e","h"]

2）解题步骤：

设置两个指针，一个在开头，一个在末尾。开头的指针称为左指针，末尾的指针称为右指针。

当左指针小于右指针时，交换两个指针指向的元素，然后左指针右移一位，右指针左移一位。

重复步骤 2，直到左指针大于或等于右指针，此时所有元素已经反转，算法结束。

3）解题框架：

function reverseString(s) {
    let left = 0, right = s.length - 1;
    while (left < right) {
        // swap s[left] and s[right]
        let temp = s[left];
        s[left] = s[right];
        s[right] = temp;        left++;
        right--;
}
}

带你读《图解算法小抄》十九、双指针（5）https://developer.aliyun.com/article/1348030?groupCode=tech_library