摸鱼学大师

题解

未归档(8)

/ 注册

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

题解 | #最长无重复子数组# 来自专栏

题目主要信息: 题目给定一个数组，要找到其中最长的无重复的子数组的长度子数组必须是数组中连续的一段具体思路: 既然要找一段连续子数组的内不重复的长度，我们可以使用滑动窗口，窗口内都是不重复的，然后窗口右界不断向右滑，如果窗口内出现了重复数组，说明新加入的元素与之前的重复了，只需要窗口左界也向...

C++ 哈希表双指针

2022-02-01

0 365

题解 | #缺失的第一个正整数# 来自专栏

题目主要信息: 题目给定一个无序整型数组，没有重复元素，可能有负数或零，需要找出其中没有出现的最小正整数具体思路: n个长度的数组，没有重复，则如果数组填满了1～n，那么缺失n+1，如果数组填不满1～n，那么缺失的就是1～n中的数字。对于这种快速查询某个元素是否出现过的问题，还是可以使用哈希表...

C++ 哈希表

2022-02-01

0 442

题解 | #数组中只出现一次的两个数字# 来自专栏

题目主要信息: 题目给定一个整型数组，其中有两个数字只出现了1次，其余数字都出现了两次，需要找到这两个数字输出按照非降序排列具体思路: 既然要找出唯二出现次数为1的两个数字，那我们可以直接统计数组中各个数字出现的次数，然后找出次数为1的两个就可以了。 step 1：用unordered_m...

C++ 哈希表

2022-02-01

0 415

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

题目主要信息: 题目要求为找到给定字符串数组中出现次数前k的字符串，按照出现频率由高到低排序输出，相同频率按照字典序字符串的字符仅包含数字字母具体思路: 很明显，这道题有两个要解决的问题，一个是统计各个字符串的出现频次，一个是找到出现次数前k的字符串然后输出。对于第一个问题，统计频次可以使...

C++ 哈希表优先队列

2022-02-01

0 504

题解 | #数组中出现次数超过一半的数字# 来自专栏

题目主要信息: 题目给出一个长度为n的数组，其中有一个数字出现次数超过了数组长度的一半，需要我们找出这个数字输入数组非空，保证有解，这样就不用考虑特殊情况具体思路: 首先我们分析一下，数组某个元素出现次数超过了数组长度的一半，那它肯定出现最多，而且只要超过了一半，其他数字不可能超过一半了，必...

C++ 哈希表

2022-02-01

0 402

题解 | #两数之和# 来自专栏

题目主要信息: 题目给出的是一个数组和一个目标值，需要我们在数组中找到两个加起来等于目标值的数组元素的下标下标按升序排列，从1开始具体思路: 我们能想到最直观的解法，可能就是两层遍历，将数组所有的二元组合枚举一遍，看看是否是和为目标值，但是这样太费时间了，既然加法这么复杂，我们是不是可以尝试...

C++ 哈希表

2022-02-01

0 513

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

题目主要信息：在S字符串中找到包含T字符串所有字符的最小连续子串两个字符串仅包含大小写字母如果S中没有包含T中所有字符的子串，返回空字符串""，若有，则存在唯一最短具体思路： step 1：字符串仅包含大小写字母，则字符集是已知且有限的，那这种情况下我们可以考虑使用哈希表——只需要维护...

C++ 哈希表

2022-01-28

0 0

题解 | #最小生成树# 来自专栏

题目的主要信息： n个节点，m条边，边权记录在邻接表cost中求最小生成树的总边权方法一：kruskal算法+并查集具体做法：最小生成树，我们可以连通的点看成是同一个并查集，利用并查集的思想来逐渐加边使所有节点连在一起。同时，最小生成树需要用kruskal算法的贪心思想，先对邻接表按照边...

C++ 并查集 prim算法 Kruskal算法

2021-12-09

18 883

题解 | #单源最短路# 来自专栏

题目的主要信息：在一个有 n 个点， m 个边的有向图中，已知每条边长，求出 1 到 n 的最短路径如果 1 无法到 n ，输出 -1 图没有自环，可能有重边方法一：floyd算法具体做法：可以用floyd算法计算任意两个节点之间的最短路径，然后取1-n的即可。用矩阵w表示任意两个节点...

C++ 图

2021-12-09

3 550

题解 | #单调栈# 来自专栏

题目的主要信息：给定一个长度为 n 的可能含有重复值的数组 arr ，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置结果返回一个二维数组，表示所有位置相应的信息，如果找不到位置，则相应地方为-1 下标0开始进阶要求：空间复杂度 O(n)O(n)O(n) ，时间复...

C++ 栈

2021-12-09

2 455