摸鱼学大师

题解

未归档(8)

/ 注册

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

题解 | #最长路径# 来自专栏

思路：题目的主要信息： n个节点，n-1条边，使之全部连通，这就是一棵树树中任意节点的路径最长值，就是求树的直径首先我们要知道一个性质：从树的根节点深度优先搜索到最远距离，再从最远距离深度优先搜索到另一最远距离就是树的直径。方法一：两次深度优先搜索具体做法：我们需要用哈希表来存储树的边结...

最长路径树的直径 dfs bfs 递归队列哈希表

2021-08-06

0 687

题解 | #那些插队的人# 来自专栏

思路：题目的主要信息：长度为n为队伍，人员编号1-n cutIn数组中是要插队的编号，依次进行插队，即加入到最前面求最后有多少人不在原来的位置方法一：哈希表具体做法：对于最后的队列，没有插过队的人肯定都排在后面，最大插队元素是其分界线，最大插队元素之前的位置都可能有改变，之后的就不会有变...

插队数组数学模拟哈希表

2021-07-30

0 439

题解 | #加起来和为目标值的组合# 来自专栏

思路：题目的主要信息：从数组num找出所有加起来等于target的组合每个组合num中每个元素只能用1次返回的值必须是非递减次序，组合不能重复方法一：递归+枝剪具体做法：对于排序后的num数组中第一个元素，我们可以考虑如果它比target大，那么后续都会比target大，没有加起来等于...

回溯递归枝剪哈希表数组

2021-07-28

0 1310

题解 | #最小覆盖子串# 来自专栏

思路：题目的主要信息：在S字符串中找到包含T字符串所有字符的最小字串要求时间复杂度如果S中没有包含T中所有字符的子串，返回空字符串""，若有有则存在唯一最短方法一：滑动窗口+哈希表+双指针具体做法：维护一个哈希表，里面是字符串T的字符为key值，初始时当字符在T...

滑动窗口哈希表字符串字串双指针

2021-07-28

0 624

题解 | #数组中只出现一次的数（其它数出现k次）# 来自专栏

思路：题目的主要信息：数组有n个无序数字，其中有一个数字只出现了1次，其他数字都出现了k次需要找到只出现了一次的数字 k>1，k无特殊情况，只需要考虑空数组方法一：排序法具体做法：首先对数字进行排序，使之呈现递增的状态，这样相同的数字必然相邻。因为其他数字至少出现大于1次，因此首尾...

数组哈希表位运算排序

2021-07-28

0 905

题解 | #树的直径# 来自专栏

思路：题目的主要信息：要求树的直径，即树上两点最远距离这里的树不止是二叉树，都有可能题目给的Tree_edge是一个点到另一个点有边，Edge_value为与之对应的边的权重weigh 方法一：两次深度优先搜索首先我们要知道一个性质：从树的根节点深度优先搜索到最远距离，再从最远距离深度...

树的直径递归队列 dfs bfs 哈希表邻接矩阵

2021-07-18

1 776

题解 | #字符串出现次数的TopK问题# 来自专栏

思路：题目的主要信息：需要统计字符串出现的频率最大复杂度为O(nlgk) 选出频率前K，相同频率算字典序最小方法一：排序法使用先统计次数，再排序，再找出前k的策略，但是不符合题目要求！！！！不符合规定复杂度分析：时间复杂度：O(nlgn)，排序算法最快O(nlgn)，遍历前k个...

哈希表字符串堆排序

2021-07-18

0 590

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

思路：题目的主要信息：数组无序，且有重复需要找连续最长子序列长度，且连续不必相邻方法一：排序法既然无序我们可以用排序来解决。具体做法：使用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