牛客786963925号

题解

/ 注册

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

题解 | #序列化二叉树#

解法一：前序遍历题目要求：1. 访问二叉树，并将访问结果存到一个字符串中返回，即：「二叉树的序列化」；2. 访问得到的字符串，重构出二叉树，即：「二叉树的反序列化」。显而易见的是，在二叉树的序列化过程中，需要「遍历二叉树」，因此可采用二叉树的遍历方法之一：「前序遍历」来实现。这是因为：前序遍历是...

C++ 二叉树先序遍历层次遍历队列递归

2021-08-08

0 455

题解 | #字典树的实现#

解法一：哈希表实现（暴力解法）题目要求实现字符串的「插入」、「查找」、「查找前缀」等功能，一个直观的想法是利用「以空间换时间」的数据结构：哈希表。哈希表在「查找」操作上的时间复杂度为，可以作为此题的解法。利用哈希表实现的思路如下：定义哈希表hash，其保存的键值对为，即以「单词」作为key，...

C++ 哈希表字典树数组

2021-08-08

0 532

题解 | #正则表达式匹配#

解法一：动态规划与此题类似，此题可以采用动态规划的方法来求解。定义二维递推数组dp，其中表示字符串str的前个字符与字符串pattern的前个字符是否匹配（设dp数组行、列分别为、，其中分别为字符串str和pattern的长度）。「动态规划算法的关键是确定递推式」，对于此题有如下几种情况：（为方...

动态规划 C++ 递归

2021-07-31

11 872

题解 | #未排序数组中累加和为给定值的最长子数组长度#

解法一：回溯 + set 利用回溯方法进行求解的思路如下：（具体递归过程见图示）对于每一个位置，都有「选」和「不选」两种可能，因此需要定义一个state数组用来记录「当前元素是否已经被选择」；字符串cur用来记录「当前」字符串的情况，在每次递归时，在cur末尾加上当前字符（若其未被选择过），然...

C++ 回溯递归 set

2021-07-25

3 421

题解 | #未排序数组中累加和为给定值的最长子数组长度#

解法一：暴力解法此题需要求解连续子数组元素的和等于目标值的最长子数组长度，因此需要两个变量分别确定子数组的头和尾。暴力解法的思路如下：定义两个变量i、j，分别表示当前子数组的头尾。其中，i指针从第0个位置开始遍历，用来表示子数组的头；j指针从i开始遍历，表示子数组的尾。在遍历过程中，若求得当前子...

哈希表 C++ 前缀和

2021-07-24

11 709

题解 | #通配符匹配#

解法一：动态规划由于此题中"*"可以匹配多个字符（包括空字符），因此枚举所有可能性较为麻烦，一种简单的思路是采用动态规划算法进行求解，具体思路如下：定义动态规划数组dp，其中dp[i] [j]表示「s字符串的前i个字符与p字符串的前j个字符是否匹配」。而对于每个位置，有如下三...

C++ 双指针动态规划

2021-07-17

1 634

题解 | #数独#

解法一：解法一的思路较为直接：对数独中的每个位置，若其不为.，即没有被数字所填，则从数字1至9遍历，分别填写该位置，并检验此时数独是否有效。若成功填满最后一个位置，即是该数独的解，否则将填写的位置重置，继续遍历。解法一的思路如图所示。在「检验数独」是否有效时，需要如下3个步骤：检验数独...

C++ 回溯递归

2021-07-17

4 878

题解 | #在旋转过的有序数组中寻找目标值#

解法一：顺序查找顺序查找的思路较为简单：从左至右遍历数组，若找到目标值，返回下标；否则返回-1。实现的代码如下： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * ...

C++ 二分查找

2021-07-14

6 828

题解 | #实现二叉树先序，中序和后序遍历#

解法一：递归「二叉树的先序遍历」的思路是：先访问根结点，再访问左子树，最后访问右子树；「二叉树的中序遍历」的思路是：先访问左子树，再访问根结点，最后访问右子树；「二叉树的后序遍历」的思路是：先访问左子树，再访问右子树，最后访问根结点；下图以「先序遍历」为例进行展示：基于上述思路，可以得...

C++ 二叉树中序遍历先序遍历后序遍历递归栈

2021-07-14

19 1876

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

利用set解法对于此题，可以利用「回溯」的思想求解：先尝试某一选择，若满足题目条件，则加到最终结果中；否则撤销该选择，重新进行下一次选择。具体而言，利用「回溯」算法求解此题的步骤如图所示：对于原数组，从第一个位置（为10）开始选，加入到临时数组arr中，并将目前的求和结果加入到cur...

C++ 递归回溯

2021-07-13

8 945