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 Day 28 "198. House Robber" starting from zero
Basically, I would like to solve the easy acceptance in descending order.
Twitter I'm doing it.
46. Permutations The difficulty level is Medium. Excerpt from Top 100 Liked Questions.
The problem is to return all permutations, given a list of different numbers. The title Permutation seems to mean permutation.
Example:
Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
This is an example of returning all permutations.
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
return list(itertools.permutations(nums))
# Runtime: 36 ms, faster than 87.99% of Python3 online submissions for Permutations.
# Memory Usage: 14.1 MB, less than 5.36% of Python3 online submissions for Permutations.
Yes. I'm sorry. In front of Python, the Medium of Let Code is like a baby.
This is the end, thank you for the match.
I'm sorry, this is too terrible, so I thought about another solution.
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
ans = []
self.dfs(nums, [], ans)
return ans
def dfs(self, nums, emp, ans):
if not nums:
ans.append(emp)
for i in range(len(nums)):
self.dfs(nums[:i]+nums[i+1:], emp+[nums[i]], ans)
# Runtime: 32 ms, faster than 96.70% of Python3 online submissions for Permutations.
# Memory Usage: 13.9 MB, less than 5.36% of Python3 online submissions for Permutations.
I implemented dfs separately.
It keeps turning with the recurrence function until the number of elements of nums is exhausted.
It can be implemented using slices.
As a reminder, in the case of nums [: i], get from the first element to the i-th, and in the case of nums [i + 1:], get from the i + 1th to the last element. I will.
Then, when the element disappears, emp is added to the originally prepared list ʻans` to make it a two-dimensional array.
This is a little faster.
If there is a good answer, I will add it.
Recommended Posts