题目描述:完全二叉树DFS转BFS

题目：

给定一个字符串，其字符序列是根据一个完全二叉树通过深度优先遍历得到的，二叉树的每个节点是一个单字符。如果对这个完全二叉树改用广度优先遍历算法，那么得到的字符串是什么，将这个字符串序列以字符串的形式输出。

输入描述：

输入一行，一个由字母和数字组成的字符串，字符串长度为2ⁿ-1，例如 2³-1 = 7，n大于等于1。如果输入字符串的长度不合要求，那么统一输出字符串WRONG INPUT。

输出描述：
输出一行字符串。

样例输入：abcdefg
样例输出：abecdfg

当我们在 Windows 平台上进行程序开发的时候，会遇到各种各样让人讨厌的问题，有时候还必须转到 Linux 环境下进行开发。然而，通过本文你将可以解决你在 Windows 平台上开发遇到的所有问题。

记录一下2020.11.03银行的三道笔试题。

1. 大意是每购买完一件产品，记录的是已经购买完的所有产品的最大价值，但是只能记录最后连续k件的最大价格。输出记录的价格。

示例：

1
2
3
4
5
6
7

输入：
1
3 2
9 6 6

输出：
9 9 6

思路：类似滑动窗口最大值

extern

extern是一种“外部声明”的关键字，字面意思就是在此处声明某种变量或函数，在外部定义。

extern关键字的主要作用是扩大变量/函数的作用域，使得其它源文件和头文件可以复用同样的变量/函数，也起到类似“分块储存”的作用，划分代码。如图所示，在一个头文件里做了外部声明，就能把变量的定义部分和函数体的实现部分转移到其它地方了，也就是extern可以实现多文件共享同一个变量、const常量、函数。

KMP是什么，做什么用的

KMP全称为Knuth Morris Pratt算法，三个单词分别是三个作者的名字。KMP是一种高效的字符串匹配算法，用来在主字符串中查找模式字符串的位置(比如在“hello,world”主串中查找“world”模式串的位置)。

KMP算法的高效体现在哪

高效性是通过和其他字符串搜索算法对比得到的，在这里拿BF(Brute Force)算法做一下对比。BF算法是一种最朴素的暴力搜索算法。它的思想是在主串的[0, n-m]区间内依次截取长度为m的子串，看子串是否和模式串一样(n是主串的长度，m是子串的长度)。代码是这样: