wangkeli3

题解

/ 注册

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

题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树#

题意给定一颗指定二叉树，判断其是否为搜索二叉树和完全二叉树思路我们可以分别判断二叉树是否为搜索二叉树和完全二叉树。对于搜索二叉树，只需要保证若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值，且其左右子树也为搜索二叉树。...

C++

2022-02-15

0 440

题解 | #N皇后问题#

题意给定一个n∗nn*nn∗n的国际象棋棋盘，求在上面放nnn个国际象棋中后的方案。思路 n皇后问题也是一类典型的回溯问题，题目的关键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后；可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同；如果同在／斜线上的行列...

C++

2022-02-15

0 406

题解 | #字符串的排列#

题意给出一个字符串，求其排列。思路该题思路与有重复项数字的全排列类似，只需要将题目中的数字换成字母即可，因此做法也可以采用回溯法，代码如下： class Solution { public: vector<string > ans;//存储答案用数组 bool us...

C++

2022-02-15

0 323

题解 | #有重复项数字的全排列#

题意有一组有重复项的数字，求出其所有全排列。思路我们用类似于解决问题无重复项数字的全排列的回溯法解决此题，两题的主要区别为该题有重复数字。以数组[1,1,2][1,1,2][1,1,2]为例，答案应该只有[1,1,2][1,1,2][1,1,2],[1,2,1][1,2,1][1,2,1],[...

C++

2022-02-15

0 477

题解 | #表达式求值#

题意给出一个只含+、-、*、左右括号和数字的表达式，求其值。思路给出的表达式是中缀表达式，含有括号，我们可以先将中缀表达式转为后缀表达式，再对后缀表达式直接计算，即可以算出表达式的结果。代码如下： class Solution { public: /** * 代码中的类名、...

C++

2022-02-10

0 338

题解 | #矩阵最长递增路径#

题意给定一个数字矩阵，找出一条路径使其经过的数字递增且最长。思路对于类迷宫题目，我们可以直接使用深度优先搜索与回溯法，把所有可能的路径求出，再找到其中最长的路径，只使用最朴素的思路，得出的代码如下。 class Solution { public: /** * 代码中的类名、...

C++

2022-02-10

0 345

题解 | #没有重复项数字的全排列#

题意有一组无重复项的数字，求出其所有全排列。思路要求全排列，我们可以利用回溯算法，例如，假设当前已经求出了一个排列，则只要回溯到填入上两个数字的状态即可以得到一个新的排列，这样不停回溯就可以求出所有全排列。代码如下： class Solution { public: vector&l...

C++

2022-02-10

0 322

题解 | #岛屿数量#

题意给定一个矩阵，计算其中只由1构成的连通块的数量。思路对于这类题目，我们可以使用FloodFill算法，从某个点开始向四周扩展，直到无法再扩展为止。以此为基础构建深度优先搜寻，将每个为1的点向外将上下左右的1变为0，然后往4个方向继续遍历，最后计算所得的连通块数量就是岛屿数量。 class ...

C++

2022-02-08

0 413

题解 | #重建二叉树#

题意给出一颗二叉树的前序遍历与中序遍历，重建一颗唯一对应的二叉树，之后返回其头节点。思路依据前序遍历与中序遍历的定义，前序遍历的第一个节点就为整棵树的根节点，我们在中序遍历中找到这个节点，那么左边的部分就是左子树的部分，右边的部分就是右子树的部分，再递归对左右子树分别重复这个查询的过程，最终就...

C++

2022-02-07

0 367

题解 | #跳台阶#

题意有nnn个台阶，每次可以跳一级或者两级，求不同的跳跃路线数量。思路不难发现，当有nnn个台阶时，有两种方法：跳跃1步，剩余n−1n-1n−1步跳跃2步，剩余n−2n-2n−2步因此这一题可以使用递归解决，要算出有nnn个台阶的方案个数，只需要算出有n−1n-1n−1和n−2n-2...

C++

2022-02-07

0 424