第一章 引言

#倒序输出
count = 10
nums = []
for i in range(count): #由小到大开始整数计数，默认从0开始
	nums.append(i)  #添加，添加到末尾
nums.reverse() #反转
print(nums)
#-----------------------------------------------------------
count = 10
nums = []
for i in range(count):
	nums.insert(0, i) #插入，将i插入到第0个位置/首位
	print(nums)

第一段代码效率会更高

习题1-2
判断字符变位，例如debit card和bad credit
解答：变位词(anagrams)指的是组成两个单词的字符相同，但位置不同的单词。aabbdd和abccab就是一对变位词。
利用collections.Counter

from collections import Counter
num1 = []
num2 = []
word1 = 'debit card'
word2 = 'bad credit'
for i1 in word1:
	nums1 += i1
for i2 in word2:
	nums2 += i2
c = Counter(nums1) #计数功能，返回字典形式
d = Counter(nums2)
if c == d:
	print(True)
else:
	print(False)

第二章 基础知识

黑盒子专栏之list
python列表：数组——它不是由若干个独立的节点相互引用而成的，而是一整块单一连续的内存区块。可直接计算出目标元素在内存中的位置。
其他语言的列表：链表（单向链表/双向链表）——通常是由一系列节点来实现的，其每个节点（尾节点除外）中都有一个指向下一节点（上一节点）的引用。必须从头开始遍历才能找到某个元素所在的位置。
而对于insert插入操作而言，要将新元素插入到列表的首位，这种操作对于链表来说没一次插入都是一样的，但是对于数组而言，每次插入一个元素，都要将数组中所有的元素向右移动一个位置，把首位空出来，再进行插入，甚至在必要时，可能还需要将这些列表元素整体搬到一个更大的数组中。
所以append操作通常会采用一种被称为动态数组或向量的特定解决方案。
渐近记法——时间复杂度
分析算法和数据结构的重要工具，核心思想是提供一种资源表示形式，分析计算时所需要的资源（指时间，有时包括内存），例如我们可以将一个程序所需要的运行时间表示为T(n)=2.4n+7,忽略单位。
渐近记法使用的是一组由希腊字母构成的记号体系，分别是大O，Ω，θ。
大O表示渐近上界，Ω表示渐近下界，θ表示他们的交集。
O和Ω是相互可逆的，如果f属于O(g)，那么g就属于Ω(f)
当n>n0时（n0是自然数），T(n)是小于cn2的，所以T(n)属于O(n2) #n2表示n的平方
交通规则
表2-1
常数级<对数级<线性级<线性对数级<平方级<立方级<多项式级<指数级<阶乘级
渐近表达式代表的都是一个函数集
简单规则
θ(n2+n3+n4+42)=θ(n4) #四次方 加法运算，以最高阶数为准
θ(4.2nlg n)=θ(nlg n) #乘法运算，常数因子忽略
福利规则
θ(f)+θ(g)=θ(f+g)
θ(f)·θ(g)=θ(f·g)

squares = [x**2 for x in seq]
#for x in seq:
#	square = x**2
#	squares.append(square)

#得出seq中所有元素两两之间的乘积之和
s = 0
for x in seq:
	for y in seq:
			s +=x*y
#两层嵌套循环的时间复杂度相当于线性级乘线性级=平方级 n*n=n2
#代码块的复杂度由其先后执行的语句累加而成。
#嵌套循环的复杂度则在此基础上成倍增加

s = 0
for x in seq:
	for y in seq:
			s +=x*y
	for z in seq:
		for w in seq:
			s +=x-w
#复杂度θ(n*(n+n*n))=θ(n3)
#或者说y循环因为占主导地位的z循环而被忽略掉了（y循环复杂度为n，z循环复杂度为n2）

#两个不同的序列seq1和seq2，分别有n和m个元素
s = 0
for x in seq1:
	for y in seq2:
		s +=x*y
#运行时间/复杂度为θ(nm)

#计算序列中各元素之间的乘积之和
s = 0
seq = [3, 4, 5, 6]
n = len(seq)
for i in range(n-1):
    for j in range(i+1, n):
        s += seq[i] * seq[j]
print(s)
#range(5)等价于range(0,5)=[0, 1, 2，3 , 4] ，步长默认为1
#算法：第一个元素乘以后在他后面的元素，第二个元素乘以在他后面的元素，········直到第n-1个乘以第n个元素为止，累加。

算法设计可以被看成是一种通过设计高效算法达成低渐近运行时间的方法，而算法工程则侧重于降低渐近复杂度中的隐藏常量。

timeit计时模块

import timeit
print(timeit.timeit('x = 2 + 3'))
print(timeit.timeit('x = sum(range(10))'))
#或者直接命令行调用
python -m timeit 'x=2+2'

cProfile模块打印函数所有步骤的用时

