动态规划

矩阵链乘法

笔记

本节给出了一个关于矩阵链相乘问题的动态规划算法。给定一个n个矩阵的矩阵链，要计算它们的乘积A1*A2*A3……An。矩阵乘法满足结合律，所以通过加括号，一个矩阵链的乘法可以按照不同的顺序进行。例如，4个矩阵的矩阵链，共有5种加括号的方式：

来自Leetcode第146题LRU缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。

来源Leetcode第134题加油站

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

来源Leetcode第133题克隆图

给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。

来自Leetcode第148题排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

来源Leetcode第150题逆波兰表达式求值

根据逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

来源Leetcode第195题第10行

给定一个文本文件 file.txt，请只打印这个文件中的第十行。

来源Leetcode第119题杨辉三角II

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
示例:

输入: 3
输出: [1,3,3,1]
进阶：

你可以优化你的算法到 O(k) 空间复杂度吗？