宫水三叶的刷题日记

题解

/ 注册

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

【宫水三叶の剑指精选】如何利用的「等差」性质降低「正则字符串匹配」算法复杂度（类比完全背包一维优化方式）

动态规划为了方便，使用 ss 代指 str，使用 pp 代指 pattern。整理一下题意，对于字符串 p 而言，有三种字符：普通字符：需要和 s 中同一位置的字符完全匹配 '.'：能够匹配 s 中同一位置的任意字符 '*'：不能够单独使用 '*'，必须和前一个字符同时搭配使用，数据保证了 ...

Java 剑指Offer 动态规划数学

2021-07-26

36 2182

【宫水三叶の真题精选】使用「双栈」解决「究极表达式计算」问题（含拓展）

【本题】双栈解法对于「任何表达式」而言，我们都使用两个栈 nums 和 ops： nums ：存放所有的数字 ops ：存放所有的数字以外的操作然后从前往后做，对遍历到的字符做分情况讨论：空格 : 跳过 ( : 直接加入 ops 中，等待与之匹配的 ) ) : 使用现有的 nums 和...

Java 栈表达式求值表达式计算问题逆波兰表达式

2021-07-07

108 7854

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

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

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

2021-07-07

4 1031

【宫水三叶の剑指精选】从更深的角度看待「对称二叉树」问题

基本思想首先要明确，题目所定义的 “对称” 是对每层而言，同时考虑空节点。因此，如果我们使用常规的遍历方式进行检查的话，需要对空节点有所表示。局部检查（层序遍历）我们使用 0x3f3f3f3f 作为无效值，并建立占位节点 emptyNode 用来代指空节点（emptyNode.val = ...

Java 递归层序遍历剑指Offer 二叉树

2021-07-05

21 2737

【宫水三叶の真题精选】详解「层序遍历」实现「序列化二叉树」

基本思路无论使用何种「遍历方式」进行二叉树存储，为了方便，我们都需要对空节点有所表示。其实题目本身的样例就给我们提供了很好的思路：使用层序遍历的方式进行存储，对于某个叶子节点的空节点进行存储，同时确保不递归存储空节点对应的子节点。层序遍历我们使用 0x3f3f3f3f 作为无效值（当然也可...

Java 层序遍历二叉树序列化二叉树

2021-07-04

36 3512

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

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

Java 链表双向链表 LRU 哈希表

2021-07-03

26 2834

【宫水三叶の剑指精选】详解「二叉树中序遍历的下一个结点」两种解法

朴素解法一个朴素的做法是，根据题目对于 TreeLinkNode 的定义，利用 next 属性存储「当前节点的父节点」这一特点。从入参节点 pNode 出发，不断利用 next 属性往上查找，直到找到整棵树的头节点，令头节点为 root。然后实现二叉树的「中序遍历」，将遍历过程中访问的节点存放...

Java 剑指Offer 二叉树中序遍历

2021-07-03

8 844

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

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

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

2021-07-01

31 2733