list

常用方法

1. 切片->使用一个冒号

2. 间隔->使用两个冒号

   a = [1,2,3,4,5]
   print(a[-3:])		# [3,4,5]
   print(a[::2])		# [1,3,5]
   print(a[1:5:2])		# [2,4]
   

3. 添加元素

   • lst.append(value)：一次添加一个元素
   • lst,insert(index,value)：在索引为index的位置添加value
     NT：时间复杂度为O(n)
   • lst.extend([1,3])：一次添加一个列表
   • lst+=[1,3]： 效果同extend，注意这个是创建新列表，extend是在原列表上扩展

4. 删除元素
   lst.remove(value)：直接删除lst中值为value的元素，若value出现多次，则只删除第一次
   lst.pop(index)：若不带参数则默认删除lst最后一个元素，带参数则删除此索引的元素
   del lst[2:] ： 删除列表的切片序列

5. in：可以用作遍历，也可以用作判断元素是否在这个列表中
   注意这是个遍历，要是单纯判断元素是否在可以使用set，效率更高

6. 其他常用API

   1. clear：清楚列表所有元素

   2. index：查找某个value的索引

   3. count：统计某个元素出现次数

   4. sort：元素排序，使用key参数定制排序规则

      • 注意：
        • sort是列表的方法，使用时是lst.sort()，对本身lst排序;
        • sorted是一个函数，使用时是sorted(lst)，不改变本身，返回新列表

      # 列表中元素为tuple，据元祖第二个值由小到大排序
      a = [(3,1),(4,1),(1,3),(5,4),(9,-10)]
      a.sort(key=lambda x:x[1])
      print(a)	
      # [(9, -10), (3, 1), (4, 1), (1, 3), (5, 4)]
      

   5. reverse：列表反转

      a = [4,1,2]
      a.reverse()
      print(a)	# [2,1,4]
      

   6. copy：浅拷贝，即只copy一层
      想要实现深拷贝可以使用copy模块中的deepcopy方法

扩展用法

list的这些方法可以很方便的当做stack使用，栈的pop和push在list中都可以O(1)实现
但是list做queue的效率就不够了，一般queue可以用deque实现

list的insert操作时间复杂度为O(n），即每次插入都要往后面移动复制一次👉需要频繁插入的操作都不适用list

还需要注意的是list是可变的，可变对象是不可哈希的，不可哈希的对象不能被映射，所以list不能作dict的键
如果需要使用list对象作键可以将list转成tuple，tuple可哈希，可以作dict的key

tuple

元组是一类不允许添加删除元素的特殊列表，即一旦创建后续不允许修改
tuple一般用在打包和解包处，即若函数有多个返回值时可以打包为一个元祖，赋值到等号左侧变量时解包
若确定对象后面不会被修改，可以使用元祖，因为元祖比list更节省内存

set

常用操作

1. 增
   st.add(value)： 向集合中添加元素
   c = st.copy()

2. 删
   st.remove(value)：删除st中值为value的元素，这里必须保证st中有value，不然会报错
   st.discard(value)：有则删除，没有则不变（与remove一样，但是没有的时候不报错）
   st.pop()：没有参数，随机删除，返回被删除的值

3. 集合运算
   交集：union，|
   并集：intersection，&
   差集：difference(返回值)，difference_update(改自身值)，-
   对称差集：symmetric_difference(返回值)，symmetric_difference_update(改自身值)，^

   lst1 = [1,2,6,7]
   lst2 = [1,2,4,5]
   s1 = set(lst1)
   s2 = set(lst2)
   s3 = s1|s2	# {1, 2, 4, 5, 6, 7}
   s4 = s1.union(s2)# {1, 2, 4, 5, 6, 7}s5 = s1&s2	# {1, 2}
   s6 = s1.intersection(s2)# {1, 2}
   

   s1 = set([1,2,6,7])
   s2 = set([1,2,4,5])
   s3 = s1.symmetric_difference(s2)
   s4 = s1^s2
   print(s3)
   print(s4)
   print(s1)
   s1.symmetric_difference_update(s2)
   print(s1)
   

4. 逻辑判断运算

   # 判断交集是否为空
   x1 = {"a", "b", "c"}
   x2 = {"e", "f", "g"}	
   print(x1.isdisjoint(x2))# 判断x1是否为x2的子集
   x1 = {"a", "b", "c"}
   x2 = {"a", "b", "c", "e", "f", "g"}
   print(x1.issubset(x2))# 判断x2是否为x1的子集，即x1是否包含x2
   x1 = {"a", "b", "c", "e", "f", "g"}
   x2 = {"a", "b", "c"}
   print( x1.issuperset(x2))
   

dict

1. 查找元素

   1. dic[key]：必须要保证有key元素
   2. dic.get(key,‘error’)：查找key，没有时返回‘error’

2. 删除
   dic.pop(key)：删除key节点，返回对应的value

3. .items() .keys() .values() 均做列表输出，使用的时候要小心，都是O(n）的复杂度

4. 排序
   sorted函数可以对字典进行排序处理，排序的结果放在一个列表中，然后返回这个列表

   dic={'a':1,'c':2,'b':5,'z':3,'d':0}
   print(sorted(dic))	# 默认对key排序输出
   print(sorted(dic.values()))
   print(sorted(dic.items(),key=lambda x:x[0]))
   print(sorted(dic.items(),key=lambda x:x[1]))
   # 对字典的排序实质上是把dict的内容用items()转换成一个个元祖，利用list对内容对二元祖的排序
   

deque

collections：python标准库，数据结构常用模块，常用类型有：deque、counter、defaultdict、OrderedDict、namedtuple

deque可以以近似O(1)的性能在deque的两端插入和删除元素

1. 增

   • 元素

     • dq.append(元素)：右端插入
     • dq.appendleft(元素)：左端插入
     • dq.insert(index,value)：在指定位置插入

   • 列表

     • dq.extend(列表)：右端扩展
     • dq.extendleft(列表)：左端扩展
2. 删
   dq.pop()：默认删除最右端元素并返回值（若dq为空，会报错）
   dq.pop(left)：默认删除最左段元素并返回值，若dq为空会报错
   dq.remove(value)：删除第一次出现的value（如无则报错）
3. 查
   1. num=dq.count()：统计元素个数
4. 其他操作
   • dq.rotate(n)：向右侧循环移动n步（若n为负数，则向左）
   • maxlen属性：只读属性，在创建deque时作为参数指定deque的最大长度

counter

属于collections 集合模块，能够简洁、高效的实现统计计数。
counter是dict字典的子类，拥有类似字典的key和value，但key为待计数的元素，value为对应元素出现的次数

counter和dict类似又有差别，在CSP中先用DICT就好啦，这里先不再展开

orderedDict

有序字典，与dict类似，只有一点不同，就是键值对的顺序会保留插入时的顺序

defaultfict

ChinaMap

heapq

heapq库是python的标准库之一，提供了构建小顶堆的方法和对小顶堆的基本操作方法，可以用于实现堆排序算法