[toc]
python 算法
命名元组namedtuple
In [1]: from collections import namedtuple
In [2]: Point = namedtuple('P','x,y')
In [3]: type(Point)
Out[3]: type
In [4]: p1 = Point(1,10)
In [5]: p1
Out[5]: P(x=1, y=10)
In [6]: p1.x
Out[6]: 1
In [7]: p1.y
Out[7]: 10
In [8]: p1.x + p1.y
Out[8]: 11
排序
(py3_env) [root@ssjinyao:~/mypython/python3]# cat sort.py
#!/usr/bin/env python3
nums = []
out = None
for i in range(3):
nums.append(int(input('{}: '.format(i))))
nums.sort()
print(nums)
#!/usr/bin/env python3
nums = []
out = None
for i in range(3):
nums.append(int(input('{}: '.format(i))))
while True:
cur = min(nums)
print(cur)
nums.remove(cur)
if len(nums) == 1:
print(nums[0])
break
#!/usr/bin/env python
nums = []
out = None
for i in range(3):
nums.append(int(input('{}:'.format(i))))
nums.sort()
print(nums)
冒泡法代码实现(一)
#!/usr/bin/env python
# -*- coding: utf-8 -*-
num_list = [
[1,9,8,5,6,7,4,3,2],
[1,2,3,4,5,6,7,8,9],
]
nums = num_list[0]
print(nums)
length = len(nums)
count_swap = 0
count = 0
for i in range(length):
for j in range(length-i-1):
count += 1
if nums[j] > nums [j+1]:
tmp = nums[j]
nums[j] = nums [j+1]
nums[j+1] = tmp
count_swap +=1
print(nums, count_swap, count)
[1, 9, 8, 5, 6, 7, 4, 3, 2]
[1, 2, 3, 4, 5, 6, 7, 8, 9] 25 36
冒泡法代码实现(二)
#!/usr/bin/env python
# -*- coding: utf-8 -*-
num_list = [
[1,9,8,5,6,7,4,3,2],
[1,2,3,4,5,5,7,8,9]
]
nums = num_list[0]
print(nums)
length = len(nums)
flag = False
count_swap = 0
count = 0
for i in range(length):
for j in range(length-i-1):
count += 1
if nums[j] > nums[j+1]:
tmp = nums[j]
nums[j] = nums[j+1]
nums[j+1] = tmp
flag = True
count_swap += 1
if not flag:
break
print(nums,count_swap,count)
字符串修改
s = "I am very very very sorry "
s.strip()
Out[4]: 'I am very very very sorry'
字符串查找
find(sub,[,start[end]]) -> int
In [1]: s = "I am very very very sorry "
In [2]: s.find("very")
Out[2]: 5
In [14]: s = 'I am very very very sorry'
In [15]: i = 0
In [16]: for x in s:
...: print(str(i)+x,end=" ")
...: i +=1
...:
0I 1 2a 3m 4 5v 6e 7r 8y 9 10v 11e 12r 13y 14 15v 16e 17r 18y 19 20s 21o 22r 23r 24y
字符串格式化
In [15]: t = ('asjin','.com')
In [16]: "{},{}".format(t[0],t[1])
Out[16]: 'asjin,.com'
In [18]: "{0},{0}".format(t[0])
Out[18]: 'asjin,asjin'
In [19]: "{}".format([1,2])
Out[19]: '[1, 2]'
对齐
In [28]: '{0}*{1}={2:>02}'.format(3,2,2*3)
Out[28]: '3*2=06'
In [29]: '{:^30}'.format('asjin.com')
Out[29]: ' asjin.com '
In [30]: '{:#^30}'.format('asjin.com')
Out[30]: '##########asjin.com###########'
In [12]: "{}:{}".format('192.168.1.100',8888)
Out[12]: '192.168.1.100:8888'
In [13]: t = ("asjin","com")
In [14]: "{}.{}".format(t[0],t[1])
Out[14]: 'asjin.com'
In [15]: "{0[0]}.{0[1]}".format(("asjin","com"))
Out[15]: 'asjin.com'
In [16]: from collections import namedtuple
In [17]: Point = namedtuple('_Point','x,y')
In [18]: p1 = Point(5,6)
In [19]: p1.x
Out[19]: 5
In [20]: p1.y
Out[20]: 6
In [23]: "Point = ({{{0.x},{0.y}}})".format(p1)
Out[23]: 'Point = ({5,6})'
进制转换
In [26]: "int: {0:d}; hex {0:x}; oct {0:o}; bin: {0:b}".format(1996)
Out[26]: 'int: 1996; hex 7cc; oct 3714; bin: 11111001100'
In [27]: "int: {0:d}; hex {0:#x}; oct {0:#o}; bin: {0:#b}".format(1996)
Out[27]: 'int: 1996; hex 0x7cc; oct 0o3714; bin: 0b11111001100'
ip 转换为十六进制
In [30]: octets = [10,180,55,1]
In [31]: "{:02X}{:02X}{:02X}{:02X}".format(*octets)
Out[31]: '0AB43701'
练习
让用户输入一个数，从后往前打印
#!/usr/bin/env python3
# -*-coding: utf-8 -*-
m = input(">>>").strip().lstrip('0')
print("这是{}位数".format(len(m)))
for i in range(len(m)):
print("{}'s count = {}".format(m[i],m.count(m[i])))
for j in range(len(m)):
n=m[-j-1]
print(n)
print(m)
#!/usr/bin/env python
# -*- coding: utf-8 -*-
num = ""
while True:
num = input("Please input a interger: ").strip()
num = int(num)
num = str(num)
if num.isdigit():
break
else:
print("Bad number")
count = [0]*10 # 0~9
for i in range(10):
count[i] = num.count(str(i))
for i in range(10):
if count[i]:
print(i,count[i])
lst = list(num)
lst.reverse()
print(lst)
输入5个数字，打印每个数字的位数， 将这些数字排序打印，要求升序打印
#!/usr/bin/env python
# -*- coding: utf-8 -*-
lst = []
for i in range(5):
m = input(">>> ").strip().lstrip("0")
print("这是{}位数".format(len(m)))
lst.append(int(m))
print(sorted(lst))
字符串格式化
In [10]: "I am %-5d" % (20,)
Out[10]: 'I am 20 '
In [11]: "I am %-5d" % (20202,)
Out[11]: 'I am 20202'
练习
- 判断是几位数
- 打印每位数字及其重复的次数
- 依次打印每一位数字，顺序个、十、百、千、万位
In [32]: num = ''
In [33]: while True:
...: num = input('Input a positive number >>>').strip().lstrip('0')
...: if num.isdigit():
...: break
...:
Input a positive number >>>111
In [34]: print("The length of {} is {}.".format(num,len(num)))
The length of 111 is 3.
倒序打印1
In [36]: for i in range(len(num),0,-1):
...: print(num[i-1],end=' ')
...: print()
3 3 0 0 9 1 5
倒序打印2
In [37]: for i in reversed(num):
...: print(i,end=' ')
...: print()
3 3 0 0 9 1 5
负索引方式打印
In [38]: for i in range(len(num)):
...: print(num[-i-1],end=' ')
...: print()
3 3 0 0 9 1 5
判断0-9的数字在字符中出现的次数，每一次迭代都是用的count,都是0(n)问题
In [57]: num = '1912334'
In [58]: for i in range(10):
...: counter[i] = num.count(str(i))
...: if counter[i]:
...: print("The count of {} is {}".format(i,counter[i]))
...:
The count of 1 is 2
The count of 2 is 1
The count of 3 is 2
The count of 4 is 1
The count of 9 is 1
失代字符串本身的字符
In [67]: num = '1912334'
In [68]: counter = [0]*10
In [69]: for x in num:
...: i = int(x)
...: if counter[i] == 0:
...: counter[i] = num.count(x)
...: print("The count of {} is {}".format(x,counter[i]))
The count of 1 is 2
The count of 9 is 1
The count of 2 is 1
The count of 3 is 2
The count of 4 is 1
bytes 定义
In [2]: bytes("abc","utf-8")
Out[2]: b'abc'
In [3]: "abc".encode()
Out[3]: b'abc'
线性结构
线性结构
- 可抚迭代for … in
- len() 可以获取长度
- 通过下标可以访问
- 可以切片
- 如列表、元组、字符串、bytes、bytearry
切片
In [1]: 'www.asjin.com'[4:10]
Out[1]: 'asjin.'
In [2]: 'www.asjin.com'[4:9]
Out[2]: 'asjin'
In [3]: 'www.asjin.com'[:9]
Out[3]: 'www.asjin'
In [4]: 'www.asjin.com'[4:]
Out[4]: 'asjin.com'
In [5]: 'www.asjin.com'[:]
Out[5]: 'www.asjin.com'
In [6]: 'www.asjin.com'[:-1]
Out[6]: 'www.asjin.co'
In [7]: 'www.asjin.com'[4:-4]
Out[7]: 'asjin'
补充for
In [15]: for j, i in enumerate(['jen', 'bb','eee']):
...: print(j,i)
0 jen
1 bb
2 eee
解构
In [4]: test,*te,test2 = "bbcccefsdde"
In [5]: test
Out[5]: 'b'
In [6]: te
Out[6]: ['b', 'c', 'c', 'c', 'e', 'f', 's', 'd', 'd']
In [7]: test2
Out[7]: 'e'
In [24]: lst = list(range(1,101,2))
In [25]: head,*_,tail = lst
In [26]: head,tail
Out[26]: (1, 99)
_是合法的标识符，看到下划线就知道这个变量就是不想被使用
取其中的元素
In [4]: lst = [1,(2,3,4),5]
In [5]: _,(*_,a),_ = lst
In [6]: a
Out[6]: 4
取JAVA_HOME 和 PATH
In [7]: s = 'JAVA_HOME=/usr/bin'
In [8]: s.partition('=')
Out[8]: ('JAVA_HOME', '=', '/usr/bin')
In [9]: name,_,path=s.partition('=')
In [10]: name,path
Out[10]: ('JAVA_HOME', '/usr/bin')
In [12]: s = 'JAVA_HOME=/usr/bin'
In [13]: name,path = s.split('=')
In [14]: print(name,path)
JAVA_HOME /usr/bin
数字统计
随机产生10个数字
要求:
每个数字取值范围[1,20]
统计重复的数字有几个？分别是什么？
统计不重复的数字有几个？ 分别是什么？
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import random
nums = []
for _ in range(10):
nums.append(random.randrange(21))
print("Origin numbers = {}".format(nums))
print()
length = len(nums)
samenums = [] # 记录相同的数字
diffnums = [] # 记录不同的数字
states = [0] * length # 记录不同的索引异同状态
for i in range(length):
flag = False # 假设没有重复
if states[i] == 1:
continue
for j in range(i+1,length):
if states[j] == 1:
continue
if nums[i] == nums[j]:
flag = True
states[j] = 1
if flag: # 有重复
samenums.append(nums[i])
states[i] = 1
else:
diffnums.append(nums[i])
print("Same numbers = {1}, counter = {0}".format(len(samenums), samenums))
print("Different numbers = {1}, Counter = {0}".format(len(diffnums),diffnums))
print(list(zip(states,nums)))
Same numbers = [8, 20], counter = 2
Different numbers = [19, 5, 10, 1, 9, 16], Counter = 6
[(0, 19), (0, 5), (0, 10), (1, 8), (1, 20), (1, 20), (0, 1), (0, 9), (1, 8), (0, 16)]
set 定义 初始化
- 约定
- set 翻译为集合
- collection 翻译为集合类型，是一个大概念
set可变的、 无序的 、 不重复的 元素集合
In [4]: s2 = set(range(5))
In [5]: s2
Out[5]: {0, 1, 2, 3, 4}
In [9]: s6={9,10,11}
In [10]: s6
Out[10]: {9, 10, 11}
In [14]: s7
Out[14]: {(1, 2), 3, 'a'}
In [15]: s2 = set(range(5))
In [16]: s2.add(5)
In [17]: s2
Out[17]: {0, 1, 2, 3, 4, 5}
集合运算, 反单个集合合并到当前集合
In [19]: s2
Out[19]: {0, 1, 2, 3, 4, 5, 6}
In [20]: s2.update({2,10,3})
In [21]: s2
Out[21]: {0, 1, 2, 3, 4, 5, 6, 10}
移除一个元素remove(elem)
- 从set 中移除一个元素
- 如果元素不存在，抛出KeyError异常
In [21]: s2 Out[21]: {0, 1, 2, 3, 4, 5, 6, 10} In [22]: s2.remove(2) In [23]: s2 Out[23]: {0, 1, 3, 4, 5, 6, 10}discard(elem) - 从set 中移除一个元素，和remove() 类似，只是不报错。
- 元素不存在，什么都不做
pop()->item - 移除并返回任意的元素
- 空集返回KeyError异常
In [23]: s2 Out[23]: {0, 1, 3, 4, 5, 6, 10} In [25]: s2.pop() Out[25]: 0 In [26]: s2 Out[26]: {1, 3, 4, 5, 6, 10} # 随机挑一个clear() - 移除所有元素
set 成员运算与效率
# list
In [27]: %%timeit lst1 = list(range(100))
...: a = -1 in lst1
1.53 µs ± 67 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
In [28]: %%timeit lst1 = list(range(100000))
...: a = -1 in lst1
1.55 ms ± 98.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
# set
In [29]: %%timeit set1 = set(range(100))
...: a = -1 in set1
38.3 ns ± 5.97 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
In [30]: %%timeit set1 = set(range(100000))
...: a = -1 in set1
37 ns ± 7.05 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
