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 Day 9 "701. Insert into a Binary Search Tree" starting from zero
It lasted 10 days, it's amazing.
1431. Kids With the Greatest Number of Candies
Given the array candies and the number ʻextra Candies. candies [i]` is the number of candies that the i-th child has.
Find out if there is a way to distribute extra candy to each child so that they can have the largest number of candies among them.
It's a little difficult to understand if it's just a problem ... It seems better to look at an actual example.
Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true]
In the case of the very first child, if you give 3 of ʻextra Candies to the 2 candies you already have, it will be 5 by 2 + 3, and it will line up with the maximum value of 5 in candies`. , True.
The same is true for the second, third and fifth children.
The only False is the fourth child, given 3 ʻextra Candies`, which is only 4 and does not reach the maximum value of 5 in the array.
After adding the value of ʻextra Candies to the number of each array, compare it with the maximum value in the array, and if it is greater than or equal to the maximum value, substitute True, and if it is less than, substitute False into candies`. , If it is a function that returns candies after going through the flow, it seems that the condition is satisfied.
First, an example of writing only recursion and branching
class Solution:
def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
num = max(candies)
for i in range(len(candies)):
if candies[i] + extraCandies >= num:
candies[i] = True
else:
candies[i] = False
return candies
# Runtime: 64 ms, faster than 33.33% of Python3 online submissions for Kids With the Greatest Number of Candies.
# Memory Usage: 13.6 MB, less than 100.00% of Python3 online submissions for Kids With the Greatest Number of Candies.
It's super simple. However, this is not very fast, and I would like to simplify it further. Considering the part that can be omitted here, I think that the if branch after the for statement is a little redundant.
class Solution:
def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
num = max(candies)
return [candy + extraCandies >= num for candy in candies]
# Runtime: 48 ms, faster than 33.33% of Python3 online submissions for Kids With the Greatest Number of Candies.
# Memory Usage: 14 MB, less than 100.00% of Python3 online submissions for Kids With the Greatest Number of Candies.
I will rewrite it like this. It's a little faster.
What follows the return is a list comprehension.
[Expression for variable in object]
It is possible to write.
In addition to the inclusion notation,
Set {expression for variable in object}
Dictionary {key expression: value expression for k, v in object}
Generator (expression for variable in object)
If you are interested, you can refer to the following documents.
In addition, there was the following as an interesting article about the speed of inclusion notation. You may want to check it when you have time.
Python list comprehension speed
Recommended Posts