常见算法
2018-08-22 本文已影响0人
梦醒家先生
1. 组合数字
num = input("please input a number:")
count = 0
for i in range(1, num):
for j in range(1, num):
for k in range(1, num):
if i != j and i != k and j != k:
print(i * 100 + j * 10 + k)
count += 1
print(count)
2. 冒泡排序
- 简介：最基础的排序
- 原理. 过程跟踪
- 内部：相邻元素两两比较 数次比较循环, 最大的元素放到了最后
- 外部：数次冒泡排序后，最终形成了一个从小到大的排序
步骤： **元素比较 (内部的比较循环) (外部的冒泡循环) ** **异常情况 **
"""
1、元素比较---比较循环---外部的冒泡循环---异常情况
2、写法：
外部循环冒泡
内部比较循环
元素比较
异常情况处理
"""
def maopao(alist):
n = len(alist)
# 外部的冒泡排序循环
for j in range(n - 1, 0, -1):
count = 0
# 内部的元素比较循环
for i in range(j):
# 元素的替换
if alist[i] > alist[i + 1]:
alist[i], alist[i + 1] = alist[i + 1], alist[i]
count += 1
# 异常情况
if count == 0:
break
if __name__ == '__main__':
alist = [3, 44, 56, 78, 4, 6, 90]
maopao(alist)
print(alist)
- 思路：
1、流程：元素比较-----比较循环——外部的冒泡循环----异常情况
2、写法：外部冒泡循环
内部比较循环
元素比较
异常情况处理
- 成本分析
最优：O(n)
最坏：O(n*n)
稳定性：稳定
3. 选择排序
- 简介：简单直观的排序算法
- 原理
- 无序队列选择最小的元素，最小元素和无序第一个元素替换
- 无序队列重复执行1
- 步骤：
- 元素比较 选最小
- 最小元素和第一元素替换
- 外部的挑选循环
"""
1、流程：比较循环（选最小）---元素替换---外部选择循环
2、写法：
外部的选择循环
内部的比较循环（选最小）
比较条件
元素替换
'每次选择循环的时候，无序列表的首个元素的下标一直在变动'
"""
def xuanze(alist):
n = len(alist)
# 外部的选择循环
for j in range(n - 1):
min_index = j
# 比较循环后，选择最小的
for i in range(min_index + 1, n):
# 元素比较
if alist[i] < alist[min_index]:
min_index = i
# 元素替换
if min_index != j:
alist[min_index], alist[j] = alist[j], alist[min_index]
if __name__ == '__main__':
alist = [3, 44, 56, 78, 4, 6, 90]
xuanze(alist)
print(alist)
- 思路：
1、流程：比较循环（选最小）----元素替换——外部选择循环
2、写法：
外部的选择循环
内部的比较循环（选最小）
比较条件
元素替换
关键点：每次选择循环的时候，无序列表的首个元素的下标一直在变动。
- 成本分析：
最优：O(n*n)
最坏：O(n*n)
稳定性：不稳定
4. 插入排序
- 简介：先定义一个有序队列，然后把无序队列中的第一个元素放到有序队列的 合适位置，重复操作，直至形成一个完整的有序队列 。打扑克
- 原理：
- 无序队列选择第一个元素放到有序队列的末尾
- 有序队列里面进行冒泡排序 (往前冒泡)
- 重复前面两个步骤
- 步骤
有序队列(外部)：
元素替换
冒泡循环
插入排序循环(内部)：
无序队列元素向有序队列放
"""
1、流程：元素替换---冒泡排序---外部的插入排序循环
2、写法：
外部的插入排序循环
有序列队的冒泡排序
有序列队的元素比较
"""
def charu(alist):
n = len(alist)
# 外部的插入排序循环
for i in range(n):
# 假设无序列表的第一个位置元素的下标值是 i
for j in range(i, 0, -1):
# 有序列表内部元素比较
if alist[j] < alist[j - 1]:
alist[j], alist[j - 1] = alist[j - 1], alist[j]
else:
break
if __name__ == '__main__':
alist = [3, 44, 56, 78, 4, 6, 90]
charu(alist)
print(alist)
- 思路：
1、流程：元素替换----冒泡排序——外部的插入排序循环
2、写法：
外部的插入排序循环
有序队列的冒泡排序
有序队列的元素比较
- 成本分析
最优：O(n)
最坏：O(n*n)
稳定性：稳定
5. 快速排序
- 简介：划分交换排序，1.从无序列表中挑选出一个元素，把无序列表分割成独立的两个部分，2.其中一部分的所有数据都比另外一部分的所有数据都要小，3.然后在按照此方法对这两部分数据进行快速排序，4.这个排序过程是递归进行。
- 原理
一、挑元素、划分组、分组重复前两步
1、在无序列表中挑选一个随机的数字，作为当前列表的中间值
2、移动左右标签，将比中间值大的放在右侧，比中间值小的放在左侧
3、当两个标签重合的时候，中间值归位
二、特点: 一句话:左手右手一个慢动作，右手左手慢动作重播
1、因为是无序队列，所以位置可以随机挑2、临时划分一个空间，存放我们挑选出来的中间元素
3、左标签位置空，移动右标签，反之一样
4、重复3，直到左右侧标签指向同一个位置，
5、把临时存放的中间元素，归位
"""
1.原理：挑元素、换分组、分组重复前两步
2.
换分组：准备工作 + 左右移动 + 元素归位
递归： 函数自调用 + 退出条件
"""
def quick_sort(alist, start, end):
# 定义递归的条件
if start < end:
# 定义三个标签
mid = alist[start]
left = start
right = end
# 定义拆分的条件
while left < right:
# 右推进（右边的值大于等于中间值）
while left < right and alist[right] >= mid:
right -= 1
alist[left] = alist[right]
# 左推进（左边的值小于中间值）
while left < right and alist[left] < mid:
left += 1
alist[right] = alist[left]
# 获取中间值
alist[left] = mid
# 1.对切割后的左边的小组进行快速排序
quick_sort(alist, start, left - 1)
# 2.对切割后右边的小组进行快速排序
quick_sort(alist, left + 1, end)
if __name__ == "__main__":
li = [54, 26, 93, 17, 77, 31, 44, 77, 20]
print(li)
quick_sort(li, 0, len(li) - 1)
print(li)
3. 列表去重
list = [1, 1, 2, 2, 3, 4, 5, 5]
new_list = set(list)
print(new_list)
def dislist(list):
new_list = []
if not list:
return
else:
for i in list:
if i not in new_list:
new_list.append(i)
else:
continue
return new_list
print(dislist(list))
# 以3为单位分组
print([[x for x in range(1, 100)][i:i + 3] for i in range(0, 100, 3)])
# 多个列表去重
a = [1, 2, 3, 4, 5]
b = [1, 2, 3]
print(set(a) & set(b)) # 取相同值,后的集合
print(set(a) ^ set(b)) # 取不同值,后的集合
# 字符串反转
string = 'hello world'
print(string[::-1])
4. 回文数
a = (input("请输入一个数字："))
x = str(a)
x = x[::-1]
if x == a:
print("True")
else:
print("False")
5. 完数
"""
题目：求指定区域内的完数（10000为例），及所有因子之和恰好等于本身，如：6=1+2+3
1 将所有的因子追加到一个列表中
2 将符合条件的数字打出来
"""
l = []
for n in range(1, 1000):
for a in range(1, n):
if n % a == 0:
l.append(a)
if sum(l) == n:
print(l)
print(n)
l = []
6.快速排序
def quick_sort(alist, first, last):
if first <= last:
split_point = find_pos(alist, first, last)
quick_sort(alist, first, split_point - 1)
quick_sort(alist, split_point + 1, last)
def find_pos(lists, low, high):
key = lists[low]
while low < high:
while low < high and lists[high] >= key:
high -= 1
lists[low] = lists[high]
while low < high and lists[low] <= key:
low += 1
lists[high] = lists[low]
lists[low] = key
return low
alist = [54, 67, 98, 41, 34, 12, 34, 54, 64, 756]
quick_sort(alist, 0, 9)
print(alist)
7. 斐波那契数列
# 一、使用函数定义
def finbo(num):
numlist = [0, 1]
for i in range(num - 2):
numlist.append(numlist[-2] + numlist[-1])
return numlist
print(finbo(10))
# 二、自定义迭代器对象
class FeiBo(object):
# 提供构造方法
def __init__(self, num):
self.num = num
super(FeiBo, self).__init__()
self.current_index = 0
# 记录初始化的前两个值
self.a = 0
self.b = 1
def __iter__(self):
# 返回迭代对象
return self
def __next__(self):
if self.current_index < self.num:
result = self.a
self.a, self.b = self.b, self.a + self.b
# 下标加一
self.current_index += 1
return result
else:
raise StopIteration
# 创建迭代器对象
fib = FeiBo(10)
for value in fib:
print(value)
8. 素数(质数）
# 1。 获取素数
import time
start = time.clock()
i = int(input('please enter an integer:'))
# 创建一个空list
r = list()
# 添加元素2
r.append(2)
# 从3开始挨个筛选
for a in range(3, i):
b = False
# 用a除以小于a的质数b
for b in r:
if a % b == 0:
b = False
break
else:
b = True
if b == True:
r.append(a)
print(r)
t = (time.clock() - start)
print(t)
# 2。判断一个数字是否为素数
num = int(input('please a num:'))
if num % 2 == 0:
print("不是素数！")
elif num == 1:
print("不是素数！")
else:
print("是一个素数！")
9. 计算字符串中出现最多的字符，并打印
# -*- coding: utf-8 -*-
str_ = 'ssdasdasefadd'
# 遍历所有的单词个数------运用浅拷贝、深拷贝
dict_char_tmp = {i: str_.count(i) for i in str_}
print("所有单词的个数：", dict_char_tmp)
dict_char = {}
for key, value in dict_char_tmp.items():
if dict_char.get(value):
# 如果有相同数量的value值，则key相同，添加到列表value中
dict_char[value].append(key)
else:
dict_char[value] = [key]
print(dict_char)
# 使用Sorted函数给 字典key值 排序---转换为列表
# dict.items()返回的是列表对象////dict.iteritems()返回的是 iterator 对象
dict_char_sort = sorted(dict_char.items(), key=lambda item: item[0], reverse=True)
print(dict_char_sort)
char_l = dict_char_sort[0][1]
print(char_l)
char_l.sort()
print("出现次数最多的字母是：", char_l[0], "个数是：", dict_char_sort[0][0])
10.找出一个字符串中最长不重复的子串
def find_long_no_repeat_substr(one_str):
"""
找出一个字符串中最长不重复的子串
:param one_str:
:return:
"""
res_list = []
length = len(one_str)
for i in range(length):
tmp = one_str[i]
for j in range(i + 1, length):
if one_str[j] not in tmp:
tmp += one_str[j]
else:
break
res_list.append(tmp)
res_list.sort(lambda x, y: cmp(len(x), len(y)))
return res_list[-1]
if __name__ == '__main__':
one_str_list = ["1234", "asdfsfadgfdgahsftw", "34236547635132347"]
for one_str in one_str_list:
res = find_long_no_repeat_substr(one_str)
print("{0}最长非重复字串为：{1}".format(one_str, res))
