每周一课：L15 Caterpillar method(15.2
2019-02-20 本文已影响1人
AiFany
0.png
P15.2 CountDistinctSlices
Count the number of distinct slices (containing only unique numbers).
-
P15.2 不同切片的个数
计算不同切片(切片中的元素均是不同的)的个数
给定一个整数M和一个由N个非负整数组成的非空数组A。数组A中的所有整数都不大于M。
一对整数(P, Q)，满足0 ≤ P ≤ Q < N，称为数组A的切片。切片由元素A[P], A[P + 1], ..., A[Q]组成。不同切片指的是切片中的元素都是唯一的。也就是说，在不同切片中没有重复的元素。
例如，考虑整数M=6和数组A：
A[0]=3，A[1]=4，A[2]=5，A[3]=5，A[4]=2
有九个不同切片：（0，0），（0，1），（0，2），（1，1），（1，2），（2，2），（3，3），（3，4）和（4，4）。
目标是计算不同切片的个数。
编写函数：
def solution(M, A)
给定一个整数M和一个由N个整数组成的非空数组A，则返回不同切片的个数。如果不同切片的数量大于1,000,000,000，则函数应返回1,0000,000,000。例如，针对上面的例子，函数应该返回9。
假定：
- N是区间[1，100,000]内的整数；
- M是区间[0，100,000]内的整数；
- 数组A的每个元素都区间[0，M]内的整数；
- 解题思路
首先数组A的每个元素都可以构成一个不同切片。 如果A[a:b+1]中不存在相同的元素，则可以构成(b-a+1)*(b-a)/2个不同切片。遍历数组A，如果出现了之前的元素，则就按照上面的公式统计已经遍历过的数组所能构成的不同切片的个数。然后更新起始的索引a，此时需要减去这个索引当刚才结束索引b的这一部分可构成的不同切片的个数。
- Python3代码
# -*- coding：utf-8 -*-
# &Author AnFany
# Lesson 15：Caterpillar method
# P 15.2 CountDistinctSlices
def computer(start, end):
"""
计算从start到end开始，连续组合的个数
:param start: 起始点
:param end: 终点
:return: 返回所有连续组合的个数
start：2
end:4
连续的组合分别为(2, 3), (2, 4), (3, 4)
因此返回3
"""
return int((end - start + 1) * (end - start + 1 - 1) / 2)
def solution(M, A):
"""
返回数组A中所有不同切片的个数
:param M: 数组A中的元素的最大值不大于此数
:param A: 数组
:return: 数组不同切片的个数
"""
sum_times = len(A) # 每个元素构成的切片都是不同切片
existed = {}
start = 0 # 计算不同切片个数的起始索引
end = 0
for index, value in enumerate(A):
end = index
if value in existed:
if existed[value] >= start:
sum_times += computer(start, index-1)
sum_times -= computer(existed[value] + 1, index-1) # 减去下一次计算会重复的部分
start = existed[value] + 1 # 更新起始索引
if sum_times >= 1e9:
return 1000000000
existed[value] = index
sum_times += computer(start, end)
return min(sum_times, 1000000000)
- 结果
image
点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。
image
image
