宫水三叶的刷题日记

题解

/ 注册

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

【宫水三叶の剑指精选】详解何为二段性丢失，以及如何恢复二段性进行二分

朴素解法一个朴素的解法是直接对数组进行线性扫描，并在遍历过程中维护一个全局最小值。代码： import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array)...

二分 Java 数组剑指Offer 二段性

2021-08-25

1 1101

【宫水三叶の剑指精选】求解最长回文子串的最优解：Manacher 算法

朴素解法这道题有一个很容易就能想到的简单做法：枚举字符串 s 中的每一位，作为回文串的中心点，左右进行扩展，直到达到边界或者不满足回文串定义为止。这样做的思路必然是正确的。但很显然这是一个朴素（暴力）做法，那么我们如何确定这一做法是否可行呢？还记得我们上一节的分析思路吗？当我们有了一个简单的...

Java 剑指Offer 回文串问题 Manacher

2021-07-26

4 985

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

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

Java 剑指Offer 哈希表摩尔投票

2021-07-26

7 935

【宫水三叶の剑指精选】一题双解 :「优先队列」&「多路归并」

基本思路根据丑数的定义，我们有如下结论：是最小的丑数。对于任意一个丑数，其与任意的质因数（、、）相乘，结果（、、）仍为丑数。优先队列（小根堆）解法有了基本的分析思路，一个简单的解法是使用优先队列：起始先将最小丑数放入队列每次从队列取出最小值，然后将所对应的丑数、...

Java 剑指Offer 数学优先队列多路归并多指针 Set

2021-07-26

5 844

【宫水三叶の剑指精选】复制带 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

【宫水三叶の剑指精选】一题四解:「位数检查」&「右移统计」&「lowbit」&「分组统计」

「位数检查」解法一个朴素的做法是，对 int 的每一位进行检查，并统计的个数。代码： public class Solution { public int NumberOf1(int n) { int ans = 0; for (int i = 0; ...

Java 剑指Offer 位运算分治

2021-07-26

9 892

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

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

Java 剑指Offer 动态规划数学

2021-07-26

36 2182

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

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

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

2021-07-05

21 2737

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

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

Java 剑指Offer 二叉树中序遍历

2021-07-03

8 844