文和906

分类

未归档(4) 项目笔记(5) 题解(103)

/ 注册

全部文章（共113篇）

题解 | #翻转单词序列#

难度较低的题目。在经历了前面的字符串处理地狱之后，这种题目我看过之后心里毫无波澜，甚至还有点想笑w。言归正传，总体的思路是：将string作为char[]遍历，遇到空格则切词，并将切下的词入栈。最后按出栈顺序将字符串拼好即可。需要注意空格的处理方式，这里我的做法是每次切词都加上空格，对头尾特殊处理。...

C++ 字符串栈

2021-10-12

0 378

题解 | #栈的压入、弹出序列#

审题后从输入序列和输出序列入手，发现规律：当两个元素在输入序列中的先后顺序与在输出序列中一致时，在这两个数之后输入的数必不可能在这两个数之前输出。围绕这一发现，设计算法逻辑：用一个辅助数组seq来储存输入序列的元素在输出序列中的位置，如seq[0]则表示输入序列中第一个元素在输出序列中的位置。遍历s...

C++ 栈

2021-10-12

0 407

题解 | #包含min函数的栈#

需求是在基本栈的功能上增加一个min的功能。这里选择增加一个栈用于维护最小值，暂且称它为最小栈。每次push时检查最小栈，为空则直接入最小栈，否则将入原始栈元素与栈顶元素比较，若入原始栈元素小于等于最小栈栈顶元素，则也将其入最小栈。之所以等于时也要入最小栈，是因为相等说明前面有一个同样数据的结点...

C++ 栈

2021-10-12

0 382

题解 | #序列化二叉树#

这道题本身挺简单的，但是坑是真的多，给我整破防了。先说一下大概的思路，直接用层序遍历来序列化。序列化的时候使用一个队列来辅助将结点值拼接到字符串上，节点为空则拼接#。反序列化时同理，使用队列来辅助反序列化，创建好的节点先入队，并且查看队头结点的情况，若其左结点为空，则将该结点设为队头结点的左结点，...

C++ 字符串二叉树队列

2021-10-11

0 431

题解 | #把二叉树打印成多行#

之前做过一道一模一样但是名字不同的题。这次就当是复习了。思路就不再写了，可以点这里看。 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int ...

C++ 二叉树广度优先搜索

2021-10-11

0 349

题解 | #对称的二叉树#

最开始尝试直接递归原树进行比较，但是思路有问题。退而求其次，直接深拷贝原树，再比较两树。在写比较函数的过程中，我发现之所以最开始原树比较不行，应该是递归函数的比较逻辑出问题了，所以在写完这种方法后继续回头研究原树比较的方法。 /* struct TreeNode { int val; ...

C++ 二叉树

2021-10-11

0 427

题解 | #二叉树的下一个结点#

根据中序遍历的规则，可以知道，当该结点有右子树时，返回其右子树最左边的结点。当该结点没有右子树时，则需要向上寻找第一个其左子树中包含该结点的结点。根据这两种需求，分别写两个函数，一个通过递归找最左边的子结点，一个通过递归找向上第一个在左子树中包含该结点的点。根结点由于其next域为空所以需要做特殊处...

C++ 二叉树递归

2021-10-09

0 372

题解 | #平衡二叉树#

核心思想是递归。首先写一个递归函数来返回树的高度，然后主函数中递归调用该函数比较左右子树的高度。没有什么特别需要注意的点，就是时间复杂度和空间复杂度有点高。但是也没有想象的那么高。 class Solution { public: bool IsBalanced_Solution(Tree...

C++ 二叉树

2021-10-09

0 385

题解 | #二叉搜索树与双向链表#

观察容易发现双向链表的顺序与该二叉树中序遍历的结果相同。故首先考虑中序遍历解题。最开始由于题目中要求空间复杂度为O(1)，故考虑原地操作，但递归的中序遍历也需要用到递归栈，如果真的要满足空间复杂度为O(1)，则需要考虑迭代中序遍历树，或放弃中序遍历的思路。这里最终还是选择使用中序遍历，将结点按中...

C++ 二叉搜索树

2021-10-09

0 419

题解 | #二叉树中和为某一值的路径#

深度优先遍历题目的变种。只需要在遍历时多传两个参数，一个用于记录路径和，一个用于记录遍历过的结点即可。这里有个小坑需要注意，最开始在递归传参时使用了引用传参，导致递归返回后参数不回还原，需要改为值传参。果然引用传参还是存在危险的，需要稍用。 /* struct TreeNode { int va...

C++ 深度优先搜索二叉树

2021-10-09

0 366