解法一：哈希表实现（暴力解法） 题目要求实现字符串的「插入」、「查找」、「查找前缀」等功能，一个直观的想法是利用「以空间换时间」的数据结构：哈希表。哈希表在「查找」操作上的时间复杂度为，可以作为此题的解法。 利用哈希表实现的思路如下： 定义哈希表hash，其保存的键值对为，即以「单词」作为key，以「该单词出现的次数」作为value。 对于插入操作：首先判断该单词是否存在在哈希表中，若存在，将其value加1；若不存在，将其插入哈希表中，并将value置为1。 对于删除操作：由于被删除的单词一定存在于哈希表中（题目明确说明），故直接将该单词的value减1即可。 对于查找操作：直接在哈...

解法一：动态规划 与此题类似，此题可以采用动态规划的方法来求解。定义二维递推数组dp，其中表示字符串str的前个字符与字符串pattern的前个字符是否匹配（设dp数组行、列分别为、，其中分别为字符串str和pattern的长度）。 「动态规划算法的关键是确定递推式」，对于此题有如下几种情况：（为方便递推式的表示，dp数组行、列分别为、，故对于字符串str和pattern的索引需要减1） 具体事例如图所示。 当为或时，说明str的第个位置和pattern的第个位置是可以匹配的，因此此时两个字符串是否匹配取决于上个位置，故有; 当为星号时，由于星号可以匹配多次（包括零次）其前一字符，因此需...

解法一：回溯 + set 利用回溯方法进行求解的思路如下：（具体递归过程见图示） 对于每一个位置，都有「选」和「不选」两种可能，因此需要定义一个state数组用来记录「当前元素是否已经被选择」； 字符串cur用来记录「当前」字符串的情况，在每次递归时，在cur末尾加上当前字符（若其未被选择过），然后进入下一次递归；当cur字符串与原字符串长度相同时，即说明已经完成「整个字符串的排列」，因此将其添加至结果中； 此外，在每次递归时，需要将该字符的state数组置位true，说明其已经被选择了；在递归完成后，需要「恢复现场」：把该字符的state数组置位false，并将其从cur中去掉； 每次递归...

