Python第四周 学习笔记（2）
直接插入排序：[*]在未排序序列中，构建一个子排序序列，直至全部数据排序完成
[*]将待排序的数，插入到已经排序的序列中合适的位置
[*]增加一个哨兵，放入待比较值，让它和后面已经排好序的序列比较，找到合适的插入点 方法一：
def insertion_sort(lst):
count_swap = 0
count_iter = 0
for i in range(1, len(lst)):
temp = lst
j = i - 1
count_iter += 1
while j >= 0 and temp < lst:
lst = lst
j -= 1
count_swap += 1
lst = temp
return lst, count_swap, count_iter
方法二：
lst =
nums = + lst
count_swap = 0
count_iter = 0
length = len(nums)
for i in range(2,length):
nums = nums
j = i - 1
count_iter += 1
while nums>nums:
nums = nums
j -= 1
count_swap +=1
nums = nums
print(nums, count_swap, count_iter)
[*]时间复杂度O(n**2)
[*]稳定排序算法
[*]使用在小规模数据比较
[*]优化点：如果比较操作代价大的话，可采用二分法查找，即二分查找插入排序
习题解析
1、求和
对下面集合中随机取数字，要求取出的数字是3的倍数但不能是4的倍数，成功取到10个数字并对取到的所有数字求和输出
{5,10,3,8,6,10,9,15,24,30,27,48,24}
lst = {5,10,3,8,6,10,9,15,24,30,27,48,24}
result = []
import random
while True:
temp = random.sample(lst, 1)
if temp % 3 == 0 and temp % 4 != 0:
result.append(temp)
if len(result) >= 10:
break
print(result, sum(result))
2、选取文件
选出含有ftp的链接，且文件类型是gz或者xz的文件，要求打印其文件名，文件名升序排列
'ftp://ftp.astron.com/pub/file/file-5.14.tar.gz',
'ftp://ftp.gmplib.org/pub/gmp-5.1.2/gmp-5.1.2.tar.xz',
'ftp://ftp.vim.org/pub/vim/unix/vim-7.3.tar.bz2',
'http://anduin.linuxfromscratch.org/sources/LFS/lfs-packages/conglomeration//iana-etc/iana-etc-2.30.tar.bz2',
'http://anduin.linuxfromscratch.org/sources/other/udev-lfs-205-1.tar.bz2',
'http://download.savannah.gnu.org/releases/libpipeline/libpipeline-1.2.4.tar.gz',
'http://download.savannah.gnu.org/releases/man-db/man-db-2.6.5.tar.xz',
'http://download.savannah.gnu.org/releases/sysvinit/sysvinit-2.88dsf.tar.bz2',
'http://ftp.altlinux.org/pub/people/legion/kbd/kbd-1.15.5.tar.gz',
'http://mirror.hust.edu.cn/gnu/autoconf/autoconf-2.69.tar.xz',
'http://mirror.hust.edu.cn/gnu/automake/automake-1.14.tar.xz'
lst = [
'ftp://ftp.astron.com/pub/file/file-5.14.tar.gz',
'ftp://ftp.gmplib.org/pub/gmp-5.1.2/gmp-5.1.2.tar.xz',
'ftp://ftp.vim.org/pub/vim/unix/vim-7.3.tar.bz2',
'http://anduin.linuxfromscratch.org/sources/LFS/lfs-packages/conglomeration//iana-etc/iana-etc-2.30.tar.bz2',
'http://anduin.linuxfromscratch.org/sources/other/udev-lfs-205-1.tar.bz2',
'http://download.savannah.gnu.org/releases/libpipeline/libpipeline-1.2.4.tar.gz',
'http://download.savannah.gnu.org/releases/man-db/man-db-2.6.5.tar.xz',
'http://download.savannah.gnu.org/releases/sysvinit/sysvinit-2.88dsf.tar.bz2',
'http://ftp.altlinux.org/pub/people/legion/kbd/kbd-1.15.5.tar.gz',
'http://mirror.hust.edu.cn/gnu/autoconf/autoconf-2.69.tar.xz',
'http://mirror.hust.edu.cn/gnu/automake/automake-1.14.tar.xz'
]
result = for i in lst if i.find('ftp') != - 1 and (i.rpartition('.')[- 1] in ['gz', 'xz'])]
result.sort()
print(result)
3、转置矩阵
随机生成4*4的方阵所有数据，打印出来
在此矩阵上求转置矩阵并打印出来
import random
matrix = []
for _ in range(4):
temp = []
for __ in range(4):
temp.append(random.randint(0, 100))
matrix.append(temp)
) for i in range(4)]
print('---------------------------------')
for i in range(len(matrix)):
for j in range(i, len(matrix)):
if i == j:
continue
matrix, matrix = matrix, matrix
) for i in range(4)]
4、生成随机的20个ID
ID格式要求：
时间戳_三位随机数字号码_8位随机小写字母
1506571959_089_xxkeabef
datetime.datetime.now().timestamp() 返回的是时间戳，但是带微秒
import random
import datetime
lst=+'_'+'{:>03}'.format(str(random.randint(0, 100)))+'_'+''.join('abcdefghijklmnopqrstuvwxyz' for _ in range(8)) for _ in range(20)]
print(lst)
5、去除重复数字
数字在上面的列表中，要得到一个没有重复数字的升序列表
要求使用2种方法完成：
1、使用集合完成去重
2、只使用列表完成去重，不使用set或者dict（有能力选做）
lst =
result=sorted(list(set(lst)))
print(result)
lst =
result = []
for i in lst:
if i in result:
continue
result.append(i)
print(sorted(result))
6、排序
375 3.5 6 20 9 -20 68
对上面的数字实现冒泡排序
lst =
length = len(lst)
for i in range(length - 1):
flag = False
for j in range(i + 1,length):
if lst > lst:
flag = True
lst, lst = lst, lst
if not flag:
break
print(lst)
7、第6题实现选择排序
lst =
length = len(lst)
for i in range(length // 2):
maxindex = i
minindex = length - i - 1
minorigin = length - i - 1
for j in range(i + 1,length - i):
if lst > lst:
maxindex = j
if lst < lst:
minindex = length - j - 1
if i != maxindex:
lst, lst = lst, lst
if minindex == i:
minindex = maxindex
if minorigin != minindex:
lst, lst = lst, lst
print(lst)
8、判断密码强弱
要求密码必须由 10-15位 指定字符组成：
十进制数字
大写字母
小写字母
下划线
要求四种类型的字符都要出现才算合法的强密码
例如：Aatb32_67mnq，其中包含大写字母、小写字母、数字和下划线，是合格的强密码
dict_lalpha =
dict_ualpha =
dict_digit =
print('{}\n{}\n{}'.format(dict_digit,dict_ualpha,dict_lalpha))
a='Aatb32_67mnq'
#dic={k:0 for v,k in enumerate(a)}
flag_l = False
flag_u = False
flag_d = False
if len(a) <10 or len(a)>15:
print('Wrong')
elif a.find('_') == -1:
print('Weak')
else:
for i in a:
if i in dict_lalpha:
flag_l = True
if i in dict_ualpha:
flag_u = True
if i in dict_digit:
flag_d = True
if flag_l and flag_d and flag_u:
print('Strong')
else:
print('Weak')
9、日志统计
状态200的不同jsp页面访问次数
统计不同类型文件的访问次数，文件类型有静态类（js、css）、图片类（jpg、jpeg、gif、png）、动态类(action、jsp、do)
日志如下：
lst=[
'116.226.208.136 - - "GET /js/check.js HTTP/1.1" 304 -',
'59.53.22.67 - - "GET /jquery/jquery.datepick.css HTTP/1.1" 304 -',
'117.93.56.165 - - "GET /jquery/jquery-1.4.2.js HTTP/1.1" 304 -',
'106.39.189.200 - - "GET /jquery/jquery.datepick.js HTTP/1.1" 304 -',
'219.146.71.17 - - "GET /jquery/jquery.datepick-zh-CN.js HTTP/1.1" 304 -',
'111.11.83.162 - - "GET /images/shim.gif HTTP/1.1" 304 -',
'117.93.56.165 - - "GET /images/button_ok.gif HTTP/1.1" 304 -',
'111.206.221.200 - - "GET /images/button_cancel.gif HTTP/1.1" 304 -',
'112.80.144.85 - - "GET /user/list.jsp HTTP/1.1" 200 7644',
'117.148.200.56 - - "GET /images/i_edit.gif HTTP/1.1" 304 -',
'183.12.49.80 - - "GET /images/i_del.gif HTTP/1.1" 304 -',
'175.19.57.147 - - "GET /images/button_view.gif HTTP/1.1" 304 -',
'117.136.63.218 - - "GET /user/list.jsp HTTP/1.1" 200 7644',
'157.55.39.102 - - "GET /login.jsp HTTP/1.1" 200 2607',
'111.206.221.68 - - "POST /user_login.action HTTP/1.1" 200 2809',
'117.93.56.165 - - "POST /user_login.action HTTP/1.1" 302 -',
'223.98.218.205 - - "GET /login/home.jsp HTTP/1.1" 200 743',
'117.136.97.78 - - "GET /login/welcome.jsp HTTP/1.1" 200 1142',
'111.206.221.68 - - "GET /login.jsp HTTP/1.1" 200 803',
'117.93.56.165 - - "GET /login/top.jsp HTTP/1.1" 200 2052',
'111.206.221.68 - - "GET /login.jsp HTTP/1.1" 200 1113'
]
diff = {'static': 0, 'pic' : 0, 'dynamic' : 0}
result={}
temp=[]
for i in lst:
status = i.rpartition('"')[-1].strip().rpartition(' ')
name = i.partition('"')[-1].partition('"').split(' ').rpartition('/')[-1]
if status == '200' and name.rpartition('.')[-1] == 'jsp':
if name in temp:
result += 1
else:
result = 1
temp.append(name)
if name.rpartition('.')[-1] in ('js','css'):
diff['static']+=1
elif name.rpartition('.')[-1] in ('jpg','jpeg','gif','png'):
diff['pic']+=1
elif name.rpartition('.')[-1] in ('action','jsp','do'):
diff['dynamic']+=1
print(result)
print(diff)
10、打印矩阵外圈
1 2 6 7
3 5 8 13
4 9 1214
10111516
打印顺序为1,2,6,7,13,14,16,15,11,10,4,3
from copy import deepcopy
matrix = [,,,]
reverse_matrix = deepcopy(matrix)
for i in range(len(reverse_matrix)):
for j in range(i, len(reverse_matrix)):
if i == j:
continue
reverse_matrix, reverse_matrix = reverse_matrix, reverse_matrix
reverse_matrix.reverse()
result=matrix+(reverse_matrix)+((matrix)[::-1])+((reverse_matrix)[::-1])
result.pop()
print(result)
11、挑战题：
打印矩阵元素
1 2 6 7
3 5 8 13
4 9 1214
10111516
之字形打印结果为1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
matrix = [,,,]
result=[]
length=len(matrix)
for i in range(length * 2 - 1):
k = 0
temp=[]
if i <= length-1:
for j in range(i+1):
k = i - j
temp.append(matrix)
if i % 2 ==1:
temp.reverse()
if i > length-1:
for j in range(length -1, i - length, -1):
k = i - j
temp.append(matrix)
if i % 2 != 1:
temp.reverse()
result += temp
print(result)
12、编写一个函数，能够接受至少2个参数，返回最小值和最大值
def min_max(x,y,*args): max=0
min=0
if x > y:
max=x
min = y
else:
max = y
min = x
for i in args:
if i > max:
max = i
if i < min:
min= i
return {'min':min, 'max':max}
13、编写一个函数，接受一个参数n，n为正整数，左打印方式。要求数字必须对齐
def triangle(n): length = 3 * n
for i in range(1,n + 1):
line = []
for j in range(1,n + 1):
line.append( str(j) if i >= j else ' ')
print('{:>{}}'.format(' '.join(line[::-1]),length))
def triangle(n): tail = ' '.join(str(i) for i in range(n, 0, -1))
width = len(tail)
for i in range(1, n):
print('{:>{}}'.format(' '.join(str(j) for j in range(i, 0, -1)),> print(tail)
14、编写一个函数，接受一个参数n，n为正整数，右打印方式。要求数字必须对齐
def triangle(n): length = 3 * n
for i in range(1,n + 1):
line = []
for j in range(1,n + 1):
line.append(str(j) if i<= n - j + 1 else ' ')
print('{:>{}}'.format(' '.join(line[::-1]),length))
def triangle(n): head = ' '.join(str(i) for i in range(n, 0, -1))
width = len(head)
print(head)
for i in range(len(head)):
if head == ' ':
print(' ' * i, head)
15、求n的阶乘（使用递归）
def fac(n): if n == 1:
return 1
return n * fac(n - 1)
16、将一个数逆序放入列表中（使用递归）
def reverse(x, lst = None): if lst is None:
lst = []
x, y = divmod(n, 10)
lst.append(y)
if x == 0:
return lst
return reverse(x, lst)
17、猴子吃桃（使用递归）
def peach(days= 10): if days == 1:
return 1
return (peach(days - 1) + 1) * 2
页:
[1]