云课堂-Python学习笔记（6）

轻轻的

　　一、列表（List）
　　1、内建数据结构，用来存储一系列元素，如：　　　



1 Lst[0] = 5.4
2 Lst[3] False
3 Lst[1:3]=['Hello',2]
　　2、列表与字符串的相同点：
　　索引（[]运算符）
　　切片（[:]）
　　拼接（+）和重复（*）
成员（in运算符）
长度（len()函数）
循环（for）
不同点：
　　使用[]生成，元素之间用逗号分隔
可以包含多种类型的对象，字符串只能是字符
内容是可变的，字符串是不可变的



1 >>> list=[5.4,'Hello',2]
2 >>> list[0] = 'a'
3 >>> list
4 ['a', 'Hello', 2]
5 >>> list[0:2]=[1.2,3,5.6]
6 >>> list
7 [1.2, 3, 5.6, 2]
8 >>> list.append('pyhton')
9 >>> list
10 [1.2, 3, 5.6, 2, 'pyhton']
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 [1.2, 3, 5.6, 2, 'pyhton', 'i', 'm', 'e', 'n', 'g', 'f', 'a', 'n', 'g']
17 >>> list.sort()
18 >>> list
19 [1.2, 2, 3, 5.6, 'a', 'e', 'f', 'g', 'g', 'i', 'm', 'n', 'n', 'pyhton']
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 = [1, 2, 3]
2 b = a // 原来列表
3 b[1] = 4
4 print a[1]
5
6 a = [1, 2, 3]
7 b = a[:] //生成一个新的列表
8 b[1] = 4
9 print a[1]
　　2、交换列表中两个元素的值



1  1 def swap(a,b) :
2  2     tmp = a
3  3     a= b
4  4     b = tmp
5  5 x = 10
6  6 y = 20
7  7 swap(x,y)
8  8 print x,y
9  9
10 10 //下面才可以
11 11 def swap(list,a,b):
12 12     temp = list[a]
13 13     list[a] = list
14 14     list = temp
15 15 x = [10,20,30]
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 = [12,11,4,6,9]
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[mid] == x:
7             return mid
8         elif list[mid] > x:
9             high = mid -1
10         else :
11             low = mid + 1
12     return -1
13     
14 list = [2,6,8,15,20]
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[j] < list[min_index]:
6                 min_index = j
7         list.insert(i,list.pop(min_index))
8         
9 list = [4,15,2,6,8,20]
10 selection_sort(list)
11 print list
方法二如下：


1 def swap(list,a,b):
2     temp = list[a]
3     list[a] = 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[j] < list[min_index]:
11                 min_index = j
12         swap(list,i,min_index)
13         
14 list = [4,15,2,6,8,20]
15 selection_sort2(list)
16 print list
　　2、冒泡排序　　　　



1 def swap(list,a,b):
2     temp = list[a]
3     list[a] = 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[i+1]:
13                 is_exchange = True
14                 swap(list,i,i+1)
15         top -= 1
16        
17 list = [4,15,2,6,8,20]
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[1]
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 = [x**2 for x in range(1,10)]


1 列表推导实现求平均分
2 sum([x[1] for x in students])/len(students)
3
4 students = [['zhang',84],['wang',77],['li',100],['zhao',55]]
5 print sum([x[1] for x in students])/len(students)
6
7 列表解析对输入数字x的因数求和
8 sum([i for i in range(1,x+1) if(x%i ==0)]
9
10 n = int (raw_input());
11 print sum([i for i in range(1,n+1) if n%i ==0 ])
　　七、按成绩从高到底排序：



1 按成绩从高到底排序：
2 students = [['zhang',84],['wang',77],['li',100],['zhao',55]]
3
4 def f(a):    //很简单，只返回a的1号元素
5     return a[1]
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[1],reverse=True)
3 print students
　　练习：给定列表 L = [1, 2, 3, 4]，将列表转换为字符串 '1234'



1 方法一
2 s = ''
3 list = [1,2,3,4]
4 n = 0
5 while n<len(list):
6     s += str(list[n])
7     n+=1
8 print s
9
10 方法二：
11 print ''.join([str(i) for i in list])
　　八、测试题
　　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[mid] == x:
19             return mid
20         elif list[mid] > 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 = [str(tmpNum) for tmpNum in lineList]
4     print("%s%s" % (" " * (NUM - len(lineList)), " ".join(lineList)))
5  
6 for i in range(NUM):
7      if i < 2:
8          list = [1] * (i + 1)
9      else:
10          list[1:-1] = [(tmpNum + list[j]) for j, tmpNum in enumerate(list[1:])]
11      printLine(list)