数据结构相关

zcx · 2023 年4 月 14 日 07:10

常问的

数组/列表：排序
python 实现数据结构八种内部排序算法-CSDN博客
链表：单链表插入、逆序等
栈：去重、逆序
二叉树：遍历、生成树

相关题：
https://ceshiren.com/t/topic/26007
https://ceshiren.com/t/topic/11100
https://ceshiren.com/t/topic/16646

算法和数据结构的区别：
数据结构是一组数据的存储结构(数组、链表、栈、队列等)，数据结构是静态的，是为算法服务的
算法是操作数据结构的一组方法，算法是作用在特殊结构之上

一、数据结构

线性表：线性表是数据排成一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。
包括：数组，链表、队列、栈。
非线性表：数据之间并不是简单的前后关系。
包括：二叉树、堆、图等。

1.数组：

连续的内存空间和相同类型的数据：使数组支持“随机访问”。
但在数组中删除、插入数据时，需要做大量的数据搬移工作。

python实现 2.数组与列表-python
初始化：

长度固定，需要申请一个固定长度的列表
存入/删除数据，要做计数操作(无需指针)
存入/删除数据，要做数据迁移
插入数据需要和已存在的数据挨着，不能有间隔

2.链表

链表和数组的区别是，内存地址不连续，节点上需要存储指向下一个/上一个节点的指针

分为：
单向链表、循环链表、双向链表、双向循环链表

https://ceshiren.com/t/topic/11561

3.队列

先进先出
分类：
顺序队列：普通队列、优化队列、循环队列——tail指针指向的空的位置，tail=head队列为空，tail>head队列不为空
链式队列——tail指针指向的位置有值的(除非是空队列)

python代码 4.队列-python
顺序队列初始化：

固定大小
存在两个指针(计数)head,tail，初始都是0(指向第一个节点)
通过tail变动入队，head出队

链式队列初始化：

不用声明队列大小
head,tail不再计数，直接是指针
声明节点类，写初始化方法(节点值，和指向下一个节点的指针)

4.堆栈

先进后出

二、算法

程序 = 数据结构 + 算法

算法概念： 解决特定问题的有限求解步骤

1.算法的特性

输入、输出、有穷性、确定性、可能性
（1）输入输出

算法具有零个或者多个输入
算法至少有一个或者多个输出

（2）有穷性
执行有限步骤后自动结束，不会出现无限循环，并且每一个步骤都在可接受的时间内完成。
（3）确定性
算法的每一步骤都有确定含义，不会出现二义性
（4）可行性
算法的每一步都必须是可行的，每一步都能通过执行有限次数完成。

2.算法设计要求

同一个问题，可以有多种解决的算法(相对好的算法是存在的)
（1）正确性
（2）可读性
（3）健壮性
（4）时间效率高：算法执行时间
（5）存储量低

3.衡量算法性能的两个维度

3.1渐进时间复杂度：估算算法的执行时间随数据规模增大的变化趋势

3.1.1时间复杂度分类
根据输入数据的特点，时间复杂度具有「最差」、「平均」、「最佳」三种情况：

举例： 线性查找，即遍历整个数组，遇到 7 则返回 true

def find_seven(nums):
    for num in nums:
        if num == 7:
            return True
    return False

最佳情况 Ω(1)
nums = [7, a, b, c, …] ，即当数组首个数字为 7 时，无论 nums 有多少元素，线性查找的循环次数都为1次；
最差情况 O(N) ——最常用的
nums = [a, b, c, …] 且 nums 中所有数字都不为 7 ，此时线性查找会遍历整个数组，循环 N 次；
平均情况 Θ
需要考虑输入数据的分布情况，计算所有数据情况下的平均时间复杂度；例如本题目，需要考虑数组长度、数组元素的取值范围等；

大O表示法: T(n) = O(f(n)) 大O是最坏情况

说明：n指的是算法处理输入的数量。
根据不同算法，具有不同定义，例如：
排序算法： N 代表需要排序的元素数量；
搜索算法： N 代表搜索范围的元素总数，例如数组大小、矩阵大小、二叉树节点数、图节点和边数等；

