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 Day24 starting from zero "21. Merge Two Sorted Lists"
Basically, I would like to solve the easy acceptance in descending order.
Twitter I'm doing it.
70. Climbing Stairs The difficulty level is easy. Excerpt from Top 100 Liked Questions.
I think this is a familiar problem for those who have taken the junior high school exam. Actually, there is a very simple solution, but I will explain it in the solution.
When you climb the stairs, you can climb one or two steps.
Given the natural number n, please answer how many ways you can reach the summit.
Example 1:
Input: 2 output: 2
In the case of 2, there is a method of climbing 2 steps at a stretch and a method of climbing 1 step twice, so 2 is returned.
Example 2:
Input: 3 Output: 3
In the case of 3, 3 is returned because there are three methods: repeating one step at a time, going up one step and going up two steps, and going up two steps and going up one step.
Actually, this is a problem with the Fibonacci sequence. You may have seen it while studying the number of cases.
By the way, the Fibonacci sequence is １,１,２,３,５,８,１３,２１,３４,５５, And so on, it is a sequence in which the sum of the previous two numbers becomes the next number.
Let's consider the case where there are 3 steps as in the example. In this case, it depends on the case at the first stage. There is a pattern of climbing one step or two steps. If you climb two steps, you will inevitably have one option because there are only one stairs left. On the other hand, if 1 is selected, there are 2 steps left, that is, 2 ways as shown in the example. The sum of these additions is the answer for each case, and this is a typical example of the Fibonacci sequence as described above.
Try other numbers as well. Let's say it has 4 steps.
Then select 1st step and 2nd step first. The first is the case of 1 step, but the rest is 3 steps. In other words, you can use the 3 ways of the previous 3 steps as they are. And in the case of 2 steps, the rest is 2 steps. In other words, there are two ways. There are 3 ways + 2 ways, so there are 5 ways.
If you add one staircase, it will increase to 8, and if you add another step, it will increase to 13 ...
Once you understand the structure of this addition, all you have to do is code the law.
As a simple example
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 1:
return n
num1, num2 = 0, 1
for i in range(n):
num1, num2 = num2, num1+num2
return num2
# Runtime: 32 ms, faster than 39.40% of Python3 online submissions for Climbing Stairs.
# Memory Usage: 13.7 MB, less than 5.97% of Python3 online submissions for Climbing Stairs.
This is the general solution. However, when I looked at the discuss, there was a faster way to write it.
from functools import lru_cache
class Solution:
@lru_cache(None)
def climbStairs(self, n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return self.climbStairs(n-1) + self.climbStairs(n-2)
# Runtime: 24 ms, faster than 91.08% of Python3 online submissions for Climbing Stairs.
# Memory Usage: 13.9 MB, less than 5.97% of Python3 online submissions for Climbing Stairs.
It's really fast ...
By the way, what is lru_cache?
So I quietly looked it up in the Official Documents.
@functools.lru_cache(user_function) @functools.lru_cache(maxsize=128, typed=False) A decorator that wraps a function in a callable object for memoization and saves up to maxsize recent calls. You can save time when you regularly call expensive functions or functions that are bound to I / O with the same arguments.
Since a dictionary is used to cache the results, the function's positional and keyword arguments must be hashable.
If the argument patterns are different, they are considered different calls and will be separate cache entries. For example, f (a = 1, b = 2) and f (b = 2, a = 1) are two separate cache entries because the order of the keyword arguments is different. .....
The LRU (least recently used) cache is most efficient when the latest call is most likely to be called again (for example, the most popular articles on the news server tend to change daily). .. The cache size limit ensures that the cache does not grow beyond the limits of long-term processes such as web servers.
In general, the LRU cache should only be used when you want to reuse the previously calculated value. So there is no point in caching functions that have side effects, functions that require you to create a separate mutable object for each call, or impure functions like time () or random ().
In other words, since the result of the called function is cached using a dictionary, if the cached result is called even in the latest call, the efficiency at the time of execution will increase.
I didn't know it, so I learned a lot, but it's important to see the discussion.
Recommended Posts