路漫漫其修远兮
吾将上下而求索

算法学习:链表

输入一个链表,从尾到头打印链表的值

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def printListFromTailToHead(self, listNode):
        answer = []
        head = listNode
        while head:
            answer.append(head.val)
            head = head.next
        return answer[::-1]


if __name__ == "__main__":
    a = ListNode("a")
    b = ListNode("b")
    c = ListNode("c")
    a.next = b
    b.next = c

    f = Solution()
    print(f.printListFromTailToHead(a))

删除节点:双指针法

https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/solution/mian-shi-ti-18-shan-chu-lian-biao-de-jie-dian-sh-2/

用数组和链表实现HashMap

python语言中的dict底层是基于hashmap结构实现的,hashmap可以在一堆数据中,很快的根据key,找到value,这个关键点主要是由hash函数实现的。

class MyHash(object):

    def __init__(self, length=10):
        self.length = length
        self.items = [[] for i in range(self.length)]

    def hash(self, key):
        """计算该key在items哪个list中,针对不同类型的key需重新实现"""
        return key % self.length

    def equals(self, key1, key2):
        """比较两个key是否相等,针对不同类型的key需重新实现"""
        return key1 == key2

    def insert(self, key, value):
        index = self.hash(key)
        if self.items[index]:
            for item in self.items[index]:
                if self.equals(key, item[0]):
                    # 添加时若有已存在的key,则先删除再添加(更新value)
                    self.items[index].remove(item)
                    break
        self.items[index].append((key, value))
        return True

    def get(self, key):
        index = self.hash(key)
        if self.items[index]:
            for item in self.items[index]:
                if self.equals(key, item[0]):
                    return item[1]
        # 找不到key,则抛出KeyError异常
        raise KeyError

    def __setitem__(self, key, value):
        """支持以 myhash[1] = 30000 方式添加"""
        return self.insert(key, value)

    def __getitem__(self, key):
        """支持以 myhash[1] 方式读取"""    
        return self.get(key)


myhash = MyHash()
myhash[1] = 30000
myhash.insert(2, 2100)
print myhash.get(1)
myhash.insert(1, 3)
print myhash.get(2)
print myhash.get(1)
print myhash[1]

未经允许不得转载:江哥架构师笔记 » 算法学习:链表

分享到:更多 ()

评论 抢沙发

评论前必须登录!