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 Day16 "344. Reverse String" starting from zero
Basically, I would like to solve the easy acceptance in descending order.
The difficulty level is easy. It's an excerpt from the Top 100 Liked Questions.
Find the element that makes up the majority in the given n size array.
It is assumed that the array is not empty and that the majority of elements are always present.
Example 1: Input: [3,2,3] Output: 3
Example 2: Input: [2,2,1,1,1,2,2] Output: 2
Both are returning the majority.
It's good to use the built-in function count, but I think it's easier to use it because Python has a Counter function.
The difference between the two is
# count:You can use it without importing. Count the number of each element.
nums = [2,2,1,1,1,2,2]
print(nums.count(0))
# 0
print(nums.count(1))
# 3
print(nums.count(2))
# 4
#counter:It cannot be used without importing. Elements can be acquired in descending order of appearance.
from collections import Counter
nums = [2,2,1,1,1,2,2]
num = collections.Counter(nums)
print(num)
# Counter({2: 4, 1: 3})
print(type(c))
# <class 'collections.Counter'>
print(issubclass(type(c), dict))
# True
You can see the difference. This time, we only need to return the one that occupies the majority, so we will consider using counter.
from collections import Counter
class Solution:
def majorityElement(self, nums: List[int]) -> int:
ans = collections.Counter(nums)
return ans.most_common(1)[0][0]
#Runtime: 172 ms, faster than 79.63% of Python3 online submissions for Majority Element.
# Memory Usage: 15.1 MB, less than 7.14% of Python3 online submissions for Majority Element.
At first, you can use ans.keys () [0], right? I thought, but the dictionary would be an error ... So I wrote it simply using the most_common () method included in Counter (returning a list of tuples in the form of (element, number of occurrences) arranged in order of number of occurrences).
I will add if there is another good method.
Recommended Posts