觅杳

题解

/ 注册

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

C++二分法求解

本题目的是判断给定数据是否存在于已知二维数组中。则可直接使用暴力法，遍历二维数组求解。但由于此方法时间复杂度高达O(n^(2)),即可能会导致运行超时。故而，需另辟蹊径。显然，当target的值大于右上角元素时，其一定不会位于第一行，故可排除，行数i增加1；则再次与此时右上角数据（第二行）...

2021-07-27

0 543

C++题解 | #最长回文子串#

>首先，当子串长度超过2时，若欲使其为回文子串，其两端字母必须相等，且除去两端字母后的子串依旧为回文子串，即当s[i + 1 : j - 1]为回文子串且s[i] == s[j] 时，s[i : j]子串为回文子串。则可得其状态转换方程为：（dp[i][j]表示s[i : j]是否为回文子串。...

2021-05-29

0 429

C++题解 | #合并两个有序的数组#

数组A的空间足以放置A和B中所有的元素，所以当前A中元素之后还有空间，用于放置B中元素，故而考虑从后往前进行放置。首先A中最大和B中最大进行比较，较大的放置在数组末尾，较小的依旧进行比较。以此类推，若A中元素首先被放置完毕，则将B中剩余元素直接复制进入A中即可，反之亦然，直到所有元素都放置完毕。cl...

2021-05-22

0 471

C++题解 | #子数组的最大累加和问题#

分治法求子数组最大累加和。从第二个位置元素开始，依次求**包含该位置元素在内**的最大子数组累计和（即该位置元素与前一位置元素之和，与该位置元素相比，哪个更大。若前者大于后者，则将该位置元素替换为该位置元素与前一位置元素之和），之后遍历数组，查询最大值即可。class Solution { pub...

2021-05-13

0 493

C++题解 | #寻找第K大#

快速排序利用快速排序（即每次都确定一个数据在从大到小的排序中所处的位置（下标））。首先经过一遍排序，基本确定元素顺序，而后判断当前所指向数据的位置（假设为第M大，此时该位置的下标也为M）是否满足题意所求，及有M == K。若恰好为第K大，则直接返回该数据，否则，若M > K，则待求数据应当位于...

2021-05-06

0 557

题解 | #找到字符串的最长无重复字符子串#

相当于将所有子串都录入到unordered_map中，保存其中最大的长度这里利用双指针，i将数据录入，如果遇到重复的，则将已录入的元素，到重复的元素为止，都从unordered_map中移除，再重新开始录入（重复的元素，其value值被更新） class Solution { public: ...

2021-04-10

0 556

题解 | #数组中相加和为0的三元组#

C++、双指针本题主要利用双指针，在确定一个数据的基础上，利用双指针确定另外两个数据。复杂在于不得重复，即去重语句的考虑。若添加位置错误或考虑欠缺，则会导致结果的减少或重复。 class Solution { public: vector<vector<int> > ...

2021-04-10

0 467

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

C++, unordered_map，简单省事。这里不用数组充当哈希表的原因是，遍历费时（O( )）。 class Solution { public: /** * * @param numbers int整型vector * @param target i...

2021-04-10

0 526

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

整体思路很简单。一个一个往后加，直到和等于目标值。这其中，若当前和会大于目标值，则跳过当前数组值，与下一个相加。若当前和小于目标值，则继续往后加下一个数。另外一点就是，去重操作，要注意判重条件的确定。此处，因为每次加和时，开头的第一个数可以重复使用，故而通过i > m，判断是否为第一个数。若不...

2021-04-10

0 740

动态规划、递推

该题与斐波那契数列如出一辙，当前状态只与前两个状态有关，且为前两者之和。利用两个变量保存前两个状态来代替dp数组，可节省空间。要跳上第n级台阶，要么从第n-1级台阶跳上去，要么从第n-2级台阶跳上去。故而，跳上第n级台阶的可选方案数目，为跳上第n-1级台阶的方案数目和跳上第n-2级台阶的之和。cl...

2021-04-08

0 443