import cProfile
def a_function():
    x=2+2
    a=0
    y=sum(range(10**3))
    for i in range(y):
        a+=i
    print(x)
    print(y)
    print(a)
cProfile.run('a_function()')

4
499500
124749875250
8 function calls in 0.025 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.025 0.025 < string>:1(< module>)
1 0.025 0.025 0.025 0.025 hello.py:2(a_function)
1 0.000 0.000 0.025 0.025 {built-in method builtins.exec}
3 0.000 0.000 0.000 0.000 {built-in method builtins.print}
1 0.000 0.000 0.000 0.000 {built-in method builtins.sum}
1 0.000 0.000 0.000 0.000 {method ‘disable’ of ‘_lsprof.Profiler’ objects}

还可使用python call graph工具可视化代码调用情况
matplotlib绘图
trace模块： 不会使用。。。。。。

2.3 图与树的实现

图论基础

1. 图G=(V, E)由一组节点V与节点边E组成，如果这些边是有方向的，那么称之为有向图。例如，边(u, v)与边(v, u)，称之为有向图中的反向并行线。相反的，并行线则不允许出现在图中。
2. 自闭环：指向节点本身的边。（只存在于有向图）
3. 邻居：与节点v相邻的节点，称为节点v的邻居。
4. 节点的度数：连接其边的个数。记为d(v)。
5. 对于有向图，入度：指向该点的边；出度：从该点出发的边。还有，入邻点或父节点；出邻点或子节点。
6. 某节点的上一层邻节点（离根节点更近的）称为它的父节点；下一层邻点则成为它的子节点（离叶节点更近的）。
7. 向上的路径中的节点称为前辈节点，向下路径中的节点称为后辈节点。包含节点v以及它所有后代节点的树称为以v为根的子树。
8. 孤点：度数为0。
9. 路径(path)：子图结构，本质都是边线序列。是一种特殊的图结构，主要以子图的形式出现。不能穿越自身，即一条路径中不能包含带有环路的子图。
10. 子路径
11. 无环的路径称之为简单路径。
12. 环路(cycle)：首末相连的路径。
13. 加权图：每条边都有不同的权值，权重w(e)。
14. 如果图结构中任意两点之间都存在路径，那么它就是连通的；对于有向图，忽略方向后它是连通的，那么称之为该图的基础无向连通图。
15. 图中最大的连通子图称为它的连通分量。（包含节点最多的连通图）
16. 在加权图中，一条路径的长度等于各边上的权值之和(边的单位为1)。
17. 无环图：不包含环的图；可以是有向图也可以是无向图。无向的无环图称为森林，它的连通分量称为树。
18. 森林(forest)：无环路图（无环图），这样的连通图就是一棵树。或者说森林就是由一棵或多棵树构成的；一棵树就是连通的森林。
19. 一棵树中，度数为1的节点称为叶节点或外部节点，其他的为内部节点。
20. 平凡图：仅有0个或1个节点的图。
21. 端点
22. 对于有向图，一条从u出发，到达v的边，u称为边的尾端，v称为边的首端。
23. 相邻节点：对于无向图，u，v互为相邻节点。对于所有v的相邻节点组成的集合，称之为v的邻接集N(v) 。
24. 任意两节点互为邻点，该图称之为完全图。
25. 点集W为V的子集，同时边集F是E的子集，则图H=(W, F)是G=(V, E)的子图，或者说G是H的超图，G包含了H。特殊的，如果点集W=V，那么说H和G是共轭的。
26. 根节点/根，根节点一般放在结构的顶端，叶节点在结构的底部，指向根节点的方向是向上的（沿着节点到根的路径）。
27. 在有根树种，根节点视为内部节点而非叶节点，即使这棵树的度数为1。
28. 节点之间的距离：最短路径长度；深度：节点与根节点之间的距离；高度：节点到它的叶节点之间的最长路径长度；整棵树的高度是根节点的高度。
29. 假设T为一个拥有n个节点的无向图，下面的命题是等价的：

• T是一棵树（这是个无环的连通图）
• T是无环图，且有n-1条边
• T是连通图，且有n-1条边
• 其任意两个节点之间有且仅有一条路径
• T是无环图，但任意再添加一条边都会产生环路
• T是连通图，但任意删除一条边都会将它分成两个连通分量

1. 兄弟节点：指的是共享同一个父节点的节点。能指定某个节点的第一个子节点或下一个兄弟节点的节点称之为这个兄弟节点是有序的，在这种情况下，这棵树就是有序树。
2. 生成树：恰好为树的生成子图。通过遍历产生的生成树称为遍历树，它的根节点就是起始节点。在遍历整个图时，生成树增多，导致生成森林的产生，每一个生成森林的分量都有它自己的根节点。
3. 如果某个有向图的基础图是一棵有根树，其所有的节点都可以通过从根节点出发的路径访问到，那么它就被称为有向树形图；图的遍历过程中会产生遍历有向树形图。
4. 有向图只要每条边都指向合适的方向，就可以形成有向无环图（简称DAG），它的结构可以是任意的。也就是说，通过指定合适的方向，就能避免有向环路的产生。

