Big-Yellow的算法工程师进阶之路

Big-Yellow / 2024-02-25 / 原文

Big-Yellow的算法工程师进阶之路

一、基础算法

二、基础数据结构

2.1 链表^[1]

2.1.1 基础理论

链表是一种以链的形式来存储数据的数据结构。链表的结构：每一个数据都与其后一个数据相连（有时候也与前一个数据相连）。链表中的每个元素都被称为一个结点, 在形状上链表就像自行车链条一样 一节接着一节
链表的优点

1、因为链表是一个链式的数据结构，你可以快速地添加和移除其中的元素。并且这也不需要像数组或者列表那样来重新组织数据。线性的数据结构用链表来实现更加容易。
2、同样因为它的链式结构，链表也不需要一个固定的或者初始的大小。

链表的缺点

1、与数组相比，链表占用更多的内存空间。这是因为你需要一个占用额外内存空间的指针来指向下一个元素。
2、在链表上执行搜索操作非常的慢。不像数组，你不能随机访问链表中的元素

链表使用

1、不知道数据列表中会有多少个元素（这是链表的一个优势 - 添加元素非常简单）。
2、不需要随机访问任何一个元素（与数组不同，你不能在链表中以一个特定的索引访问元素）。
3、要在数据列表的中间插入元素。
4、你需要以常数式时间从数据列表中插入和删除元素（与数组不同，你不需要先移动数据列表中的每一个其他元素）。

2.1.2 Python实现^[2]

只需要意识到你将要添加到链表中的每一个元素都只是一个结点（就像链条中的一环）。头结点（链表中的第一个结点）的特殊之处在于你先确定一个头结点，然后再开始向它后面添加其他结点

1、单向链表****

创建链表

创建链表

class Node:
    def __init__(self, val):
        self.val = val # 存放数据
        self.next = None # 指向下一个节点

定义链表

定义链表

class SingleLinkList(object):
    """单链表"""
    def __init__(self):
        self.head = None
    
    def is_empty(self):
        """判断链表是否为空"""
        return self.head is None
    def length(self):
        """链表长度"""
        cur = self.head
        count = 0
        while cur:
            coun +=1
            cur = self.head.next
        return count
    def item(self):
        """遍历链表"""
        cur = self.head
        while cur:
            yield cur.val
            # 指针下移
            cur = cur.next
    def add(self, val):
        """向链表头部添加节点"""
        node = Node(val)
        node.next = self.head
        self.head = node
    def append(self, val):
        """向链表尾部添加节点"""
        node = Node(val)
        if self.is_empty():
            self.head = node
        else:
            cur = self.head
            while cur.next:
                cur = cur.next
            cur.next = node
    def insert(self, index, val):
        """指定位置插入元素"""
        if index <0:
            self.add(val)
        else:
            node = Node(val)
            cur = self.head
            for i in range(index- 1):
                cur = cur.next
            node.next = cur.next
            cur.next = node
    def remove(self, val):
        """删除节点"""
        cur = self.head
        pre = None
        while cur:
            if cur.next == val:
                if not pre:
                    self.head = cur.next
                else:
                    pre.next = cur.next
                return True
            else:
                pre = cur
                cur = cur.next
        
if __name__ == '__main__':
    link_list = SingleLinkList()
    # 向链表尾部添加数据
    for i in range(5):
        link_list.append(i)
    # 向头部添加数据
    link_list.add(6)
    # 遍历链表数据
    for i in link_list.item():
        print(i, end='\t')
    # 链表数据插入数据
    link_list.insert(3, 9)
    print('\n', list(link_list.item()))
    # 删除链表数据
    link_list.remove(0)
    # 查找链表数据
    print(link_list.find(4))

三、🐉LeetCode推荐习题

1、LRU缓存

🔗题目链接：https://leetcode.cn/problems/lru-cache/description/
📃题目描述：请你设计并实现一个满足LRU (最近最少使用) 缓存约束的数据结构。实现LRUCache 类：

LRUCache(int capacity) 以正整数作为容量capacity初始化LRU缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回$-1$。
void put(int key, int value)如果关键字 key 已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字。

函数get和put必须以$O(1)$的平均时间复杂度运行。
⚙️解题思路：

问题描述

示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

Code

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data = dict()
    def get(self, key: int) -> int:
        s = self.data.get(key, -1)
        if s != -1:
            self.data.pop(key)
            self.data[key]= s
        return s
    def put(self, key: int, value: int) -> None:
        if key in self.data:
            self.data.pop(key)
            self.data[key] = value
        else:
            # 不在 data 里面的话：1、超过了容量,那么进行替代；2、没有超过容量：那么添加
            if len(self.data) < self.capacity:
                k = next(iter(self.data))
                self.data.pop(k)
                self.data[key] = value
            else:
                self.data[key] = value