摸鱼学大师

题解

未归档(8)

/ 注册

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

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

思路：题目的主要信息：链表至少为1，不用担心为空判断单链表中的数值是否是回文因为比较回文的基本思路是最前和最后比较，然后依次向中间靠齐，但是这是一个单链表，无法向前，所以我们要用另外的方法使它逆序。方法一：中点逆链表法具体做法：找到链表长度，然后找到链表中间结点，从中间结点开始往后...

链表双指针回文栈

2021-07-18

0 554

题解 | #数组中的最长连续子序列# 来自专栏

思路：题目的主要信息：数组无序，且有重复需要找连续最长子序列长度，且连续不必相邻方法一：排序法既然无序我们可以用排序来解决。具体做法：使用sort的快排，将序列排成递增序列。然后遍历数组，依次将其与前一个数比较，若是比前一个大1，则连续子序列增加1；若是与前一个一样大，需要不管直接...

哈希表数组子序列排序

2021-07-18

1 684

题解 | #LFU缓存结构设计# 来自专栏

思路：题目的主要信息：实现LFU的set与get函数，且复杂度为O(1) 每次调用这两个函数会给一个频率赋值，超出长度则移除频率最少的，若有频率相同，则移除访问时间最早的方法一：平衡二叉树+哈希表哈希表有非常好的之间访问，可以达成O(1)，而经过算术符号重载后的平衡二叉树，能够找到最近最...

哈希表模拟 LFU 平衡二叉树

2021-07-18

0 857

题解 | #设计LRU缓存结构# 来自专栏

思路：题目的主要信息：实现LRU缓存的模拟结构，包括加入函数set，访问函数get 结构有长度限制，加入新数时，超出长度则需要删除最不常访问的，其中set与get都访问两个函数都是O(1) 方法一：构建双向链表插入与访问值都是O(1)，没有任何一种数据结构可以做到。于是我们可以想到数据...

LRU 模拟双向链表哈希表

2021-07-18

5 1683

题解 | #最长公共子序列-II# 来自专栏

思路：题目的主要信息：仅存在一个最长公共子序列，不需要去重最长公共子序列为空需要返回"-1"，而不是空序列，最后要变换我们以dp[i][j]表示在s1中以i结尾，s2中以j结尾的字符串的最长公共子序列长度，若是i与j相等，则该问题可以变成1+dp[i][j]，即最长公...

动态规划字符串公共子序列递归栈

2021-07-18

1 1320

题解 | #最长递增子序列# 来自专栏

思路：先找最长递增子序列长度再根据长度逆向得到序列（逆向的原因是字典序更小，若是小值跑到后面去的情况，同样长度大值跑后面只会增加子序列长度）要找到最长的递增子序列长度，常用方法是动态规划，dp[i]表示到元素i结尾时，最长的子序列的长度，初始化全部为1。方法一：暴力动态规划（超时）具...

动态规划二分法子序列数组

2021-07-17

1 1184

题解 | #包含min函数的栈# 来自专栏

思路：题目中的要求：实现栈的push、pop、top、min函数访问每个函数的时间复杂度为O(1) 我们都知道栈结构的push、pop、top操作都是O(1)，但是min函数做不到，于是想到在push的时候将最小值记录下来，由于栈先进后出的特殊性，只能同样用栈来记录最小值。方法：双栈法 ...

栈

2021-07-17

2 566

题解 | #字符串变形# 来自专栏

思路：题目的要求：限制时间为O(n) 将字符串大小写反转，这个遍历字符串即可，也在O(n)以内反转单词的位置方法一：双逆转具体做法：第一次反转整个字符串，这样基本的单词逆序就有了，但是每个单词的字符也是逆的第二次遍历字符串的同时反转每个单词 class Solution { ...

字符串逆序栈反转线性时间

2021-07-16

2 779

题解 | #寻找第K大# 来自专栏

思路：题目中给到的信息：利用快速排序的思想有重复数字，不用去重，也不用管稳定性与否方法一：重载sort 因为sort使用的是快速排序，因此这种方法勉强算是利用了快排思想。这次要寻找第K大，sort函数默认递增，因此需要将其重载为递减，然后遍历到第k个。 class Solution {...

快速排序递归二分法

2021-07-16

14 1487

题解 | #丢棋子问题# 来自专栏

思路：题目中给到的信息：第0层不会碎某层没有碎，下面的必然不会碎；某层碎了，上面的必然碎要求最坏情况方法一：暴力递归（超时）设count(n,k)计算的是n层楼时且有k个棋子，在最差的情况下需要仍的最少次数。当k=0时，没有棋子，不用仍当n=0时，棋子肯定不会碎，所以count...

丢棋子动态规划递归

2021-07-16

1 668