常见算法

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. 外部：数次冒泡排序后，最终形成了一个从小到大的排序

步骤： **元素比较 (内部的比较循环) (外部的冒泡循环) ** **异常情况 **

"""
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. 无序队列选择最小的元素，最小元素和无序第一个元素替换
2. 无序队列重复执行1

• 步骤：

1. 元素比较 选最小
2. 最小元素和第一元素替换
3. 外部的挑选循环

"""
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. 有序队列里面进行冒泡排序 (往前冒泡)
3. 重复前面两个步骤

• 步骤

有序队列(外部)：

​ 元素替换

​ 冒泡循环

插入排序循环(内部)：

​ 无序队列元素向有序队列放

"""
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))