工作日,周三,实验室线路改造装修,工地一样,唉,来,今天和车神哥一起来提升自己的Python编程和面试能力吧,刷天梯~
以下为我的天梯积分规则:
每日至少一题:一题积分+10分
若多做了一题,则当日积分+20分(+10+10)
若做了三道以上,则从第三题开始算+20分(如:做了三道题则积分-10+10+20=40;做了四道题则积分–10+10+20+20=60)初始分为100分
若差一天没做题,则扣积分-10分(周六、周日除外注:休息)
坚持!!!
初级算法
刷题目录
数组
题干
给定两个数组,编写一个函数来计算它们的交集。
示例1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2,2]
示例2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[4,9]
分析:
目标是求得两数组的交集,那么,我们确定第一个数组的每一个数的个数,然后再去检索第二个数组中是否含有这个数,且此数的个数是多少个,求min()取最小值即可,即为交集的个数。
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
n1 = len(nums1)
sum1 = []
# 先对两数组进行排序
nums1.sort()
nums2.sort()
for i_1 in range(n1):
Minima = min(nums1.count(nums1[i_1]), nums2.count(nums1[i_1])) # 取最小的值则为交集
if Minima > 0:
sum1.append(nums1[i_1])
nums2.remove(nums1[i_1]) # 如果有相同的出现,则删除nums2数组的同一值,以防重复输出
return sum1
效果嘛,感觉还能再继续优化
优化
好!咱们再继续优化优化算法
针对题干中进阶的问题,我们再继续改进下,nums1的数比nums2的少很多,那么我们是否需要判断数组的数,将小的放在前进行迭代,这样可以节省很多时间。然后若已经排好序,那么我们可以省去排序操作。
再来:
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
n1 = len(nums1)
n2 = len(nums2)
sum1 = []
sum2 = []
# 判断两数组的数谁最多
if n1 > n2:
for idx in range(n2):
Minima1 = min(nums1.count(nums2[idx]), nums2.count(nums2[idx]))
if Minima1 > 0:
sum1.append(nums2[idx])
nums1.remove(nums2[idx])
return sum1
else:
for i_1 in range(n1):
Minima2 = min(nums1.count(nums1[i_1]), nums2.count(nums1[i_1]))
if Minima2 > 0:
sum2.append(nums1[i_1])
nums2.remove(nums1[i_1]) # 如果有相同的出现,则删除nums2数组的同一值,以防重复输出
return sum2
效果还是不是很好,再优化
dict_1 = collections.defaultdict(int)
dict_2 = collections.defaultdict(int)
for x in nums1:
dict_1[x] += 1
for x in nums2:
dict_2[x] += 1
result = []
for k in dict_1.keys():
result.extend([k] * min(dict_1[k], dict_2[k]))
return result