云课堂-Python学习笔记（6）
一、列表（List）1、内建数据结构，用来存储一系列元素，如：
1 Lst = 5.4
2 Lst False
3 Lst=['Hello',2]
2、列表与字符串的相同点：
索引（[]运算符）
切片（[:]）
拼接（+）和重复（*）
成员（in运算符）
长度（len()函数）
循环（for）
不同点：
使用[]生成，元素之间用逗号分隔
可以包含多种类型的对象，字符串只能是字符
内容是可变的，字符串是不可变的
1 >>> list=
2 >>> list = 'a'
3 >>> list
4 ['a', 'Hello', 2]
5 >>> list=
6 >>> list
7
8 >>> list.append('pyhton')
9 >>> list
10
11 >>> list.extend('zimengfang')
12 >>> list
13 [1.2, 3, 5.6, 2, 'pyhton', 'z', 'i', 'm', 'e', 'n', 'g', 'f', 'a', 'n', 'g
14 >>> list.pop(5)
15 'z'
16
17 >>> list.sort()
18 >>> list
19
20 >>> list.reverse()
21 ['pyhton', 'n', 'n', 'm', 'i', 'g', 'g', 'f', 'e', 'a', 5.6, 3, 2, 1.2]
3、示例、输入10个数字，求其平均值
1 nums = []
2 for i in range(10):
3 nums.append(float(raw_input()))
4 avg = sum(nums) / (len(nums))
5 print avg
sum（）为内建函数，max,min等
二、1、列表赋值
1 a =
2 b = a // 原来列表
3 b = 4
4 print a
5
6 a =
7 b = a[:] //生成一个新的列表
8 b = 4
9 print a
2、交换列表中两个元素的值
11 def swap(a,b) :
22 tmp = a
33 a= b
44 b = tmp
55 x = 10
66 y = 20
77 swap(x,y)
88 print x,y
99
10 10 //下面才可以
11 11 def swap(list,a,b):
12 12 temp = list
13 13 list = list
14 14 list = temp
15 15 x =
16 16 swap(x,0,1)
17 17 print x
3、查找：在列表中查找一个值，并返回该值第一次出现的位置，不存在返回-1
1 def search(list,x):
2 for i in range(len(list)):
3 if list == x:
4 return i
5 retern -1
6
7 list =
8 print search(list,6);
9
10 print list.index(6) //不存在异常
自定义的search函数，如果数字不存在返回-1，而函数index，不存在会出现异常
三、时间复杂度
1、量化一个算法的运行时间为输入的长度
2、不需要显示的计算这些常数
3、大O表示，只保留高阶项
4n+4 = O(n)
137n + 271 = O(n)
n*n*n + 3n = O（n*n）
4、线性查找时间复杂度为：O(n)
四、二分查找：
1、编写函数bi_search,输入一个有序（由大到小）列表和一个值，如果该值在列表中，则返回相应的位置，否则返回-1
2、考虑以下3中情况：
如果输入值小于列表中间的元素，则只需在列表前半部分继续查找
如果输入值大于列表中间的元素，则只需在列表后半部分继续查找
如果输入值等于列表中间的元素，返回该值
1 def bi_search(list,x) :
2 low = 0
3 high = len(list)-1
4 while low <= high:
5 mid = (low + high)/2
6 if list == x:
7 return mid
8 elif list > x:
9 high = mid -1
10 else :
11 low = mid + 1
12 return -1
13
14 list =
15 print bi_search(list,15)
16
17 时间复杂度O（log2 n)
五、排序
1、选择排序，步骤：i）、找到最小的元素、删除 ii）、把最小的元素插入第一位置 iii）、重复上面两步
1 def selection_sort(list):
2 for i in range(len(list)):
3 min_index = i
4 for j in range(i+1,len(list)):
5 if list < list:
6 min_index = j
7 list.insert(i,list.pop(min_index))
8
9 list =
10 selection_sort(list)
11 print list
方法二如下：
1 def swap(list,a,b):
2 temp = list
3 list = list
4 list = temp
5
6 def selection_sort2(list):
7 for i in range(len(list)):
8 min_index = i
9 for j in range(i+1,len(list)):
10 if list < list:
11 min_index = j
12 swap(list,i,min_index)
13
14 list =
15 selection_sort2(list)
16 print list
2、冒泡排序
1 def swap(list,a,b):
2 temp = list
3 list = list
4 list = temp
5
6 def bubble_sort(list):
7 top = len(list)-1
8 is_exchange = True
9 while is_exchange :
10 is_exchange = False
11 for i in range(len(list)-1):
12 if list > list:
13 is_exchange = True
14 swap(list,i,i+1)
15 top -= 1
16
17 list =
18 bubble_sort(list)
19 print list
3、内建函数：
sorted(list)
list.sort()
quicksort()
六、嵌套列表、示例：计算所有学生的平均分
1 students = [['zhang',84],['wang',77],['li',100],['zhao',55]]
2
3 s = 0
4 for student in students:
5 s += student
6 print float(s) / len(students)
1、列表解析或推导
一种由原列表创建新列表的简洁方法：[表达式 for 变量 in 列表 if条件]
1 list = []
2 for x in range(1,10):
3 list.append(x **2)
4 print list
5 列表解析：
6 list =
1 列表推导实现求平均分
2 sum( for x in students])/len(students)
3
4 students = [['zhang',84],['wang',77],['li',100],['zhao',55]]
5 print sum( for x in students])/len(students)
6
7 列表解析对输入数字x的因数求和
8 sum(
9
10 n = int (raw_input());
11 print sum()
七、按成绩从高到底排序：
1 按成绩从高到底排序：
2 students = [['zhang',84],['wang',77],['li',100],['zhao',55]]
3
4 def f(a): //很简单，只返回a的1号元素
5 return a
6
7 students.sort(key=f,reverse=True)
8
9 print students
其实有内嵌函数lambda函数
1、匿名函数
1 >>> def f(x):return x**2
2 ...
3 >>> print f(8)
4 64
5 >>> g = lambda x:x**2
6 >>>
7 >>> print g(8)
8 64
9 >>>
2、lambda函数实现按成绩排序
1 students = [['zhang',84],['wang',77],['li',100],['zhao',55]]
2 students.sort(key=lambda x:x,reverse=True)
3 print students
练习：给定列表 L = ，将列表转换为字符串 '1234'
1 方法一
2 s = ''
3 list =
4 n = 0
5 while n<len(list):
6 s += str(list)
7 n+=1
8 print s
9
10 方法二：
11 print ''.join()
八、测试题
1、编写程序，完成下列题目：（3分）
题目内容：
定义一个 prime() 函数求整数 n 以内（不包括n）的所有素数（1不是素数），并返回一个按照升序排列的素数列表。使用递归来实现一个二分查找算法函数bi_search()，该函数实现检索任意一个整数在 prime() 函数生成的素数列表中位置（索引）的功能，并返回该位置的索引值，若该数不存在则返回 -1。
输入格式:
第一行为正整数 n
接下来若干行为待查找的数字，每行输入一个数字
输出格式：
每行输出相应的待查找数字的索引值
输入样例：
10
2
4
6
7
输出样例：
0
-1
-1
3
时间限制：500ms内存限制：32000kb
1 L1 = []
2 n = int (raw_input())
3 for i in range(2, n):
4 list = []
5 for x in range(2, i/2 + 1):
6 if i % x == 0:
7 list.append(x)
8 if not list:
9 L1.append(i)
10
11
12 def bi_search(list,x) :
13 low = 0
14 high = len(list)-1
15
16 while low <= high:
17 mid = (low + high)/2
18 if list == x:
19 return mid
20 elif list > x:
21 high = mid -1
22 else :
23 low = mid + 1
24 return -1
25
26 numbers = []
27 while(True):
28 input = raw_input()
29 if input.upper() == "":
30 break
31 numbers.append(int(input))
32
33 for i in range(0,len(numbers)):
34 print bi_search(L1,numbers)
2编写程序，完成下列题目：（2分）
题目内容：
帕斯卡三角形，又称杨辉三角形是二项式系数在三角形中的一种几何排列。帕斯卡三角形通常从第0行开始枚举，并且每一行的数字是上一行相邻两个数字的和。在第0行只写一个数字1，然后构造下一行的元素。将上一行中数字左侧上方和右侧上方的数值相加。如果左侧上方或者右侧上方的数字不存在，用0替代。下面给出6行的帕斯卡三角形：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
编写程序，输入帕斯卡三角形的高度 n，然后生成和上面例子一样风格的三角形。
输入格式:
一个正整数 n
输出格式：
相应高度的帕斯卡三角形，两个数字之间有一个空格
输入样例：
6
输出样例：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
时间限制：500ms内存限制：32000kb
1 NUM = int(raw_input())
2 def printLine(lineList):
3 lineList =
4 print("%s%s" % (" " * (NUM - len(lineList)), " ".join(lineList)))
5
6 for i in range(NUM):
7 if i < 2:
8 list = * (i + 1)
9 else:
10 list = [(tmpNum + list) for j, tmpNum in enumerate(list)]
11 printLine(list)
页:
[1]