基本算法回顾1

从今天开始在学习编程同时，回顾数据结构算法的知识点，主要参考王铮老师的课。

今天先回顾大纲和一些简单的算法。

基础部分将回顾：

数组、链表、栈、队列、递归、排序、线性排序、排序优化、

二分查找、跳表、散列表、哈希算法、

二叉树基础、红黑树、递归树、堆和堆排序、

图、深度优先和广度优先搜索、

字符串匹配、Trie树、AC自动机、

贪心算法、分治算法、回溯算法、

动态规划

高级篇 略

实战篇

项目地址：https://github.com/wangzheng0822/algo

学习路径图

复杂度分析

需要了解大O复杂度，分析算法复杂度，以及常见的复杂度量级。

__author__ = "xx"
__date__ = "2020/6/27 21:29"


prices = {
    'AAPL': 191.88,
    'GOOG': 1186.96,
    'IBM': 149.24,
    'ORCL': 48.44,
    'ACN': 166.89,
    'FB': 208.09,
    'SYMC': 21.29
}
# 生成式：用股票价格大于100元的股票构造一个新的字典
price2 = {key: value for key, value in prices.items() if value > 100}
print(price2)


## 嵌套列表：
# [[None]*2 for _ in range(3)]
# >>> [[None, None], [None, None], [None, None]]
def score_analysic():
    names = ['关羽', '张飞', '赵云', '马超', '黄忠']
    courses = ['语文', '数学', '英语']
    scores = [[None] * len(courses) for _ in range(len(names))]
    for row, name in enumerate(names):
        for col, course in enumerate(courses):
            scores[row][col] = float(input(f"请输入{name}的{course}课程成绩:"))
            print(scores)


# `heapq`模块（堆排序）:
"""
从列表中找出最大的或最小的N个元素
堆结构(大根堆/小根堆)
"""
import heapq

list1 = [34, 25, 12, 99, 87, 63, 58, 78, 88, 92]
list2 = [
    {'name': 'IBM', 'shares': 100, 'price': 91.1},
    {'name': 'AAPL', 'shares': 50, 'price': 543.22},
    {'name': 'FB', 'shares': 200, 'price': 21.09},
    {'name': 'HPQ', 'shares': 35, 'price': 31.75},
    {'name': 'YHOO', 'shares': 45, 'price': 16.35},
    {'name': 'ACME', 'shares': 75, 'price': 115.65}
]
print(heapq.nsmallest(3, list1))
print(heapq.nlargest(2, list2, key=lambda x: x['shares']))


import itertools

itertools.cycle(('A', 'B', 'C'))

"""
算法

排序、查找
"""
def select_sort(items, comp=lambda x,y: x<y):
    """简单选择排序
    每趟选取最小的元素,与位置i替换
    """
    items = items[:]
    for i in range(len(items)-1 ):
        min_index = i
        for j in range(i+1, len(items)):
            if comp(items[j], items[min_index]):
                min_index = j
        # 注意：这个交换要在第i躺结束后做
        items[i], items[min_index] = items[min_index], items[i]
    return items


def bubble_sort(items, comp=lambda x,y: x>y):
    """冒泡排序
    每次比较都对相邻的做移动，每趟将最大值移至后面，就像冒泡似的。
    """
    items = items[:]
    for i in range(len(items)-1 ):
        # 设置swapped的隐含意思的:如果一趟下来无元素交换，说明已经有序了。
        swapped = False
        for j in range(len(items)-1-i):
            if comp(items[j], items[j+1]):
                items[j], items[j+1] = items[j+1], items[j]
                swapped = True
        if not swapped:
            break
    return items

def bubble_sort_plus(items, comp=lambda x,y: x>y):
    """冒泡排序 加强版

    """
    pass

# 归并排序
# 将要排序的序列，分成两部分排序，再合并。可用递归
def merge(items1, items2, comp=lambda x,y: x<y):
    """
    :items1 :有序
    :items2 ；有序
    由此可见，归并排序是不稳定的
    """
    items = []
    index1, index2 = 0,0
    while index1 < len(items1) and index2<len(items2):
        if comp(items1[index1], items2[index2]):
            items.append(items1[index1])
            index1 += 1
        else:
            items.append(items2[index2])
            index2 += 1
    # and的意思是两者都满足True才执行，结束while意味着其中一个序列已经结束了.剩下的直接加到items后面即可
    items += items1[index1:]
    items += items2[index2:]
    return items

def _merge_sort(items, comp=lambda x,y: x<y):
    """归并排序"""
    if len(items) < 2:
        return items
    mid = len(items) // 2
    left = _merge_sort(items[:mid], comp)
    right = _merge_sort(items[mid:], comp)
    return merge(left, right, comp)

def merge_sort(items, comp=lambda x, y: x < y):
    return _merge_sort(list(items), comp)


def seq_search(items, key):
    """顺序查找"""
    for index, item in enumerate(items):
        if item == key:
            return index
    return -1


def bin_search(items, key):
    """折半查找"""
    start, end = 0, len(items)-1
    while start <= end:
        mid = (start + end) // 2
        if key > items[mid]:
            start = mid + 1
        elif key < items[mid]:
            end = mid-1
        else:
            return mid
    return -1


list1 = [34, 25, 12, 99, 87, 63, 58, 78, 88, 92]
print("list1 排序后：")
print( _merge_sort(list1) )

# print(merge_sort(2, ))
# list(2) 怎么办
print(bin_search(list1, 2))



"""
贪婪法：
求解当前最满意的解，不需要最优，即快速、满意的解

输入：
20 6
电脑 200 20
收音机 20 4
钟 175 10
花瓶 50 2
书 10 1
油画 90 9
"""
class Thing(object):
    """物品"""
    def __init__(self, name, price, weight):
        self.name = name
        self.price = price
        self.weight = weight

    @property
    def value(self):
        """价格 重量比"""
        return self.price / self.weight

def input_Thing():
    """录入信息，指定格式
    没有做int格式检查，直接报错
    """
    name_str, price_str, weight_str = input("请输入（油画 90 9）商品价格重量：").split()
    return name_str, int(price_str), int(weight_str)

def thief_going():
    max_weight, num_of_thing = map(int, input("小偷的最大负重 眼前想偷的物品件数：").split())
    all_things = []
    # * 没印象了
    for _ in range(num_of_thing):
        all_things.append(Thing(*input_Thing()))
    all_things.sort(key=lambda x: x.value, reverse=True)
    total_weight = 0
    total_price = 0
    for thing in all_things:
        if total_weight + thing.weight <= max_weight:
            print(f"小偷拿走了{thing.name}")
            total_weight += thing.weight
            total_price += thing.price
    print(f"总价值：{total_price}元")

# thief_going()

"""
分治法：

快速排序： 选择枢轴对元素做划分，左边的比枢轴小，右边大

"""
def quick_sort(items, comp=lambda x,y: x<=y):
    items = list(items)[:]
    _quick_sort(items, 0, len(items)-1, comp)
    return items

def _quick_sort(items, start, end, comp):
    # if start < end:
    #     pos =
    pass

"""
回溯法例子：试探，退回一步重新选择

[骑士巡逻](https://zh.wikipedia.org/zh/%E9%AA%91%E5%A3%AB%E5%B7%A1%E9%80%BB)。
八皇后、迷宫寻路
"""

"""
动态规划：
将求解问题分解为若干子问题。保留其解，避免产生大量运算。
"""


# 
list(map( lambda x:x**2, filter(lambda x: x%2, range(1,10)) ))

[x**2 for x in range(1,10) if x%2]