Linktable-Array.py

# 4. 最长回文子串
def palindrome(s:str, left:int, right:int):
    while left>=0 and right<len(s) and s[left]==s[right]:
        left -= 1
        right += 1
    return s[left+1: right]

def longest_palindrome(s:str):
    result = ''
    for i in range(len(s)):
        pal1 = palindrome(s, i, i)
        pal2 = palindrome(s, i, i+1)
        result = pal1 if len(pal1)>len(result) else result
        result = pal2 if len(pal2)>len(result) else result
    return result


# 25-10-16 实现双链表
class Node:
    def __init__(self, x):
        self.val = x
        self.prev = None
        self.next = None

class MyLinkedList:

    def __init__(self):
        self.head = Node(None)
        self.tail = Node(None)
        self.head.next = self.tail
        self.head.prev = None
        self.tail.prev = self.head
        self.tail.next = None
        self.size = 0

    def get(self, index: int) -> int:
        if index > self.size or index < 0:
            return -1
        elif index <= self.size // 2:
            p = self.head.next  # 从实际的第一个节点开始
            for _ in range(index):
                p = p.next
        elif index > self.size // 2:
            p = self.tail.prev  # 从实际的最后一个节点开始
            for _ in range(self.size-index-1):
                p = p.prev
        return p.val

    def addAtHead(self, val: int) -> None:
        newnode = Node(val)
        newnode.next = self.head.next
        newnode.prev = self.head
        self.head.next.prev = newnode
        self.head.next = newnode
        self.size += 1

    def addAtTail(self, val: int) -> None:
        newnode = Node(val)
        newnode.next = self.tail
        newnode.prev = self.tail.next
        self.tail.prev.next = newnode
        self.tail.prev = newnode
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        p = None
        if index > self.size or index < 0:
            print('index超出链表范围')
        elif index == self.size:
            self.addAtTail(val)
        elif index == 1:
            self.addAtHead(val)
        elif index <= self.size // 2:
            p = self.head.next
            for _ in range(index-1):
                p = p.next
        else:
            p = self.tail.prev
            for _ in range(self.size - index):
                p = p.prev
        newnode = Node(val)
        newnode.next = p.next
        newnode.prev = p
        p.next.prev = newnode
        p.next = newnode
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        p = None
        if self.size < 0 or index >= self.size:
            raise  IndexError("No elements to remove")
        elif index <= self.size // 2:
            p = self.head.next
            for _ in range(index):
                p = p.next
        else:
            p = self.tail.prev
            for _ in range(self.size - index - 1):
                p = p.prev
        p.prev.next = p.next
        p.next.prev = p.prev
        p.next = None
        p.prev = None
        self.size -= 1
        


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

# 25-10-19 基于双链表实现哈希表
class Nodeh:
    """双链表节点类，存储键值对及前后指针"""
    def __init__(self, key, value):
        self.key = key          # 键
        self.value = value      # 值
        self.prev = None        # 前驱节点
        self.next = None        # 后继节点


class HashTable:
    """基于双链表的拉链法哈希表（支持负载因子监控和自动扩容）"""
    def __init__(self, initial_size=10, load_factor_threshold=0.7):
        self.size = initial_size               # 哈希表当前大小
        self.table = [None] * self.size        # 哈希表数组（存储双链表头节点）
        self.count = 0                         # 元素数量
        self.load_factor_threshold = load_factor_threshold  # 负载因子阈值（超过则扩容）

    def _hash(self, key):
        """哈希函数：计算键在当前表大小下的索引"""
        return hash(key) % self.size

    def _resize(self, new_size):
        """扩容哈希表：创建新表并重新哈希所有元素"""
        # 1. 创建新的哈希表数组
        new_table = [None] * new_size
        
        # 2. 遍历原表中的所有元素，重新哈希到新表
        for i in range(self.size):
            current = self.table[i]  # 原表第i个索引的链表头节点
            while current:
                # 保存当前节点的下一个节点（避免迁移时指针丢失）
                next_node = current.next
                
                # 计算当前节点在新表中的索引
                new_index = hash(current.key) % new_size
                
                # 将当前节点插入新表对应索引的链表头部
                # 调整新节点与新表链表的指针关系
                current.next = new_table[new_index]  # 新节点的后继指向新表链表头
                if new_table[new_index]:
                    new_table[new_index].prev = current  # 新表链表头的前驱指向新节点
                current.prev = None  # 新节点成为头节点，前驱置空
                
                # 更新新表的链表头
                new_table[new_index] = current
                
                # 处理下一个节点
                current = next_node
        
        # 3. 更新哈希表的大小和数组
        self.size = new_size
        self.table = new_table
        print(f"哈希表已扩容至大小: {self.size}")  # 调试信息

    def put(self, key, value):
        """插入或更新键值对，自动检查并触发扩容"""
        index = self._hash(key)
        head = self.table[index]
        
        # 1. 查找是否已存在该键，存在则更新值（不改变元素数量，无需扩容）
        current = head
        while current:
            if current.key == key:
                current.value = value
                return
            current = current.next
        
        # 2. 不存在则插入新节点（插入到链表头部）
        new_node = Nodeh(key, value)
        new_node.next = head  # 新节点的后继指向原头节点
        if head:
            head.prev = new_node  # 原头节点的前驱指向新节点
        self.table[index] = new_node  # 更新链表头为新节点
        self.count += 1  # 元素数量+1
        
        # 3. 检查负载因子，超过阈值则扩容（新大小为原大小的2倍）
        current_load_factor = self.count / self.size
        if current_load_factor > self.load_factor_threshold:
            self._resize(self.size * 2)

    def get(self, key):
        """查找键对应的值，不存在返回None"""
        index = self._hash(key)
        current = self.table[index]
        
        while current:
            if current.key == key:
                return current.value
            current = current.next
        return None

    def remove(self, key):
        """删除指定键，成功返回True，失败返回False"""
        index = self._hash(key)
        current = self.table[index]
        
        while current:
            if current.key == key:
                # 调整前后节点的指针关系
                prev_node = current.prev
                next_node = current.next
                
                if prev_node:
                    prev_node.next = next_node
                else:
                    # 当前节点是头节点，更新链表头
                    self.table[index] = next_node
                if next_node:
                    next_node.prev = prev_node
                
                self.count -= 1
                if self.count == self.size//8:
                    self._resize(self.size//4)
                return True
            current = current.next
        return False

    def __str__(self):
        """打印哈希表内容（包含大小和元素数量）"""
        result = [f"哈希表（大小: {self.size}, 元素数量: {self.count}, 负载因子: {self.count/self.size:.2f}）:"]
        for i in range(self.size):
            nodes = []
            current = self.table[i]
            while current:
                nodes.append(f"{current.key}:{current.value}")
                current = current.next
            if nodes:
                result.append(f"  索引{i}: [{', '.join(nodes)}]")
        return "\n".join(result)