我要出去乱说

分类

C++(2) 程序员代码面试指南(20) 题解(2)

/ 注册

TA的专栏 50篇文章 3人订阅

程序员代码面试指南（C++版题解）

41篇文章 592人学习

我的面经汇总

9篇文章 21587人学习

全部文章（共42篇）

程序员代码面试指南 1.11：可见的山峰对数量（数学题）来自专栏

1、思路当环形结构中只有一座山峰时，可见山峰对数量为0。当有两座时，可见山峰对数量为1。当有三座时可见山峰对数量为3。可以推导得出当有n座山峰时，可见山峰对数量为2 * n - 3；假设环形结构中有n座山峰，除了最高山峰和次高山峰外还剩下n - 2座山峰，这n - 2座山峰中每一座都能根据小...

C++

2022-06-25

1 522

程序员代码面试指南 3.10：找到搜索二叉树中两个错误的节点来自专栏

1、思路对二叉树进行中序遍历得到的节点值是升序的，若出现降序的情况，说明找到了错误的节点，降序分两种情况讨论： 1、中序遍历时节点值出现两次降序，如[1, 5, 3, 4, 2]，第一次降序为5->3，第二次降序为4->2； 2、中序遍历时节点值出现一次降序，如[1, 2, 4, ...

C++

2022-06-24

0 298

程序员代码面试指南 3.7：找到二叉树中的最大搜索二叉子树来自专栏

1、思路需要求出以每一个节点为头节点的子树的最大搜索二叉子树。对于每一个节点，我们用一个结构体ReturnType来保存该节点的四种信息：1、maxBSTHead 该子树中最大二叉搜索树的头节点；2、maxBSTSize 该子树中最大二叉搜索树的节点个数；3、min 该子树中最小节点值；4、ma...

C++

2022-06-22

1 425

程序员代码面试指南 3.9：二叉树按层打印与ZigZag打印来自专栏

1、思路模板题，就是二叉树的层序遍历和锯齿形遍历；输出比较麻烦。 2、代码 #include <iostream> #include <queue> #include <algorithm> using namespace std; struct ...

C++

2022-06-22

0 388

程序员代码面试指南 3.6：二叉树中找累加和为指定值的路径来自专栏

1、思路前序遍历的同时计算从根节点到当前节点路径之和，哈希表的键表示路径前缀和，值表示路径终点所在的层（因为路径只能由上自下）；遍历过程中若在哈希表中找到curSum - targetSum，则表示已经找到一条累加和为指定值的路径，更新其路径长度；哈希表初始化hash[0] = 0，表示...

C++

2022-06-04

1 291

程序员代码面试指南 3.5：遍历二叉树的神级方法来自专栏

1、思路因为遍历二叉树的递归方法实际使用了函数站，非递归的方法使用了申请的栈，两者的额外空间都与树的高度相关，所以空间复杂度为，为二叉树的高度；减少空间复杂度的难点在于从子节点返回父节点，Morris遍历利用了二叉树中大量存在的空闲节点来实现从下层到上层的遍历； Morris遍历原理：...

2022-06-02

0 412

程序员代码面试指南 3.4：二叉树的序列化和反序列化来自专栏

1、思路跟普通的二叉树先序遍历和层序遍历一样，只不过用string替代了vector。注意建树方式。 2、代码 #include <iostream> #include <string> #include <queue> using namespa...

2022-06-01

1 405

程序员代码面试指南 3.1：实现二叉树先序、中序和后序遍历来自专栏

模板题，注意简单的建树方法。 #include <iostream> #include <vector> #include <stack> #include <algorithm> using namespace std; struct Tree...

2022-05-31

1 372

程序员代码面试指南 2.19：合并两个有序的单链表来自专栏

1、思路同时遍历两条有序链表，将较少的节点接到head之后；当一条链表遍历完毕后，直接将另一条链表剩余部分全部接在后面即可。 2、代码 list_node * merge_list(list_node * head1, list_node * head2) { list_node...

2022-05-14

1 408

程序员代码面试指南 2.18：向有序的环形单链表中插入新节点来自专栏

1、思路遍历有序环形链表，找到小于num的节点；创建num节点，将它插入到合适的位置即可；考虑到待插入节点的值可能比头节点更小的情况，要从链表的尾结点开始遍历。若遍历了一圈没有找到小于num的节点，则在表尾后（即表头前）新增这个num节点。 2、代码 list_node * i...

2022-05-14

1 342