算法练习 9 ：马路上的路灯

题目描述：

城市E的马路上有很多路灯，每两个相邻路灯之间的间隔都是1公里。小赛是城市E的领导，为了使E城市更快更好的发展，需要在城市E的一段长度为M的主干道上的一些区域建地铁。这些区域要是建了地铁，就需要挪走相应的路灯。可以把长度为M的主干道看成一个数轴，一端在数轴0的位置，另一端在M的位置；数轴上的每个整数点都有一个路灯。要建地铁的这些区域可以用它们在数轴上的起始点和终止点表示，已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的路灯（包括区域端点处的两个路灯）移走。你能帮助小赛计算一下，将这些路灯移走后，马路上还有多少路灯？

算法思路分析：

1、输入马路长度M，和N个需要建地铁区域的路段个数N；

2、输入N段路段的起点和终点坐标start、end；

3、将所有的节点存入set(因为这里的路灯是一个坐标一个，不管开始和结尾重不重合只要有这一点，路灯就得移除)，set的特点就是没有重复元素；

3、总的路灯数（M+1）-Set的大小（即需要移除的路灯数len(set)）；

代码练习：

if __name__ == "__main__":    while 1:        input_raw = raw_input()        M = int(input_raw.split()[0])        N = int(input_raw.split()[1])        set_point = set()        for i in range(N):            area = raw_input()            start = int(area.split()[0])            end = int(area.split()[1])            for j in range(start, end + 1):                set_point.add(j)        print M + 1 - len(set_point)

基础知识补充：

1、set：

set() 函数创建一个无序不重复元素集，可进行关系测试，删除重复数据，还可以计算交集、差集、并集等。

增加

集合元素的增加支持两种类型，单个元素的增加用add方法，对序列的增加用update方法。add的作用类似列表中的append，而update类似extend方法。update方法可以支持同时传入多个参数：

>>> a={1,2}>>> a.update([3,4],[1,2,7])>>> a{1, 2, 3, 4, 7}>>> a.update("hello")>>> a{1, 2, 3, 4, 7, 'h', 'e', 'l', 'o'} #序列>>> a.add("hello")>>> a{1, 2, 3, 4, 'hello', 7, 'h', 'e', 'l', 'o'} #单个元素

注：增加已有的元素不会对集合产生影响，也不会抛出异常

删除

集合删除单个元素有两种方法，两者的区别是在元素不在原集合中时是否会抛出异常，set.discard(x)不会，set.remove(x)会抛出KeyError错误：

>>> a={1,2,3,4}>>> a.discard(1)>>> a{2, 3, 4}>>> a.discard(1)>>> a{2, 3, 4}>>> a.remove(1)Traceback (most recent call last):  File "<input>", line 1, in <module>KeyError: 1

集合操作

• 并集：set.union(s),也可以用a|b计算
• 交集：set.intersection(s)，也可以用a&b计算
• 差集：set.difference(s)，也可以用a-b计算
• 求对称差集：set.symmetric_difference(s)，相当于两个集合互求差集后再求并集，其实就是返回两个集合中只出现一次的元素，也可以用a^b计算。

>>> a={1,2,3,4}>>> b={3,4,5,6}>>> a.symmetric_difference(b){1, 2, 5, 6}

• set.update(s)操作相当于将两个集合求并集并赋值给原集合，其他几种集合操作也提供各自的update版本来改变原集合的值，形式如intersection_update(),也可以支持多参数形式。

包含关系

两个集合之间一般有三种关系，相交、包含、不相交。在Python中分别用下面的方法判断：

• set.isdisjoint(s)：判断两个集合是不是不相交
• set.issuperset(s)：判断集合是不是包含其他集合，等同于a>=b
• set.issubset(s)：判断集合是不是被其他集合包含，等同于a<=b

如果要真包含关系，就用符号操作>和<。

不变集合

Python提供了不能改变元素的集合的实现版本，即不能增加或删除元素，类型名叫frozenset，使用方法如下：

>>> a = frozenset("hello")>>> afrozenset({'l', 'h', 'e', 'o'})

需要注意的是frozenset仍然可以进行集合操作，只是不能用带有update的方法。如果要一个有frozenset中的所有元素的普通集合，只需把它当作参数传入集合的构造函数中即可：

>>> a = frozenset("hello")>>> a = set(a)>>> a.add(12)>>> a{'l', 12, 'h', 'e', 'o'}

----------------------------------------------------------------------------------------------------------

详细内容请关注公众号：目标检测和深度学习

----------------------------------------------------------------------------------------------------------