第一题：LRU缓存机制
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
利用单链表的方式：
public class LRUCache
{
private readonly int _length;
private readonly List<KeyValuePair<int, int>> _lst;
public LRUCache(int capacity)
{
_length = capacity;
_lst = new List<KeyValuePair<int, int>>();
}
private int GetIndex(int key)
{
for (int i=0,len=_lst.Count;i<len;i++)
{
if (_lst[i].Key == key)
{
return i;
}
}
return -1;
}
public int Get(int key)
{
int index = GetIndex(key);
if (index!=-1)
{
int val = _lst[index].Value;
_lst.RemoveAt(index);
_lst.Add(new KeyValuePair<int, int>(key, val));
return val;
}
return -1;
}
public void Put(int key, int value)
{
int index = GetIndex(key);
if (index!=-1)
{
_lst.RemoveAt(index);
}
else if (_lst.Count == _length)
{
_lst.RemoveAt(0);
}
_lst.Add(new KeyValuePair<int, int>(key, value));
}
}
第二题：排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
public class Solution
{
public ListNode SortList(ListNode head)
{
if (head == null)
return null;
return MergeSort(head);
}
private ListNode MergeSort(ListNode node)
{
if (node.next == null)
{
return node;
}
ListNode p1 = node;
ListNode p2 = node;
ListNode cut = null;
while (p1 != null && p1.next != null)
{
cut = p2;
p2 = p2.next;
p1 = p1.next.next;
}
cut.next = null;
ListNode l1 = MergeSort(node);
ListNode l2 = MergeSort(p2);
return MergeTwoLists(l1, l2);
}
private ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
ListNode pHead = new ListNode(-1);
ListNode temp = pHead;
while (l1 != null && l2 != null)
{
if (l1.val < l2.val)
{
temp.next = l1;
l1 = l1.next;
}
else
{
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}
if (l1 != null)
temp.next = l1;
if (l2 != null)
temp.next = l2;
return pHead.next;
}
}
第三题：最小栈
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
public class MinStack
{
/** initialize your data structure here. */
private readonly IList<int> _lst;
public MinStack()
{
_lst = new List<int>();
}
public void Push(int x)
{
_lst.Add(x);
}
public void Pop()
{
_lst.RemoveAt(_lst.Count - 1);
}
public int Top()
{
return _lst[_lst.Count - 1];
}
public int GetMin()
{
return _lst.Min();
}
}
