本文共 3820 字，大约阅读时间需要 12 分钟。

题目描述

链表排序，要求时间复杂度O(nlogn)，空间复杂度O(1)

例子

Example 1:

Input: 4->2->1->3

Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0

Output: -1->0->3->4->5

思想

联想几个时间复杂度O(nlogn)的排序：堆排序（麻烦），快排（要移位，还要交换），归并排序（找中点，可以用快慢指针找中点）

解法

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):    def sortList(self, head):        """        :type head: ListNode        :rtype: ListNode        """        if not head or not head.next:            return head        fast = slow = pre = head        while fast and fast.next:    # Mark: pre            pre = slow            slow = slow.next            fast = fast.next.next        pre.next = None                left = self.sortList(head)        right = self.sortList(slow)        return self.merge(left, right)            def merge(self, left, right):        dummy = ListNode(-1)        p = dummy        while left and right:            if left.val < right.val:                p.next = left                left = left.next            else:                p.next = right                right = right.next            p = p.next        if left:            p.next = left        else:            p.next = right        return dummy.next

题目描述

设计一种LRU的数据结构，支持下面两个操作：get和put。

get(key) - 如果key在缓存中，返回key对应的value(总是正数)，否则返回-1

put(key, value) - 设置值；如果key不存在，插入值。当缓存达到容量时，它应该在插入新项前使最近最少使用的项无效。

最好O(1)的时间复杂度

如果一个数据长时间没有使用，且又有新的数据加入，那么应该将最长时间没有使用的数据去除

例子

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);

cache.put(2, 2);

cache.get(1); // returns 1

cache.put(3, 3); // evicts key 2

cache.get(2); // returns -1 (not found)

cache.put(4, 4); // evicts key 1

cache.get(1); // returns -1 (not found)

cache.get(3); // returns 3

cache.get(4); // returns 4

思想

首先，涉及查询，考虑用字典来存储。 难点 - 如何找到哪个节点最久没被使用？ 定义一个双向链表，尾部的节点最久没被使用。每次访问某节点时，删除该节点，并把该节点放在头部。

注意双向链表的head和tail没有数据。

解法

双向链表的插入和删除

class LRUCache(object):    class Node(object):        def __init__(self, key, value):            self.key = key            self.value = value            self.next, self.prev = None, None    def __init__(self, capacity):        """        :type capacity: int        """        self.capacity = capacity        self.size = 0        self.dic = {
   }    # self.dic[key] = Node(key, value)        self.head, self.tail = self.Node(-1,-1) , self.Node(-1,-1)        self.head.next, self.tail.prev = self.tail, self.head        def removeNode(self, node):        node.prev.next = node.next        node.next.prev = node.prev        node.prev, node.next = None, None            def insertNode(self, node):        node.prev = self.head        node.next = self.head.next        self.head.next.prev, self.head.next = node, node    def get(self, key):        """        :type key: int        :rtype: int        """        if key not in self.dic:            return -1        else:            node = self.dic[key]            self.removeNode(node)            self.insertNode(node)            return node.value    def put(self, key, value):        """        :type key: int        :type value: int        :rtype: void        """        if key in self.dic:            node = self.dic[key]            self.removeNode(node)            self.insertNode(node)            node.value = value        else:            # Remove the tailest node            if self.size == self.capacity:                remove = self.tail.prev                self.removeNode(remove)                del self.dic[remove.key]                self.size -= 1            # Insert the headest node            node = self.Node(key, value)            self.insertNode(node)            self.dic[key] = node            self.size += 1            # Your LRUCache object will be instantiated and called as such:# obj = LRUCache(capacity)# param_1 = obj.get(key)# obj.put(key,value)

转载地址：http://vzkfb.baihongyu.com/