LeetCode笔记 – 第 12 页 – 娄禹的个人博客

LeetCode #61：Rotate List(旋转链表)

思路不难，就是将链尾拆下来插到链首 k 次，类似于 “循环右移”。需要注意的是如果直接写循环 k 次会超时（题目中 k 的范围是 0 <= k <= 2 * 10⁹），这个时候的优化思路是统计一下链表的元素总数 count，再把循环次数设为 k 模 count，就能应对 k 很大但 count 很小的情况了（避免了大量重复的右移）。

LeetCode #53：Maximum Subarray(最大子数组和)

本题是一个经典的动态规划问题。需要注意的是解题时将 dp[i] 定义为数组 nums 中以 num[i] 结尾的最大连续子串和，最终不能直接返回 dp[n-1]，因为给定数组的最大连续子数组不一定以该数组的最后一个数结尾。这里采用一个额外的 res 变量来记录最大值。

LeetCode #146：LRU Cache(实现 LRU 缓存)

考研 OS 和计组的高频考点，当初只会纸上做题手算替换页面和 Cache，现在需要手撸代码了。由于要求 get() 和 put() 函数在 O(1) 的复杂度执行，采用 Hashmap 映射双链表结点的方法，写到一半迭代器的用法忘了还去搜了半天【cai

LeetCode #206：Reverse Linked List(反转单链表)

学过链表的应该都会写，但是这个题有个坑就是链表的头结点是存放数据的，这与大部分数据结构教材不同（我以为头结点不存放数据结果死活过不了）。和题解不同的是我手动给它安了一个不存放数据的头结点运用头插法。