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 Day12 starting from zero "617. Merge Two Binary Trees"
Basically, I would like to solve the easy acceptance in descending order.
The difficulty level is Medium. Recently, it seems that there are many good questions because I preferentially select from Top 100 Liked Questions. Of course, it is advantageous to have mathematical knowledge, but it is very interesting because there are many problems that will lead to the correct answer if you think carefully even if you do not have it.
A natural number num is given. Calculates the number of 1s in the binary representation of all numbers i in the range 0 ≤ i ≤ num and returns them as an array.
Do you think that this problem is only a problem statement? It will be. Let's look at an example.
Example 1:
Input: 2 Output: [0,1,1]
In this case, 2 is given as num.
Converting [0,1,2] to a binary number yields [0,1,10], counting the number of 1s contained in each of these values gives 011, and converting to an array gives [0,1,10]. It becomes 1]. Finally returns this array.
Example 2:
Input: 5 Output: [0,1,1,2,1,2]
In this case, 5 is given as num.
Converting [0,1,2,3,4,5] to a binary number gives [0,1,10,11,100,101], and counting the number of 1s contained in these values gives 011212, [0, 1,1,2,1,2].
First, prepare a list to return, ʻans`, and consider using a for statement that repeats values from 1 to num + 1.
It does a binary conversion for each number, adds a count of 1 to the list, and finally returns the first prepared ʻans`. Perhaps the most important of these problems is an algorithm that also performs binary conversion and counts the number of 1.
Divide the i-th of ʻansby 2, and add the value to the remainder when i is divided by 2, and it will be converted well. This is because if the value ofnum` is odd, the last digit will be 1, and 1 will be deleted by right-shifting. If it is even, it will always be 0, so even if right-shifting, the same value will be obtained. This is because it becomes one of.
Considering this example, for example, if num is 4,
ans[4/2]+(4%2)
It will be. In this case, it is the second of ʻans [0,1,1,2] `, that is, 1. The 1 and 0, which is the remainder of (4% 2), are added, and 1 which is the number of 1s of '100' when 4 is converted to binary is added to the list.
I wrote as follows.
class Solution:
def countBits(self, num: int) -> List[int]:
ans = [0]
for i in range(1,num+1):
ans.append(ans[i//2] + (i%2))
return ans
# Runtime: 84 ms, faster than 72.90% of Python3 online submissions for Counting Bits.
# Memory Usage: 20.7 MB, less than 5.00% of Python3 online submissions for Counting Bits.
I've been thinking about this problem for a long time. I want to come up with a solution more quickly.
Recommended Posts