黑盒子专栏之：dict与set
哈希（hash）也翻译作散列（hashing）。Hash算法/哈希算法，是将一个不定长的输入，通过散列函数变换成一个定长的输出，即散列值。
这种散列变换是一种单向运算，具有不可逆性即不能根据散列值还原出输入信息，因此严格意义上讲Hash算法是一种消息摘要算法，不是一种加密算法。常见的hash算法有：SM3、MD5、SHA-1等 。
使用Hash算法的数据结构叫做哈希表，也叫散列表，主要是为了提高查询的效率。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数就是hash函数，存放记录的数组叫做哈希表。在数据结构中应用时，有时需要较高的运算速度而弱化考虑抗碰撞性，可以使用自己构建的哈希函数。

# coding:utf-8
# 自定义哈希函数：通常可利用除留余数、移位、循环哈希、平方取中等方法。
# 下面这个例子就是我自己定义的一个哈希函数，运用了取模运算和异或运算。

def my_hash(x):
    return (x % 7) ^ 2 #^是按位异或逻辑运算符，比如5^6，其实是101^110，结果是011，所以5^6的答案是3

print(my_hash(1)) # 输出结果：3
print(my_hash(2)) # 输出结果：0
print(my_hash(3)) # 输出结果：1
print(my_hash(4)) # 输出结果：6

#--------------------------------------------------
#python内置的hash函数
#hash() 调用

print(hash(1))
print(hash(1.0))    # 相同的数值，不同类型，哈希值是一样的
print(hash("abc"))
print(hash("hello world"))

在运行时发现了一个现象：相同字符串在同一次运行时的哈希值是相同的，但是不同次运行的哈希值不同。这是由于Python的字符串hash算法有一个启动时随机生成secret prefix/suffix的机制，存在随机化现象：对同一个字符串输入，不同解释器进程得到的hash结果可能不同。因此当需要做可重现可跨进程保持一致性的hash，需要用到hashlib模块。
以上参考博客：Hash算法（含python实现）
散列值的构成是在常数级时间内完成的，在对dict和set中的元素进行访问时所耗费的时间都是常数级的。
集合（set）是一个无序的不重复元素序列。 可以使用大括号 { } 或者 set() 函数创建集合
注意：创建一个空集合必须用 set() 而不是 { }，因为 { } 是用来创建一个空字典。
字典（dict）是Python中另一个非常有用的内置数据类型。 列表是有序的对象集合，字典是无序的对象集合。
两者之间的区别在于：字典当中的元素是通过键来存取的，而不是通过偏移存取。 字典是一种映射类型，字典用"{ }"标识，它是一个无序的键(key) : 值(value)对集合。 键(key)必须使用不可变类型。 在同一个字典中，键(key)必须是唯一的。

# python3
# 创建一个set
parame = {value01,value02,...} #打印后自动去重，可以多个字符串
# 或者
set(value) #打印后自动去重，只能是一个字符串

>>> a=set('asdsavss')
>>> a
{'a', 'v', 's', 'd'}

>>> a={'sadsafsa','dgdgdsgf','a','a'}
>>> a
{'a', 'sadsafsa', 'dgdgdsgf'}

>>> a={} #创建一个空字典
>>> a
{}

邻接列表及其类似结构
对于图结构的实现，最直观的方式就是使用邻接列表，针对每个节点设置一个邻接/邻居列表。相当于之前讨论的N(v)函数，代表的是v的邻接节点集，N[v]就是一个v邻居节点集。
用来容纳邻接结构（list或set或dict）的主容器都属于列表类型，它们都以节点编号为索引值。当然，使用dict类型充当主要结构是一种更好的选择。

# 简单明了的邻接集表示方法
# 假设注释段为节点，左侧为对应的邻接节点集。
a, b, c, d, e = range(5)
N = [
{b, c, d}, #a 
{a},       #b
{a, e},    #c
{c, d, e}  #d
]

# 邻接列表
N = [
[b, c, d], #a 
[a],       #b
[a, e],    #c
[c, d, e]  #d
]

# 加权邻接字典, 以下value为假设的权值
N = [
{b:2, c:2, d:1},    #a 
{a:3},              #b
{a:4, e:2},         #c
{c:6, d:5, e:1}     #d
]

# 邻接集的字典表示法
N = {
'a':set('bcd'),
'b':set('a'),
'c':set('ae'),
'd':set('cde')
}

邻接矩阵
图的另一种常见表示法就是邻接矩阵了。