宫水三叶的刷题日记

题解

/ 注册

全部文章 / 题解（共7篇）

【宫水三叶の真题精选】一题双解：「哈希表」&「原地算法」

模拟 + 哈希表如果不考虑 random 指针的话，对一条链表进行拷贝，我们只需要使用两个指针：一个用于遍历原链表，一个用于构造新链表（始终指向新链表的尾部）即可。这一步操作可看做是「创建节点 + 构建 next 指针关系」。现在在此基础上增加一个 random 指针，我们可以将 next 指针...

Java 链表模拟原地算法

2021-09-06

1 825

【宫水三叶の剑指精选】一题三解 :「栈/队列」&「差值法」&「快慢指针」

栈/队列解法一个使用额外空间的解法是利用栈（队列），将所有的节点压入占中栈（队列）中，令当前栈（队列）容量为。然后从栈顶（队列头）弹出个（个）元素，最后一个出栈（出队列）的元素即是答案。代码（栈）： import java.util.*; public class Solution...

链表 Java 快慢指针栈队列数学

2021-09-02

4 918

【宫水三叶の真题精选】链表模拟题（含哨兵技巧运用）

朴素解法（哨兵技巧）这是道模拟题，模拟人工竖式做加法的过程：从最低位至最高位，逐位相加，如果和大于等于 10，则保留个位数字，同时向前一位进 1 如果最高位有进位，则需在最前面补 1。做有关链表的题目，有个常用技巧：添加一个虚拟头结点（哨兵），帮助简化边界情况的判断。一些细节：由于给定的两...

Java 链表模拟哨兵

2021-08-27

11 987

【宫水三叶の剑指精选】一题五解 :「朴素解法」&「栈解法」&「Set 解法」&「差值法」&「等值法」

朴素解法一个朴素的解法自然是两层枚举，逐个检查哪个节点相同。代码： public class Solution { public ListNode FindFirstCommonNode(ListNode a, ListNode b) { for (ListNode h1...

Java 单链表链表栈 Set 哈希表数学剑指Offer

2021-07-26

41 2184

【宫水三叶の真题精选】运用「桶排序」& 手写「双向链表」实现严格 O(1) 的 LFUCache

基本分析前两天我们刚讲过 NC 93 设计LRU缓存结构，简单理解 LRU 就是「移除最久不被使用的元素」。因此对于 LRU 我们只需要在使用「哈希表」的同时，维护一个「双向链表」即可：每次发生 get 或 put 的时候就将元素存放双向链表头部当需要移除元素时，则从双向链表尾部开始移除 ...

Java 链表双向链表哈希表数据结构 LFU

2021-07-07

4 1031

【宫水三叶の真题精选】使用「哈希表」+「双向链表」实现 LRUCache

基本分析 LRU 是一种十分常见的页面置换算法。将 LRU 翻译成大白话就是：当不得不淘汰某些数据时（通常是容量已满），选择最久未被使用的数据进行淘汰。题目让我们实现一个容量固定的 LRUCache 。如果插入数据时，发现容器已满时，则先按照 LRU 规则淘汰一个数据，再将新数据插入，其中「插入...

Java 链表双向链表 LRU 哈希表

2021-07-03

26 2834

【剑指の精选】详解「删除链表中重复结点」的两种解法

迭代解法首先一个比较「直观且通用」的思路是，采用「边遍历边构造」的方式：建一个「虚拟头节点」dummy 以减少边界判断，往后的答案链表会接在 dummy 后面；使用 tail 代表当前有效链表的结尾；通过原输入的 pHead 指针进行链表扫描。对原链表进行遍历，只要原链表尚未到达结尾，...

Java 递归剑指Offer 单链表迭代链表

2021-07-01

31 2733