File: python/array.py

# 1.数组的插入、删除、按照下标随机访问操作；
# 2.数组中的数据类型是Int
#
# Author:Lee

class Array():

    def __init__(self):
        '''数组类初始化方法.'''
        self.__data = []  # 数据存储List

    def find(self, index):
        '''数组的查找方法.

        参数：
            index:将要查找的数据的下标

        返回：
            如果查找成功，则返回找到的数据
            如果查找失败，则返回False
        '''
        if index > len(self.__data) or index < 0:
            return False
        else:
            return self.__data[index]

    def delete(self, index):
        '''数组的删除方法.

        参数：
            index:将要删除的数据的下标

        返回：
            如果删除成功，则返回True
            如果删除失败，则返回False
        '''
        if index > len(self.__data) or index < 0:
            return False
        else:
            self.__data.pop(index)
            return True

    def insert(self, index, value):
        '''数组插入数据操作.

        参数：
            index:将要插入的下标
            value：将要插入的数据

        返回：
            如果插入成功，则返回True
            如果插入失败，则返回False
        '''
        if index > len(self.__data) or index < 0:
            return False
        else:
            self.__data.insert(index, value)
            return True

    def insertToTail(self, value):
        '''直接在数组尾部插入数据.

        参数：
            value:将要插入的数据
        '''
        self.__data.append(value)

    def printAll(self):
        '''打印当前数组所有数据'''
        print(self.__data)



File: python/45_bitmap/bitmap.py

"""
    Author: Wenru Dong
"""

from typing import Optional