均摊时间复杂度： 更特殊的场景，对一个数据结构进线一组连续操作，大部分情况时间复杂度都很低，只有个别情况时间复杂度较高，且这些操作之间存在前后连续的时序关系。

3.2渐进空间复杂度：估算算法的存储空间随数据规模增大的变化趋势

3.2.1 空间类型
空间复杂度涉及的空间类型

输入空间：存储输入数据所需的空间大小；
暂存空间：算法运行过程中，存储所有中间变量和对象等数据所需的空间大小；
输出空间：算法运行返回时，存储输出数据所需的空间大小；
通常情况下，空间复杂度指在输入数据大小为 N 时，算法运行所使用的「暂存空间」+「输出空间」的总体大小。

3.2.1 内存类型
而根据不同来源，算法使用的内存空间分为三类：

指令空间：编译后，程序指令所使用的内存空间。
数据空间：算法中的各项变量使用的空间，包括：声明的常量、变量、动态数组、动态对象等使用的内存空间。
栈帧空间：程序调用函数是基于栈实现的，函数在调用期间，占用常量大小的栈帧空间，直至返回后释放。如以下代码所示，在循环中调用函数，每轮调用 test() 返回后，栈帧空间已被释放，因此空间复杂度仍为 O(1) 。

def test():
    return 0

def algorithm(N):
    for _ in range(N):
        test()

算法中，栈帧空间的累计常出现于递归调用。如以下代码所示，通过递归调用，会同时存在 N 个未返回的函数 algorithm() ，此时累计使用 O(N) 大小的栈帧空间。

def algorithm(N):
    if N <= 1: return 1
    return algorithm(N - 1) + 1

通常情况下，空间复杂度统计算法在 “最差情况” 下使用的空间大小，以体现算法运行所需预留的空间量，使用符号 O 表示。——最差情况有两层含义，分别为「最差输入数据」、算法运行中的「最差运行点」

4.算法思想

（1）穷举/枚举算法思想：从所有可能的情况中搜索答案
（2）递推算法思想：根据已有数据和关系，逐步推导而得到结果

顺推法：从已知条件出发，逐步推算解决办法
逆推法：从已知结果出发，用迭代表达式逐步推出问题开始的条件

（3）递归算法思想：不断调用自身达到求解问题方法，要求待求解问题可以分解为相同问题的子问题。
定义介绍
猴子吃桃问题
说明：正常是由前一个推后一个，这个是倒推(后一个推前一个)

#第n天吃之前数量确认
def  peach(n):
    if n==10:
        return 1
    return (peach(n+1)+1)*2  #因为已知的是下一天的数量f(n+1)，不知道前一天数据f(n-1)
f(1)  #1534

（4）分治算法思想
将一个规模为N的问题分解为K个规模较小的子问题(这些问题相互独立且与原问题性质相同)
求出子问题的解，即可得到原问题解
（5）贪心算法思想
贪心算法不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优选择。使用贪心策略要注意局部最优与全局最优的关系，选择当前的局部最优并不一定能推导出问题的全局最优。
从问题的某一个初始解出发，逐步逼近给定目标。
饼干分发问题
python实现

class Solution:

    def findContentChild(self,g :list,s :list):
        # g 每个小朋友胃口值列表
        # s 每个小饼干尺寸值列表
        # 1.先排序，默认升序
        g.sort()
        s.sort()
        count = 0 # 被满足孩子数量
        i = len(g)-1 # 胃口值列表的最后一个索引值
        j = len(s)-1 # 饼干尺寸列表的最后一个索引值
        while i>=0 and j>=0:
            # 用饼干尺寸s[j]去匹配孩子胃口g[i]
            if g[i] <= s[j]: #当前孩子可以被满足
                count += 1
                j -= 1 # 用下一个饼干去找合适的胃口
            # 无论胃口符合不符合i都要减1
            # 以上是符合，不符合就是孩子胃口太大，找下一个合适的小一点的胃口
            i -= 1
        return  count

