23.02.09 Today’s Leetcode
2306. Naming a Company (hard)
첫번째 Solution : O(n^2)
class Solution:
def distinctNames(self, ideas: List[str]) -> int:
idea_ = set(ideas)
n = len(ideas)
res = 0
for i in range(n):
for j in range(n):
a, b = ideas[i], ideas[j]
a_, b_ = b[0] + a[1:], a[0] + b[1:]
if a_ in idea_ or b_ in idea_:
continue
else:
res += 1
# print(a_, b_)
return res
두번째 Solution : O(n^2), group with same first letters 교집합을 이용한 풀이.
class Solution:
def distinctNames(self, ideas: List[str]) -> int:
# Group idea by their initials.
initial_groups = [set() for _ in range(26)]
for idea in ideas:
initial_groups[ord(idea[0]) - ord('a')].add(idea[1:])
answer = 0
# Calculate number of valid names from every pair of groups.
for i in range(25):
for j in range(i + 1, 26):
# Get the number of mutual suffixes.
num_of_mutual = len(initial_groups[i] & initial_groups[j])
# Valid names are only from distinct suffixes in both groups.
# Since we can swap a with b and swap b with a to create two valid names, multiple answer by 2.
answer += 2 * (len(initial_groups[i]) - num_of_mutual) * (len(initial_groups[j]) - num_of_mutual)
return answer
350. Intersection of Two Arrays II (easy)
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
a, b = Counter(nums1), Counter(nums2)
res = []
for key in a.keys() & b.keys():
for i in range(min(a[key], b[key])):
res.append(key)
return res
121. Best Time to Buy and Sell Stock (easy)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
local_max = prices[0]
local_min = prices[0]
res = 0
for price in prices:
if price < local_min:
local_min = price
local_max = price
local_max = max(local_max, price)
res = max(res, local_max - local_min)
return res