解法一：暴力解法 此题需要求解连续子数组元素的和等于目标值的最长子数组长度，因此需要两个变量分别确定子数组的头和尾。 暴力解法的思路如下：定义两个变量i、j，分别表示当前子数组的头尾。其中，i指针从第0个位置开始遍历，用来表示子数组的头；j指针从i开始遍历，表示子数组的尾。在遍历过程中，若求得当前子数组的和等于目标值，则将结果与res比较并更新（如果大于res），否则继续遍历。 根据上述思路，实现的代码如下： 注意：该方法复杂度较高，会超出运行时间限制。 class Solution { public: /** * max length of the subarray sum...

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

解法一： 解法一的思路较为直接：对数独中的每个位置，若其不为.，即没有被数字所填，则从数字1至9遍历，分别填写该位置，并检验此时数独是否有效。若成功填满最后一个位置，即是该数独的解，否则将填写的位置重置，继续遍历。 解法一的思路如图所示。 在「检验数独」是否有效时，需要如下3个步骤： 检验数独的每一行是否有效，因此需要对「刚才所填写的数字」所在的「行」进行遍历； 检验数独的每一列是否有效，因此需要对「刚才所填写的数字」所在的「列」进行遍历； 检验每一个3x3的方块是否有效，对于位置(i, j)，其所在的方块区域为： 行：从i / 3 * 3到 i / 3 * 3 + 1; 列：从j / ...

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

解法一：递归 「二叉树的先序遍历」的思路是：先访问根结点，再访问左子树，最后访问右子树； 「二叉树的中序遍历」的思路是：先访问左子树，再访问根结点，最后访问右子树； 「二叉树的后序遍历」的思路是：先访问左子树，再访问右子树，最后访问根结点； 下图以「先序遍历」为例进行展示： 基于上述思路，可以得到实现代码如下： /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** ...

利用set解法 对于此题，可以利用「回溯」的思想求解：先尝试某一选择，若满足题目条件，则加到最终结果中；否则撤销该选择，重新进行下一次选择。 具体而言，利用「回溯」算法求解此题的步骤如图所示： 对于原数组，从第一个位置（为10）开始选，加入到临时数组arr中，并将目前的求和结果加入到curr中； 在选择了第一个数的基础上，从第二个数开始（为10）继续选择，并将目前的求和结果加入到curr中； 以此类推，若curr的取值大于目标值（如10、10、20、50），说明现有组合无法完成目标，故撤销最后一次选择，重新开始别的选择（从60开始，继续重复上述步骤）； 若满足条件，则将arr加入到最...

解法一：自顶向下 一棵二叉树为「平衡二叉树」的条件为：该树为空树，或者其左右子树的高度差最大为1。因此，判断一棵二叉树是否平衡需要求其子树高度，并比较左右子树高度差。 因此此题的解题步骤如下： 设计「求二叉树高度」的函数getHeight(root)，作用是求以root为根结点的二叉树高度； 遍历原二叉树，对其每个结点调用getHeight(root)函数，若存在某左右子树的高度差大于等于2，则是不平衡的；否则是平衡二叉树。 求取二叉树高度的思路如图所示。 图中，红色箭头方向为递归方向，绿色箭头方向为回溯方向。 当结点为空时，其高度为0； 当结点无左孩子、右孩子时，其高度为1； 否则...

解法一：中序遍历（递归）+ 层次遍历 一棵「二叉搜索树」需要满足要求：对于每个结点，左子树上的所有结点小于它，右子树上的所有结点大于它。 判断一棵二叉树是否为「二叉搜索树」的通用方法为：对该二叉树进行中序遍历，若遍历结果为「严格」单调递增的，则是一棵二叉搜索树，否则不是。 这是因为：中序遍历的步骤是：对于每个结点，先访问其「左子树」，再访问该结点，最后访问其「右子树」；而一棵二叉搜索树左子树结点必小于该结点、右子树上的结点必大于该结点，因此中序遍历的结果为严格单调递增。解法一通过「递归」的方式进行中序遍历，并维护了一个数组用以保存中序遍历的结果，遍历数组来判断是否为严格递增的。 判断一棵树是否...

解法一：虚拟结点 此题要求删除「所有的」重复结点，而存在「原链表头结点出现重复」这种情况。因此，为了实现方便，定义虚拟结点dummy，其next指针指向原头结点。 思路如图所示。 定义指针p，用以遍历链表；定义指针tail，用以指向当前「无重复链表」表尾； 每次p指针向前移动，并比较「当前位置取值」与「下一结点取值」是否相等： 若不相等，说明当前位置为非重复结点，更新tail指针； 否则，p指针不断向前移动直至「当前结点与下一结点取值不同为止」； 当p到达链表表尾而最外层while循环仍未结束，说明「链表表尾为非重复结点」，更新tail指针。 注意：在最外层while循环结束时，需...

解法一：递归 递归方法通过定义递归函数helper，遍历树的每一层，并将结果放入结果数组res的相应位置，因此需要定义level变量以记录当前访问到的层数。在完成对某一凑层的遍历时，按照相同方式递归地访问左孩子和右孩子，且层数加1。 实现代码如下： /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class ...

解法一：使用队列 据题意，需要按照每一层的方式打印二叉树，因此较为直接的解法为「层次遍历」。 二叉树的层次遍历通过队列实现较为方便，步骤如下： 初始情况，根结点入队列； 定义变量size记录当前队列长度； 对于「当前队列」，遍历其所有元素：依次出队列、访问该元素、左右孩子入队列。注意：新入队列的「左右孩子」应当在下一层被访问，因此循环次数为size次。 重复上述步骤直至队列为空。 步骤如图所示。 此外，此题目要求「之字形」打印，因此定义变量level记录当前层的打印方向。 代码如下： /* struct TreeNode { int val; struct TreeNo...