|
|
直接插入排序：
- 在未排序序列中，构建一个子排序序列，直至全部数据排序完成
- 将待排序的数，插入到已经排序的序列中合适的位置
- 增加一个哨兵，放入待比较值，让它和后面已经排好序的序列比较，找到合适的插入点 方法一：
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[j]:
lst[j + 1] = lst[j]
j -= 1
count_swap += 1
lst[j + 1] = temp
return lst, count_swap, count_iter
方法二：
lst = [1, 9, 8, 5, 6, 7, 4, 3, 2]
nums = [0] + lst
count_swap = 0
count_iter = 0
length = len(nums)
for i in range(2,length):
nums[0] = nums
j = i - 1
count_iter += 1
while nums[j]>nums[0]:
nums[j+1] = nums[j]
j -= 1
count_swap +=1
nums[j + 1] = nums[0]
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[0] % 3 == 0 and temp[0] % 4 != 0:
result.append(temp[0])
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 = [i.rpartition('/')[- 1] 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)
[print(matrix) for i in range(4)]
print('---------------------------------')
for i in range(len(matrix)):
for j in range(i, len(matrix[0])):
if i == j:
continue
matrix[j], matrix[j] = matrix[j], matrix[j]
[print(matrix) for i in range(4)]
4、生成随机的20个ID
ID格式要求：
时间戳_三位随机数字号码_8位随机小写字母
1506571959_089_xxkeabef
datetime.datetime.now().timestamp() 返回的是时间戳，但是带微秒
import random
import datetime
lst=[str(datetime.datetime.now().timestamp()).split('.')[0]+'_'+'{:>03}'.format(str(random.randint(0, 100)))+'_'+''.join('abcdefghijklmnopqrstuvwxyz'[random.randint(0,25)] for _ in range(8)) for _ in range(20)]
print(lst)
5、去除重复数字
[29, 30, 37, 22, 59, 75, 79, 41, 61, 75, 75, 78, 63, 52, 44, 20, 27, 29, 48, 66, 60, 36, 67, 73, 41, 54, 66, 46, 74, 47, 61, 23, 38, 61, 51, 55, 48, 59, 28, 68, 65, 74, 73, 58, 29, 31, 53, 31, 61, 22, 44, 33, 21, 41, 21, 35, 32, 59, 76, 32, 45, 78, 29, 65, 76, 70, 54, 22, 32, 52, 62, 42, 41, 73, 72, 64, 56, 50, 40, 64, 41, 47, 68, 73, 27, 69, 64, 21, 78, 57, 61, 27, 27, 66, 23, 21, 53, 40, 28, 64]
数字在上面的列表中，要得到一个没有重复数字的升序列表
要求使用2种方法完成：
1、使用集合完成去重
2、只使用列表完成去重，不使用set或者dict（有能力选做）
lst = [29, 30, 37, 22, 59, 75, 79, 41, 61, 75, 75, 78, 63, 52, 44, 20, 27, 29, 48, 66, 60, 36, 67, 73, 41, 54, 66, 46, 74, 47, 61, 23, 38, 61, 51, 55, 48, 59, 28, 68, 65, 74, 73, 58, 29, 31, 53, 31, 61, 22, 44, 33, 21, 41, 21, 35, 32, 59, 76, 32, 45, 78, 29, 65, 76, 70, 54, 22, 32, 52, 62, 42, 41, 73, 72, 64, 56, 50, 40, 64, 41, 47, 68, 73, 27, 69, 64, 21, 78, 57, 61, 27, 27, 66, 23, 21, 53, 40, 28, 64]
result=sorted(list(set(lst)))
print(result)
lst = [29, 30, 37, 22, 59, 75, 79, 41, 61, 75, 75, 78, 63, 52, 44, 20, 27, 29, 48, 66, 60, 36, 67, 73, 41, 54, 66, 46, 74, 47, 61, 23, 38, 61, 51, 55, 48, 59, 28, 68, 65, 74, 73, 58, 29, 31, 53, 31, 61, 22, 44, 33, 21, 41, 21, 35, 32, 59, 76, 32, 45, 78, 29, 65, 76, 70, 54, 22, 32, 52, 62, 42, 41, 73, 72, 64, 56, 50, 40, 64, 41, 47, 68, 73, 27, 69, 64, 21, 78, 57, 61, 27, 27, 66, 23, 21, 53, 40, 28, 64]
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 = [375, 3.5, 6, 20, 9, -20, 68]
length = len(lst)
for i in range(length - 1):
flag = False
for j in range(i + 1,length):
if lst > lst[j]:
flag = True
lst, lst[j] = lst[j], lst
if not flag:
break
print(lst)
7、第6题实现选择排序
lst = [375, 3.5, 6, 20, 9, -20, 68]
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[j] > lst[maxindex]:
maxindex = j
if lst[length - j - 1] < lst[minindex]:
minindex = length - j - 1
if i != maxindex:
lst, lst[maxindex] = lst[maxindex], lst
if minindex == i:
minindex = maxindex
if minorigin != minindex:
lst[minorigin], lst[minindex] = lst[minindex], lst[minorigin]
print(lst)
8、判断密码强弱
要求密码必须由 10-15位 指定字符组成：
十进制数字
大写字母
小写字母
下划线
要求四种类型的字符都要出现才算合法的强密码
例如：Aatb32_67mnq，其中包含大写字母、小写字母、数字和下划线，是合格的强密码
dict_lalpha = [chr(i) for i in range(97,123)]
dict_ualpha = [chr(i) for i in range(65,91)]
dict_digit = [str(i) for i in range(10)]
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 - - [28/Apr/2015:09:01:38 +0800] "GET /js/check.js HTTP/1.1" 304 -',
'59.53.22.67 - - [28/Apr/2015:09:01:38 +0800] "GET /jquery/jquery.datepick.css HTTP/1.1" 304 -',
'117.93.56.165 - - [28/Apr/2015:09:01:38 +0800] "GET /jquery/jquery-1.4.2.js HTTP/1.1" 304 -',
'106.39.189.200 - - [28/Apr/2015:09:01:38 +0800] "GET /jquery/jquery.datepick.js HTTP/1.1" 304 -',
'219.146.71.17 - - [28/Apr/2015:09:01:38 +0800] "GET /jquery/jquery.datepick-zh-CN.js HTTP/1.1" 304 -',
'111.11.83.162 - - [28/Apr/2015:09:01:38 +0800] "GET /images/shim.gif HTTP/1.1" 304 -',
'117.93.56.165 - - [28/Apr/2015:09:01:38 +0800] "GET /images/button_ok.gif HTTP/1.1" 304 -',
'111.206.221.200 - - [28/Apr/2015:09:01:38 +0800] "GET /images/button_cancel.gif HTTP/1.1" 304 -',
'112.80.144.85 - - [28/Apr/2015:09:01:46 +0800] "GET /user/list.jsp HTTP/1.1" 200 7644',
'117.148.200.56 - - [28/Apr/2015:09:01:46 +0800] "GET /images/i_edit.gif HTTP/1.1" 304 -',
'183.12.49.80 - - [28/Apr/2015:09:01:46 +0800] "GET /images/i_del.gif HTTP/1.1" 304 -',
'175.19.57.147 - - [28/Apr/2015:09:01:46 +0800] "GET /images/button_view.gif HTTP/1.1" 304 -',
'117.136.63.218 - - [28/Apr/2015:09:05:46 +0800] "GET /user/list.jsp HTTP/1.1" 200 7644',
'157.55.39.102 - - [28/Apr/2015:09:05:56 +0800] "GET /login.jsp HTTP/1.1" 200 2607',
'111.206.221.68 - - [28/Apr/2015:09:05:58 +0800] "POST /user_login.action HTTP/1.1" 200 2809',
'117.93.56.165 - - [28/Apr/2015:09:06:12 +0800] "POST /user_login.action HTTP/1.1" 302 -',
'223.98.218.205 - - [28/Apr/2015:09:06:12 +0800] "GET /login/home.jsp HTTP/1.1" 200 743',
'117.136.97.78 - - [28/Apr/2015:09:06:12 +0800] "GET /login/welcome.jsp HTTP/1.1" 200 1142',
'111.206.221.68 - - [28/Apr/2015:09:06:12 +0800] "GET /login.jsp HTTP/1.1" 200 803',
'117.93.56.165 - - [28/Apr/2015:09:06:12 +0800] "GET /login/top.jsp HTTP/1.1" 200 2052',
'111.206.221.68 - - [28/Apr/2015:09:06:13 +0800] "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('"')[0].split(' ')[1].rpartition('/')[-1]
if status[0] == '200' and name.rpartition('.')[-1] == 'jsp':
if name in temp:
result[name] += 1
else:
result[name] = 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 12 14
10 11 15 16
打印顺序为1,2,6,7,13,14,16,15,11,10,4,3
from copy import deepcopy
matrix = [[1,2,6,7],[3,5,8,13],[4,9,12,14],[10,11,15,16]]
reverse_matrix = deepcopy(matrix)
for i in range(len(reverse_matrix)):
for j in range(i, len(reverse_matrix[0])):
if i == j:
continue
reverse_matrix[j], reverse_matrix[j] = reverse_matrix[j], reverse_matrix[j]
reverse_matrix.reverse()
result=matrix[0]+(reverse_matrix[0])[1:]+((matrix[len(matrix)-1])[::-1])[1:]+((reverse_matrix[len(reverse_matrix)-1])[::-1])[1:]
result.pop()
print(result)
11、挑战题：
打印矩阵元素
1 2 6 7
3 5 8 13
4 9 12 14
10 11 15 16
之字形打印结果为1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
matrix = [[1,2,6,7],[3,5,8,13],[4,9,12,14],[10,11,15,16]]
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[k][j])
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[k][j])
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[i + 1:])
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 |
|
QQ群⑧：
窥视卡
雷达卡
发表于 2018-8-10 13:19:47
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