宫水三叶的刷题日记

题解

/ 注册

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

【宫水三叶の真题精选】涵盖所有的「存图方式」与「最短路算法（详尽注释）」

基本分析为了方便，我们约定为点数，为边数。根据题意，首先的数据范围只有，的数据范围为，使用「邻接表」或「邻接矩阵」来存图都可以。存图方式在开始讲解最短路之前，我们先来学习三种「存图」方式。邻接矩阵这是一种使用二维矩阵来进行存图的方式。适用于边数较多的稠密图使用，当边数...

Java 图论 spfa Dijkstra 最短路链式前向星邻接矩阵邻接表

2021-09-06

20 1449

【宫水三叶の真题精选】一题四解 :「优先队列（堆）」&「全排序」&「数组划分」

优先队列（小根堆）一个直观的想法是使用「优先队列（小根堆）」，起始将所有元素放入堆中，然后再从堆中取出个元素并「顺序」构造答案。代码： import java.util.*; public class Solution { public ArrayList<Integer>...

优先队列堆全排序快速排序

2021-09-06

2 590

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

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

Java 链表模拟原地算法

2021-09-06

1 637

【宫水三叶の真题精选】一题四解 :「动态规划」&「打表」&「矩阵快速幂」

递推实现动态规划既然转移方程都给出了，直接根据转移方程从头到尾递递推一遍即可。代码： public class Solution { public int Fibonacci(int n) { if (n <= 1) return n; int a ...

Java 动态规划记忆化搜索打表矩阵快速幂

2021-09-06

2 545

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

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

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

2021-09-02

4 704

【宫水三叶の真题精选】利用二段性进行二分找分割点

朴素做法一个朴素的做法，从前往后进行处理，直到遇到符合条件的位置。代码： import java.util.*; public class Solution { public int search (int[] nums, int target) { int n = n...

Java 二分数组

2021-08-27

3 1200

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

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

Java 链表模拟哨兵

2021-08-27

11 816

【宫水三叶の真题精选】经典数据结构运用题（附进阶两问）

数据结构运用这是一道经典的数据结构运用题。具体的，我们可以使用两个优先队列（堆）来维护整个数据流数据，令维护数据流左半边数据的优先队列（堆）为 l，维护数据流右半边数据的优先队列（堆）为 r。显然，**为了可以在的复杂度内取得当前中位数，我们应当令 l 为大根堆，r 为小根堆，并人为固定 ...

Java 堆优先队列数据结构运用

2021-08-27

1 494

【宫水三叶の真题精选】详解动态规划解法

动态规划整理一下题意，对于字符串 p 而言，有三种字符：普通字符：需要和 s 中同一位置的字符完全匹配 '?'：能够匹配 s 中同一位置的任意字符 '*'：能够匹配任意字符串所以本题关键是分析当出现 '*' 这种字符时，是匹配 0 个字符、还是 1 个字符、还是 2 个字符 ... ...

Java 动态规划线性DP

2021-08-26

4 807

【宫水三叶の真题精选】一题四解：朴素解法 & 预处理最值 & 单调栈 & 面积差

朴素解法对于每根柱子而言，我们只需要找出「其左边最高的柱子」和「其右边最高的柱子」。对左右的最高柱子取一个最小值，再和当前柱子的高度做一个比较，即可得出当前位置可以接下的雨水。同时，边缘的柱子不可能接到雨水（某一侧没有柱子）。这样的做法属于「暴力做法」，但题目没有给数据范围，我们无法分析到底...

Java 单调栈

2021-08-26

8 749