摸鱼学大师

题解

未归档(8)

/ 注册

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

题解 | #最长的括号子串# 来自专栏

题目的主要信息：一个长度为nnn的仅包含左右括号的字符串计算最长的格式正确的括号子串的长度方法一：栈具体做法：可以使用栈来记录左括号下标，每次遇到右括号则弹出左括号的下标，然后长度则更新为当前下标与栈顶下标的距离。因为遇到不符合的括号，可能会会使栈为空，因此需要使用start记录上一次...

C++ 栈动态规划字符串

2021-12-07

0 337

题解 | #二叉树中和为某一值的路径(一)# 来自专栏

题目的主要信息：给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径路径定义为从树的根结点开始往下一直到叶子结点所经过的结点路径只能从父节点到子节点，不能从子节点到父节点要求：空间复杂度 O(n)O(n)O(n)，时间复杂度 O(n)O(n...

C++ dfs 栈递归二叉树

2021-12-04

0 359

题解 | #按之字形顺序打印二叉树# 来自专栏

题目的主要信息：给定一个二叉树，返回该二叉树的之字形层序遍第一层从左向右，下一层从右向左，一直这样交替进阶要求：空间复杂度：O(n)O(n)O(n)，时间复杂度：O(n)O(n)O(n) 方法一：非递归层次遍历具体做法：按照层次遍历按层打印二叉树的方式，每层分开打印，然后对于每一层利用...

C++ 栈队列 bfs

2021-12-03

0 353

题解 | #二叉搜索树的第k个节点# 来自专栏

题目主要信息：给定一棵结点数为n二叉搜索树，需要其中的第k小的TreeNode结点值返回第k小的节点值即可不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1 保证n个节点的值不一样思路：根据二叉搜索树的性质，其中序遍历是由大到小的，由此仅需要中序遍历找到第k个小的结...

C++ 递归栈 dfs

2021-12-01

1 449

题解 | #翻转单词序列# 来自专栏

题目的主要信息：将一个英文语句以单词为单位逆序排放所有单词之间用一个空格隔开，没有仅含空格的案例进阶要求：时间复杂度O(n)O(n)O(n)，空间复杂度O(n)O(n)O(n) 方法一：两次反转具体做法：将输入的字符串反转，得到了完全逆序的字符串，单词与单词之间确实是逆序了，但是单词内...

C++ 字符串栈

2021-11-30

0 304

题解 | #火车进站# 来自专栏

题目的主要信息：给定n列火车的入栈序列，0<n<100<n<100<n<10，用数列1-9表示每列火车火车只能从一个方向进，另一个方向出，只有站内的火车出去了，另外的才能进去要求输出所有火车出站的方案，以字典序排序输出方法一：全排列+栈具体做法：我...

C++ dfs 递归回溯栈

2021-10-30

2 651

题解 | #矩阵乘法计算量估算# 来自专栏

题目的主要信息：编写程序计算不同的计算顺序时矩阵乘法需要进行的乘法次数计算顺序由字符串给出，A-Z的大写字母表示矩阵，括号决定运算顺序，每次运算都有括号比如 ( ( A B ) C ) 或者 ( A ( B C ) ) 进阶要求：时间复杂度O(n)O(n)O(n)，空间复杂度O(n)O(n)...

C++ 递归栈字符串

2021-10-29

0 379

题解 | #表达式求值# 来自专栏

题目的主要信息：输入一个表达式（用字符串表示），求这个表达式的值字符串中有0-9的数字，加减乘除符号，只有小括号表达式一定合法，不用判断括号是否合法之类的问题除数用整数运算方法一：递归具体做法：括号中的运算式可以看成运算式的子问题，因此可以用递归解决。第一次运算是运算字符串的起始...

C++ 递归栈

2021-10-26

73 4702

题解 | #迷宫问题# 来自专栏

题目的主要信息：一个n∗mn*mn∗m的矩阵表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走要求找出从左上角到右下角的最短路线入口点为[0,0][0,0][0,0],第一格一定是可以走的路数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道方法一：d...

C++ dfs 栈递归

2021-10-24

10 2504

题解 | #重建二叉树# 来自专栏

题目的主要信息：根据二叉树的前序遍历序列和中序遍历序列，重建该二叉树，并返回根节点两个遍历都没有重复的元素方法一：递归具体做法：对于二叉树的前序遍历，我们知道序列的第一个元素必定是根节点的值，因为序列没有重复的元素，因此中序遍历中可以找到相同的这个元素，而我们又知道中序遍历中根节点将二叉...

C++ 二叉树栈递归

2021-09-29

0 383