class Bitmap:
    def __init__(self, num_bits: int):
        self._num_bits = num_bits
        self._bytes = bytearray(num_bits // 8 + 1)
    
    def setbit(self, k: int) -> None:
        if k > self._num_bits or k < 1: return
        self._bytes[k // 8] |= (1 << k % 8)
    
    def getbit(self, k: int) -> Optional[bool]:
        if k > self._num_bits or k < 1: return
        return self._bytes[k // 8] & (1 << k % 8) != 0


if __name__ == "__main__":
    bitmap = Bitmap(10)
    bitmap.setbit(1)
    bitmap.setbit(3)
    bitmap.setbit(6)
    bitmap.setbit(7)
    bitmap.setbit(8)

    for i in range(1, 11):
        print(bitmap.getbit(i))


File: python/14_sorts/counting_sort.py

"""
    计数排序

    Author: Wenru
"""

from typing import List
import itertools

def counting_sort(a: List[int]):
    if len(a) <= 1: return
    
    # a中有counts[i]个数不大于i
    counts = [0] * (max(a) + 1)
    for num in a:
        counts[num] += 1
    counts = list(itertools.accumulate(counts))

    # 临时数组，储存排序之后的结果
    a_sorted = [0] * len(a)
    for num in reversed(a):
        index = counts[num] - 1
        a_sorted[index] = num
        counts[num] -= 1
    
    a[:] = a_sorted


if __name__ == "__main__":
    a1 = [1, 2, 3, 4]
    counting_sort(a1)
    print(a1)

    a2 = [1, 1, 1, 1]
    counting_sort(a2)
    print(a2)

    a3 = [4, 5, 0, 9, 3, 3, 1, 9, 8, 7]
    counting_sort(a3)
    print(a3)



File: python/05_array/myarray.py

#
# 1) Insertion, deletion and random access of array
# 2) Assumes int for element type
#
# Author: Wenru
#


class MyArray:
    """A simple wrapper around List.
    You cannot have -1 in the array.
    """

    def __init__(self, capacity: int):
        self._data = []
        self._capacity = capacity

    def __getitem__(self, position: int) -> object:
        return self._data[position]

    def __setitem__(self, index: int, value: object):
        self._data[index] = value

    def __len__(self) -> int:
        return len(self._data)

    def __iter__(self):
        for item in self._data:
            yield item

    def find(self, index: int) -> object:
        try:
            return self._data[index]
        except IndexError:
            return None

    def delete(self, index: int) -> bool:
        try:
            self._data.pop(index)
            return True
        except IndexError:
            return False

    def insert(self, index: int, value: int) -> bool:
        if len(self) >= self._capacity:
            return False
        else:
            return self._data.insert(index, value)

    def print_all(self):
        for item in self:
            print(item)


def test_myarray():
    array = MyArray(5)
    array.insert(0, 3)
    array.insert(0, 4)
    array.insert(1, 5)
    array.insert(3, 9)
    array.insert(3, 10)
    assert array.insert(0, 100) is False
    assert len(array) == 5
    assert array.find(1) == 5
    assert array.delete(4) is True
    array.print_all()


if __name__ == "__main__":
    test_myarray()



File: python/39_backtracking/backtracking.py

"""
    Author: Wenru Dong
"""

from typing import List

def eight_queens() -> None:
    solutions = []

    def backtracking(queens_at_column: List[int], index_sums: List[int], index_diffs: List[int]) -> None:
        row = len(queens_at_column)
        if row == 8:
            solutions.append(queens_at_column)
            return
        for col in range(8):
            if col in queens_at_column or row + col in index_sums or row - col in index_diffs: continue
            backtracking(queens_at_column + [col], index_sums + [row + col], index_diffs + [row - col])
    
    backtracking([], [], [])
    print(*(" " + " ".join("*" * i + "Q" + "*" * (8 - i - 1) + "\n" for i in solution) for solution in solutions), sep="\n")


if __name__ == "__main__":

    eight_queens()



File: python/28_binary_heap/heap.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

import math
import random


class Heap:
    def __init__(self, nums=None, capacity=100):
        self._data = []
        self._capacity = capacity
        if type(nums) == list and len(nums) <= self._capacity:
            for n in nums:
                assert type(n) is int
                self._data.append(n)
        self._length = len(self._data)
        self._heapify()

    def _heapify(self):
        if self._length <= 1:
            return

        # idx of the Last Parent node
        lp = (self._length - 2) // 2

        for i in range(lp, -1, -1):
            self._heap_down(i)

    def _heap_down(self, idx):
        pass

    def insert(self, num):
        pass

    def get_top(self):
        if self._length <= 0:
            return None
        return self._data[0]

    def remove_top(self):
        if self._length <= 0:
            return None

        self._data[0], self._data[-1] = self._data[-1], self._data[0]
        ret = self._data.pop()
        self._length -= 1
        self._heap_down(0)

        return ret

    def get_data(self):
        return self._data

    def get_length(self):
        return self._length

    @staticmethod
    def _draw_heap(data):
        """
        格式化打印
        :param data:
        :return:
        """
        length = len(data)

        if length == 0:
            return 'empty heap'

        ret = ''
        for i, n in enumerate(data):
            ret += str(n)
            # 每行最后一个换行
            if i == 2 ** int(math.log(i + 1, 2) + 1) - 2 or i == len(data) - 1:
                ret += '\n'
            else:
                ret += ', '

        return ret

    def __repr__(self):
        return self._draw_heap(self._data)


class MaxHeap(Heap):
    def _heap_down(self, idx):
        if self._length <= 1:
            return

        lp = (self._length - 2) // 2

        while idx <= lp:
            lc = 2 * idx + 1
            rc = lc + 1

            if rc <= self._length-1:
                tmp = lc if self._data[lc] > self._data[rc] else rc
            else:
                tmp = lc

            if self._data[tmp] > self._data[idx]:
                self._data[tmp], self._data[idx] = self._data[idx], self._data[tmp]
                idx = tmp
            else:
                break

    def insert(self, num):
        if self._length >= self._capacity:
            return False

        self._data.append(num)
        self._length += 1

        nn = self._length - 1
        while nn > 0:
            p = (nn-1) // 2

            if self._data[nn] > self._data[p]:
                self._data[nn], self._data[p] = self._data[p], self._data[nn]
                nn = p
            else:
                break

        return True


class MinHeap(Heap):
    def _heap_down(self, idx):
        if self._length <= 1:
            return

        lp = (self._length - 2) // 2

        while idx <= lp:
            lc = 2 * idx + 1
            rc = lc + 1

            if rc <= self._length-1:
                tmp = lc if self._data[lc] < self._data[rc] else rc
            else:
                tmp = lc

            if self._data[tmp] < self._data[idx]:
                self._data[tmp], self._data[idx] = self._data[idx], self._data[tmp]
                idx = tmp
            else:
                break

    def insert(self, num):
        if self._length >= self._capacity:
            return False

        self._data.append(num)
        self._length += 1

        nn = self._length - 1
        while nn > 0:
            p = (nn-1) // 2

            if self._data[nn] < self._data[p]:
                self._data[nn], self._data[p] = self._data[p], self._data[nn]
                nn = p
            else:
                break

        return True


if __name__ == '__main__':
    nums = list(range(10))
    random.shuffle(nums)

    max_h = MaxHeap(nums)
    print('--- max heap ---')
    print(max_h)

    print('--- min heap ---')
    min_h = MinHeap(nums)
    print(min_h)



File: python/28_binary_heap/binary_heap.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

import math
import random


class BinaryHeap:
    """
    大顶堆
    """
    def __init__(self, data=None, capacity=100):
        self._data = []
        self._capacity = capacity
        if type(data) is list:
            if len(data) > self._capacity:
                raise Exception('Heap oversize, capacity:{}, data size:{}'.format(self._capacity, len(data)))
            self._type_assert(data)
            self._data = data

        self._length = len(self._data)

    def heapify(self):
        """
        堆化
        :return:
        """
        self._heapify(self._data, self._length-1)

    def _heapify(self, data, tail_idx):
        """
        堆化内部实现
        :param data: 需要堆化的数据
        :param tail_idx: 尾元素的索引
        :return:
        """
        # heapify data[:tail_idx+1]
        if tail_idx <= 0:
            return

        # idx of the Last Parent node
        lp = (tail_idx - 1) // 2

        for i in range(lp, -1, -1):
            self._heap_down(data, i, tail_idx)

    @staticmethod
    def _heap_down(data, idx, tail_idx):
        """
        将指定的位置堆化
        :param data: 需要堆化的数据
        :param idx: data: 中需要堆化的位置
        :param tail_idx: 尾元素的索引
        :return:
        """
        assert type(data) is list

        lp = (tail_idx - 1) // 2
        # top-down
        while idx <= lp:
            # Left and Right Child index
            lc = 2 * idx + 1
            rc = lc + 1

            # right child exists
            if rc <= tail_idx:
                tmp = lc if data[lc] > data[rc] else rc
            else:
                tmp = lc

            if data[tmp] > data[idx]:
                data[tmp], data[idx] = data[idx], data[tmp]
                idx = tmp
            else:
                break

    def insert(self, num):
        """
        插入
        :param num:
        :return:
        """
        if self._length < self._capacity:
            if self._insert(self._data, num):
                self._length += 1
                return True
        return False

    @staticmethod
    def _insert(data, num):
        """
        堆中插入元素的内部实现
        :param data:
        :param num:
        :return:
        """
        assert type(data) is list
        assert type(num) is int

        data.append(num)
        length = len(data)

        # idx of New Node
        nn = length - 1
        # bottom-up
        while nn > 0:
            p = (nn-1) // 2
            if data[nn] > data[p]:
                data[nn], data[p] = data[p], data[nn]
                nn = p
            else:
                break

        return True

    def get_top(self):
        """
        取堆顶
        :return:
        """
        if self._length <= 0:
            return None
        return self._data[0]

    def remove_top(self):
        """
        取堆顶
        :return:
        """
        ret = None
        if self._length > 0:
            ret = self._remove_top(self._data)
            self._length -= 1
        return ret

    @staticmethod
    def _remove_top(data):
        """
        取堆顶内部实现
        :param data:
        :return:
        """
        assert type(data) is list

        length = len(data)
        if length == 0:
            return None

        data[0], data[-1] = data[-1], data[0]
        ret = data.pop()
        length -= 1

        # length == 0 or == 1, return
        if length > 1:
            BinaryHeap._heap_down(data, 0, length-1)

        return ret

    @staticmethod
    def _type_assert(nums):
        assert type(nums) is list
        for n in nums:
            assert type(n) is int

    @staticmethod
    def _draw_heap(data):
        """
        格式化打印
        :param data:
        :return:
        """
        length = len(data)

        if length == 0:
            return 'empty heap'

        ret = ''
        for i, n in enumerate(data):
            ret += str(n)
            # 每行最后一个换行
            if i == 2**int(math.log(i+1, 2)+1) - 2 or i == len(data) - 1:
                ret += '\n'
            else:
                ret += ', '

        return ret

    def __repr__(self):
        return self._draw_heap(self._data)


if __name__ == '__main__':
    nums = list(range(10))
    random.shuffle(nums)

    bh = BinaryHeap(nums)
    print('--- before heapify ---')
    print(bh)

    # heapify
    bh.heapify()
    print('--- after heapify ---')
    print(bh)

    # insert
    print('--- insert ---')
    if bh.insert(8):
        print('insert success')
    else:
        print('insert fail')
    print(bh)

    # get top
    print('--- get top ---')
    print('get top of the heap: {}'.format(bh.get_top()))
    bh.remove_top()
    print(bh)



File: python/28_binary_heap/binary_heap_sort.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from binary_heap import BinaryHeap


class BinaryHeapSort(BinaryHeap):
    def __init__(self):
        super(BinaryHeapSort, self).__init__()

    def sort(self, nums):
        """
        排序
        1. 堆化，大顶堆
        2. 排序，从后往前遍历，首尾元素互换，子数组堆化
        :param nums:
        :return:
        """
        assert type(nums) is list
        length = len(nums)

        if length <= 1:
            return

        self._type_assert(nums)

        # heapify
        self._heapify(nums, length-1)

        # sort
        for i in range(length-1, 0, -1):
            nums[0], nums[i] = nums[i], nums[0]
            self._heap_down(nums, 0, i-1)

        return


if __name__ == '__main__':
    bhs = BinaryHeapSort()
    nums = [3, 5, 2, 6, 1, 7, 6]

    print('--- before sort ---')
    print(nums)

    bhs.sort(nums)
    print('--- after sort ---')
    print(nums)



File: python/28_binary_heap/top_k.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

import random
from heap import MinHeap


def top_k(nums, k):
    """
    返回数组的前k大元素
    :param nums:
    :param k:
    :return:
    """
    if len(nums) <= k:
        return nums

    min_h = MinHeap(nums[:k], k)
    for i in range(k, len(nums)):
        tmp = min_h.get_top()
        if nums[i] > tmp:
            min_h.remove_top()
            min_h.insert(nums[i])

    return min_h.get_data()


if __name__ == '__main__':
    nums = []
    k = 3

    for i in range(20):
        nums.append(random.randint(1, 100))

    print('--- nums ---')
    print(nums)

    print('--- top {} ---'.format(k))
    print(top_k(nums, k))



File: python/28_binary_heap/priority_queue.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

import math


class QueueNode:
    def __init__(self, priority, data=None):
        assert type(priority) is int and priority >= 0
        self.priority = priority
        self.data = data

    def __repr__(self):
        return str((self.priority, self.data))


class PriorityQueue:
    def __init__(self, capacity=100):
        self._capacity = capacity
        self._q = []
        self._length = 0

    def enqueue(self, priority, data=None):
        if self._length >= self._capacity:
            return False

        new_node = QueueNode(priority, data)
        self._q.append(new_node)
        self._length += 1

        # update queue
        nn = self._length - 1
        while nn > 0:
            p = (nn - 1) // 2
            if self._q[nn].priority < self._q[p].priority:
                self._q[nn], self._q[p] = self._q[p], self._q[nn]
                nn = p
            else:
                break

        return True

    def dequeue(self):
        if self._length <= 0:
            raise Exception('the queue is empty....')

        self._q[0], self._q[-1] = self._q[-1], self._q[0]
        ret = self._q.pop()
        self._length -= 1

        if self._length > 1:
            # update queue
            lp = (self._length - 2) // 2
            idx = 0

            while idx <= lp:
                lc = 2 * idx + 1
                rc = lc + 1

                if rc <= self._length - 1:
                    tmp = lc if self._q[lc].priority < self._q[rc].priority else rc
                else:
                    tmp = lc

                if self._q[tmp].priority < self._q[idx].priority:
                    self._q[tmp], self._q[idx] = self._q[idx], self._q[tmp]
                    idx = tmp
                else:
                    break
        return ret

    def get_length(self):
        return self._length

    @staticmethod
    def _draw_heap(data):
        """
        格式化打印
        :param data:
        :return:
        """
        length = len(data)

        if length == 0:
            return 'empty'

        ret = ''
        for i, n in enumerate(data):
            ret += str(n)
            # 每行最后一个换行
            if i == 2 ** int(math.log(i + 1, 2) + 1) - 2 or i == len(data) - 1:
                ret += '\n'
            else:
                ret += ', '

        return ret

    def __repr__(self):
        def formater(node):
            assert type(node) is QueueNode
            return node.priority, node.data

        data = list(map(formater, self._q))
        return self._draw_heap(data)


if __name__ == '__main__':
    pq = PriorityQueue()
    pq.enqueue(5, 'Watch TV')
    pq.enqueue(2, 'Learning')
    pq.enqueue(10, 'Go Sleep')
    pq.enqueue(0, 'Go Home')
    pq.enqueue(7, 'Mobile Games')
    print(pq)

    while pq.get_length() > 0:
        print(pq.dequeue())



File: python/40_dynamic_programming/yh_triangle.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from typing import List

Layer_nums = List[int]


def yh_triangle(nums: List[Layer_nums]) -> int:
    """
    从根节点开始向下走，过程中经过的节点，只需存储经过它时最小的路径和
    :param nums:
    :return:
    """
    assert len(nums) > 0
    n = len(nums)   # 层数
    memo = [[0]*n for i in range(n)]
    memo[0][0] = nums[0][0]

    for i in range(1, n):
        for j in range(i+1):
            # 每一层首尾两个数字，只有一条路径可以到达
            if j == 0:
                memo[i][j] = memo[i-1][j] + nums[i][j]
            elif j == i:
                memo[i][j] = memo[i-1][j-1] + nums[i][j]
            else:
                memo[i][j] = min(memo[i-1][j-1] + nums[i][j], memo[i-1][j] + nums[i][j])
    return min(memo[n-1])


def yh_triangle_space_optimization(nums: List[Layer_nums]) -> int:
    assert len(nums) > 0
    n = len(nums)
    memo = [0] * n
    memo[0] = nums[0][0]

    for i in range(1, n):
        for j in range(i, -1, -1):
            if j == i:
                memo[j] = memo[j-1] + nums[i][j]
            elif j == 0:
                memo[j] = memo[j] + nums[i][j]
            else:
                memo[j] = min(memo[j-1] + nums[i][j], memo[j] + nums[i][j])
    return min(memo)


def yh_triangle_bottom_up(nums: List[Layer_nums]) -> int:
    assert len(nums) > 0
    n = len(nums)
    memo = nums[-1].copy()

    for i in range(n-1, 0, -1):
        for j in range(i):
            memo[j] = min(memo[j] + nums[i-1][j], memo[j+1] + nums[i-1][j])
    return memo[0]


if __name__ == '__main__':
    nums = [[3], [2, 6], [5, 4, 2], [6, 0, 3, 2]]
    print(yh_triangle(nums))
    print(yh_triangle_space_optimization(nums))
    print(yh_triangle_bottom_up(nums))



File: python/40_dynamic_programming/knapsack.py

"""
    Author: Wenru Dong
"""

from typing import List

def knapsack01(weights: List[int], values: List[int], capacity: int) -> int:
    # Denote the state as (i, c), where i is the stage number,
    # and c is the capacity available. Denote f(i, c) to be the
    # maximum value when the capacity available is c, and Item 0
    # to Item i-1 are to be packed.
    # The goal is to find f(n-1, W), where W is the total capacity.
    # Then the DP functional equation is:
    #   f(i, c) = max(xᵢvᵢ + f(i-1, c-xᵢwᵢ)), xᵢ ∈ D, i ≥ 0,
    #   f(-1, c) = 0, 0 ≤ c ≤ W,
    # where
    #                  /  {0},    if wᵢ > c
    #   D = D(i, c) = 
    #                  \  {0, 1}, if wᵢ ≤ c

    prev = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        prev = [c >= w and max(prev[c], prev[c-w] + v) for c in range(capacity + 1)]
    return prev[-1]


if __name__ == "__main__":
    # To find the maximum weight that can be packed,
    # set values equal to the weights
    print(knapsack01([2, 2, 4, 6, 3], [2, 2, 4, 6, 3], 9))



File: python/40_dynamic_programming/01_bag.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from typing import List, Tuple


def bag(items_info: List[int], capacity: int) -> int:
    """
    固定容量的背包，计算能装进背包的物品组合的最大重量

    :param items_info: 每个物品的重量
    :param capacity: 背包容量
    :return: 最大装载重量
    """
    n = len(items_info)
    memo = [[-1]*(capacity+1) for i in range(n)]
    memo[0][0] = 1
    if items_info[0] <= capacity:
        memo[0][items_info[0]] = 1

    for i in range(1, n):
        for cur_weight in range(capacity+1):
            if memo[i-1][cur_weight] != -1:
                memo[i][cur_weight] = memo[i-1][cur_weight]   # 不选
                if cur_weight + items_info[i] <= capacity:    # 选
                    memo[i][cur_weight + items_info[i]] = 1

    for w in range(capacity, -1, -1):
        if memo[-1][w] != -1:
            return w


def bag_with_max_value(items_info: List[Tuple[int, int]], capacity: int) -> int:
    """
    固定容量的背包，计算能装进背包的物品组合的最大价值

    :param items_info: 物品的重量和价值
    :param capacity: 背包容量
    :return: 最大装载价值
    """
    n = len(items_info)
    memo = [[-1]*(capacity+1) for i in range(n)]
    memo[0][0] = 0
    if items_info[0][0] <= capacity:
        memo[0][items_info[0][0]] = items_info[0][1]

    for i in range(1, n):
        for cur_weight in range(capacity+1):
            if memo[i-1][cur_weight] != -1:
                memo[i][cur_weight] = memo[i-1][cur_weight]
                if cur_weight + items_info[i][0] <= capacity:
                    memo[i][cur_weight + items_info[i][0]] = max(memo[i][cur_weight + items_info[i][0]],
                                                                 memo[i-1][cur_weight] + items_info[i][1])
    return max(memo[-1])


if __name__ == '__main__':
    # [weight, ...]
    items_info = [2, 2, 4, 6, 3]
    capacity = 9
    print(bag(items_info, capacity))

    # [(weight, value), ...]
    items_info = [(3, 5), (2, 2), (1, 4), (1, 2), (4, 10)]
    capacity = 8
    print(bag_with_max_value(items_info, capacity))



File: python/41_dynamic_programming/coins_problem.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from typing import List


def coins_dp(values: List[int], target: int) -> int:
    # memo[i]表示target为i的时候，所需的最少硬币数
    memo = [0] * (target+1)
    # 0元的时候为0个
    memo[0] = 0

    for i in range(1, target+1):
        min_num = 999999
        # 对于values中的所有n
        # memo[i]为 min(memo[i-n1], memo[i-n2], ...) + 1
        for n in values:
            if i >= n:
                min_num = min(min_num, 1 + memo[i-n])
            else:   # values中的数值要从小到大排序
                break
        memo[i] = min_num

    # print(memo)
    return memo[-1]


min_num = 999999
def coins_backtracking(values: List[int], target: int, cur_value: int, coins_count: int):
    if cur_value == target:
        global min_num
        min_num = min(coins_count, min_num)
    else:
        for n in values:
            if cur_value + n <= target:
                coins_backtracking(values, target, cur_value+n, coins_count+1)


if __name__ == '__main__':
    values = [1, 3, 5]
    target = 23
    print(coins_dp(values, target))
    coins_backtracking(values, target, 0, 0)
    print(min_num)




File: python/41_dynamic_programming/min_dist.py

"""
    Author: Wenru Dong
"""

from typing import List
from itertools import accumulate

def min_dist(weights: List[List[int]]) -> int:
    """Find the minimum weight path from the weights matrix."""
    m, n = len(weights), len(weights[0])
    table = [[0] * n for _ in range(m)]
    # table[i][j] is the minimum distance (weight) when
    # there are i vertical moves and j horizontal moves
    # left.
    table[0] = list(accumulate(reversed(weights[-1])))
    for i, v in enumerate(accumulate(row[-1] for row in reversed(weights))):
        table[i][0] = v
    for i in range(1, m):
        for j in range(1, n):
            table[i][j] = weights[~i][~j] + min(table[i - 1][j], table[i][j - 1])
    return table[-1][-1]


def min_dist_recur(weights: List[List[int]]) -> int:
    m, n = len(weights), len(weights[0])
    table = [[0] * n for _ in range(m)]
    def min_dist_to(i: int, j: int) -> int:
        if i == j == 0: return weights[0][0]
        if table[i][j]: return table[i][j]
        min_left = float("inf") if j - 1 < 0 else min_dist_to(i, j - 1)
        min_up = float("inf") if i - 1 < 0 else min_dist_to(i - 1, j)
        return weights[i][j] + min(min_left, min_up)
    return min_dist_to(m - 1, n - 1)


if __name__ == "__main__":
    weights = [[1, 3, 5, 9], [2, 1, 3, 4], [5, 2, 6, 7], [6, 8, 4, 3]]
    print(min_dist(weights))
    print(min_dist_recur(weights))



File: python/12_sorts/quicksort_twoway.py

import random


def QuickSort(arr):
    # 双向排序: 提高非随机输入的性能
    # 不需要额外的空间,在待排序数组本身内部进行排序
    # 基准值通过random随机选取
    # 入参: 待排序数组, 数组开始索引 0, 数组结束索引 len(array)-1
    if arr is None or len(arr) < 1:
        return arr

    def swap(arr, low, upper):
        tmp = arr[low]
        arr[low] = arr[upper]
        arr[upper] = tmp
        return arr

    def QuickSort_TwoWay(arr, low, upper):
        # 小数组排序i可以用插入或选择排序
        # if upper-low < 50 : return arr
        # 基线条件: low index = upper index; 也就是只有一个值的区间
        if low >= upper:
            return arr
        # 随机选取基准值, 并将基准值替换到数组第一个元素
        swap(arr, low, int(random.uniform(low, upper)))
        temp = arr[low]
        # 缓存边界值, 从上下边界同时排序
        i, j = low, upper
        while True:
            # 第一个元素是基准值,所以要跳过
            i += 1
            # 在小区间中, 进行排序
            # 从下边界开始寻找大于基准值的索引
            while i <= upper and arr[i] <= temp:
                i += 1
            # 从上边界开始寻找小于基准值的索引
            # 因为j肯定大于i, 所以索引值肯定在小区间中
            while arr[j] > temp:
                j -= 1
            # 如果小索引大于等于大索引, 说明排序完成, 退出排序
            if i >= j:
                break
            swap(arr, i, j)
        # 将基准值的索引从下边界调换到索引分割点
        swap(arr, low, j)
        QuickSort_TwoWay(arr, low, j - 1)
        QuickSort_TwoWay(arr, j + 1, upper)
        return arr

    return QuickSort_TwoWay(arr, 0, len(arr) - 1)


if __name__ == "__main__":
    a1 = [3, 5, 6, 7, 8]
    a2 = [2, 2, 2, 2]
    a3 = [4, 3, 2, 1]
    a4 = [5, -1, 9, 3, 7, 8, 3, -2, 9]
    QuickSort(a1)
    print(a1)
    QuickSort(a2)
    print(a2)
    QuickSort(a3)
    print(a3)
    QuickSort(a4)
    print(a4)



File: python/12_sorts/quick_sort.py

"""
    Author: Wenru
"""

from typing import List
import random


def quick_sort(a: List[int]):
    _quick_sort_between(a, 0, len(a) - 1)


def _quick_sort_between(a: List[int], low: int, high: int):
    if low < high:
        # get a random position as the pivot
        k = random.randint(low, high)
        a[low], a[k] = a[k], a[low]

        m = _partition(a, low, high)  # a[m] is in final position
        _quick_sort_between(a, low, m - 1)
        _quick_sort_between(a, m + 1, high)


def _partition(a: List[int], low: int, high: int):
    pivot, j = a[low], low
    for i in range(low + 1, high + 1):
        if a[i] <= pivot:
            j += 1
            a[j], a[i] = a[i], a[j]  # swap
    a[low], a[j] = a[j], a[low]
    return j


def test_quick_sort():
    a1 = [3, 5, 6, 7, 8]
    quick_sort(a1)
    assert a1 == [3, 5, 6, 7, 8]
    a2 = [2, 2, 2, 2]
    quick_sort(a2)
    assert a2 == [2, 2, 2, 2]
    a3 = [4, 3, 2, 1]
    quick_sort(a3)
    assert a3 == [1, 2, 3, 4]
    a4 = [5, -1, 9, 3, 7, 8, 3, -2, 9]
    quick_sort(a4)
    assert a4 == [-2, -1, 3, 3, 5, 7, 8, 9, 9]


if __name__ == "__main__":
    a1 = [3, 5, 6, 7, 8]
    a2 = [2, 2, 2, 2]
    a3 = [4, 3, 2, 1]
    a4 = [5, -1, 9, 3, 7, 8, 3, -2, 9]
    quick_sort(a1)
    print(a1)
    quick_sort(a2)
    print(a2)
    quick_sort(a3)
    print(a3)
    quick_sort(a4)
    print(a4)



File: python/12_sorts/merge_sort.py

"""
    Author: Wenru
"""

from typing import List


def merge_sort(a: List[int]):
    _merge_sort_between(a, 0, len(a) - 1)


def _merge_sort_between(a: List[int], low: int, high: int):
    # The indices are inclusive for both low and high.
    if low < high:
        mid = low + (high - low) // 2
        _merge_sort_between(a, low, mid)
        _merge_sort_between(a, mid + 1, high)
        _merge(a, low, mid, high)


def _merge(a: List[int], low: int, mid: int, high: int):
    # a[low:mid], a[mid+1, high] are sorted.
    i, j = low, mid + 1
    tmp = []
    while i <= mid and j <= high:
        if a[i] <= a[j]:
            tmp.append(a[i])
            i += 1
        else:
            tmp.append(a[j])
            j += 1
    start = i if i <= mid else j
    end = mid if i <= mid else high
    tmp.extend(a[start:end + 1])
    a[low:high + 1] = tmp


def test_merge_sort():
    a1 = [3, 5, 6, 7, 8]
    merge_sort(a1)
    assert a1 == [3, 5, 6, 7, 8]
    a2 = [2, 2, 2, 2]
    merge_sort(a2)
    assert a2 == [2, 2, 2, 2]
    a3 = [4, 3, 2, 1]
    merge_sort(a3)
    assert a3 == [1, 2, 3, 4]
    a4 = [5, -1, 9, 3, 7, 8, 3, -2, 9]
    merge_sort(a4)
    assert a4 == [-2, -1, 3, 3, 5, 7, 8, 9, 9]


if __name__ == "__main__":
    a1 = [3, 5, 6, 7, 8]
    a2 = [2, 2, 2, 2]
    a3 = [4, 3, 2, 1]
    a4 = [5, -1, 9, 3, 7, 8, 3, -2, 9]
    merge_sort(a1)
    print(a1)
    merge_sort(a2)
    print(a2)
    merge_sort(a3)
    print(a3)
    merge_sort(a4)
    print(a4)



File: python/42_dynamic_programming/longest_increasing_subsequence.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from typing import List


def longest_increasing_subsequence(nums: List[int]) -> int:
    """
    最长子上升序列的一种DP解法，从回溯解法转化，思路类似于有限物品的背包问题
    每一次决策都算出当前可能的lis的长度，重复子问题合并，合并策略是lis的末尾元素最小
    时间复杂度：O(n^2)
    空间复杂度：O(n^2)，可优化至O(n)

    没leetcode上的参考答案高效，提供另一种思路作为参考
    https://leetcode.com/problems/longest-increasing-subsequence/solution/
    :param nums:
    :return:
    """
    if not nums:
        return 0

    n = len(nums)
    # memo[i][j] 表示第i次决策，长度为j的lis的 最小的 末尾元素数值
    # 每次决策都根据上次决策的所有可能转化，空间上可以类似背包优化为O(n)
    memo = [[-1] * (n+1) for _ in range(n)]

    # 第一列全赋值为0，表示每次决策都不选任何数
    for i in range(n):
        memo[i][0] = 0
    # 第一次决策选数组中的第一个数
    memo[0][1] = nums[0]

    for i in range(1, n):
        for j in range(1, n+1):
            # case 1: 长度为j的lis在上次决策后存在，nums[i]比长度为j-1的lis末尾元素大
            if memo[i-1][j] != -1 and nums[i] > memo[i-1][j-1]:
                memo[i][j] = min(nums[i], memo[i-1][j])

            # case 2: 长度为j的lis在上次决策后存在，nums[i]比长度为j-1的lis末尾元素小/等
            if memo[i-1][j] != -1 and nums[i] <= memo[i-1][j-1]:
                memo[i][j] = memo[i-1][j]

            if memo[i-1][j] == -1:
                # case 3: 长度为j的lis不存在，nums[i]比长度为j-1的lis末尾元素大
                if nums[i] > memo[i-1][j-1]:
                    memo[i][j] = nums[i]
                # case 4: 长度为j的lis不存在，nums[i]比长度为j-1的lis末尾元素小/等
                break

    for i in range(n, -1, -1):
        if memo[-1][i] != -1:
            return i


if __name__ == '__main__':
    # 要求输入的都是大于0的正整数(可优化至支持任意整数)
    nums = [2, 9, 3, 6, 5, 1, 7]
    print(longest_increasing_subsequence(nums))



File: python/42_dynamic_programming/min_edit_dist.py

"""
    Author: Wenru Dong
"""

def levenshtein_dp(s: str, t: str) -> int:
    m, n = len(s), len(t)
    table = [[0] * (n) for _ in range(m)]

    for i in range(n):
        if s[0] == t[i]:
            table[0][i] = i - 0
        elif i != 0:
            table[0][i] = table[0][i - 1] + 1
        else:
            table[0][i] = 1

    for i in range(m):
        if s[i] == t[0]:
            table[i][0] = i - 0
        elif i != 0:
            table[i][0] = table[i - 1][0] + 1
        else:
            table[i][0] = 1

    for i in range(1, m):
        for j in range(1, n):
            table[i][j] = min(1 + table[i - 1][j], 1 + table[i][j - 1], int(s[i] != t[j]) + table[i - 1][j - 1])

    print(table)
    return table[-1][-1]


def common_substring_dp(s: str, t: str) -> int:
    m, n = len(s), len(t)
    table = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            table[i][j] = max(table[i - 1][j], table[i][j - 1], int(s[i - 1] == t[j - 1]) + table[i - 1][j - 1])
    return table[-1][-1]


if __name__ == "__main__":
    s = "mitcmu"
    t = "mtacnu"

    print(levenshtein_dp(s, t))
    print(common_substring_dp(s, t))

    s = "kitten"
    t = "sitting"

    print(levenshtein_dp(s, t))
    print(common_substring_dp(s, t))

    s = "flaw"
    t = "lawn"

    print(levenshtein_dp(s, t))
    print(common_substring_dp(s, t))


File: python/38_divide_and_conquer/merge_sort_counting.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

inversion_num = 0


def merge_sort_counting(nums, start, end):
    if start >= end:
        return

    mid = (start + end)//2
    merge_sort_counting(nums, start, mid)
    merge_sort_counting(nums, mid+1, end)
    merge(nums, start, mid, end)


def merge(nums, start, mid, end):
    global inversion_num
    i = start
    j = mid+1
    tmp = []
    while i <= mid and j <= end:
        if nums[i] <= nums[j]:
            inversion_num += j - mid - 1
            tmp.append(nums[i])
            i += 1
        else:
            tmp.append(nums[j])
            j += 1

    while i <= mid:
        # 这时nums[i]的逆序数是整个nums[mid+1: end+1]的长度
        inversion_num += end - mid
        tmp.append(nums[i])
        i += 1

    while j <= end:
        tmp.append(nums[j])
        j += 1

    nums[start: end+1] = tmp


if __name__ == '__main__':
    print('--- count inversion number using merge sort ---')
    # nums = [5, 0, 4, 2, 3, 1, 6, 8, 7]
    nums = [5, 0, 4, 2, 3, 1, 3, 3, 3, 6, 8, 7]
    print('nums  : {}'.format(nums))
    merge_sort_counting(nums, 0, len(nums)-1)
    print('sorted: {}'.format(nums))
    print('inversion number: {}'.format(inversion_num))



File: python/33_bm/bm.py

"""
    Boyer-Moore string-search algorithm.

    Author: Wenru Dong
"""

from typing import List, Tuple

SIZE = 256

def _generate_bad_character_table(pattern: str) -> List[int]:
    bc = [-1] * SIZE
    for i, char in enumerate(pattern):
        bc[ord(char)] = i
    return bc


def _generate_good_suffix_table(pattern: str) -> Tuple[List[bool], List[int]]:
    m = len(pattern)
    # prefix[k] records whether the last k-character suffix of pattern
    # can match with the first k-character prefix of pattern.
    # suffix[k] records the starting index of the last substring of
    # pattern that can match with the last k-character suffix of pattern.
    prefix, suffix = [False] * m, [-1] * m
    # For each substring patter[:i+1], we find the common suffix with
    # pattern, and the starting index of this common suffix.
    # This way we can re-write previous suffix[k] to record the index
    # as large as possible, hence the last substring.
    for i in range(m - 1):
        j = i  # starting index of the common suffix
        k = 0  # length of the common suffix
        while j >= 0 and pattern[j] == pattern[~k]:
            j -= 1
            k += 1
            suffix[k] = j + 1
        if j == -1: prefix[k] = True
    return (prefix, suffix)


def _move_by_good_suffix(bad_character_index: int, suffix: List[int], prefix: List[bool]) -> int:
    k = len(suffix) - 1 - bad_character_index
    if suffix[k] != -1: return bad_character_index - suffix[k] + 1
    # Test from k - 1
    for r, can_match_prefix in enumerate(reversed(prefix[:k]), bad_character_index + 2): 
        if can_match_prefix: return r
    return len(suffix)


def bm(s: str, pattern: str) -> int:
    bc = _generate_bad_character_table(pattern)
    prefix, suffix = _generate_good_suffix_table(pattern)
    n, m = len(s), len(pattern)
    i = 0
    while i <= n - m:
        j = m - 1  # bad character index in pattern
        while j >= 0: 
            if s[i + j] != pattern[j]: break
            j -= 1
        if j < 0: return i
        
        x = j - bc[ord(s[i + j])]
        y = 0
        if j < m - 1:
            y = _move_by_good_suffix(j, suffix, prefix)
        i += max(x, y)
    return -1


if __name__ == "__main__":

    s = "Here is a simple example"
    pattern = "example"
    print(bm(s, pattern))

    s = "abcdcccdc"
    pattern = "cccd"
    print(s.find(pattern) == bm(s, pattern))


File: python/33_bm/bm_.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

SIZE = 256


def bm(main, pattern):
    """
    BM算法
    匹配规则：
    1. 坏字符规则
    2. 好字符规则
    :param main:
    :param pattern:
    :return:
    """
    assert type(main) is str and type(pattern) is str
    n, m = len(main), len(pattern)

    if n <= m:
        return 0 if main == pattern else -1

    # bc
    bc = [-1] * SIZE
    generate_bc(pattern, m, bc)

    # gs
    suffix = [-1] * m
    prefix = [False] * m
    generate_gs(pattern, m, suffix, prefix)

    i = 0
    while i < n-m+1:
        j = m - 1
        while j >= 0:
            if main[i+j] != pattern[j]:
                break
            else:
                j -= 1

        # pattern整个已被匹配，返回
        if j == -1:
            return i

        # 1. bc规则计算后移位数
        x = j - bc[ord(main[i+j])]

        # 2. gs规则计算后移位数
        y = 0
        if j != m - 1:    # 存在gs
            y = move_by_gs(j, m, suffix, prefix)

        i += max(x, y)

    return -1


def generate_bc(pattern, m, bc):
    """
    生成坏字符哈希表
    :param pattern:
    :param m:
    :param bc:
    :return:
    """
    for i in range(m):
        bc[ord(pattern[i])] = i


def generate_gs(pattern, m, suffix, prefix):
    """
    好后缀预处理
    :param pattern:
    :param m:
    :param suffix:
    :param prefix:
    :return:
    """
    for i in range(m-1):
        k = 0   # pattern[:i+1]和pattern的公共后缀长度
        for j in range(i, -1, -1):
            if pattern[j] == pattern[m-1-k]:
                k += 1
                suffix[k] = j
                if j == 0:
                    prefix[k] = True
            else:
                break


def move_by_gs(j, m, suffix, prefix):
    """
    通过好后缀计算移动值
    需要处理三种情况：
    1. 整个好后缀在pattern仍能找到
    2. 好后缀里存在 *后缀子串* 能和pattern的 *前缀* 匹配
    3. 其他
    :param j:
    :param m:
    :param suffix:
    :param prefix:
    :return:
    """
    k = m - 1 - j           # j指向从后往前的第一个坏字符，k是此次匹配的好后缀的长度

    if suffix[k] != -1:             # 1. 整个好后缀在pattern剩余字符中仍有出现
        return j - suffix[k] + 1
    else:
        for r in range(j+2, m):     # 2. 后缀子串从长到短搜索
            if prefix[m-r]:
                return r
        return m                    # 3. 其他情况


if __name__ == '__main__':
    print('--- search ---')
    m_str = 'dfasdeeeetewtweyyyhtruuueyytewtweyyhtrhrth'
    p_str = 'eyytewtweyy'
    print('[Built-in Functions] result:', m_str.find(p_str))
    print('[bm] result:', bm(m_str, p_str))



File: python/07_linkedlist/linked_list_algo.py

"""
    1) Reverse singly-linked list
    2) Detect cycle in a list
    3) Merge two sorted lists
    4) Remove nth node from the end
    5) Find middle node

    Author: Wenru
"""

from typing import Optional


class Node:
    
    def __init__(self, data: int, next=None):
        self.data = data
        self._next = next

# Reverse singly-linked list
# 单链表反转
# Note that the input is assumed to be a Node, not a linked list.
def reverse(head: Node) -> Optional[Node]:
    reversed_head = None
    current = head
    while current:
        reversed_head, reversed_head._next, current = current, reversed_head, current._next
    return reversed_head

# Detect cycle in a list
# 检测环
def has_cycle(head: Node) -> bool:
    slow, fast = head, head
    while fast and fast._next:
        slow = slow._next
        fast = fast._next._next
        if slow == fast:
            return True
    return False

# Merge two sorted linked list
# 有序链表合并
def merge_sorted_list(l1: Node, l2: Node) -> Optional[Node]:
    if l1 and l2:
        p1, p2 = l1, l2
        fake_head = Node(None)
        current = fake_head
        while p1 and p2:
            if p1.data <= p2.data:
                current._next = p1
                p1 = p1._next
            else:
                current._next = p2
                p2 = p2._next
            current = current._next
        current._next = p1 if p1 else p2
        return fake_head._next
    return l1 or l2

# Remove nth node from the end
# 删除倒数第n个节点。假设n大于0
def remove_nth_from_end(head: Node, n: int) -> Optional[Node]:
    fast = head
    count = 0
    while fast and count < n:
        fast = fast._next
        count += 1
    if not fast and count < n:  # not that many nodes
        return head
    if not fast and count == n:
        return head._next
    
    slow = head
    while fast._next:
        fast, slow = fast._next, slow._next
    slow._next = slow._next._next
    return head

def find_middle_node(head: Node) -> Optional[Node]:
    slow, fast = head, head
    fast = fast._next if fast else None
    while fast and fast._next:
        slow, fast = slow._next, fast._next._next
    return slow

def print_all(head: Node):
    nums = []
    current = head
    while current:
        nums.append(current.data)
        current = current._next
    print("->".join(str(num) for num in nums))



File: python/08_stack/simple_browser.py

"""
    a simple browser realize
    Author: zhenchao.zhu
    解答：我们使用两个栈，X 和 Y，我们把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈 X 中出栈，
    并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。
    当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，
    那就说明没有页面可以点击前进按钮浏览了。
"""

import sys
# 引用当前文件夹下的single_linked_list
sys.path.append('linked_stack.py')
from linked_stack import LinkedStack
#from .linked_stack import LinkedStack

class NewLinkedStack(LinkedStack):

    def is_empty(self):
        return not self._top


class Browser():

    def __init__(self):
        self.forward_stack = NewLinkedStack()
        self.back_stack = NewLinkedStack()

    def can_forward(self):
        if self.back_stack.is_empty():
            return False

        return True

    def can_back(self):
        if self.forward_stack.is_empty():
            return False

        return True

    def open(self, url):
        print("Open new url %s" % url, end="\n")
        self.forward_stack.push(url)

    def back(self):
        if self.forward_stack.is_empty():
            return

        top = self.forward_stack.pop()
        self.back_stack.push(top)
        print("back to %s" % top, end="\n")

    def forward(self):
        if self.back_stack.is_empty():
            return

        top = self.back_stack.pop()
        self.forward_stack.push(top)
        print("forward to %s" % top, end="\n")


if __name__ == '__main__':

    browser = Browser()
    browser.open('a')
    browser.open('b')
    browser.open('c')
    if browser.can_back():
        browser.back()

    if browser.can_forward():
        browser.forward()

    browser.back()
    browser.back()
    browser.back()



File: python/08_stack/linked_stack.py

"""
    Stack based upon linked list
    基于链表实现的栈
    
    Author: Wenru
"""

from typing import Optional

class Node:
    
    def __init__(self, data: int, next=None):
        self._data = data
        self._next = next
    

class LinkedStack:
    """A stack based upon singly-linked list.
    """
    def __init__(self):
        self._top: Node = None
    
    def push(self, value: int):
        new_top = Node(value)
        new_top._next = self._top
        self._top = new_top
    
    def pop(self) -> Optional[int]:
        if self._top:
            value = self._top._data
            self._top = self._top._next
            return value
    
    def __repr__(self) -> str:
        current = self._top
        nums = []
        while current:
            nums.append(current._data)
            current = current._next
        return " ".join(f"{num}]" for num in nums)

if __name__ == "__main__":
    stack = LinkedStack()
    for i in range(9):
        stack.push(i)
    print(stack)
    for _ in range(3):
        stack.pop()
    print(stack)


File: python/26_red_black_tree/red_black_tree.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from queue import Queue
import pygraphviz as pgv
import random

OUTPUT_PATH = 'E:/'


class TreeNode:
    def __init__(self, val=None, color=None):
        self.val = val
        assert color in ['r', 'b']
        self.color = 'red' if color == 'r' else 'black'

        self.left = None
        self.right = None
        self.parent = None

    def is_black(self):
        return self.color == 'black'

    def set_black(self):
        self.color = 'black'
        return

    def set_red(self):
        self.color = 'red'


class RedBlackTree:
    """
    红黑树实现
    参考资料：
    1. 《算法导论》
    第13章 红黑树
    13.3 插入 p178
    13.4 删除 p183

    2. 红黑树（二）：删除
    https://zhuanlan.zhihu.com/p/25402654
    """
    def __init__(self, val_list=None):
        self.root = None
        self.black_leaf = TreeNode(color='b')  # 共用的黑色叶子节点

        # 可用数组初始化
        if type(val_list) is list:
            for n in val_list:
                assert type(n) is int
                self.insert(n)

    def search(self, val):
        """
        搜索
        :param val:
        :return:
        """
        if self.root is None:
            return None

        n = self.root
        while n != self.black_leaf:
            if val < n.val:
                n = n.left
            elif val > n.val:
                n = n.right
            else:
                return n
        return None

    def insert(self, val):
        """
        插入
        :param val:
        :return:
        """
        assert type(val) is int

        new_node = TreeNode(val, 'r')  # 新插入的节点为红色

        # 根节点
        if self.root is None:
            self.root = new_node
        else:
            n = self.root
            while n != self.black_leaf:  # 黑色叶子节点
                p = n
                if val < n.val:
                    n = n.left
                elif val > n.val:
                    n = n.right
                else:
                    raise KeyError('val:{} already exists')  # 该值已存在，插入失败

            if val < p.val:
                p.left = new_node
            else:
                p.right = new_node
            new_node.parent = p

        new_node.left = new_node.right = self.black_leaf
        # 插入后调整
        self._insert_fixup(new_node)

    def _insert_fixup(self, node):
        """
        插入调整
        参考资料：《算法导论》 13.3 p178-179
        :param node:
        :return:
        """
        n = node
        while n is not self.root and not n.parent.is_black():
            # 父p 叔u 祖父g
            p = self.parent(n)
            u = self.bro(p)
            g = self.parent(p)

            if not u.is_black():        # case 1
                p.set_black()           # case 1
                u.set_black()           # case 1
                g.set_red()             # case 1
                n = g                   # case 1
                continue

            if p == g.left:     # p为左结点
                if n == p.right:        # case 2
                    self.rotate_l(p)    # case 2
                    n, p = p, n         # case 2
                p.set_black()           # case 3
                g.set_red()             # case 3
                self.rotate_r(g)        # case 3
            else:               # p为右节点
                if n == p.left:         # case 2
                    self.rotate_r(p)    # case 2
                    n, p = p, n         # case 2
                p.set_black()           # case 3
                g.set_red()             # case 3
                self.rotate_l(g)        # case 3

        # 根节点强制置黑，有两种情况根节点是红色：
        # 1. 新插入时是红色
        # 2. 经过case 1调整过后变红色
        self.root.color = 'black'

    def delete(self, val):
        """
        删除
        :param val:
        :return:
        """
        assert type(val) is int

        n = self.search(val)
        if n is None:
            print('can not find any nodes with value: {}'.format(val))
            return

        self._delete_node(n)

    def _delete_node(self, node):
        """
        删除节点内部实现
        参考资料：《算法导论》 13.4 p183-184
        实现方式有微调，当n有2个子节点时，将s拷贝至n，转为删除s(s最多有一个子节点)
        :param node:
        :return:
        """
        n = node

        # n的子节点个数等于2
        if self.children_count(n) == 2:
            # 寻找n的后继s
            s = n.right
            while s.left != self.black_leaf:
                s = s.left
            n.val = s.val
            # 将删除n转化为删除s
            n = s

        # n的子节点个数小于2
        if n.left == self.black_leaf:
            c = n.right
        else:
            c = n.left
        self._transplant(n, c)

        # 删除的节点是黑色，需要调整
        if n.is_black():
            self._delete_fixup(c)
        return

    def _delete_fixup(self, node):
        """
        删除调整
        参考资料：《算法导论》 13.4 p185-187
        :param node:
        :return:
        """
        n = node
        while n != self.root and n.is_black():
            p = self.parent(n)
            b = self.bro(n)

            # 左右节点对称
            if p.left == n:
                if not b.is_black():
                    b.set_black()                   # case 1
                    p.set_red()                     # case 1
                    self.rotate_l(p)                # case 1
                    # new bro after rotate
                    b = self.bro(n)                 # case 1

                if b.left.is_black() and b.right.is_black():
                    b.set_red()                     # case 2
                    n = p                           # case 2
                else:
                    if b.right.is_black():
                        b.left.set_black()          # case 3
                        b.set_red()                 # case 3
                        self.rotate_r(b)            # case 3
                        # new bro after rotate
                        b = self.bro(n)             # case 3

                    # 注意，因为p可能是红或黑，所以不能直接赋值颜色，只能copy
                    b.color = p.color               # case 4
                    p.set_black()                   # case 4
                    b.right.set_black()             # case 4
                    self.rotate_l(p)                # case 4
                    # trick, 调整结束跳出while
                    n = self.root                   # case 4
            else:
                if not b.is_black():
                    b.set_black()                   # case 1
                    p.set_red()                     # case 1
                    self.rotate_r(p)                # case 1
                    # new bro after rotate
                    b = self.bro(n)                 # case 1

                if b.left.is_black() and b.right.is_black():
                    b.set_red()                     # case 2
                    n = p                           # case 2
                else:
                    if b.left.is_black():
                        b.right.set_black()         # case 3
                        b.set_red()                 # case 3
                        self.rotate_l(b)            # case 3
                        # new bro after rotate
                        b = self.bro(n)             # case 3

                    # 注意，因为p可能是红或黑，所以不能直接赋值颜色，只能copy
                    b.color = p.color               # case 4
                    p.set_black()                   # case 4
                    b.left.set_black()              # case 4
                    self.rotate_r(p)                # case 4
                    # trick, 调整结束跳出while
                    n = self.root                   # case 4

        # 将n设为黑色，从上面while循环跳出，情况有两种
        # 1. n是根节点，直接无视附加的黑色
        # 2. n是红色的节点，则染黑
        n.set_black()

    def _transplant(self, n1, n2):
        """
        节点移植， n2 -> n1
        :param n1: 原节点
        :param n2: 移植节点
        :return:
        """
        if n1 == self.root:
            if n2 != self.black_leaf:
                self.root = n2
                n2.parent = None
            else:
                self.root = None    # 只有删除根节点时会进来
        else:
            p = self.parent(n1)
            if p.left == n1:
                p.left = n2
            else:
                p.right = n2

            n2.parent = p

    def rotate_l(self, node):
        """
        左旋
        :param node:
        :return:
        """
        if node is None:
            return

        if node.right is self.black_leaf:
            return
            # raise Exception('try rotate left , but the node "{}" has no right child'.format(node.val))

        p = self.parent(node)
        x = node
        y = node.right

        # node为根节点时，p为None，旋转后要更新根节点指向
        if p is not None:
            if x == p.left:
                p.left = y
            else:
                p.right = y
        else:
            self.root = y

        x.parent, y.parent = y, p

        if y.left != self.black_leaf:
            y.left.parent = x

        x.right, y.left = y.left, x

    def rotate_r(self, node):
        """
        右旋
        :param node:
        :return:
        """
        if node is None:
            return

        if node.left is self.black_leaf:
            return
            # raise Exception('try rotate right , but the node "{}" has no left child'.format(node.val))

        p = self.parent(node)
        x = node
        y = node.left

        # 同左旋
        if p is not None:
            if x == p.left:
                p.left = y
            else:
                p.right = y
        else:
            self.root = y

        x.parent, y.parent = y, p

        if y.right is not None:
            y.right.parent = x

        x.left, y.right = y.right, x

    @staticmethod
    def bro(node):
        """
        获取兄弟节点
        :param node:
        :return:
        """
        if node is None or node.parent is None:
            return None
        else:
            p = node.parent
            if node == p.left:
                return p.right
            else:
                return p.left

    @staticmethod
    def parent(node):
        """
        获取父节点
        :param node:
        :return:
        """
        if node is None:
            return None
        else:
            return node.parent

    def children_count(self, node):
        """
        获取子节点个数
        :param node:
        :return:
        """
        return 2 - [node.left, node.right].count(self.black_leaf)

    def draw_img(self, img_name='Red_Black_Tree.png'):
        """
        画图
        用pygraphviz画出节点和箭头
        箭头的红色和黑色分别代表左和右
        :param img_name:
        :return:
        """
        if self.root is None:
            return

        tree = pgv.AGraph(directed=True, strict=True)

        q = Queue()
        q.put(self.root)

        while not q.empty():
            n = q.get()
            if n != self.black_leaf:  # 黑色叶子的连线由各个节点自己画
                tree.add_node(n.val, color=n.color)
                #  画父节点箭头
                # if n.parent is not None:
                #     tree.add_edge(n.val, n.parent.val)

                for c in [n.left, n.right]:
                    q.put(c)
                    color = 'red' if c == n.left else 'black'
                    if c != self.black_leaf:
                        tree.add_edge(n.val, c.val, color=color)
                    else:
                        tree.add_edge(n.val, 'None', color=color)

        tree.graph_attr['epsilon'] = '0.01'
        tree.layout('dot')
        tree.draw(OUTPUT_PATH + img_name)
        return True


if __name__ == '__main__':
    rbt = RedBlackTree()

    # insert
    nums = list(range(1, 25))
    # random.shuffle(nums)
    for num in nums:
        rbt.insert(num)

    # search
    search_num = 23
    n = rbt.search(search_num)
    if n is not None:
        print(n)
    else:
        print('node {} not found'.format(search_num))

    # delete
    rbt.delete(4)

    # draw image
    rbt.draw_img('rbt.png')



File: python/09_queue/dynamic_array_queue.py

"""
    Author: Wenru
"""

from typing import Optional

class DynamicArrayQueue:

    def __init__(self, capacity: int):
        self._items = []
        self._capacity = capacity
        self._head = 0
        self._tail = 0
    
    def enqueue(self, item: str) -> bool:
        if self._tail == self._capacity:
            if self._head == 0: return False
            
            self._items[0 : self._tail - self._head] = self._items[self._head : self._tail]
            self._tail -= self._head
            self._head = 0
        
        if self._tail == len(self._items):
            self._items.append(item)
        else:
            self._items[self._tail] = item
        self._tail += 1
        return True

    def dequeue(self) -> Optional[str]:
        if self._head != self._tail:
            item = self._items[self._head]
            self._head += 1
            return item
    
    def __repr__(self) -> str:
        return " ".join(item for item in self._items[self._head:self._tail])

if __name__ == "__main__":
    q = DynamicArrayQueue(10)
    for i in range(10):
        q.enqueue(str(i))
    print(q)

    for _ in range(3):
        q.dequeue()
    print(q)

    q.enqueue("7")
    q.enqueue("8")
    print(q)


File: python/09_queue/linked_queue.py

"""
    Queue based upon linked list

    Author: Wenru
"""

from typing import Optional

class Node:
    
    def __init__(self, data: str, next=None):
        self.data = data
        self._next = next

class LinkedQueue:

    def __init__(self):
        self._head: Optional[Node] = None
        self._tail: Optional[Node] = None
    
    def enqueue(self, value: str):
        new_node = Node(value)
        if self._tail:
            self._tail._next = new_node
        else:
            self._head = new_node
        self._tail = new_node
    
    def dequeue(self) -> Optional[str]:
        if self._head:
            value = self._head.data
            self._head = self._head._next
            if not self._head:
                self._tail = None
            return value
    
    def __repr__(self) -> str:
        values = []
        current = self._head
        while current:
            values.append(current.data)
            current = current._next
        return "->".join(value for value in values)


if __name__ == "__main__":
    q = LinkedQueue()
    for i in range(10):
        q.enqueue(str(i))
    print(q)

    for _ in range(3):
        q.dequeue()
    print(q)

    q.enqueue("7")
    q.enqueue("8")
    print(q)



File: python/09_queue/array_queue.py

"""
    Queue based upon array
    用数组实现的队列

    Author: Wenru
"""

from typing import Optional

class ArrayQueue:
    
    def __init__(self, capacity: int):
        self._items = []
        self._capacity = capacity
        self._head = 0
        self._tail = 0

    def enqueue(self, item: str) -> bool:
        if self._tail == self._capacity:
            if self._head == 0:
                return False
            else:
                for i in range(0, self._tail - self._head):
                    self._items[i] = self._items[i + self._head]
                self._tail = self._tail - self._head
                self._head = 0
        
        self._items.insert(self._tail, item)
        self._tail += 1
        return True
    
    def dequeue(self) -> Optional[str]:
        if self._head != self._tail:
            item = self._items[self._head]
            self._head += 1
            return item
        else:
            return None
    
    def __repr__(self) -> str:
        return " ".join(item for item in self._items[self._head : self._tail])




File: python/09_queue/circular_queue.py

"""
    Author: Wenru
"""

from typing import Optional
from itertools import chain

class CircularQueue:

    def __init__(self, capacity):
        self._items = []
        self._capacity = capacity + 1
        self._head = 0
        self._tail = 0
    
    def enqueue(self, item: str) -> bool:
        if (self._tail + 1) % self._capacity == self._head:
            return False
        
        self._items.append(item)
        self._tail = (self._tail + 1) % self._capacity
        return True
    
    def dequeue(self) -> Optional[str]:
        if self._head != self._tail:
            item = self._items[self._head]
            self._head = (self._head + 1) % self._capacity
            return item
    
    def __repr__(self) -> str:
        if self._tail >= self._head:
            return " ".join(item for item in self._items[self._head : self._tail])
        else:
            return " ".join(item for item in chain(self._items[self._head:], self._items[:self._tail]))

if __name__ == "__main__":
    q = CircularQueue(5)
    for i in range(5):
        q.enqueue(str(i))
    q.dequeue()
    q.dequeue()
    q.enqueue(str(5))
    print(q)



File: python/17_skiplist/skip_list_comments.py

import random


class SkipListNode(object):
    def __init__(self, val, high=1):
        # 节点存储的值
        self.data = val
        # 节点对应索引层的深度
        self.deeps = [None] * high


class SkipList(object):
    """
        An implementation of skip list.
        The list stores positive integers without duplicates.
        跳表的一种实现方法。
        跳表中储存的是正整数，并且储存的是不重复的。
        Author: Ben
    """

    def __init__(self):
        # 索引层的最大深度
        self.__MAX_LEVEL = 16
        # 跳表的高度
        self._high = 1
        # 每一索引层的首节点, 默认值为None
        self._head = SkipListNode(None, self.__MAX_LEVEL)

    def find(self, val):
        cur = self._head
        # 从索引的顶层, 逐层定位要查找的值
        # 索引层上下是对应的, 下层的起点是上一个索引层中小于插入值的最大值对应的节点
        for i in range(self._high - 1, -1, -1):
            # 同一索引层内, 查找小于插入值的最大值对应的节点
            while cur.deeps[i] and cur.deeps[i].data < val:
                cur = cur.deeps[i]

        if cur.deeps[0] and cur.deeps[0].data == val:
            return cur.deeps[0]
        return None

    def insert(self, val):
        '''
        新增时, 通过随机函数获取要更新的索引层数,
        要对低于给定高度的索引层添加新结点的指针
        '''
        high = self.randomLevel()
        if self._high < high:
            self._high = high
        # 申请新结点
        newNode = SkipListNode(val, high)
        # cache用来缓存对应索引层中小于插入值的最大节点
        cache = [self._head] * high
        cur = self._head

        # 在低于随机高度的每一个索引层寻找小于插入值的节点
        for i in range(high - 1, -1, -1):
            # 每个索引层内寻找小于带插入值的节点
            # ! 索引层上下是对应的, 下层的起点是上一个索引层中小于插入值的最大值对应的节点
            while cur.deeps[i] and cur.deeps[i].data < val:
                cur = cur.deeps[i]
            cache[i] = cur

        # 在小于高度的每个索引层中插入新结点
        for i in range(high):
            # new.next = prev.next \ prev.next = new.next
            newNode.deeps[i] = cache[i].deeps[i]
            cache[i].deeps[i] = newNode

    def delete(self, val):
        '''
        删除时, 要将每个索引层中对应的节点都删掉
        '''
        # cache用来缓存对应索引层中小于插入值的最大节点
        cache = [None] * self._high
        cur = self._head
        # 缓存每一个索引层定位小于插入值的节点
        for i in range(self._high - 1, -1, -1):
            while cur.deeps[i] and cur.deeps[i].data < val:
                cur = cur.deeps[i]
            cache[i] = cur
        # 如果给定的值存在, 更新索引层中对应的节点
        if cur.deeps[0] and cur.deeps[0].data == val:
            for i in range(self._high):
                if cache[i].deeps[i] and cache[i].deeps[i].data == val:
                    cache[i].deeps[i] = cache[i].deeps[i].deeps[i]

    def randomLevel(self, p=0.25):
        '''
        #define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
        https://github.com/antirez/redis/blob/unstable/src/t_zset.c
        '''
        high = 1
        for _ in range(self.__MAX_LEVEL - 1):
            if random.random() < p:
                high += 1
        return high

    def __repr__(self):
        vals = []
        p = self._head
        while p.deeps[0]:
            vals.append(str(p.deeps[0].data))
            p = p.deeps[0]
        return '->'.join(vals)


if __name__ == '__main__':
    sl = SkipList()
    for i in range(100):
        sl.insert(i)
    print(sl)
    p = sl.find(7)
    print(p.data)
    sl.delete(37)
    print(sl)
    sl.delete(37.5)
    print(sl)



File: python/17_skiplist/skip_list.py

"""
    An implementation of skip list.
    The list stores positive integers without duplicates.

    跳表的一种实现方法。
    跳表中储存的是正整数，并且储存的是不重复的。

    Author: Wenru
"""

from typing import Optional
import random

class ListNode:

    def __init__(self, data: Optional[int] = None):
        self._data = data
        self._forwards = []   # Forward pointers

class SkipList:

    _MAX_LEVEL = 16

    def __init__(self):
        self._level_count = 1
        self._head = ListNode()
        self._head._forwards = [None] * type(self)._MAX_LEVEL

    def find(self, value: int) -> Optional[ListNode]:
        p = self._head
        for i in range(self._level_count - 1, -1, -1):   # Move down a level
            while p._forwards[i] and p._forwards[i]._data < value:
                p = p._forwards[i]   # Move along level
        
        return p._forwards[0] if p._forwards[0] and p._forwards[0]._data == value else None

    def insert(self, value: int):
        level = self._random_level()
        if self._level_count < level: self._level_count = level
        new_node = ListNode(value)
        new_node._forwards = [None] * level
        update = [self._head] * level     # update is like a list of prevs

        p = self._head
        for i in range(level - 1, -1, -1):
            while p._forwards[i] and p._forwards[i]._data < value:
                p = p._forwards[i]
            
            update[i] = p     # Found a prev

        for i in range(level):
            new_node._forwards[i] = update[i]._forwards[i]   # new_node.next = prev.next
            update[i]._forwards[i] = new_node     # prev.next = new_node
        
    def delete(self, value):
        update = [None] * self._level_count
        p = self._head
        for i in range(self._level_count - 1, -1, -1):
            while p._forwards[i] and p._forwards[i]._data < value:
                p = p._forwards[i]
            update[i] = p
        
        if p._forwards[0] and p._forwards[0]._data == value:
            for i in range(self._level_count - 1, -1, -1):
                if update[i]._forwards[i] and update[i]._forwards[i]._data == value:
                    update[i]._forwards[i] = update[i]._forwards[i]._forwards[i]     # Similar to prev.next = prev.next.next

    def _random_level(self, p: float = 0.5) -> int:
        level = 1
        while random.random() < p and level < type(self)._MAX_LEVEL:
            level += 1
        return level

    def __repr__(self) -> str:
        values = []
        p = self._head
        while p._forwards[0]:
            values.append(str(p._forwards[0]._data))
            p = p._forwards[0]
        return "->".join(values)


if __name__ == "__main__":
    l = SkipList()
    for i in range(10):
        l.insert(i)
    print(l)
    p = l.find(7)
    print(p._data)
    l.delete(3)
    print(l)


File: python/24_tree/binary_search_tree.py

"""
    Binary search tree

    Author: Wenru Dong
"""
from typing import Optional

class TreeNode:
    def __init__(self, value: int):
        self.val = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self._root = None
    
    def find(self, value: int) -> Optional[TreeNode]:
        node = self._root
        while node and node.val != value:
            node = node.left if node.val > value else node.right
        return node
    
    def insert(self, value: int):
        if not self._root:
            self._root = TreeNode(value)
            return
        parent = None
        node = self._root
        while node:
            parent = node
            node = node.left if node.val > value else node.right
        new_node = TreeNode(value)
        if parent.val > value:
            parent.left = new_node
        else:
            parent.right = new_node

    def delete(self, value: int):
        node = self._root
        parent = None
        while node and node.val != value:
            parent = node
            node = node.left if node.val > value else node.right
        if not node: return
        
        # 要删除的节点有两个子节点
        if node.left and node.right:
            successor = node.right
            successor_parent = node
            while successor.left:
                successor_parent = successor
                successor = successor.left
            node.val = successor.val
            parent, node = successor_parent, successor
        
        # 删除节点是叶子节点或者仅有一个子节点
        child = node.left if node.left else node.right
        if not parent:
            self._root = child
        elif parent.left == node:
            parent.left = child
        else:
            parent.right = child



File: python/11_sorts/sorts.py

"""
    Bubble sort, insertion sort and selection sort
    冒泡排序、插入排序、选择排序

    Author: Wenru
"""

from typing import List


# 冒泡排序
def bubble_sort(a: List[int]):
    length = len(a)
    if length <= 1:
        return

    for i in range(length):
        made_swap = False
        for j in range(length - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                made_swap = True
        if not made_swap:
            break


# 插入排序
def insertion_sort(a: List[int]):
    length = len(a)
    if length <= 1:
        return

    for i in range(1, length):
        value = a[i]
        j = i - 1
        while j >= 0 and a[j] > value:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = value


# 选择排序
def selection_sort(a: List[int]):
    length = len(a)
    if length <= 1:
        return

    for i in range(length):
        min_index = i
        min_val = a[i]
        for j in range(i, length):
            if a[j] < min_val:
                min_val = a[j]
                min_index = j
        a[i], a[min_index] = a[min_index], a[i]


def test_bubble_sort():
    test_array = [1, 1, 1, 1]
    bubble_sort(test_array)
    assert test_array == [1, 1, 1, 1]
    test_array = [4, 1, 2, 3]
    bubble_sort(test_array)
    assert test_array == [1, 2, 3, 4]
    test_array = [4, 3, 2, 1]
    bubble_sort(test_array)
    assert test_array == [1, 2, 3, 4]


def test_insertion_sort():
    test_array = [1, 1, 1, 1]
    insertion_sort(test_array)
    assert test_array == [1, 1, 1, 1]
    test_array = [4, 1, 2, 3]
    insertion_sort(test_array)
    assert test_array == [1, 2, 3, 4]
    test_array = [4, 3, 2, 1]
    insertion_sort(test_array)
    assert test_array == [1, 2, 3, 4]


def test_selection_sort():
    test_array = [1, 1, 1, 1]
    selection_sort(test_array)
    assert test_array == [1, 1, 1, 1]
    test_array = [4, 1, 2, 3]
    selection_sort(test_array)
    assert test_array == [1, 2, 3, 4]
    test_array = [4, 3, 2, 1]
    selection_sort(test_array)
    assert test_array == [1, 2, 3, 4]


if __name__ == "__main__":
    array = [5, 6, -1, 4, 2, 8, 10, 7, 6]
    bubble_sort(array)
    print(array)

    array = [5, 6, -1, 4, 2, 8, 10, 7, 6]
    insertion_sort(array)
    print(array)

    array = [5, 6, -1, 4, 2, 8, 10, 7, 6]
    selection_sort(array)
    print(array)



File: python/39_back_track/permutations.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from typing import List

permutations_list = []  # 全局变量，用于记录每个输出


def permutations(nums: List, n: int, pick_count: int):
    """
    从nums选取n个数的全排列

    回溯法，用一个栈记录当前路径信息
    当满足n==0时，说明栈中的数已足够，输出并终止遍历
    :param nums:
    :param n:
    :param pick_count:
    :return:
    """
    if n == 0:
        print(permutations_list)
    else:
        for i in range(len(nums) - pick_count):
            permutations_list[pick_count] = nums[i]
            nums[i], nums[len(nums) - pick_count - 1] = nums[len(nums) - pick_count - 1], nums[i]
            permutations(nums, n-1, pick_count+1)
            nums[i], nums[len(nums) - pick_count - 1] = nums[len(nums) - pick_count - 1], nums[i]


if __name__ == '__main__':
    nums = [1, 2, 3, 4]
    n = 3
    print('--- list ---')
    print(nums)

    print('\n--- pick num ---')
    print(n)

    print('\n--- permutation list ---')
    permutations_list = [0] * n
    permutations(nums, n, 0)




File: python/39_back_track/eight_queens.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

# 棋盘尺寸
BOARD_SIZE = 8

solution_count = 0
queen_list = [0] * BOARD_SIZE


def eight_queens(cur_column: int):
    """
    输出所有符合要求的八皇后序列
    用一个长度为8的数组代表棋盘的列，数组的数字则为当前列上皇后所在的行数
    :return:
    """
    if cur_column >= BOARD_SIZE:
        global solution_count
        solution_count += 1
        # 解
        print(queen_list)
    else:
        for i in range(BOARD_SIZE):
            if is_valid_pos(cur_column, i):
                queen_list[cur_column] = i
                eight_queens(cur_column + 1)


def is_valid_pos(cur_column: int, pos: int) -> bool:
    """
    因为采取的是每列放置1个皇后的做法
    所以检查的时候不必检查列的合法性，只需要检查行和对角
    1. 行：检查数组在下标为cur_column之前的元素是否已存在pos
    2. 对角：检查数组在下标为cur_column之前的元素，其行的间距pos - QUEEN_LIST[i]
       和列的间距cur_column - i是否一致
    :param cur_column:
    :param pos:
    :return:
    """
    i = 0
    while i < cur_column:
        # 同行
        if queen_list[i] == pos:
            return False
        # 对角线
        if cur_column - i == abs(pos - queen_list[i]):
            return False
        i += 1
    return True


if __name__ == '__main__':
    print('--- eight queens sequence ---')
    eight_queens(0)

    print('\n--- solution count ---')
    print(solution_count)



File: python/39_back_track/regex.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

is_match = False


def rmatch(r_idx: int, m_idx: int, regex: str, main: str):
    global is_match
    if is_match:
        return

    if r_idx >= len(regex):     # 正则串全部匹配好了
        is_match = True
        return

    if m_idx >= len(main) and r_idx < len(regex):   # 正则串没匹配完，但是主串已经没得匹配了
        is_match = False
        return

    if regex[r_idx] == '*':     # * 匹配1个或多个任意字符，递归搜索每一种情况
        for i in range(m_idx, len(main)):
            rmatch(r_idx+1, i+1, regex, main)
    elif regex[r_idx] == '?':   # ? 匹配0个或1个任意字符，两种情况
        rmatch(r_idx+1, m_idx+1, regex, main)
        rmatch(r_idx+1, m_idx, regex, main)
    else:                       # 非特殊字符需要精确匹配
        if regex[r_idx] == main[m_idx]:
            rmatch(r_idx+1, m_idx+1, regex, main)


if __name__ == '__main__':
    regex = 'ab*eee?d'
    main = 'abcdsadfkjlekjoiwjiojieeecd'
    rmatch(0, 0, regex, main)
    print(is_match)



File: python/39_back_track/01_bag.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from typing import List

# 背包选取的物品列表
picks = []
picks_with_max_value = []


def bag(capacity: int, cur_weight: int, items_info: List, pick_idx: int):
    """
    回溯法解01背包，穷举
    :param capacity: 背包容量
    :param cur_weight: 背包当前重量
    :param items_info: 物品的重量和价值信息
    :param pick_idx: 当前物品的索引
    :return:
    """
    # 考察完所有物品，或者在中途已经装满
    if pick_idx >= len(items_info) or cur_weight == capacity:
        global picks_with_max_value
        if get_value(items_info, picks) > \
                get_value(items_info, picks_with_max_value):
            picks_with_max_value = picks.copy()
    else:
        item_weight = items_info[pick_idx][0]
        if cur_weight + item_weight <= capacity:    # 选
            picks[pick_idx] = 1
            bag(capacity, cur_weight + item_weight, items_info, pick_idx + 1)

        picks[pick_idx] = 0                         # 不选
        bag(capacity, cur_weight, items_info, pick_idx + 1)


def get_value(items_info: List, pick_items: List):
    values = [_[1] for _ in items_info]
    return sum([a*b for a, b in zip(values, pick_items)])


if __name__ == '__main__':
    # [(weight, value), ...]
    items_info = [(3, 5), (2, 2), (1, 4), (1, 2), (4, 10)]
    capacity = 8

    print('--- items info ---')
    print(items_info)

    print('\n--- capacity ---')
    print(capacity)

    picks = [0] * len(items_info)
    bag(capacity, 0, items_info, 0)

    print('\n--- picks ---')
    print(picks_with_max_value)

    print('\n--- value ---')
    print(get_value(items_info, picks_with_max_value))



File: python/35_trie/trie_.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from queue import Queue
import pygraphviz as pgv

OUTPUT_PATH = 'E:/'


class Node:
    def __init__(self, c):
        self.data = c
        self.is_ending_char = False
        # 使用有序数组，降低空间消耗，支持更多字符
        self.children = []

    def insert_child(self, c):
        self._insert_child(Node(c))

    def _insert_child(self, node):
        """
        插入一个子节点
        :param c:
        :return:
        """
        v = ord(node.data)
        idx = self._find_insert_idx(v)
        length = len(self.children)

        if idx == length:
            self.children.append(node)
        else:
            self.children.append(None)
            for i in range(length, idx, -1):
                self.children[i] = self.children[i-1]
            self.children[idx] = node

    def has_child(self, c):
        return True if self.get_child(c) is not None else False

    def get_child(self, c):
        """
        搜索子节点并返回
        :param c:
        :return:
        """
        start = 0
        end = len(self.children) - 1
        v = ord(c)

        while start <= end:
            mid = (start + end)//2
            if v == ord(self.children[mid].data):
                return self.children[mid]
            elif v < ord(self.children[mid].data):
                end = mid - 1
            else:
                start = mid + 1
        # 找不到返回None
        return None

    def _find_insert_idx(self, v):
        """
        二分查找，找到有序数组的插入位置
        :param v:
        :return:
        """
        start = 0
        end = len(self.children) - 1

        while start <= end:
            mid = (start + end)//2
            if v < ord(self.children[mid].data):
                end = mid - 1
            else:
                if mid + 1 == len(self.children) or v < ord(self.children[mid+1].data):
                    return mid + 1
                else:
                    start = mid + 1
        # v < self.children[0]
        return 0

    def __repr__(self):
        return 'node value: {}'.format(self.data) + '\n' \
               + 'children:{}'.format([n.data for n in self.children])


class Trie:
    def __init__(self):
        self.root = Node(None)

    def gen_tree(self, string_list):
        """
        创建trie树

        1. 遍历每个字符串的字符，从根节点开始，如果没有对应子节点，则创建
        2. 每一个串的末尾节点标注为红色(is_ending_char)
        :param string_list:
        :return:
        """
        for string in string_list:
            n = self.root
            for c in string:
                if n.get_child(c) is None:
                    n.insert_child(c)
                n = n.get_child(c)
            n.is_ending_char = True

    def search(self, pattern):
        """
        搜索

        1. 遍历模式串的字符，从根节点开始搜索，如果途中子节点不存在，返回False
        2. 遍历完模式串，则说明模式串存在，再检查树中最后一个节点是否为红色，是
           则返回True，否则False
        :param pattern:
        :return:
        """
        assert type(pattern) is str and len(pattern) > 0

        n = self.root
        for c in pattern:
            if n.get_child(c) is None:
                return False
            n = n.get_child(c)

        return True if n.is_ending_char is True else False

    def draw_img(self, img_name='Trie.png'):
        """
        画出trie树
        :param img_name:
        :return:
        """
        if self.root is None:
            return

        tree = pgv.AGraph('graph foo {}', strict=False, directed=False)

        # root
        nid = 0
        color = 'black'
        tree.add_node(nid, color=color, label='None')

        q = Queue()
        q.put((self.root, nid))
        while not q.empty():
            n, pid = q.get()
            for c in n.children:
                nid += 1
                q.put((c, nid))
                color = 'red' if c.is_ending_char is True else 'black'
                tree.add_node(nid, color=color, label=c.data)
                tree.add_edge(pid, nid)

        tree.graph_attr['epsilon'] = '0.01'
        tree.layout('dot')
        tree.draw(OUTPUT_PATH + img_name)
        return True


if __name__ == '__main__':
    string_list = ['abc', 'abd', 'abcc', 'accd', 'acml', 'P@trick', 'data', 'structure', 'algorithm']

    print('--- gen trie ---')
    print(string_list)
    trie = Trie()
    trie.gen_tree(string_list)
    # trie.draw_img()

    print('\n')
    print('--- search result ---')
    search_string = ['a', 'ab', 'abc', 'abcc', 'abe', 'P@trick', 'P@tric', 'Patrick']
    for ss in search_string:
        print('[pattern]: {}'.format(ss), '[result]: {}'.format(trie.search(ss)))



File: python/35_trie/trie.py

"""
    Author: Wenru Dong
"""

class TrieNode:
    def __init__(self, data: str):
        self._data = data
        self._children = [None] * 26
        self._is_ending_char = False
    

class Trie:
    def __init__(self):
        self._root = TrieNode("/")

    def insert(self, text: str) -> None:
        node = self._root
        for index, char in map(lambda x: (ord(x) - ord("a"), x), text):
            if not node._children[index]:
                node._children[index] = TrieNode(char)
            node = node._children[index]
        node._is_ending_char = True
    
    def find(self, pattern: str) -> bool:
        node = self._root
        for index in map(lambda x: ord(x) - ord("a"), pattern):
            if not node._children[index]: return False
            node = node._children[index]
        return node._is_ending_char


if __name__ == "__main__":

    strs = ["how", "hi", "her", "hello", "so", "see"]
    trie = Trie()
    for s in strs:
        trie.insert(s)
    
    for s in strs:
        print(trie.find(s))
    
    print(trie.find("swift"))


File: python/32_bf_rk/bf_rk.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from time import time


def bf(main, pattern):
    """
    字符串匹配，bf暴搜
    :param main: 主串
    :param pattern: 模式串
    :return:
    """
    n = len(main)
    m = len(pattern)

    if n <= m:
        return 0 if pattern == main else -1

    for i in range(n-m+1):
        for j in range(m):
            if main[i+j] == pattern[j]:
                if j == m-1:
                    return i
                else:
                    continue
            else:
                break
    return -1


def simple_hash(s, start, end):
    """
    计算子串的哈希值
    每个字符取acs-ii码后求和
    :param s:
    :param start:
    :param end:
    :return:
    """
    assert start <= end

    ret = 0
    for c in s[start: end+1]:
        ret += ord(c)
    return ret


def rk(main, pattern):
    n = len(main)
    m = len(pattern)

    if n <= m:
        return 0 if pattern == main else -1

    # 子串哈希值表
    hash_memo = [None] * (n-m+1)
    hash_memo[0] = simple_hash(main, 0, m-1)
    for i in range(1, n-m+1):
        hash_memo[i] = hash_memo[i-1] - simple_hash(main, i-1, i-1) + simple_hash(main, i+m-1, i+m-1)

    # 模式串哈希值
    hash_p = simple_hash(pattern, 0, m-1)

    for i, h in enumerate(hash_memo):
        # 可能存在哈希冲突
        if h == hash_p:
            if pattern == main[i:i+m]:
                return i
            else:
                continue
    return -1


if __name__ == '__main__':
    m_str = 'a'*10000
    p_str = 'a'*200+'b'

    print('--- time consume ---')
    t = time()
    print('[bf] result:', bf(m_str, p_str))
    print('[bf] time cost: {0:.5}s'.format(time()-t))

    t = time()
    print('[rk] result:', rk(m_str, p_str))
    print('[rk] time cost: {0:.5}s'.format(time()-t))

    print('')
    print('--- search ---')
    m_str = 'thequickbrownfoxjumpsoverthelazydog'
    p_str = 'jump'
    print('[bf] result:', bf(m_str, p_str))
    print('[rk] result:', rk(m_str, p_str))



File: python/34_kmp/kmp.py

"""
    KMP algorithm

    Author: Wenru Dong
"""

from typing import List

def kmp(s: int, pattern: int) -> int:
    m = len(pattern)
    partial_match_table = _get_partial_match_table(pattern)
    j = 0
    for i in range(len(s)):
        while j >= 0 and s[i] != pattern[j]:
            j = partial_match_table[j]
        j += 1
        if j == m:
            return i - m + 1
    return -1


def _get_partial_match_table(pattern: int) -> List[int]:
    # Denote πᵏ(i) as π applied to i for k times,
    # i.e., π²(i) = π(π(i)).
    # Then we have the result:
    #    π(i) = πᵏ(i-1) + 1,
    # where k is the smallest integer such that
    # pattern[πᵏ(i-1)+1] == pattern[i].

    # The value of π means the maximum length
    # of proper prefix/suffix.
    # The index of π means the length of the prefix
    # considered for pattern.
    # For example, π[2] means we are considering the first 2 characters
    # of the pattern.
    # If π[2] == 1, it means for the prefix of the pattern, P[0]P[1],
    # it has a maximum length proper prefix of 1, which is also the
    # suffix of P[0]P[1].
    # We also add a π[0] == -1 for easier handling of boundary
    # condition.
    
    m = len(pattern)
    π = [0] * (m + 1)
    π[0] = k = -1  # We use k here to represent πᵏ(i)
    for i in range(1, m + 1):
        while k >= 0 and pattern[k] != pattern[i - 1]:
            k = π[k]
        k += 1
        π[i] = k
    return π


if __name__ == "__main__":

    s = "abc abcdab abcdabcdabde"
    pattern = "bcdabd"
    print(kmp(s, pattern), s.find(pattern))

    s = "hello"
    pattern = "ll"
    print(kmp(s, pattern), s.find(pattern))


File: python/34_kmp/kmp_.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-


def kmp(main, pattern):
    """
    kmp字符串匹配
    :param main:
    :param pattern:
    :return:
    """
    assert type(main) is str and type(pattern) is str

    n, m = len(main), len(pattern)

    if m == 0:
        return 0
    if n <= m:
        return 0 if main == pattern else -1

    # 求解next数组
    next = get_next(pattern)

    j = 0
    for i in range(n):
        # 在pattern[:j]中，从长到短递归去找最长的和后缀子串匹配的前缀子串
        while j > 0 and main[i] != pattern[j]:
            j = next[j-1] + 1   # 如果next[j-1] = -1，则要从起始字符取匹配

        if main[i] == pattern[j]:
            if j == m-1:
                return i-m+1
            else:
                j += 1
    return -1


def get_next(pattern):
    """
    next数组生成

    注意：
    理解的难点在于next[i]根据next[0], next[1]…… next[i-1]的求解
    next[i]的值依赖于前面的next数组的值，求解思路：
    1. 首先取出前一个最长的匹配的前缀子串，其下标就是next[i-1]
    2. 对比下一个字符，如果匹配，直接赋值next[i]为next[i-1]+1，因为i-1的时候已经是最长
    *3. 如果不匹配，需要递归去找次长的匹配的前缀子串，这里难理解的就是递归地方式，next[i-1]
        是i-1的最长匹配前缀子串的下标结尾，则 *next[next[i-1]]* 是其次长匹配前缀子串的下标
        结尾
    *4. 递归的出口，就是在次长前缀子串的下一个字符和当前匹配 或 遇到-1，遇到-1则说明没找到任
        何匹配的前缀子串，这时需要找pattern的第一个字符对比

    ps: next[m-1]的数值其实没有任何意义，求解时可以不理。网上也有将next数组往右平移的做法。
    :param pattern:
    :return:
    """
    m = len(pattern)
    next = [-1] * m

    next[0] = -1

    # for i in range(1, m):
    for i in range(1, m-1):
        j = next[i-1]       # 取i-1时匹配到的最长前缀子串
        while j != -1 and pattern[j+1] != pattern[i]:
            j = next[j]     # 次长的前缀子串的下标，即是next[next[i-1]]

        # 根据上面跳出while的条件，当j=-1时，需要比较pattern[0]和当前字符
        # 如果j!=-1，则pattern[j+1]和pattern[i]一定是相等的
        if pattern[j+1] == pattern[i]:  # 如果接下来的字符也是匹配的，那i的最长前缀子串下标是next[i-1]+1
            j += 1
        next[i] = j

    return next


if __name__ == '__main__':
    m_str = "aabbbbaaabbababbabbbabaaabb"
    p_str = "abbabbbabaa"

    print('--- search ---')
    print('[Built-in Functions] result:', m_str.find(p_str))
    print('[kmp] result:', kmp(m_str, p_str))



File: python/43_topological_sorting/topological_sorting.py

"""
    Author: Wenru Dong
"""

from collections import deque
from itertools import filterfalse

class Graph:
    def __init__(self, num_vertices: int):
        self._num_vertices = num_vertices
        self._adjacency = [[] for _ in range(num_vertices)]
    
    def add_edge(self, s: int, t: int) -> None:
        self._adjacency[s].append(t)

    def tsort_by_kahn(self) -> None:
        in_degree = [0] * self._num_vertices
        for v in range(self._num_vertices):
            if len(self._adjacency[v]):
                for neighbour in self._adjacency[v]:
                    in_degree[neighbour] += 1
        q = deque(filterfalse(lambda x: in_degree[x], range(self._num_vertices)))
        while q:
            v = q.popleft()
            print(f"{v} -> ", end="")
            for neighbour in self._adjacency[v]:
                in_degree[neighbour] -= 1
                if not in_degree[neighbour]:
                    q.append(neighbour)
        print("\b\b\b   ")

    def tsort_by_dfs(self) -> None:
        inverse_adjacency = [[] for _ in range(self._num_vertices)]
        for v in range(self._num_vertices):
            if len(self._adjacency[v]):
                for neighbour in self._adjacency[v]:
                    inverse_adjacency[neighbour].append(v)
        visited = [False] * self._num_vertices

        def dfs(vertex: int) -> None:
            if len(inverse_adjacency[vertex]):
                for v in inverse_adjacency[vertex]:
                    if not visited[v]:
                        visited[v] = True
                        dfs(v)
            print(f"{vertex} -> ", end="")
        
        for v in range(self._num_vertices):
            if not visited[v]:
                visited[v] = True
                dfs(v)
        
        print("\b\b\b   ")


if __name__ == "__main__":

    dag = Graph(4)
    dag.add_edge(1, 0)
    dag.add_edge(2, 1)
    dag.add_edge(1, 3)
    dag.tsort_by_kahn()
    dag.tsort_by_dfs()



File: python/16_bsearch/bsearch_variants.py

"""
    Author: Wenru
    Fix: nzjia
"""

from typing import List

def bsearch_left(nums: List[int], target: int) -> int:
    """Binary search of the index of the first element
    equal to a given target in the ascending sorted array.
    If not found, return -1.
    """
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    if low < len(nums) and nums[low] == target:
        return low
    else:
        return -1


def bsearch_right(nums: List[int], target: int) -> int:
    """Binary search of the index of the last element
    equal to a given target in the ascending sorted array.
    If not found, return -1.
    """
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] <= target:
            low = mid + 1
        else:
            high = mid - 1
    if high >= 0 and nums[high] == target:
        return high
    else:
        return -1


def bsearch_left_not_less(nums: List[int], target: int) -> int:
    """Binary search of the index of the first element
    not less than a given target in the ascending sorted array.
    If not found, return -1.
    """
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    if low < len(nums) and nums[low] >= target:
        return low
    else:
        return -1

def bsearch_right_not_greater(nums: List[int], target: int) -> int:
    """Binary search of the index of the last element
    not greater than a given target in the ascending sorted array.
    If not found, return -1.
    """
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] <= target:
            low = mid + 1
        else:
            high = mid - 1
    if high >= 0 and nums[high] <= target:
        return high
    else:
        return -1

if __name__ == "__main__":
    a = [1, 1, 2, 3, 4, 6, 7, 7, 7, 7, 10, 22]

    print(bsearch_left(a, 0) == -1)
    print(bsearch_left(a, 7) == 6)
    print(bsearch_left(a, 30) == -1)

    print(bsearch_right(a, 0) == -1)
    print(bsearch_right(a, 7) == 9)
    print(bsearch_right(a, 30) == -1)

    print(bsearch_left_not_less(a, 0) == 0)
    print(bsearch_left_not_less(a, 5) == 5)
    print(bsearch_left_not_less(a, 30) == -1)

    print(bsearch_right_not_greater(a, 0) == -1)
    print(bsearch_right_not_greater(a, 6) == 5)
    print(bsearch_right_not_greater(a, 30) == 11)



File: python/23_binarytree/binary_tree.py

"""
    Pre-order, in-order and post-order traversal of binary trees.

    Author: Wenru Dong
"""
from typing import TypeVar, Generic, Generator, Optional

T = TypeVar("T")

class TreeNode(Generic[T]):
    def __init__(self, value: T):
        self.val = value
        self.left = None
        self.right = None
    

# Pre-order traversal
def pre_order(root: Optional[TreeNode[T]]) -> Generator[T, None, None]:
    if root:
        yield root.val
        yield from pre_order(root.left)
        yield from pre_order(root.right)

# In-order traversal
def in_order(root: Optional[TreeNode[T]]) -> Generator[T, None, None]:
    if root:
        yield from in_order(root.left)
        yield root.val
        yield from in_order(root.right)

# Post-order traversal
def post_order(root: Optional[TreeNode[T]]) -> Generator[T, None, None]:
    if root:
        yield from post_order(root.left)
        yield from post_order(root.right)
        yield root.val


if __name__ == "__main__":

    singer = TreeNode("Taylor Swift")

    genre_country = TreeNode("Country")
    genre_pop = TreeNode("Pop")

    album_fearless = TreeNode("Fearless")
    album_red = TreeNode("Red")
    album_1989 = TreeNode("1989")
    album_reputation = TreeNode("Reputation")

    song_ls = TreeNode("Love Story")
    song_wh = TreeNode("White Horse")
    song_wanegbt = TreeNode("We Are Never Ever Getting Back Together")
    song_ikywt = TreeNode("I Knew You Were Trouble")
    song_sio = TreeNode("Shake It Off")
    song_bb = TreeNode("Bad Blood")
    song_lwymmd = TreeNode("Look What You Made Me Do")
    song_g = TreeNode("Gorgeous")

    singer.left, singer.right = genre_country, genre_pop
    genre_country.left, genre_country.right = album_fearless, album_red
    genre_pop.left, genre_pop.right = album_1989, album_reputation
    album_fearless.left, album_fearless.right = song_ls, song_wh
    album_red.left, album_red.right = song_wanegbt, song_ikywt
    album_1989.left, album_1989.right = song_sio, song_bb
    album_reputation.left, album_reputation.right = song_lwymmd, song_g

    print(list(pre_order(singer)))
    print(list(in_order(singer)))
    print(list(post_order(singer)))



File: python/23_binarytree/binary_search_tree.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from queue import Queue
import math


class TreeNode:
    def __init__(self, val=None):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None


class BinarySearchTree:
    def __init__(self, val_list=[]):
        self.root = None
        for n in val_list:
            self.insert(n)

    def insert(self, data):
        """
        插入
        :param data:
        :return:
        """
        assert(isinstance(data, int))

        if self.root is None:
            self.root = TreeNode(data)
        else:
            n = self.root
            while n:
                p = n
                if data < n.val:
                    n = n.left
                else:
                    n = n.right

            new_node = TreeNode(data)
            new_node.parent = p
            
            if data < p.val:
                p.left = new_node
            else:
                p.right = new_node

        return True

    def search(self, data):
        """
        搜索
        返回bst中所有值为data的节点列表
        :param data:
        :return:
        """
        assert(isinstance(data, int))

        # 所有搜索到的节点
        ret = []

        n = self.root
        while n:
            if data < n.val:
                n = n.left
            else:
                if data == n.val:
                    ret.append(n)
                n = n.right

        return ret

    def delete(self, data):
        """
        删除
        :param data:
        :return:
        """
        assert (isinstance(data, int))

        # 通过搜索得到需要删除的节点
        del_list = self.search(data)

        for n in del_list:
            # 父节点为空，又不是根节点，已经不在树上，不用再删除
            if n.parent is None and n != self.root:
                continue
            else:
                self._del(n)

    def _del(self, node):
        """
        删除
        所删除的节点N存在以下情况：
        1. 没有子节点：直接删除N的父节点指针
        2. 有一个子节点：将N父节点指针指向N的子节点
        3. 有两个子节点：找到右子树的最小节点M，将值赋给N，然后删除M
        :param data:
        :return:
        """
        # 1
        if node.left is None and node.right is None:
            # 情况1和2，根节点和普通节点的处理方式不同
            if node == self.root:
                self.root = None
            else:
                if node.val < node.parent.val:
                    node.parent.left = None
                else:
                    node.parent.right = None

                node.parent = None
        # 2
        elif node.left is None and node.right is not None:
            if node == self.root:
                self.root = node.right
                self.root.parent = None
                node.right = None
            else:
                if node.val < node.parent.val:
                    node.parent.left = node.right
                else:
                    node.parent.right = node.right

                node.right.parent = node.parent
                node.parent = None
                node.right = None
        elif node.left is not None and node.right is None:
            if node == self.root:
                self.root = node.left
                self.root.parent = None
                node.left = None
            else:
                if node.val < node.parent.val:
                    node.parent.left = node.left
                else:
                    node.parent.right = node.left

                node.left.parent = node.parent
                node.parent = None
                node.left = None
        # 3
        else:
            min_node = node.right
            # 找到右子树的最小值节点
            if min_node.left:
                min_node = min_node.left

            if node.val != min_node.val:
                node.val = min_node.val
                self._del(min_node)
            # 右子树的最小值节点与被删除节点的值相等，再次删除原节点
            else:
                self._del(min_node)
                self._del(node)

    def get_min(self):
        """
        返回最小值节点
        :return:
        """
        if self.root is None:
            return None

        n = self.root
        while n.left:
            n = n.left
        return n.val

    def get_max(self):
        """
        返回最大值节点
        :return:
        """
        if self.root is None:
            return None

        n = self.root
        while n.right:
            n = n.right
        return n.val

    def in_order(self):
        """
        中序遍历
        :return:
        """
        if self.root is None:
            return []

        return self._in_order(self.root)

    def _in_order(self, node):
        if node is None:
            return []

        ret = []
        n = node
        ret.extend(self._in_order(n.left))
        ret.append(n.val)
        ret.extend(self._in_order(n.right))
        
        return ret

    def __repr__(self):
        # return str(self.in_order())
        print(str(self.in_order()))
        return self._draw_tree()

    def _bfs(self):
        """
        bfs
        通过父子关系记录节点编号
        :return:
        """
        if self.root is None:
            return []

        ret = []
        q = Queue()
        # 队列[节点，编号]
        q.put((self.root, 1))

        while not q.empty():
            n = q.get()

            if n[0] is not None:
                ret.append((n[0].val, n[1]))
                q.put((n[0].left, n[1]*2))
                q.put((n[0].right, n[1]*2+1))

        return ret

    def _draw_tree(self):
        """
        可视化
        :return:
        """
        nodes = self._bfs()
        
        if not nodes:
            print('This tree has no nodes.')
            return

        layer_num = int(math.log(nodes[-1][1], 2)) + 1
        
        prt_nums = []
        
        for i in range(layer_num):
            prt_nums.append([None]*2**i)

        for v, p in nodes:
            row = int(math.log(p ,2))
            col = p % 2**row
            prt_nums[row][col] = v

        prt_str = ''
        for l in prt_nums:
            prt_str += str(l)[1:-1] + '\n'

        return prt_str


if __name__ == '__main__':
    nums = [4, 2, 5, 6, 1, 7, 3]
    bst = BinarySearchTree(nums)
    print(bst)

    # 插入
    bst.insert(1)
    bst.insert(4)
    print(bst)

    # 搜索
    for n in bst.search(2):
        print(n.parent.val, n.val)

    # 删除
    bst.insert(6)
    bst.insert(7)
    print(bst)
    bst.delete(7)
    print(bst)
    bst.delete(6)
    print(bst)
    bst.delete(4)
    print(bst)

    # min max
    print(bst.get_max())
    print(bst.get_min())



File: python/36_ac_automata/ac_automata.py

"""
    Aho-Corasick Algorithm

    Author: Wenru Dong
"""

from collections import deque
from typing import List

class ACNode:
    def __init__(self, data: str):
        self._data = data
        self._children = [None] * 26
        self._is_ending_char = False
        self._length = -1
        self._suffix = None
    

class ACAutomata:
    def __init__(self):
        self._root = ACNode("/")

    def _build_suffix_link(self) -> None:
        q = deque()
        q.append(self._root)
        while q:
            node = q.popleft()
            for child in node._children:
                if child:
                    if node == self._root:
                        child._suffix = self._root
                    else:
                        suffix = node._suffix
                        while suffix:
                            suffix_child = suffix._children[ord(child._data) - ord("a")]
                            if suffix_child:
                                child._suffix = suffix_child
                                break
                            suffix = suffix._suffix
                        if not suffix:
                            child._suffix = self._root
                    q.append(child)

    def _insert(self, text: str) -> None:
        node = self._root
        for index, char in map(lambda x: (ord(x) - ord("a"), x), text):
            if not node._children[index]:
                node._children[index] = ACNode(char)
            node = node._children[index]
        node._is_ending_char = True
        node._length = len(text)

    def insert(self, patterns: List[str]) -> None:
        for pattern in patterns:
            self._insert(pattern)
        self._build_suffix_link()

    def match(self, text: str) -> None:
        node = self._root
        for i, char in enumerate(text):
            index = ord(char) - ord("a")
            while not node._children[index] and node != self._root:
                node = node._suffix
            node = node._children[index]
            if not node:
                node = self._root
            tmp = node
            while tmp != self._root:
                if tmp._is_ending_char:
                    print(f"匹配起始下标{i - tmp._length + 1}，长度{tmp._length}")
                tmp = tmp._suffix


if __name__ == "__main__":

    patterns = ["at", "art", "oars", "soar"]
    ac = ACAutomata()
    ac.insert(patterns)
    
    ac.match("soarsoars")



File: python/36_ac_automata/ac_automata_.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from trie_ import Node, Trie
from queue import Queue


class ACNode(Node):
    def __init__(self, c: str):
        super(ACNode, self).__init__(c)
        self.fail = None
        self.length = 0

    def insert_child(self, c: str):
        self._insert_child(ACNode(c))


class ACTrie(Trie):
    def __init__(self):
        self.root = ACNode(None)


def ac_automata(main: str, ac_trie: ACTrie) -> list:
    root = ac_trie.root
    build_failure_pointer(ac_trie)

    ret = []
    p = root
    for i, c in enumerate(main):
        while p != root and not p.has_child(c):
            p = p.fail

        if p.has_child(c):  # a char matched, try to find all potential pattern matched
            q = p.get_child(c)
            while q != root:
                if q.is_ending_char:
                    ret.append((i-q.length+1, i))
                    # ret.append(main[i-q.length+1:i+1])
                q = q.fail
            p = p.get_child(c)

    return ret


def build_failure_pointer(ac_trie: ACTrie) -> None:
    root = ac_trie.root

    # queue: [(node, node.length) ....]
    node_queue = Queue()
    node_queue.put((root, root.length))

    root.fail = None
    while not node_queue.empty():
        p, length = node_queue.get()
        for pc in p.children:
            pc.length = length + 1
            if p == root:
                pc.fail = root
            else:
                q = p.fail
                # same as kmp
                while q != root and not q.has_child(pc.data):
                    q = q.fail

                # cases now:
                # 1. q == root
                # 2. q != root and q.has_child(pc.data)
                if q.has_child(pc.data):
                    pc.fail = q.get_child(pc.data)
                else:
                    pc.fail = root
            node_queue.put((pc, pc.length))


if __name__ == '__main__':
    ac_trie = ACTrie()
    ac_trie.gen_tree(['fuck', 'shit', 'TMD', '傻叉'])

    print('--- ac automata ---')
    m_str = 'fuck you, what is that shit, TMD你就是个傻叉傻叉傻叉叉'
    print('original str  : {}'.format(m_str))

    filter_range_list = ac_automata(m_str, ac_trie)
    str_filtered = m_str
    for start, end in filter_range_list:
        str_filtered = str_filtered.replace(str_filtered[start:end+1], '*'*(end+1-start))

    print('after filtered: {}'.format(str_filtered))



File: python/31_bfs_dfs/graph.py

# -*- coding:utf-8 -*-


class Undigraph(object):


    def __init__(self, vertex_num):
        self.v_num = vertex_num
        self.adj_tbl = []
        for i in range(self.v_num + 1):
            self.adj_tbl.append([])

    def add_edge(self, s, t):
        if s > self.v_num or t > self.v_num:
            return False
        self.adj_tbl[s].append(t)
        self.adj_tbl[t].append(s)
        return True
    
    def __len__(self):
        return self.v_num

    def __getitem__(self, ind):
        if ind > self.v_num:
            raise IndexError("No Such Vertex!")
        return self.adj_tbl[ind]

    def __repr__(self):
        return str(self.adj_tbl)

    def __str__(self):
        return str(self.adj_tbl)


class Digraph(object):


    def __init__(self, vertex_num):
        self.v_num = vertex_num
        self.adj_tbl = []
        for i in range(self.v_num + 1):
            self.adj_tbl.append([])
    
    def add_edge(self, frm, to):
        if frm > self.v_num or to > self.v_num:
            return False
        self.adj_tbl[frm].append(to)

    def __len__(self):
        return self.v_num

    def __getitem__(self, ind):
        if ind > self.v_num:
            raise IndexError("No such vertex!")
        return self.ajd_tbl[ind]

    def __repr__(self):
        return str(self.adj_tbl)

    def __str__(self):
        return str(self.adj_tbl)


if __name__ == '__main__':
    ug = Undigraph(10)
    ug.add_edge(1, 9)
    ug.add_edge(1, 3)
    ug.add_edge(3, 2)
    print(ug.adj_tbl)
    
    dg = Digraph(10)
    dg.add_edge(1, 9)
    dg.add_edge(1, 3)
    dg.add_edge(3, 4)
    print(dg.adj_tbl)



File: python/31_bfs_dfs/graph_application.py

# -*- coding:utf-8 -*-



from collections import deque
from graph import Undigraph

def find_vertex_by_degree(graph, s, degree):
    if len(graph) <= 1:
        return []
    if degree == 0:
        return [s]
    d_vertices = []
    queue = deque()
    prev = [-1] * len(graph)
    visited = [False] * len(graph)
    visited[s] = True
    queue.append(s)
    while len(queue) > 0:
        sz = len(queue)
        for i in range(sz):
            v = queue.popleft()
            for adj_v in graph[v]:
                if not visited[adj_v]:
                    prev[adj_v] = v
                    visited[adj_v] = True
                    queue.append(adj_v)
        degree -= 1
        if degree == 0 and len(queue) != 0:
            return queue 

   
if __name__ == '__main__':
    g = Undigraph(8)
    g.add_edge(0, 1)
    g.add_edge(0, 3)
    g.add_edge(1, 2)
    g.add_edge(1, 4)
    g.add_edge(2, 5)
    g.add_edge(3, 4)
    g.add_edge(4, 5)
    g.add_edge(4, 6)
    g.add_edge(5, 7)
    g.add_edge(6, 7)
    print(find_vertex_by_degree(g, 0, 4))



File: python/31_bfs_dfs/bfs_dfs.py

"""
    Breadth-first search and depth-first search.

    Author: Wenru Dong
"""

from typing import List, Optional, Generator, IO
from collections import deque

class Graph:
    """Undirected graph."""
    def __init__(self, num_vertices: int):
        self._num_vertices = num_vertices
        self._adjacency = [[] for _ in range(num_vertices)]

    def add_edge(self, s: int, t: int) -> None:
        self._adjacency[s].append(t)
        self._adjacency[t].append(s)

    def _generate_path(self, s: int, t: int, prev: List[Optional[int]]) -> Generator[str, None, None]:
        if prev[t] or s != t:
            yield from self._generate_path(s, prev[t], prev)
        yield str(t)

    def bfs(self, s: int, t: int) -> IO[str]:
        """Print out the path from Vertex s to Vertex t
        using bfs.
        """
        if s == t: return

        visited = [False] * self._num_vertices
        visited[s] = True
        q = deque()
        q.append(s)
        prev = [None] * self._num_vertices

        while q:
            v = q.popleft()
            for neighbour in self._adjacency[v]:
                if not visited[neighbour]:
                    prev[neighbour] = v
                    if neighbour == t:
                        print("->".join(self._generate_path(s, t, prev)))
                        return
                    visited[neighbour] = True
                    q.append(neighbour)

    def dfs(self, s: int, t: int) -> IO[str]:
        """Print out a path from Vertex s to Vertex t
        using dfs.
        """
        found = False
        visited = [False] * self._num_vertices
        prev = [None] * self._num_vertices

        def _dfs(from_vertex: int) -> None:
            nonlocal found
            if found: return
            visited[from_vertex] = True
            if from_vertex == t:
                found = True
                return
            for neighbour in self._adjacency[from_vertex]:
                if not visited[neighbour]:
                    prev[neighbour] = from_vertex
                    _dfs(neighbour)
        
        _dfs(s)
        print("->".join(self._generate_path(s, t, prev)))


if __name__ == "__main__":
    
    graph = Graph(8)

    graph.add_edge(0, 1)
    graph.add_edge(0, 3)
    graph.add_edge(1, 2)
    graph.add_edge(1, 4)
    graph.add_edge(2, 5)
    graph.add_edge(3, 4)
    graph.add_edge(4, 5)
    graph.add_edge(4, 6)
    graph.add_edge(5, 7)
    graph.add_edge(6, 7)

    graph.bfs(0, 7)
    graph.dfs(0, 7)



File: python/15_bsearch/bsearch_recursion.py

"""
    Author: dreamkong
"""

from typing import List


def bsearch(nums: List[int], target: int) -> int:
    return bsearch_internally(nums, 0, len(nums)-1, target)


def bsearch_internally(nums: List[int], low: int, high: int, target: int) -> int:
    if low > high:
        return -1

    mid = low+int((high-low) >> 2)
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        return bsearch_internally(nums, mid+1, high, target)
    else:
        return bsearch_internally(nums, low, mid-1, target)



File: python/15_bsearch/bsearch.py

"""
    Author: Wenru
"""

from typing import List

def bsearch(nums: List[int], target: int) -> int:
    """Binary search of a target in a sorted array
    without duplicates. If such a target does not exist,
    return -1, othewise, return its index.
    """
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1



File: python/06_linkedlist/palindrome.py

"""
    check a single-linked list whether a palindrome
"""

import sys
# 引用当前文件夹下的single_linked_list
sys.path.append('singly_linked_list')
from singly_linked_list import SinglyLinkedList

def reverse(head):
    reverse_head = None
    while head:
        next = head._next
        head._next = reverse_head
        reverse_head = head
        head = next

    return reverse_head

def is_palindrome(l):
    l.print_all()
    slow = l._head
    fast = l._head
    position = 0
    while fast and fast._next:
        slow = slow._next
        fast = fast._next._next
        position += 1

    reverse_node = reverse(slow)
    head_node = l._head
    is_palin = True
    while (head_node and reverse_node):
        if (head_node.data == reverse_node.data):
            head_node = head_node._next
            reverse_node = reverse_node._next
        else:
            is_palin = False
            break

    return is_palin

if __name__ == '__main__':
    # the result should be False, True, True, True, True
    test_str_arr = ['ab', 'aa', 'aba', 'abba', 'abcba']
    for str in test_str_arr:
        l = SinglyLinkedList()
        for i in str:
            l.insert_value_to_head(i)

        print(is_palindrome(l))






File: python/06_linkedlist/LRUCache.py

# Definition for singly-linked list.
class DbListNode(object):
    def __init__(self, x, y):
        self.key = x
        self.val = y
        self.next = None
        self.prev = None


class LRUCache:
    '''
    leet code: 146
        运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。
        它应该支持以下操作： 获取数据 get 和 写入数据 put 。
        获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
        写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。
            当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间

    哈希表+双向链表
    哈希表: 查询 O(1)
    双向链表: 有序, 增删操作 O(1)

    Author: Ben
    '''

    def __init__(self, capacity: int):
        self.cap = capacity
        self.hkeys = {}
        # self.top和self.tail作为哨兵节点, 避免越界
        self.top = DbListNode(None, -1)
        self.tail = DbListNode(None, -1)
        self.top.next = self.tail
        self.tail.prev = self.top

    def get(self, key: int) -> int:

        if key in self.hkeys.keys():
            # 更新结点顺序
            cur = self.hkeys[key]
            # 跳出原位置
            cur.next.prev = cur.prev
            cur.prev.next = cur.next
            # 最近用过的置于链表首部
            top_node = self.top.next
            self.top.next = cur
            cur.prev = self.top
            cur.next = top_node
            top_node.prev = cur

            return self.hkeys[key].val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.hkeys.keys():
            cur = self.hkeys[key]
            cur.val = value
            # 跳出原位置
            cur.prev.next = cur.next
            cur.next.prev = cur.prev

            # 最近用过的置于链表首部
            top_node = self.top.next
            self.top.next = cur
            cur.prev = self.top
            cur.next = top_node
            top_node.prev = cur
        else:
            # 增加新结点至首部
            cur = DbListNode(key, value)
            self.hkeys[key] = cur
            # 最近用过的置于链表首部
            top_node = self.top.next
            self.top.next = cur
            cur.prev = self.top
            cur.next = top_node
            top_node.prev = cur
            if len(self.hkeys.keys()) > self.cap:
                self.hkeys.pop(self.tail.prev.key)
                # 去掉原尾结点
                self.tail.prev.prev.next = self.tail
                self.tail.prev = self.tail.prev.prev

    def __repr__(self):
        vals = []
        p = self.top.next
        while p.next:
            vals.append(str(p.val))
            p = p.next
        return '->'.join(vals)


if __name__ == '__main__':
    cache = LRUCache(2)
    cache.put(1, 1)
    cache.put(2, 2)
    print(cache)
    cache.get(1)  # 返回  1
    cache.put(3, 3)  # 该操作会使得密钥 2 作废
    print(cache)
    cache.get(2)  # 返回 -1 (未找到)
    cache.put(4, 4)  # 该操作会使得密钥 1 作废
    print(cache)
    cache.get(1)  # 返回 -1 (未找到)
    cache.get(3)  # 返回  3
    print(cache)
    cache.get(4)  # 返回  4
    print(cache)



File: python/06_linkedlist/singlyLinkedList.py

# 1.单链表的插入、删除、查找操作；
# 2.链表中存储的数据类型是Int
#
# Author:Lee


class Node(object):
    """链表结构的Node节点"""

    def __init__(self, data, next_node=None):
        """Node节点的初始化方法.
        参数:
            data:存储的数据
            next:下一个Node节点的引用地址
        """
        self.__data = data
        self.__next = next_node

    @property
    def data(self):
        """Node节点存储数据的获取.
        返回:
            当前Node节点存储的数据
        """
        return self.__data

    @data.setter
    def data(self, data):
        """Node节点存储数据的设置方法.
        参数:
            data:新的存储数据
        """
        self.__data = data

    @property
    def next_node(self):
        """获取Node节点的next指针值.
        返回:
            next指针数据
        """
        return self.__next

    @next_node.setter
    def next_node(self, next_node):
        """Node节点next指针的修改方法.
        参数:
            next:新的下一个Node节点的引用
        """
        self.__next = next_node


class SinglyLinkedList(object):
    """单向链表"""

    def __init__(self):
        """单向列表的初始化方法."""
        self.__head = None

    def find_by_value(self, value):
        """按照数据值在单向列表中查找.
        参数:
            value:查找的数据
        返回:
            Node
        """
        node = self.__head
        while (node is not None) and (node.data != value):
            node = node.next_node
        return node

    def find_by_index(self, index):
        """按照索引值在列表中查找.
        参数:
            index:索引值
        返回:
            Node
        """
        node = self.__head
        pos = 0
        while (node is not None) and (pos != index):
            node = node.next_node
            pos += 1
        return node

    def insert_to_head(self, value):
        """在链表的头部插入一个存储value数值的Node节点.
        参数:
            value:将要存储的数据
        """
        node = Node(value)
        node.next_node = self.__head
        self.__head = node

    def insert_after(self, node, value):
        """在链表的某个指定Node节点之后插入一个存储value数据的Node节点.
        参数:
            node:指定的一个Node节点
            value:将要存储在新Node节点中的数据
        """
        if node is None:  # 如果指定在一个空节点之后插入数据节点，则什么都不做
            return

        new_node = Node(value)
        new_node.next_node = node.next
        node.next = new_node

    def insert_before(self, node, value):
        """在链表的某个指定Node节点之前插入一个存储value数据的Node节点.
        参数:
            node:指定的一个Node节点
            value:将要存储在新的Node节点中的数据
        """
        if (node is None) or (self.__head is None):  # 如果指定在一个空节点之前或者空链表之前插入数据节点，则什么都不做
            return

        if node == self.__head:  # 如果是在链表头之前插入数据节点，则直接插入
            self.insert_to_head(value)
            return

        new_node = Node(value)
        pro = self.__head
        not_found = False  # 如果在整个链表中都没有找到指定插入的Node节点，则该标记量设置为True
        while pro.next_node != node:  # 寻找指定Node之前的一个Node
            if pro.next_node is None:  # 如果已经到了链表的最后一个节点，则表明该链表中没有找到指定插入的Node节点
                not_found = True
                break
            else:
                pro = pro.next_node
        if not not_found:
            pro.next_node = new_node
            new_node.next_node = node

    def delete_by_node(self, node):
        """在链表中删除指定Node的节点.
        参数:
            node:指定的Node节点
        """
        if self.__head is None:  # 如果链表是空的，则什么都不做
            return

        if node == self.__head:  # 如果指定删除的Node节点是链表的头节点
            self.__head = node.next_node
            return

        pro = self.__head
        not_found = False  # 如果在整个链表中都没有找到指定删除的Node节点，则该标记量设置为True
        while pro.next_node != node:
            if pro.next_node is None:  # 如果已经到链表的最后一个节点，则表明该链表中没有找到指定删除的Node节点
                not_found = True
                break
            else:
                pro = pro.next_node
        if not not_found:
            pro.next_node = node.next_node

    def delete_by_value(self, value):
        """在链表中删除指定存储数据的Node节点.
        参数:
            value:指定的存储数据
        """
        if self.__head is None:  # 如果链表是空的，则什么都不做
            return

        if self.__head.data == value:  # 如果链表的头Node节点就是指定删除的Node节点
            self.__head = self.__head.next_node

        pro = self.__head
        node = self.__head.next_node
        not_found = False
        while node.data != value:
            if node.next_node is None:  # 如果已经到链表的最后一个节点，则表明该链表中没有找到执行Value值的Node节点
                not_found = True
                break
            else:
                pro = node
                node = node.next_node
        if not_found is False:
            pro.next_node = node.next_node

    def delete_last_n_node(self, n):
        """删除链表中倒数第N个节点.
        主体思路：
            设置快、慢两个指针，快指针先行，慢指针不动；当快指针跨了N步以后，快、慢指针同时往链表尾部移动，
            当快指针到达链表尾部的时候，慢指针所指向的就是链表的倒数第N个节点
        参数:
            n:需要删除的倒数第N个序数
        """
        fast = self.__head
        slow = self.__head
        step = 0

        while step <= n:
            fast = fast.next_node
            step += 1

        while fast.next_node is not None:
            tmp = slow
            fast = fast.next_node
            slow = slow.next_node

        tmp.next_node = slow.next_node

    def find_mid_node(self):
        """查找链表中的中间节点.
        主体思想:
            设置快、慢两种指针，快指针每次跨两步，慢指针每次跨一步，则当快指针到达链表尾部的时候，慢指针指向链表的中间节点
        返回:
            node:链表的中间节点
        """
        fast = self.__head
        slow = self.__head

        while fast.next_node is not None:
            fast = fast.next_node.next_node
            slow = slow.next_node

        return slow

    def create_node(self, value):
        """创建一个存储value值的Node节点.
        参数:
            value:将要存储在Node节点中的数据
        返回:
            一个新的Node节点
        """
        return Node(value)

    def print_all(self):
        """打印当前链表所有节点数据."""
        pos = self.__head
        if pos is None:
            print("当前链表还没有数据")
            return
        while pos.next_node is not None:
            print(str(pos.data) + " --> ", end="")
            pos = pos.next_node
        print(str(pos.data))

    def reversed_self(self):
        """翻转链表自身."""
        if self.__head is None or self.__head.next is None:  # 如果链表为空，或者链表只有一个节点
            return

        pre = self.__head
        node = self.__head.next
        while node is not None:
            pre, node = self.__reversed_with_two_node(pre, node)

        self.__head.next = None
        self.__head = pre

    def __reversed_with_two_node(self, pre, node):
        """翻转相邻两个节点.
        参数:
            pre:前一个节点
            node:当前节点
        返回:
            (pre,node):下一个相邻节点的元组
        """
        tmp = node.next_node
        node.next_node = pre
        pre = node  # 这样写有点啰嗦，但是能让人更能看明白
        node = tmp
        return pre, node

    def has_ring(self):
        """检查链表中是否有环.
        主体思想：
            设置快、慢两种指针，快指针每次跨两步，慢指针每次跨一步，如果快指针没有与慢指针相遇而是顺利到达链表尾部
            说明没有环；否则，存在环
        返回:
            True:有环
            False:没有环
        """
        fast = self.__head
        slow = self.__head

        while (fast.next_node is not None) and (fast is not None):
            fast = fast.next_node
            slow = slow.next_node
            if fast == slow:
                return True

        return False



File: python/06_linkedlist/singly_linked_list.py

"""
    1) Insertion, deletion and search of singly-linked list;
    2) Assumes int type for data in list nodes.

    Author: Wenru
"""
from typing import Optional


class Node:

    def __init__(self, data: int, next_node=None):
        self.data = data
        self._next = next_node


class SinglyLinkedList:

    def __init__(self):
        self._head = None

    def find_by_value(self, value: int) -> Optional[Node]:
        p = self._head
        while p and p.data != value:
            p = p._next
        return p

    def find_by_index(self, index: int) -> Optional[Node]:
        p = self._head
        position = 0
        while p and position != index:
            p = p._next
            position += 1
        return p

    def insert_value_to_head(self, value: int):
        new_node = Node(value)
        self.insert_node_to_head(new_node)

    def insert_node_to_head(self, new_node: Node):
        if new_node:
            new_node._next = self._head
            self._head = new_node

    def insert_value_after(self, node: Node, value: int):
        new_node = Node(value)
        self.insert_node_after(node, new_node)

    def insert_node_after(self, node: Node, new_node: Node):
        if not node or not new_node:
            return
        new_node._next = node._next
        node._next = new_node

    def insert_value_before(self, node: Node, value: int):
        new_node = Node(value)
        self.insert_node_before(node, new_node)

    def insert_node_before(self, node: Node, new_node: Node):
        if not self._head or not node or not new_node:
            return
        if self._head == node:
            self.insert_node_to_head(new_node)
            return
        current = self._head
        while current._next and current._next != node:
            current = current._next
        if not current._next:  # node is not even in the list
            return
        new_node._next = node
        current._next = new_node

    def delete_by_node(self, node: Node):
        if not self._head or not node:
            return
        if node._next:
            node.data = node._next.data
            node._next = node._next._next
            return
        # node is the last one or not in the list
        current = self._head
        while current and current._next != node:
            current = current._next
        if not current:  # node not in the list
            return
        current._next = node._next

    def delete_by_value(self, value: int):
        if not self._head or not value:
            return
        fake_head = Node(value + 1)
        fake_head._next = self._head
        prev, current = fake_head, self._head
        while current:
            if current.data != value:
                prev._next = current
                prev = prev._next
            current = current._next
        if prev._next:
            prev._next = None
        self._head = fake_head._next  # in case head.data == value

    def __repr__(self) -> str:
        nums = []
        current = self._head
        while current:
            nums.append(current.data)
            current = current._next
        return "->".join(str(num) for num in nums)

    # 重写__iter__方法，方便for关键字调用打印值
    def __iter__(self):
        node = self._head
        while node:
            yield node.data
            node = node._next

    def print_all(self):
        current = self._head
        if current:
            print(f"{current.data}", end="")
            current = current._next
        while current:
            print(f"->{current.data}", end="")
            current = current._next
        print("\n", flush=True)


if __name__ == "__main__":
    l = SinglyLinkedList()
    for i in range(15):
        l.insert_value_to_head(i)
    node9 = l.find_by_value(9)
    l.insert_value_before(node9, 20)
    l.insert_value_before(node9, 16)
    l.insert_value_before(node9, 16)
    l.delete_by_value(16)
    node11 = l.find_by_index(3)
    l.delete_by_node(node11)
    l.delete_by_node(l._head)
    l.delete_by_value(13)
    print(l)
    for value in l:
        print(value)



File: python/28_heap/min_heap.py

class Heap(object):
    '''
    索引从0开始的小顶堆
    参考: https://github.com/python/cpython/blob/master/Lib/heapq.py

    author: Ben
    '''

    def __init__(self, nums):
        self._heap = nums

    def _siftup(self, pos):
        '''
        从上向下的堆化
        将pos节点的子节点中的最值提升到pos位置
        '''
        start = pos
        startval = self._heap[pos]
        n = len(self._heap)
        # 完全二叉树特性
        child = pos * 2 + 1
        # 比较叶子节点
        while child < n:
            right = child + 1
            # 平衡二叉树的特性, 大的都在右边
            if right < n and not self._heap[right] > self._heap[child]:
                child = right
            self._heap[pos] = self._heap[child]
            pos = child
            child = pos * 2 + 1
        self._heap[pos] = startval

        # 此时只有pos是不确定的
        self._siftdown(start, pos)

    def _siftdown(self, start, pos):
        '''
        最小堆: 大于start的节点, 除pos外已经是最小堆
        以pos为叶子节点, start为根节点之间的元素进行排序. 将pos叶子节点交换到正确的排序位置
        操作: 从叶子节点开始, 当父节点的值大于子节点时, 父节点的值降低到子节点
        '''
        startval = self._heap[pos]
        while pos > start:
            parent = (pos - 1) >> 1
            parentval = self._heap[parent]
            if parentval > startval:
                self._heap[pos] = parentval
                pos = parent
                continue
            break
        self._heap[pos] = startval

    def heapify(self):
        '''
        堆化: 从后向前(从下向上)的方式堆化, _siftup中pos节点的子树已经是有序的,
        这样要排序的节点在慢慢减少
        1. 因为n/2+1到n的节点是叶子节点(完全二叉树的特性), 它们没有子节点,
        所以, 只需要堆化n/2到0的节点, 以对应的父节点为根节点, 将最值向上筛选,
        然后交换对应的根节点和查找到的最值
        2. 因为开始时待排序树的根节点还没有排序, 为了保证根节点的有序,
        需要将子树中根节点交换到正确顺序
        '''
        n = len(self._heap)
        for i in reversed(range(n // 2)):
            self._siftup(i)

    def heappop(self):
        '''
        弹出堆首的最值 O(logn)
        '''
        tail = self._heap.pop()
        # 为避免破环完全二叉树特性, 将堆尾元素填充到堆首
        # 此时, 只有堆首是未排序的, 只需要一次从上向下的堆化
        if self._heap:
            peak = self._heap[0]
            self._heap[0] = tail
            self._siftup(0)
            return peak
        return tail

    def heappush(self, val):
        '''
        添加元素到堆尾 O(logn)
        '''
        n = len(self._heap)
        self._heap.append(val)
        # 此时只有堆尾的节点是未排序的, 将添加的节点迭代到正确的位置
        self._siftdown(0, n)

    def __repr__(self):
        vals = [str(i) for i in self._heap]
        return '>'.join(vals)


if __name__ == '__main__':
    h = Heap([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
    h.heapify()
    print(h)
    print(h.heappop())
    print(h)
    h.heappush(3.5)
    print(h)
    h.heappush(0.1)
    print(h)
    h.heappush(0.5)
    print(h)
    print(h.heappop())
    print(h)



File: python/28_heap/heap.py

"""
    Max-heap

    Author: Wenru Dong
"""

from typing import Optional, List

class Heap:
    def __init__(self, capacity: int):
        self._data = [0] * (capacity + 1)
        self._capacity = capacity
        self._count = 0
    
    @classmethod
    def _parent(cls, child_index: int) -> int:
        """The parent index."""
        return child_index // 2
    
    @classmethod
    def _left(cls, parent_index: int) -> int:
        """The left child index."""
        return 2 * parent_index
    
    @classmethod
    def _right(cls, parent_index: int) -> int:
        """The right child index."""
        return 2 * parent_index + 1

    def _siftup(self) -> None:
        i, parent = self._count, Heap._parent(self._count)
        while parent and self._data[i] > self._data[parent]:
            self._data[i], self._data[parent] = self._data[parent], self._data[i]
            i, parent = parent, Heap._parent(parent)

    @classmethod
    def _siftdown(cls, a: List[int], count: int, root_index: int = 1) -> None:
        i = larger_child_index = root_index
        while True:
            left, right = cls._left(i), cls._right(i)
            if left <= count and a[i] < a[left]:
                larger_child_index = left
            if right <= count and a[larger_child_index] < a[right]:
                larger_child_index = right
            if larger_child_index == i: break
            a[i], a[larger_child_index] = a[larger_child_index], a[i]
            i = larger_child_index

    def insert(self, value: int) -> None:
        if self._count >= self._capacity: return
        self._count += 1
        self._data[self._count] = value
        self._siftup()

    def remove_max(self) -> Optional[int]:
        if self._count:
            result = self._data[1]
            self._data[1] = self._data[self._count]
            self._count -= 1
            Heap._siftdown(self._data, self._count)
            return result

    @classmethod
    def build_heap(cls, a: List[int]) -> None:
        """Data in a needs to start from index 1."""
        for i in range((len(a) - 1)//2, 0, -1):
            cls._siftdown(a, len(a) - 1, i)
    
    @classmethod
    def sort(cls, a: List[int]) -> None:
        """Data in a needs to start from index 1."""
        cls.build_heap(a)
        k = len(a) - 1
        while k > 1:
            a[1], a[k] = a[k], a[1]
            k -= 1
            cls._siftdown(a, k)

    def __repr__(self):
        return self._data[1 : self._count + 1].__repr__()


if __name__ == "__main__":
    hp = Heap(10)
    hp.insert(3)
    hp.insert(9)
    hp.insert(1)
    hp.insert(8)
    hp.insert(7)
    hp.insert(3)
    print(hp)
    for _ in range(6):
        print(hp.remove_max())
    a = [0, 6, 3, 4, 0, 9, 2, 7, 5, -2, 8, 1, 6, 10]
    Heap.sort(a)
    print(a[1:])


# 数据结构和算法必知必会的50个代码实现
### 微信搜索我的公众号“小争哥”，或者微信扫描下面二维码关注
### 关注微信公众号，回复”PDF“获取独家算法资料。
### 前Google工程师，10万人跟着学的《数据结构和算法之美》《设计模式之美》专栏作者
![t2](https://github.com/wangzheng0822/markdownphotos/blob/master/pics/qrcode_for_gh_9b0e7afdff20_258.jpg)

## 数组
* 实现一个支持动态扩容的数组
* 实现一个大小固定的有序数组，支持动态增删改操作
* 实现两个有序数组合并为一个有序数组

## 链表
* 实现单链表、循环链表、双向链表，支持增删操作
* 实现单链表反转
* 实现两个有序的链表合并为一个有序链表
* 实现求链表的中间结点

## 栈
* 用数组实现一个顺序栈
* 用链表实现一个链式栈
* 编程模拟实现一个浏览器的前进、后退功能

## 队列
* 用数组实现一个顺序队列
* 用链表实现一个链式队列
* 实现一个循环队列

## 递归
* 编程实现斐波那契数列求值f(n)=f(n-1)+f(n-2)
* 编程实现求阶乘n!
* 编程实现一组数据集合的全排列

## 排序
* 实现归并排序、快速排序、插入排序、冒泡排序、选择排序
* 编程实现O(n)时间复杂度内找到一组数据的第K大元素

## 二分查找
* 实现一个有序数组的二分查找算法
* 实现模糊二分查找算法（比如大于等于给定值的第一个元素）

## 散列表
* 实现一个基于链表法解决冲突问题的散列表
* 实现一个LRU缓存淘汰算法

## 字符串
* 实现一个字符集，只包含a～z这26个英文字母的Trie树
* 实现朴素的字符串匹配算法

## 二叉树
* 实现一个二叉查找树，并且支持插入、删除、查找操作
* 实现查找二叉查找树中某个节点的后继、前驱节点
* 实现二叉树前、中、后序以及按层遍历

## 堆
* 实现一个小顶堆、大顶堆、优先级队列
* 实现堆排序
* 利用优先级队列合并K个有序数组
* 求一组动态数据集合的最大Top K

## 图
* 实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法
* 实现图的深度优先搜索、广度优先搜索
* 实现Dijkstra算法、A*算法
* 实现拓扑排序的Kahn算法、DFS算法

## 回溯
* 利用回溯算法求解八皇后问题
* 利用回溯算法求解0-1背包问题

## 分治
* 利用分治算法求一组数据的逆序对个数

## 动态规划
* 0-1背包问题
* 最小路径和
* 编程实现莱文斯坦最短编辑距离
* 编程实现查找两个字符串的最长公共子序列
* 编程实现一个数据序列的最长递增子序列