其他贪心算法经典案例
（6）回溯/试探算法思想
（7）迭代
（8）动态规划

zcx · 2023 年5 月 2 日 12:42

按照老师的逻辑重新代码如下，并附上详细注释思路
1.数组

# coding:utf-8
class Array:
    def __init__(self,capacity)->None:
        self.data = [-1] * capacity # 初始化capacity大小的空间，初始值-1
        self.count = 0  # 实际存的数据量
        self.n = capacity  # 数组容量

    # 插入
    # location是索引，从0开始
    def  insert(self,location,value):
        # 超出数组实际存数个数不能插入
        # 因为如要从后往前挪，所以范围是倒序的 -1
        # range(start,end) 不包括end，实际范围是end+1,即为start~end+1,这个范围是目标挪动范围
        # count这个是数组长度，如果作为索引这个位置是没有值的
        if location < 0  or location > self.count:
            return  False
        # 数组满了
        if self.count == self.n:
            return False
        # 非以上情况，就可以插入了，向后移动依次移动位置
        for i in range(self.count,location,-1):
            self.data[i] = self.data[i-1]
        # 插入数据
        self.data[location] = value
        self.count += 1
        return True


    def delete(self,location):
        if location < 0 or location >= self.count:
            return False
        # 移动要移动的数据的后边的数据，索引位置location+1，self.count-1往前移动一位
        for i in range(location+1,self.count):
            self.data[i-1] = self.data[i]
        # 增加删除要记得数量变化
        self.count -= 1
        return True


    def find(self,location):
        if location < 0 or location >= self.count:
            return -1
        return  self.data[location]


def test_demo():
    array = Array(5)
    array.insert(0, 1)
    array.insert(0, 2)
    array.insert(1, 3)
    array.insert(2, 4)
    array.insert(4, 5)

    # 判断插入不成功
    assert not array.insert(0, 100)
    assert array.find(0) == 2
    assert array.find(2) == 4
    assert array.find(4) == 5
    assert array.find(10) == -1
    assert array.count == 5
    removed = array.delete(4)
    assert removed
    assert array.find(4) == -1
    removed = array.delete(10)
    assert not removed
    # 2 3 4 1 5
    assert array.data == [2, 3, 4, 1, 5]


if __name__ == '__main__':
    test_demo()

2.队列
普通队列/基础队列


# coding:utf-8

# 基础队列/普通队列
class Queue1:
    def __init__(self,capacity):
        self.n = capacity
        self.items = [-1] * capacity
        self.head = 0
        self.tail = 0

   # 入队，从tail进入队列
    def enqueue(self,value):
        # 队列满了
        if self.tail == self.n :
            return False
        # 入队
        self.items[self.tail] = value
        self.tail += 1
        return True

   # 出队，从head出队
    def dequeue(self):
        # 判断队列是否为空，一旦tail>head队列就是有值的
        if self.tail == self.head :
            return None
        value = self.items[self.head]
        self.head += 1
        return value


def test_queue1():
    a = Queue1(10)
    a.enqueue("10")
    a.enqueue("20")
    deque_item = a.dequeue()
    assert deque_item == "10"
    a.enqueue("30")
    assert a.items[a.head] == "20"
    assert a.items[a.tail - 1] == "30"

优化队列

# 优化队列
class Queue2:
    def __init__(self,capacity: int)->None:
        self.n = capacity
        self.items = [-1] * capacity
        self.head = 0
        self.tail = 0

    # 入队
    def enqueue(self,value):
        # 判断是否是队列满了
        if self.tail == self.n:
            # 从队列头到尾部都是有数据的，真的队列满的
            if self.head == 0:
                return  False
            # tail在队列最尾端，且head不在最前边，需要把数据移动到队列的开头
            for i in range(self.head,self.tail):
                self.items[i-1] = self.items[i]
                # 移动后要修改头尾指针
                self.tail -= self.head
                self.head = 0
        # 新数据入队
        self.items[self.tail] = value
        self.tail += 1
        return True

    def  dequeue(self):
        if self.head == self.tail:
            return None
        value = self.items[self.head]
        self.head  += 1
        return value

