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.
Leet Code Table of Contents Starting from Zero
Last time Leet Code Day20 "134. Gas Station" starting from zero
Basically, I would like to solve the easy acceptance in descending order.
Twitter I'm doing it.
448. Find All Numbers Disappeared in an Array
The difficulty level is easy. One of the Top 100 Liked Questions. The number of easy questions in the Top 100 Liked Questions has decreased considerably.
Given an array of integers where 1 ≤ a [i] ≤ n (n is the size of the array), some elements will appear twice and others will appear once.
Find all the elements that are not visible in this given array.
Input: [4,3,2,7,8,2,3,1]
Output: [5,6]
Since the non-existent values between 1 and 8 are 5 and 6, those two are returned.
The first implementation this time is to sort the array, compare the sorted array with the original array, and add it to the array that returns a non-existent value.
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
num,ans = set(sorted(nums)),[]
for i in range(1,len(nums)+1):
if i not in num:
ans.append(i)
return ans
# Runtime: 464 ms, faster than 11.82% of Python3 online submissions for Find All Numbers Disappeared in an Array.
# Memory Usage: 23.7 MB, less than 7.14% of Python3 online submissions for Find All Numbers Disappeared in an Array.
However, it's not very fast, and it doesn't save that much memory consumption. So this time I tried to implement it elsewhere.
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
for num in nums:
ans = abs(num) - 1
if nums[ans] > 0:
nums[ans] *= -1
return [i+1 for i in range(len(nums)) if nums[i] > 0]
# Runtime: 380 ms, faster than 63.11% of Python3 online submissions for Find All Numbers Disappeared in an Array.
# Memory Usage: 21.5 MB, less than 17.86% of Python3 online submissions for Find All Numbers Disappeared in an Array.
It has improved a little.
The latter gets ʻabs to get the absolute value, and if nums [ans] is greater than zero, substitutes nums [ans] for the value lacking -1 in nums [ans] . .. Finally, I wrote it by getting the length of nums in the comprehension notation, doing i + 1 if nums [i]> 0`, and finally returning.
Because of the simple processing, it is interesting to think that the amount of calculation etc. will change greatly with just one writing method.
If there is a good answer, I will add it.
Recommended Posts