pegasuswang/python_data_structures_and_algorithms

Python 中文数据结构和算法教程

python_data_structures_and_algorithms's Issues

链接失效了

电子书：《Python web 入坑指南》 点进去提示:This page does not exist yet.

LinkedList错误

当链表执行完clear方法时 assert list(ll)==[] 错误

AttributeError: 'NoneType' object has no attribute 'value'

应当在iter_node中加入判断

if self.tailnode is None:                                              
    return None

在clear()中加入

self.tailnode = None

linked_list.py的remove方法貌似有误

在链表的remove方法中 这行代码实现，经过测试貌似是有问题的。
def remove(self, value): # O(n)
""" 删除包含值的一个节点，将其前一个节点的 next 指向被查询节点的下一个即可
.............
if curnode is self.tailnode: # NOTE: 注意更新 tailnode
if prevnode is self.root:
self.tailnode = None
else:
self.tailnode = prevnode
del curnode

按照源代码意义，这行代码实际上是将被删除结点之后的结点都给删除了，而并非方法实现的删除单个结点。
实际测试也是如此。
比如生成链表0-->1-->2-->3-->4--->5
删除3结点
按照源代码 结果是 0-->1--->2
我这边的修改的代码是：
if prevode is self.root:
self.tailnode = None
if curnode == self.tailnode:
self.tailnode = prevode
del curnode

如果是我弄错了，还请告知解惑。

关于链表remove 时间复制度问题

你好，
对于链表remove时间复杂度有些疑问
我认为无论是单链表、双链表，删除一个元素的时间复杂度都是O(n)，因为都需要遍历整个链表；
删除一个node时间复杂度都是O(1)，因为都只需要将前后两个node相连，
为什么lru_cache 不用单链表要用双链表呢？

堆与堆排序的问题

def _siftdown(self, ndx):
        left = 2 * ndx + 1
        right = 2 * ndx + 2
        # determine which node contains the larger value
        largest = ndx
        if (left < self._count and     # 有左孩子
                self._elements[left] >= self._elements[largest] and
                self._elements[left] >= self._elements[right]):  # 原书这个地方没写实际上找的未必是largest
            largest = left
        elif right < self._count and self._elements[right] >= self._elements[largest]:
            largest = right
        if largest != ndx:
            self._elements[ndx], self._elements[largest] = self._elements[largest], self._elements[ndx]
            self._siftdown(largest)

若self.elements = [4,3,2,1,0]这种结构的话，这种会报错，是否应该先判断右孩子是否存在，然后再判断左孩子？

  def _siftdown(self, ndx):
        left = 2 * ndx + 1
        right = 2 * ndx + 2
        # determine which node contains the larger value
        largest = ndx
        if (right < self._count and  # 有右孩子
                self._elements[right] >= self._elements[largest] and
                self._elements[left] <= self._elements[right]):  # 原书这个地方没写实际上找的未必是largest
            largest = right
        elif left < self._count and self._elements[left] >= self._elements[largest]:
            largest = left
        if largest != ndx:
            self._elements[ndx], self._elements[largest] = self._elements[largest], self._elements[ndx]
            self._siftdown(largest)

array 可以装别的 class吗? 自定义的class

python_data_structures_and_algorithms/docs/02_数组和列表/array_and_list.py

Line 14 in 3469a79

class Array(object):

thank you

LinkedList中关于size检查的部分

linked_list.py 中, class LinkedList 的 append 方法和 appendleft 方法中对于maxsize的检查有问题, 不是大于号而应该是大于等于号.

例如:

In [17]: l = LinkedList(4)

In [18]: l.append(0);l.append(1);l.append(2);l.append(3);

In [19]: l.append(4)

In [20]: l.append(5)
---------------------------------------------------------------------------
Exception  

关于您python-web-guide仓库的一个问题

那里没有issue区,故在此提一下issue
clone了您最新代码, make serve报错
Warning, treated as error:
/root/python-web-guide-master/codingstyle/codingstyle.rst:182: ERROR: Unknown target name: "\u300athe elements of programming style\u300bhttps://en.wikipedia.org/wiki/the_elements_of_programming_style>".

centos7.6 ubuntu18.04 win10上均是此问题, 127.0.0.1:8000显示404

linked_list.py 中的remove操作仍然是错误的

很明显，你的prevnode并没有更新，从头到尾都是指向的根节点，这样的话，你每删除一个元素，实际上就是把这个元素前面的所有元素都删了，remove方法应该这样写：
def remove(self, value): # O(n)
""" 删除包含值的一个节点，将其前一个节点的 next 指向被查询节点的下一个即可
:param value:
"""
prevnode = self.root #
curnode = self.root.next
for curnode in self.iter_node():
if curnode.value == value:
prevnode.next = curnode.next
del curnode
self.length -= 1
return 1 # 表明删除成功
else：
prevnode = curnode
return -1 # 表明删除失败

单测问题

老师您好，我看您的课程中我发现您每次写完单测函数之后不执行那个函数，是因为您的那个测试工具就会自动执行里面的函数吗？

你好，剑指offer33题目的标题和内容不匹配哈，标题是最小数，代码是最大数

rt

README最后的微信收款码没有显示出来

README最后的微信收款码没有显示出来，是不是需要传到海外服务器地址？

视频能否考虑开源啊？

Pegasus，从知乎和哔哩哔哩关注你很久了，也看了你的很多vim视频，想问一下算法部分的视频能否开源啊？

priority queue优先级相同的元素

在priority queue里，如果只是比较tuple。在存在优先级相同的元素的时候，可能会出现问题。因为如果优先级相同，就会比较后面的value，这就不能保证FIFO。

HashTable里的_find_key() 是有bug，还是我理解有问题

    def _find_key(self, key):
        index = self._hash(key)
        _len = len(self._table)
        while self._table[index] is not HashTable.UNUSED:
            if self._table[index] is HashTable.EMPTY:
                index = (index*5 + 1) % _len
                continue
            elif self._table[index].key == key:
                return index
            else:
                index = (index*5 + 1) % _len
        return None

如果此时 len=8，table里有5个有效值3个EMPTY没有UNUSED，此时find的key不是5个有效值之一，那不是就永远不会退出while了吗？

LinkedList中appendleft方法

appendleft方法应该加入以下代码，否则新建链表先用appendleft再用append，会导致appendleft加入的节点丢失
if self.tailnode is None: self.tailnode = node

冒泡算法

冒泡算法介绍时，"它的**如下。对一个数组进行 n 轮迭代，每次比较相邻两个元素"，这里应该是 n-1吧，因为程序也是这样写的，所以为了统一，建议修改为n-1。

link：https://github.com/PegasusWang/python_data_structures_and_algorithms/blob/master/docs/12_%E5%9F%BA%E6%9C%AC%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/basic_sort.md

leetcode实战

请问 leetcode 实战教程 有对应的电子书或讲义吗

gitbook勘误

您好，在数据结构和算法 04队列有一句可能写错了～

2.看起来队列需要从头删除，向尾部增加元素，也就是 list.insert(0, element) 和 list.append(element)
应该不是insert是 pop

感谢您的教程～

btree.py里面的preorder_trav_use_stack

里面插入的是不是应该为peek 而不是 subtree

哈希表的二次探测函数有bug，会出现无限循环

大佬，你这里哈希表的二次探测函数，会出现无限循环的情况。

def _find_slot_for_insert(self, key):
    index = self._hash(key)
    _len = len(self._table)
    while not self._slot_can_insert(index):  # 直到找到一个可以用的槽
        index = (index * 5 + 1) % _len
    return index

def _slot_can_insert(self, index):
    return (self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED)

如上，如果index为5，此时5的位置上如果存在数据了，则需要继续找。假设此时_len为7，index为5， 则：（5 * 5 + 1）% 7 结果最终还是5，循环就无法跳出。

你好,关于循环双向链表的remove方法的一些疑问

我试了下,remove方法,发现只是长度上的改变,
链表的值没有改变(即使我使用del,删除对应的节点).
我修改的删除代码如下:

    def remove(self, value_node: Node):
        if self.lenght == 0:
            # raise Exception("is empty")
            return
        # 后一个节点连接前一个节点
        value_node.next.previous = value_node.previous
        # 前一个节点连接后一个节点
        value_node.previous = value_node.next
        del value_node
        # 记住还要记得删除节点
        self.lenght -= 1
        return 1

测试代码为:

    # 添加元素
    cycle_double_link_list.append(0)
    cycle_double_link_list.append(1)
    cycle_double_link_list.append(2)
    # 坐标添加元素
    cycle_double_link_list.appendLeft(4)

    # 长度判断
    assert len(cycle_double_link_list) == 4

    cycle_double_link_list.remove(value_node=head_node)
    assert len(cycle_double_link_list) == 3
    #下面这句报错,之前没错
    # assert list(cycle_double_link_list) == [0,1,2]

如果要实现列表的实时更新,该怎么做.谢谢.

[建议]教材介绍中追加勘误页的链接

Data Structures and Algorthms Using Python (数据结构与算法 Python实现版) 书中的小错误太多太多了.

最好能对照本书的官方勘误来阅读:

http://bcs.wiley.com/he-bcs/Books?action=resource&bcsId=9003&itemId=0470618299&resourceId=35653

hashtable中的key和value没有解释明白

Hash table 的几个问题

刚看了视频，有几个关于hash table的问题。

1. _load_factor为什么用装饰@Property？@Property有什么特殊的么，不装饰可以么？

2. 第90行，if key in self:。 这里能用in 是应为之前定义了__contains__是吧。

3. 在没有冲突的情况下，同一个hash函数，同一个key值，对于不同大小的hash table，得到的index是一样的么？这是必要条件，还是也可以不一样？比如hash table 的大小是5的时候，在没有冲突的情况下，hash(3) = 2， 那当hash table的大小变成10的时候，hash(3)一定要等于2么？

4. _rehash函数里面， 110行， 如果旧的slot 是empty的，不需要放在新的hash里面么？比如在旧的hash table里第5个slot有数A，又加了一个数B，hash值也是5，冲突，然后经过计算，B被放到了第6个slot。然后我们删掉第5个slot里的A，第五个slot是empty。 这时候rehash一下，第五个slot的状态是unsed。如果查找B，首先计算得到的是5，但是发现slot 5是unused， 会返回None。 所以是不是应该empty的slot也要考虑。

5. 第60行hash(key)，是用了python自带的hash的函数，如果不用python的hash函数，怎么能将所有的key map到数字呢？

关于bst删除节点时的两个疑问

请教两个问题，谢谢

一、 “删除只有一个孩子的节点时，只要把它的父亲指向它的孩子”，这里貌似有问题，例如：
root的key为60，左孩子为10，右孩子为70，然后70的左孩子为30
若删除70这个节点，则按上述规则30将会成为60的右孩子，不符合bst特性

二、 删除两个孩子的节点时，代码是这么写的：
successor_node = self._bst_min_node(subtree.right)
subtree.key, subtree.value = successor_node.key, successor_node.value
subtree.right = self._bst_remove(subtree.right, successor_node.key)

既然是互换了两个节点，为什么要最后一行给互换后节点的右孩子再去赋值？是否直接self._bst_remove(subtree.right, successor_node.key)就可以了？

关于Hash的问题

class Slot(object):
"""定义一个 hash 表 数组的槽
注意，一个槽有三种状态，看你能否想明白
1.从未使用 HashMap.UNUSED。此槽没有被使用和冲突过，查找时只要找到 UNUSED 就不用再继续探查了
2.使用过但是 remove 了，此时是 HashMap.EMPTY，该探查点后边的元素扔可能是有key
3.槽正在使用 Slot 节点
"""
def init(self, key, value):
self.key, self.value = key, value

这里的“ 2.使用过但是 remove 了，此时是 HashMap.EMPTY，该探查点后边的元素扔可能是有key”remove之后曹不应该为空了么 仍有可能是有key是什么意思

课时6find方法为什么不能和remove那样呢

循环双端列表链表append问题

dll = CirculateDoubleLinkedList()
此时maxsize = None 使用append方法 和appendleft 还是可以添加

append方法里面没有抛出异常
if self.maxsize is not None and len(self) > self.maxsize:
raise Exception("full")

改成下面代码就可以限制
if self.maxsize is None or len(self) >= self.maxsize:
raise Exception("full")