LeetCode题解283.move-zeroes

题目地址

https://leetcode.com/problems/move-zeroes/description/

题目描述

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.

思路

如果题目没有要求modify in-place 的话，我们可以先遍历一遍将包含0的和不包含0的存到两个数字，
然后拼接两个数组即可。 但是题目要求modify in-place， 也就是不需要借助额外的存储空间，刚才的方法
空间复杂度是O(n).

那么如果modify in-place呢？ 空间复杂度降低为1。

我们可以借助一个游标记录位置，然后遍历一次，将非0的原地修改，最后补0即可。

关键点解析

无

代码

• 语言支持：JS, C++, Python

JavaScript Code:

/*
 * @lc app=leetcode id=283 lang=javascript
 *
 * [283] Move Zeroes
 *
 * https://leetcode.com/problems/move-zeroes/description/
 *
 * algorithms
 * Easy (53.69%)
 * Total Accepted:    435.1K
 * Total Submissions: 808.3K
 * Testcase Example:  '[0,1,0,3,12]'
 *
 * 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.
 *
 */
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let index = 0;
    for(let i = 0; i < nums.length; i++) {
        const num = nums[i];
        if (num !== 0) {
            nums[index++] = num;
        }
    }

    for(let i = index; i < nums.length; i++) {
        nums[index++] = 0;
    }
};

C++ Code：

解题思想与上面JavaScript一致，做了少许代码优化（非性能优化，因为时间复杂度都是O(n)）：
增加一个游标来记录下一个待处理的元素的位置，这样只需要写一次循环即可。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        vector<int>::size_type nonZero = 0;
        vector<int>::size_type next = 0;
        while (next < nums.size()) {
            if (nums[next] != 0) {
                // 使用std::swap()会带来8ms的性能损失
                // swap(nums[next], nums[nonZero]);
                auto tmp = nums[next];
                nums[next] = nums[nonZero];
                nums[nonZero] = tmp;
                ++nonZero;
            }
            ++next;
        }
    }
};

Python Code:

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        slow = fast = 0
        while fast < len(nums):
            if nums[fast] != 0:
                nums[fast], nums[slow] = nums[slow], nums[fast]
                slow += 1
            fast += 1

LeetCode题解172.factorial-trailing-zeroes

题目地址 https://leetcode.com/problems/factorial-trailing-zeroes/description/ 题目描述 Given an integer n, return the number of trailing zeroes in n!. Example 1: Input: 3 Output: 0 Explana…

LeetCode题解计算机为什么是基于二进制的？

可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制

LeetCode题解深度优先遍历和回溯的关系？

深度优先遍历的范围更大还是回溯的范围更大？为什么？题解：我的理解是：dfs是回溯思想的一种体现- 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。- dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。个人拙见。

LeetCode题解盲人买袜子。

他们都各自买了两对黑袜和两对白袜，八对袜子的布质、大小完全相同，而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢？题解：暴力破解， 把袜子都拆开 一人一只 哈哈

LeetCode题解10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。

10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。要求用程序模拟十万次，暴力求出该概率来自：字节跳动 算法工程师一面的第一题 （3月30日，60分钟，牛客网视频面）https://www.nowcoder.com/discuss/395924