摸鱼学大师

题解

未归档(8)

/ 注册

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

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

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

回溯递归枝剪哈希表数组

2021-07-28

0 1310

题解 | #集合的所有子集# 来自专栏

思路：题目的主要信息：有一个没有重复元素的整数集合S，经测试S的元素本就是升序求所有子集，子集顺序不定，子集中无重复内容，但是子集中的元素必须是升序方法一：穷举法具体做法：学过离散数学就知道，如果集合的元素是个，那就有个子集，如果我们枚举一一构造，那就需要做一个到的映射，我们可以想到二进...

子集集合数组二进制递归回溯

2021-07-28

0 682

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

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

数组哈希表位运算排序

2021-07-28

0 905

题解 | #最小的K个数# 来自专栏

思路：题目的主要信息：对于一个给定无序数组，返回最小的k个元素 k和数组有特殊情况需要单独讨论，且数组最大10000 方法一：堆排序具体做法：使用Java自带的PriorityQueue模拟一个大顶堆，堆的大小限定在最大k：遍历数组，前k个元素直接入堆，后续元素如果比堆顶元素大，则弹出堆顶，...

数组堆排序计数法

2021-07-27

0 534

题解 | #几步可以从头跳到尾# 来自专栏

思路：题目的主要信息： n长度的数组，每个元素表示从该数下标位置最多可往后跳跃多少个从1开始，无0的情况方法一：动态规划（可能会超时）题目要求的是找出从1跳到n最快的路径，即所需步数最短，我们可以想到遍历所有的路径，从中找出步数最短的路径。具体做法：我们可以用dp[i]表示第i个元素到最后...

动态规划贪心数组

2021-07-27

0 956

题解 | #不相邻最大子序列和# 来自专栏

思路：题目的主要信息：在数组中，选取一组序列，使和最大选取的数中，位置不能相邻可以不选或是选一个数方法一：递归（超时）具体做法：对于n个元素的数组，如果最后一个数字被选择了，则前一个数字必不会被选，那就是n-2的结果加上最后一个数字，如果最后一个数字没有被选择，则是n-1的结果，选取其...

动态规划递归数组子序列

2021-07-25

0 549

题解 | #排序# 来自专栏

思路：题目的主要信息：给数组排序不要求稳定与否就十分普通的排序问题，不考虑时间空间，常见的排序算法都可以，以下介绍几种。方法一：sort函数（快排）具体做法：直接调用sort函数排序。 class Solution { public: vector<int> MyS...

数组排序堆排序快速排序归并排序冒泡排序优先队列

2021-07-25

0 0

题解 | #数组中的逆序对# 来自专栏

思路：题目的主要信息：逆序对：前面的数字比后一个数字大，构成一对逆序对答案可能会非常大，因此用到了取余1000000007 不用考虑相同的数字最能想到思路，莫过于依次比较数组中每两个数，然后统计逆序对的数量。但是既然答案都会非常大了，数据量最大也可能达到10510^5105，依次比较可能...

排序归并排序数组逆序对

2021-07-22

1 505

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

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

哈希表数组子序列排序

2021-07-18

1 684

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

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

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

2021-07-17

1 1184