[toc]

python 算法

命名元组namedtuple

COPY
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

排序

COPY
(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)

COPY
#!/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

COPY
#!/usr/bin/env python
nums = []
out = None
for i in range(3):
    nums.append(int(input('{}:'.format(i))))
 
nums.sort()
print(nums)

冒泡法代码实现(一)

COPY
#!/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)

COPY
[1, 9, 8, 5, 6, 7, 4, 3, 2]
[1, 2, 3, 4, 5, 6, 7, 8, 9] 25 36

冒泡法代码实现(二)

COPY
#!/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)

字符串修改

COPY
s = "I am very very very sorry   "
s.strip()
Out[4]: 'I am very very very sorry'

字符串查找

COPY
find(sub,[,start[end]]) -> int

COPY
In [1]: s = "I am very very very sorry "
In [2]: s.find("very")
Out[2]: 5

COPY
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

字符串格式化

COPY
In [15]: t = ('asjin','.com')
In [16]: "{},{}".format(t[0],t[1])
Out[16]: 'asjin,.com'

COPY
In [18]: "{0},{0}".format(t[0])
Out[18]: 'asjin,asjin'
 
In [19]: "{}".format([1,2])
Out[19]: '[1, 2]'

对齐

COPY
In [28]: '{0}*{1}={2:>02}'.format(3,2,2*3)
Out[28]: '3*2=06'

COPY
In [29]: '{:^30}'.format('asjin.com')
Out[29]: '          asjin.com           '
In [30]: '{:#^30}'.format('asjin.com')
Out[30]: '##########asjin.com###########'

COPY
In [12]: "{}:{}".format('192.168.1.100',8888)
Out[12]: '192.168.1.100:8888'

COPY
In [13]: t = ("asjin","com")
In [14]: "{}.{}".format(t[0],t[1])
Out[14]: 'asjin.com'

COPY
In [15]: "{0[0]}.{0[1]}".format(("asjin","com"))
Out[15]: 'asjin.com'

COPY
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})'

进制转换

COPY
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'

COPY
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 转换为十六进制

COPY
In [30]: octets = [10,180,55,1]
In [31]: "{:02X}{:02X}{:02X}{:02X}".format(*octets)
Out[31]: '0AB43701'

练习

让用户输入一个数，从后往前打印

COPY
#!/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)

COPY
#!/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个数字，打印每个数字的位数， 将这些数字排序打印，要求升序打印

COPY
#!/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))

字符串格式化

COPY
In [10]: "I am %-5d" % (20,)
Out[10]: 'I am 20   '
In [11]: "I am %-5d" % (20202,)
Out[11]: 'I am 20202'

练习

1. 判断是几位数
2. 打印每位数字及其重复的次数
3. 依次打印每一位数字，顺序个、十、百、千、万位

COPY
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

COPY
In [36]: for i in range(len(num),0,-1):
    ...:     print(num[i-1],end=' ')
    ...: print()
3 3 0 0 9 1 5

倒序打印2

COPY
In [37]: for i in reversed(num):
    ...:     print(i,end=' ')
    ...: print()
3 3 0 0 9 1 5

负索引方式打印

COPY
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)问题

COPY
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

失代字符串本身的字符

COPY
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 定义

COPY
In [2]: bytes("abc","utf-8")
Out[2]: b'abc'
In [3]: "abc".encode()
Out[3]: b'abc'

线性结构

线性结构

• 可抚迭代for … in
• len() 可以获取长度
• 通过下标可以访问
• 可以切片
• 如列表、元组、字符串、bytes、bytearry

切片

COPY
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

COPY
In [15]: for j, i in enumerate(['jen', 'bb','eee']):
    ...:     print(j,i)
0 jen
1 bb
2 eee

解构

COPY
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'

COPY
In [24]: lst = list(range(1,101,2))
In [25]: head,*_,tail = lst
In [26]: head,tail
Out[26]: (1, 99)

_是合法的标识符，看到下划线就知道这个变量就是不想被使用

取其中的元素

COPY
In [4]: lst = [1,(2,3,4),5]
In [5]: _,(*_,a),_ = lst
In [6]: a
Out[6]: 4

取JAVA_HOME 和 PATH

COPY
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')

COPY
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]
统计重复的数字有几个？分别是什么？
统计不重复的数字有几个？ 分别是什么？

COPY
#!/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)))

COPY
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 可变的、 无序的 、 不重复的 元素集合

COPY
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}

集合运算, 反单个集合合并到当前集合

COPY
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异常

  COPY
  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异常

  COPY
  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 成员运算与效率

COPY
# 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)

COPY
# 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)