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.
Basically, I would like to solve the easy acceptance in descending order.
Last time Leet Code Day2 1108. Defanging an IP Address starting from zero
1313. Decompress Run-Length Encoded List
We are given a list nums of integers representing a list compressed with run-length encoding. Consider each adjacent pair of elements [freq, val] = [nums[2i], nums[2i+1]](with i >= 0). For each such pair, there are freq elements with value val concatenated in a sublist. Concatenate all the sublists from left to right to generate the decompressed list. Return the decompressed list.
Lick the list given in order from the front and make one pair with two.
Then, the former is treated as freq as the number of elements, and the latter is treated as value as the value. For example, if freq = 1, value = 2, it becomes [2].
In the case of nums = [1,2,3,4] given as an example, the first pair is freq = 1, value = 2,
The second pair is freq = 3, value = 4, so [2] + [4,4,4], and adding them to the list says [2,4,4,4] Become.
The problem is to create a function that returns these.
class Solution:
def decompressRLElist(self, nums: List[int]) -> List[int]:
ans = []
for i in range(0,len(nums),2):
ans += [nums[i+1]]*nums[i]
return ans
# Runtime: 60 ms, faster than 95.75% of Python3 online submissions for Decompress Run-Length Encoded List.
# Memory Usage: 13.9 MB, less than 100.00% of Python3 online submissions for Decompress Run-Length Encoded List.
If you read the problem, you can see that it is important to take the number of elements by turning it with a for statement for the time being.
The key to this problem is i and i + 1, how to implement the technique of getting the elements in increments of two and multiplying them by the number in front of them.
Fortunately, Python only needs to apply numbers to the arguments of the range function in the order (start, stop, step).
start is the number of starts. I started from 0 in this example.
How many stops do you end up with? Here, the number of elements does not exceed the number of nums, so the number of elements of nums, that is, len (nums) can be used.
step is a numerical value indicating how many elements are skipped when reading the number of elements.
For example, in this test case, the argument [1,2,3,4] is given, so 1 and 3 are assigned to i in this range function.
It may be a very mundane answer, but you can get the number you are looking for by skipping 0 to freq by 2 in the for statement and multiplying it by the number after it when you add it. be able to.
In addition, in exactly the same way of thinking, this way of thinking seems to be superior in discussion.
class Solution:
def decompressRLElist(self, nums: List[int]) -> List[int]:
ans = []
for i in range(1,len(nums),2):
ans += [nums[i]]*nums[i-1]
return ans
# Runtime: 60 ms, faster than 95.75% of Python3 online submissions for Decompress Run-Length Encoded List.
# Memory Usage: 14 MB, less than 100.00% of Python3 online submissions for Decompress Run-Length Encoded List.
Honestly, either one is fine because the speed and memory consumption do not change.
In addition, there are some fierce people in the world who answer in one line. For example, such an example.
def decompressRLElist(self, A):
return [x for a, b in zip(A[0::2], A[1::2]) for x in [b] * a]
# Runtime: 88 ms, faster than 5.86% of Python3 online submissions for Decompress Run-Length Encoded List.
# Memory Usage: 14.1 MB, less than 100.00% of Python3 online submissions for Decompress Run-Length Encoded List.
In the for statement, 0 to 2 skips and 1 to 2 skips are put in ʻaandb`, respectively, and finally the product of them is assigned to x.
The zip function is used in this answer, but the zip function is as follows. zip functions
Create an iterator that collects elements from each iterator. This function returns an iterator of a tuple, whose i-th tuple contains the i-th element of each argument sequence or iterable. This iterator will stop when the shortest of the input iterators is exhausted. Given a single iterable argument, returns an iterator consisting of a one-element tuple. With no arguments, it returns an empty iterator.
Isn't this problem a very good problem because the problem statement is ambiguous? The story is also raised in discussion. Actually, it seems that the evaluation of bad is much higher than that of good, so it may not be very helpful.
Recommended Posts