心空之上

分类

/ 注册

全部文章（共68篇）

题解 | #设计LFU缓存结构#

基本思路题目要求在缓存满时移除调用次数最少的key，并且在调用次数相同时移除最早进入的key，那么移除调用次数最少的key可以用一个最小频率minFreq来记录，移除最早进入的key就需要一个双向链表维护，每次进行查询或插入操作时都将该节点更新到链表头部，这样链表尾部存放的就是最早进入的key了。所...

2023-08-29

0 380

题解 | #设计LRU缓存结构#

基本思路使用HashMap作为缓存，key就是传进来的key，但是value需要包装成一个双向链表的节点，通过双向链表连接HashMap中所有Entry的value，双向链表的头部节点表示最近使用的节点，尾部节点表示最近最少使用的节点，因此缓存满时移除的是尾部节点。双向链表中的节点也需要保存key，...

2023-08-28

0 343

题解 | #螺旋矩阵#

基本思路螺旋矩阵每次遍历一个边界，因此可以设置上下左右四个边界，表示当前可以遍历边界，然后遍历顺序为上边界的左到右遍历，右边界的上到下遍历，下边界的右到左遍历，左边界的下到上遍历，每遍历完一个边界就往里移动边界，表示下一次可以遍历的边界，并判断边界是否合法，当上边界超过下边界，以及左边界超过右边界时...

2023-08-27

0 294

题解 | #顺时针旋转矩阵#

基本思路顺时针旋转矩阵后，第一行变成最后一列，最后一行变成第一列，可以创建一个新的数组，然后遍历原数组中的每行放到新数组的对应列中，最后返回新的数组，这样空间复杂度是O(n^2)。或者观察顺时针旋转矩阵的规律，发现顺时针旋转矩阵就是矩阵转置后再将每行逆序得到的，而矩阵转置就是对角线元素互换，因此可以...

2023-08-27

0 298

题解 | #旋转数组#

基本思路将数组的循环往后移动m个位置，需要注意m可能比n大，所以要m对n取余得到最终需要旋转的数量，然后进行三次数组逆序操作，第一次将数组整体倒序，实现数组右边的元素跑到左边，第二次将数组前m个元素倒序，实现前m个元素跟原来的顺序相同，第三次将数组后n-m个元素倒序，实现后n-m个元素跟原来的顺序相...

2023-08-25

0 356

题解 | #删除有序链表中重复的元素-II#

基本思路要设置一个表头作为前置节点，然后比较前置节点后面的两个节点值是否相等，如果相等就连续去掉这些相等节点，使前置节点的下一个节点为下一次要比较的节点，如果后面两个节点值不相等，就更新前置节点为当前节点，下一次比较就从当前节点的后两个节点开始。参考参考题解 import java.util.*; ...

2023-08-25

0 355

题解 | #判断一个链表是否为回文结构#

基本思路一个链表是回文的说明从前往后遍历链表和从后往前遍历链表的结果是相同的，但是要实现从后往前遍历链表就需要新建一个反转链表存放原链表的所有节点，所以还是需要先遍历一遍原链表，将里面的节点取出，那这样的话直接将链表中的节点取出放到数组后，用双指针从前往后和从后往前遍历数组就更方便了，不需要新建一个...

2023-08-25

0 302

题解 | #链表相加(二)#

基本思路两个数相加需要从后往前相加再进位，但是单向链表很难从后往前相加，因此可以将两个链表反转后从前往后相加，就相当于反转前从后往前相加，遍历时遇到空指针时则将该节点记录为0，这样保证较长的链表没遍历完时还可以处理加法逻辑，如果两个链表都记录完后，还有进位，就还需要创建节点存储进位。结果链表采用头插...

2023-08-25

0 285

题解 | #两个链表的第一个公共结点#

基本思路题目要找的公共节点是指两个链表中节点引用相同的节点，而不是节点值相同的节点，因此我们要比较的是两个链表的节点引用是否相等来判断是否有公共节点。由于两个链表长度不一致，一般需要先将长链表遍历到剩余长度和短链表相同的长度再逐个比较，但是可以将两个链表拼接起来循环遍历，如果链表A遍历结束后就遍历链...

2023-08-24

0 390

题解 | #链表中倒数最后k个结点#

基本思路慢指针停在链表开头，先让快指针走k个节点判断链表长度是否达到k，如果链表长度大于k，则慢指针从开头和快指针同时遍历链表，因为快指针始终比慢指针多k个节点，所以当快指针达到链表末尾时，慢指针的位置就是链表倒数第k个节点。参考参考题解 import java.util.*; /* * pub...

2023-08-24

0 320