【04_移动零】

一、问题

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

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

二、思路

初始化指针：定义一个指针non_zero_index，它将用于跟踪下一个非零元素应该放置的位置。初始时，这个指针指向数组的起始位置（索引0）。遍历数组：使用一个循环遍历数组nums中的每个元素。循环的索引变量是i，它从0开始，直到数组的最后一个元素。检查元素是否为零：在每次迭代中，我们检查当前索引i处的元素是否为0。交换非零元素：如果当前元素不是0（即nums[i] != 0），我们需要将它移动到数组的前面。为了实现这一点，我们将当前非零元素与non_zero_index指针所指向的元素进行交换。这样，非零元素就被移动到了数组的前面。更新非零元素位置指针：交换完成后，我们将non_zero_index向前移动一位，以便在下一次迭代中指向下一个应该放置非零元素的位置。继续遍历：循环继续进行，直到遍历完数组中的所有元素。结束：当循环结束后，所有非零元素都已经被移动到了数组的前面，而零元素则被留在了后面。返回结果：最后，函数返回修改后的数组。

三、解法

class Solution:def moveZeroes(self, nums: list[int]) -> None:left = 0right = 0for right in range(len(nums)):if nums[right] != 0:nums[left],nums[right] = nums[right],nums[left]left += 1return  numsif __name__ == '__main__':nums = [0,1,0,3,5,0,12]solution = Solution()result = solution.moveZeroes(nums)print(result)

四、学习汇总

学习到的：
1、指针是索引维度的，所以，指针left ,可以用nums[left]来表示
2、遍历索引，需要使用range(len(nums))
3、关于双指针：双指针是一种常用的算法设计技巧，它利用两个或多个指针来遍历和操作数据结构，尤其是在数组和字符串中。双指针技术可以解决多种问题，如搜索、排序、滑动窗口等。以下是双指针技术的一些基本原理和应用场景：### 基本原理1. **遍历**：双指针通常用于遍历数据结构，一个指针从开始位置移动，另一个从结束位置或中间位置移动。2. **分割**：通过两个指针，可以将数据结构分割成多个部分，分别处理。3. **比较**：两个指针可以用于比较数据结构中的元素，以找到特定的条件或模式。4. **更新**：在遍历过程中，可以根据需要更新指针指向的元素。5. **优化**：双指针可以减少不必要的操作，提高算法的效率。### 应用场景1. **查找特定元素**：- **两个元素之和**：给定一个数组和一个目标值，找出数组中加起来等于目标值的两个元素的索引。通过一个指针固定一个元素，另一个指针遍历数组找到匹配的元素。2. **滑动窗口**：- **最长子串**：找出一个字符串中不包含重复字符的最长子串。使用两个指针定义窗口的开始和结束，移动结束指针扩展窗口，直到遇到重复字符，然后移动开始指针缩小窗口。3. **排序**：- **归并排序**：使用双指针分别指向已排序数组的起始位置，逐步合并。4. **搜索旋转排序数组**：- **二分查找的变种**：在旋转过的有序数组中查找特定元素，通过比较中间元素与两端点，决定指针如何移动。5. **链表问题**：- **链表相交**：找出两个链表相交的起始节点。使用两个指针分别遍历两个链表，如果链表长度不同，则让较长链表的指针先走，直到两个指针相遇。6. **循环数组问题**：- **循环链表的入口**：使用快慢指针，快指针每次走两步，慢指针每次走一步，如果存在环，则快慢指针会相遇。7. **矩阵问题**：- **搜索矩阵**：在一个有序矩阵中查找一个元素，可以使用双指针从矩阵的左上角开始，根据元素值调整指针位置。### 实现技巧- **同步移动**：两个指针同步移动，一个指针固定，另一个根据条件移动。
- **异步移动**：两个指针独立移动，根据各自的条件调整位置。
- **交叉使用**：在某些情况下，两个指针可能会交换角色或位置。双指针技术的核心在于通过控制指针的移动和位置，有效地解决问题，同时优化算法的性能。