宫水三叶的刷题日记

题解

/ 注册

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

【宫水三叶の剑指精选】一题双解 : 简单题学摩尔投票（一道容易被拓展空间优化简单题）

基本分析为了让解法更具有「通用性」，我们可以考虑添加一个额外条件：数组中不一定存在「出现次数超过一半的数字」，如果不存在的话返回。这也是在面试过程中，很容易被拓展的一个点。哈希表一个朴素的做法是使用哈希表进行计数，如果发现某个元素数量超过总数一半，说明找到了答案。代码： import ...

Java 剑指Offer 哈希表摩尔投票

2021-07-26

7 935

【宫水三叶の剑指精选】复制带 random 指针链表的两种方式 :「哈希表」&「原地算法」

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

Java 剑指Offer 单链表哈希表原地算法

2021-07-26

18 1081

【宫水三叶の剑指精选】一题五解 :「朴素解法」&「栈解法」&「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