Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day 14 "136. Single Number" starting from zero

Basically, I would like to solve the easy acceptance in descending order.

problem

283. Move Zeroes

The difficulty level is easy. This time is also an excerpt from the Top 100 Liked Questions.

The problem is that given an array, we lick all the elements in it, and if the value is 0, we insert that 0 at the end. At that time, the problem is that the order of elements with non-zero values must be kept as they are.

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

solution

I came up with two ideas, so I implemented one of them. One is to move 0, and the other is to move a non-zero value. First, I implemented the former.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(1,len(nums)+1):
            if nums[-i] == 0:
                nums.pop(-i)
                nums.append(0)
# Runtime: 52 ms, faster than 54.28% of Python3 online submissions for Move Zeroes.
# Memory Usage: 15 MB, less than 5.97% of Python3 online submissions for Move Zeroes.

Elements are deleted and inserted at the end with pop and append.

On the other hand, the latter is implemented as follows.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        h = -1
        for i in range(len(nums)):
            if nums[i] != 0:
                h += 1
                nums[h], nums[i] = nums[i], nums[h]
# Runtime: 52 ms, faster than 54.28% of Python3 online submissions for Move Zeroes.
# Memory Usage: 15 MB, less than 5.97% of Python3 online submissions for Move Zeroes.

First, substitute -1 for h and the number of elements for ʻi. And if nums [i]is not 0, add 1 to h and substitutenums [i]fornums [h]andnums [h]fornums [i]`. It can be replaced by. As a result, by doing this for all, all non-zero values will be sorted to the beginning without disturbing the order.

This time I thought about it in two steps. I will add if there is a better way of thinking.

[PYTHON] Let Code Day 15 "283. Move Zeroes" starting from zero

Overview

problem

solution