《开篇》Array - LeetCode 283.Move Zeroes 视频讲解

PS: 先更文章，后续更新每道题目详细解读 & 视频
通过大概10道题来熟悉，常见的算法题类型：Array ，String，Stack，LinkList，Tree，Dynamic Programming，DFS/BFS，Backtracking，Greedy，Divide and Conquer

本文中的算法题大概需要2-3周来完成

1.Array

LeetCode 283.Move Zeroes (Easy)

Given an array nums , write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements

Example:

Input: [0,1,0,3,12]

Output: [1,3,12,0,0]

Note:

You must do this in-place without making a copy of the array

Minimize the total number of operations

题意：将0元素移动到数组的末尾，并且要保证非零元素的顺序，不能复制数组。

Solution 1: 复制一个数组，不满足 Note 1
Solution 2: 遍历一遍，0就交换非0的num
- [0,1,0,3,12] -> [1,0,0,3,12] ->[1,3,0,0,12] ->[1,3,12,0,0] ; T(n)：O(n) ; operations: 3n
Solution 3: 遍历一遍,非零元素进行前置，遍历完成后，未前置的进行0的填充。T(n): O(2n) 满足Note 2 。operations: n
题解：

Solution{
    //Solution 2
    public void moveZeroes(int[] nums) {
    	int j = 0;
    	for(int i = 0; i < nums.length; i++) {
        	if(nums[i] != 0) {
            	int temp = nums[j];
            	nums[j] = nums[i];
            	nums[i] = temp;
            	j++;
            }    	
        }
    }
    //Solution 3
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0){
                nums[j++] = nums[i];
            }
        }
        
        for (;j<nums.length;j++){
            nums[j] = 0;
        }
    }
}

1.Array

LeetCode 283.Move Zeroes (Easy)

FEATURED TAGS