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 27 "101. Symmetric Tree" starting from zero
Basically, I would like to solve the easy acceptance in descending order.
Twitter I'm doing it.
198. House Robber The difficulty level is easy. Excerpt from Top 100 Liked Questions.
You are a thief planning to thief from a house along the street. A certain amount of money is hidden in each house. The only restriction to prevent robbery from each house is that each adjacent house has a security system attached and the police are automatically notified if two adjacent houses are breached on the same night.
Consider the list of non-negative integers that represent the amount of money in each household and find the maximum amount that can be stolen tonight without warning the police.
Let's look at the problem based on the explanation.
Example 1:
Input: [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.
In this example, 4 is returned because the amount taken from the first and third homes is the largest.
Example 2:
Input: [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.
In this example, 12 is returned because the amount of money taken from the first, third, and fifth homes is the largest.
class Solution:
def rob(self, nums: List[int]) -> int:
pre = cur = 0
for i in nums:
pre,cur = cur,max(pre+i,cur)
return cur
# Runtime: 20 ms, faster than 98.32% of Python3 online submissions for House Robber.
# Memory Usage: 14.1 MB, less than 9.09% of Python3 online submissions for House Robber.
I think that you can finish the race by licking the list from the front and substituting cur for pre and pre + i and cur for cur, whichever is larger.
For example. In the case of [1,2,3,1] in the example
pre = 0,1,2,4
cur = 1,2,4,4
The order is as follows, and finally the correct answer of 4 is returned.
I think that it is a problem that can be solved better by focusing on how to operate it when licking from the front without thinking badly.
If there is a good answer, I will add it.
Recommended Posts