Python 数据结构与算法

WHAT

• 介绍Python数据结构与算法第三方库 可用作学习也可用于直接使用算法
• 介绍pysnooper--man's debugger

algorithms

algorithms第三方库

• 根据目录学习

  
  {075C5F19-7EAA-4CB0-B5A5-F115464FD08E}_20190827160419.jpg
• 举例学习 josephus问题
  算法源代码
  josephus问题相关著名的Josephus问题

"""
介绍算法解决的是什么问题
There are people sitting in a circular fashion,
print every third member while removing them,
the next counter starts immediately after the member is removed.
Print till all the members are exhausted.
For example:
Input: consider 123456789 members sitting in a circular fashion,
Output: 369485271
"""

# 具体算法
def josephus(int_list, skip):
    skip = skip - 1                     # list starts with 0 index
    idx = 0
    len_list = (len(int_list))
    while len_list > 0:
        idx = (skip + idx) % len_list   # hash index to every 3rd
        yield int_list.pop(idx)
        len_list -= 1

pysooper Python运行记录利器

• 有时候我们看到了解决思路 但是不知道具体怎么运行的 或者想不通的时候
  https://github.com/cool-RR/PySnooper

import pysnooper

# 跟踪日志记录
@pysnooper.snoop()
def josephus(int_list, skip):
    skip = skip - 1  # list starts with 0 index
    idx = 0
    len_list = (len(int_list))
    res = []
    while len_list > 0:
        idx = (skip + idx) % len_list  # hash index to every 3rd
        res.append(int_list.pop(idx))
        len_list -= 1
    return res


josephus([1, 2, 3, 4, 5, 6, 7, 8, 9], 3)

• 输出日志
• 是否现在更清楚知道解决思路?

Source path:... C:/Users/74109/Desktop/MxShop-master/l.py
Starting var:.. int_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Starting var:.. skip = 3
15:52:54.569968 call        10 def josephus(int_list, skip):
15:52:54.569968 line        11     skip = skip - 1  # list starts with 0 index
Modified var:.. skip = 2
15:52:54.569968 line        12     idx = 0
New var:....... idx = 0
15:52:54.569968 line        13     len_list = (len(int_list))
New var:....... len_list = 9
15:52:54.569968 line        14     res = []
New var:....... res = []
15:52:54.569968 line        15     while len_list > 0:
15:52:54.569968 line        16         idx = (skip + idx) % len_list  # hash index to every 3rd
Modified var:.. idx = 2
15:52:54.569968 line        17         res.append(int_list.pop(idx))
Modified var:.. int_list = [1, 2, 4, 5, 6, 7, 8, 9]
Modified var:.. res = [3]
15:52:54.569968 line        18         len_list -= 1
Modified var:.. len_list = 8
15:52:54.569968 line        15     while len_list > 0:
15:52:54.569968 line        16         idx = (skip + idx) % len_list  # hash index to every 3rd
Modified var:.. idx = 4
15:52:54.569968 line        17         res.append(int_list.pop(idx))
Modified var:.. int_list = [1, 2, 4, 5, 7, 8, 9]
Modified var:.. res = [3, 6]
15:52:54.569968 line        18         len_list -= 1
Modified var:.. len_list = 7
15:52:54.569968 line        15     while len_list > 0:
15:52:54.569968 line        16         idx = (skip + idx) % len_list  # hash index to every 3rd
Modified var:.. idx = 6
15:52:54.569968 line        17         res.append(int_list.pop(idx))
Modified var:.. int_list = [1, 2, 4, 5, 7, 8]
Modified var:.. res = [3, 6, 9]
15:52:54.569968 line        18         len_list -= 1
Modified var:.. len_list = 6
15:52:54.569968 line        15     while len_list > 0:
15:52:54.569968 line        16         idx = (skip + idx) % len_list  # hash index to every 3rd
Modified var:.. idx = 2
15:52:54.569968 line        17         res.append(int_list.pop(idx))
Modified var:.. int_list = [1, 2, 5, 7, 8]
Modified var:.. res = [3, 6, 9, 4]
15:52:54.569968 line        18         len_list -= 1
Modified var:.. len_list = 5
15:52:54.570964 line        15     while len_list > 0:
15:52:54.570964 line        16         idx = (skip + idx) % len_list  # hash index to every 3rd
Modified var:.. idx = 4
15:52:54.570964 line        17         res.append(int_list.pop(idx))
Modified var:.. int_list = [1, 2, 5, 7]
Modified var:.. res = [3, 6, 9, 4, 8]
15:52:54.570964 line        18         len_list -= 1
Modified var:.. len_list = 4
15:52:54.570964 line        15     while len_list > 0:
15:52:54.570964 line        16         idx = (skip + idx) % len_list  # hash index to every 3rd
Modified var:.. idx = 2
15:52:54.570964 line        17         res.append(int_list.pop(idx))
Modified var:.. int_list = [1, 2, 7]
Modified var:.. res = [3, 6, 9, 4, 8, 5]
15:52:54.570964 line        18         len_list -= 1
Modified var:.. len_list = 3
15:52:54.570964 line        15     while len_list > 0:
15:52:54.570964 line        16         idx = (skip + idx) % len_list  # hash index to every 3rd
Modified var:.. idx = 1
15:52:54.570964 line        17         res.append(int_list.pop(idx))
Modified var:.. int_list = [1, 7]
Modified var:.. res = [3, 6, 9, 4, 8, 5, 2]
15:52:54.570964 line        18         len_list -= 1
Modified var:.. len_list = 2
15:52:54.570964 line        15     while len_list > 0:
15:52:54.570964 line        16         idx = (skip + idx) % len_list  # hash index to every 3rd
15:52:54.570964 line        17         res.append(int_list.pop(idx))
Modified var:.. int_list = [1]
Modified var:.. res = [3, 6, 9, 4, 8, 5, 2, 7]
15:52:54.570964 line        18         len_list -= 1
Modified var:.. len_list = 1
15:52:54.570964 line        15     while len_list > 0:
15:52:54.570964 line        16         idx = (skip + idx) % len_list  # hash index to every 3rd
Modified var:.. idx = 0
15:52:54.570964 line        17         res.append(int_list.pop(idx))
Modified var:.. int_list = []
Modified var:.. res = [3, 6, 9, 4, 8, 5, 2, 7, 1]
15:52:54.570964 line        18         len_list -= 1
Modified var:.. len_list = 0
15:52:54.572959 line        15     while len_list > 0:
15:52:54.572959 line        19     return res
15:52:54.572959 return      19     return res
Return value:.. [3, 6, 9, 4, 8, 5, 2, 7, 1]