def test_queue2():
    a = Queue2(3)
    a.enqueue("10")
    a.enqueue("20")
    a.enqueue("30")
    result = a.enqueue("40")
    assert not result
    deque_item = a.dequeue()
    assert deque_item == "10"
    a.enqueue("30")
    assert a.items[0] == "20"
    assert a.items[2] == "30"

循环队列

class Queue3:
    def __init__(self,capacity):
        self.n = capacity
        self.items = [-1]*capacity
        self.head = 0
        self.tail = 0

    def enqueue(self,value):
        # 判断栈满
        if (self.tail+1)% self.n == self.head:
            return  False
        self.items[self.tail] = value
        self.tail = (self.tail+1)% self.n
        return True

    def dequeue(self):
        # 判断栈空
        if self.tail == self.head:
            return None
        value = self.items[self.head]
        self.head = (self.head+1)% self.n
        return value


def test_queue3():
    a = Queue3(3)
    a.enqueue("10")
    a.enqueue("20")
    result = a.enqueue("30")
    assert not result
    a.dequeue()
    a.enqueue("30")
    assert a.items[2] == "30"
    result = a.enqueue("10")
    assert not result

链式队列

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

    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self,value):
        # 判断链式队列是不是为空(不为空的时候，tail指向最后一个节点)
        # 队列为空时
        if self.tail is None:
            new_node = self.Node(value)
            self.tail = new_node
            self.head = new_node
        else: # 队列不为空时
            self.tail.next = self.Node(value)
            self.tail =self.tail.next

    def dequeue(self):
        if self.tail is  None:
            return -1
        value = self.head.data
        self.head = self.head.next
        return value


def test_queue4():
    a = Queue4()
    a.enqueue("10")
    a.enqueue("20")
    a.enqueue("30")
    deque_item = a.dequeue()
    assert deque_item == "10"
    assert a.head.data == "20"
    assert a.head.next.data == "30"

zcx · 2023 年5 月 30 日 09:14

链表

class SinglyLinkedList:
    class Node:
        def __init__(self ,value):
            self.data = value
            self.next = None


    def __init__(self):
        self.head = None


    # 在头节点前插入一个新节点
    def insert_to_head(self ,value):
        new_node = self.Node(value)
        # 链表无元素
        if self.head  is None:
            self.head = new_node
        else:
            # 链表有值，即为头部也有值
            # 需要把新的节点作为新的头节点，旧的头节点作为普通节点，即为新节点的后继节点
            new_node.next = self.head # 特殊注意
            self.head = new_node
        return new_node

    # 在尾节点插入新节点
    def insert_tail(self, value):
        if self.head is None:
            self.insert_to_head(value)
            return
        q = self.head
        # 寻找尾部节点
        while q.next is not None:
            q = q.next
        new_node = self.Node(value)
        q.next =  new_node



    # 在某节点后插入新节点
    def insert_after(self ,node ,value):
        if node is None:
            return
        new_node = self.Node(value)
        # 原node后边的节点先赋值给新node的next指针
        new_node.next = node.next
        # 原节点的next指针指向新节点
        node.next = new_node


    def insert_before(self ,node ,value):
        if self.head is None:
            self.insert_to_head(value)
            return
        q = self.head
        # 遍历出要插入节点前的节点node的前节点
        while q.next is not None and q.next != node:
            q = q.next
        # 找到了前节点,新节点连接前后
        if q.next == node:
            new_node = self.Node(value)
            new_node.next = node
            q.next = new_node


    def  find_by_value(self ,value):
        if self.head is None:
            return
        q = self.head
        while q is not None and q.data != value :
            q = q.next
        if q is None:
            return
        return q

    def delete_by_value(self ,value):
        if self.head is None:
            return
        q = self.head
        # 记录前一个节点
        pre_node = None
        while q is not None and q.data != value:
            pre_node = q  # 这个必须在前
            q = q.next
        # 链表中没有等于这个值的节点
        if q is None:
            return False
        # head的值value
        if pre_node is None:
            self.head = self.head.next
        else:
            pre_node.next = q.next
        return True

    def print_all(self):
        if self.head is None:
            return
        q = self.head
        count_link = 0
        while q is not None:
            print(q.data)
            count_link += 1
            q = q.next
        # 链表长度
        return count_link

        def revserse_linklist(self):
            pre_node = None
        cur = self.head
        while cur:
            next_node = cur.next
            cur.next = pre_node
            pre_node = cur
            cur = next_node
        self.head = pre_node # 这样才能找到头，可以直接应用print_all()打印
        return pre_node


def test_link():
    link = SinglyLinkedList()
    data = [1, 2, 5, 3, 1]
    for i in data:
        link.insert_tail(i)
    link.insert_to_head(99)
    # 打印内容为 99 1 2 5 3 1
    link.print_all()
    link.delete_by_value(2)
    assert not link.delete_by_value(999)
    assert link.delete_by_value(99)
    # 打印内容为 1 5 3 1
    link.print_all()
    assert link.find_by_value(2) is None
    new_node = link.find_by_value(3)
    link.insert_after(new_node, 10)
    assert link.find_by_value(3).next.data == 10
    link.insert_before(new_node, 30)
    assert link.find_by_value(5).next.data == 30
    print('反转前')
    link.print_all()
    print('反转后')
    link.revserse_linklist()
    link.print_all()

    # q = head
    # while q !=None:
    #     print(q.data)
    #     q = q.next


# 快慢指针找链表中间值
'''
若字符串长度是奇数，那么返回的节点就是中间的节点
若字符串长度是偶数，那么返回的节点就是中间的位置的前一个节点
'''
# def  get_mid(first:SinglyLinkedList.Node)->SinglyLinkedList.Node:
#     fast = first
#     slow = first
#     while fast.next and  fast.next.next :
#         fast = fast.next.next
#         slow = slow.next
#     return slow


def  get_mid(first):
    fast = first
    slow = first
    while fast.next and  fast.next.next :
        fast = fast.next.next
        slow = slow.next
    return slow

# 链表反转
def reverse_linklist(head):
    pre = None
    cur = head
    while cur:
        # 先把head后的节点找到
        next_node = cur.next
        # 之后把head指向None(后边的节点就不是None了，就是前节点)
        cur.next = pre
        # 把当前的节点head作为反转节点的前节点
        pre = cur
        # 把临时指针指向下一个节点
        cur = next_node
    return pre


# todo:回文字符串
'''
如何判断一个字符串是否是回文字符串的问题，我想你应该听过，我们今天的题目就是基于这个问题的改造版本。
如果字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？你有什么好的解决思路呢？相应的时间空间复杂度又是多少呢？
'''



# 检查是否是回溯字符串
def backTrackingStr(str_b ,first):
    fast = first
    slow = first
    while fast.next and fast.next.next:
        fast = fast.next.next
        slow = slow.next
    # todo:为啥reverse_linklist()参数不是slow.next
    # slow是中间节点,链表反转的参数就是找到的中间值(和链表的长度是奇偶无关)
    reverse_head =reverse_linklist(slow)
    head = first
    is_palin = True
    while head and reverse_head:
        if reverse_head.data == head.data:
            head = head.next
            reverse_head = reverse_head.next
        else:
            is_palin = False
            break
    return is_palin


if __name__ == '__main__':
    # test_link()
    # 初始化数据，放入链表
    link_str = SinglyLinkedList()
    str1 = '3213'
    str_head = link_str.insert_to_head(str1[0])  # 记录头指针作为找中点函数的入参
    for i in str1[1:]:
        link_str.insert_tail(i)
    # link_str.print_all()
    # todo:找链表中间值
    mid_node = get_mid(str_head)
    print(backTrackingStr(link_str, str_head))