作者:aGreadyCat__895 | 来源:互联网 | 2023-09-18 11:22
一、引言
刷过 LeetCode 的同学应该都知道:
LeetCode 是一个在线 OJ 系统,经常会有些涉及到链表、二叉树、数组的题目,在线做题如果出现了奇怪的问题,也不能自行打断点查看哪里出了问题;想要自己本地打开 IDE 进行编译调试吧,又发现没有对应的链表、二叉树、数组这种拿来即可使用的数据结构。
因此,我开始萌生了自己写一个 LeetCode 内置数据结构库的想法。中间因为种种原因,或因为能力不够,或因为知识欠缺,或因为琐事太多,一直一直也未能完成这个心愿。
这两天刚好学习了动态链接库的编写,正好应景就初步完成了一个简略的 LeetCode 内置数据库的开发 :)
为了方便 LeetCode 在线刷题可以拿到本地调试运行,也为了提升自己的技术水平,我对自己这个 LeetCode 内置数据结构库提出了以下需求:
动态链接库:只需要拿到 .Lib 文件、.dll 文件、.h 文件,即可拿到我的 LeetCode 解决方案中调用调试运行
初步决定实现的数据结构:数组(LCArray)、二叉树(LCBinaryTree)、单链表(LCSingleLinkedList),暂时决定先实现这三个,后期可以视情况进行添加
实现功能:
- 接受指定格式输入初始化:例如二叉树的输入 [1, 2, 3, null, 4, 5],再比如数组的输入 [1, 2, 3, 4, 5]
- 能够获取到数据结构:例如二叉树就可以返回一个根节点(有些程序就可以直接拿着这个根节点进行算法演算),例如单链表返回根节点
- 能够打印数据结构:打印出当前的数据结构的信息
需求还算比较简单的,可能有些同学不了解为什么要做这么一个数据结构库,这里我以二叉树为例子进行讲解:
比如我们在 LeetCode 上的一道跟二叉树有关的题目的 Custom TestCase
中输入如下字符串:
[1, 2, 3, null, 4, null, 5]
我们就可以看到 LeetCode 为我们显示的二叉树结构图:
其中,输入的每个值都是一个节点,只是输入为 null
的节点默认为空节点。
因此,为了实现这样一个内置的数据结构机制,我萌生并实现了这么一个 LeetCode 内置数据结构库。
二、LeetCode::LCArray:内置数组
那么现在开始,整个项目命名为 LeetCodeDataStructure,定义一个名字控件 namespace,并且定义了三种内置数据结构:数组、二叉树、单链表,另外定义了单链表节点和二叉树的叶子节点。
整个项目是动态链接库项目,这是为了方便这个库链接到其他项目中使用,这也是我设计的初衷。关于如果编写、调用动态链接库,可以查看我写的以下两篇博客:
简单 Demo:C++编写、调用动态链接库
简单Demo:动态调用自己编写的动态链接库
想要实现一个能够接受输入为:
[1, 2, 3, 4, 5]
的数组结构,并且能够将其转换为 std::vector
结构,其实还是比较简单的。
初始化:接受一个 std::string
类型的输入 ” [1, 2, 3, 4, 5]”,通过正则表达式判断输入是否合理,匹配字符串中的数字并将其压入记录即可
输出:直接返回一个 std::vector
即可
打印:遍历打印即可
LeetCode::LCArray 的实现还算比较简单的,主要就是正则表达式的运用:
bool LeetCode::LCArray::_ConstructArray(std::string strInput)
{
std::string strTemp(strInput);
std::smatch match;
std::regex regexBracket("\\[.*\\[|\\].*\\]");
std::regex regexString("\\[(\\s*\\d\\s*[,]\\s*)*\\s*\\d\\s*\\]");
std::regex regexInteger("\\d");
if (std::regex_search(strTemp, match, regexBracket)) {
return false;
}
strTemp = strInput;
if (std::regex_search(strTemp, match, regexString)) {
std::string strInteger = match.str();
std::smatch matchInteger;
while (std::regex_search(strInteger, matchInteger, regexInteger)) {
std::string integerTemp = matchInteger.str();
m_vecArray.push_back(std::atoi(integerTemp.c_str()));
strInteger = matchInteger.suffix().str();
}
return true;
} else {
return false;
}
}
这个函数是 LeetCode::LCArray 类的核心实现,用于匹配读取其中的数据,并将其转换为 std::vector类型。
三、LeetCode::LCBinaryTree:内置二叉树
内置二叉树的实现是一个比较难的问题,主要难点在于:
输入:二叉树的构建在引言里已经展示过了,输入是类似 [1, 2, 3, null, 4, 5]
的字符串数据,要编写正确的正则表达式能够读取出来数据
二叉树的建立:要建立一个二叉树结构,可以使用 std::vector
来记录所有节点的信息(包括空节点),然后再在其中遍历设置每个节点的指向即可
二叉树的输出:这里我模仿 Linux 的树结构显示法显示了二叉树的结构,在子节点上以 L 和 R 来区分是左子节点还是右子节点
分析了以上三个难点,接下来我们来一一突破。
首先,要书写一个能够识别 [1, 2, 3, 4, null, 5]
的正则表达式:
\[(\s*\d\s*,|\s*null\s*,)*(\s*\d\s*|\s*null\s*)\]
这里我通过多次尝试,写出了这么一个正则表达式,验证也是正确的(有关正则表达式的内容可以点击这里进行学习 正则表达式30分钟入门教程)。
然后,二叉树的建立其实还算简单。主要是如何设置二叉树的节点的指向。我们可以把所有的输入都与一个二叉树节点一一对应起来(即使为 null 也认为是一个叶子节点,不过值为 null 而已,我们可以以 -1 来替代之)。
如图,我们的标记是从 0 开始的,因此数组中记录的节点信息就是如图显示的顺序,其中 3 和 5 都是空节点。根据查看我们能够总结出一个规律,那就是:
第 i 个节点的左子节点必然是第 i * 2 + 1 个节点
第 i 个节点的右子节点必然是第 i * 2 + 2 个节点
根据这个规律,我们就可以设置出每个节点的指向了,然后拿到第一个节点(也就是根节点),就相当于拿到了一个二叉树结构了。
接下来,最后一个难点:如果输出二叉树结构。
仔细思考下,其实也不难,主要是控制好遍历的层次,每一层子节点的递进,控制好缩进一层即可,主要实现是一个递归函数:
void LeetCode::LCBinaryTree::_PrintTreeNode(const TreeNode node, int depth, enum EPrintDirection eDirection) const
{
int myDepth = depth;
std::cout <<"|";
while (myDepth--) std::cout <<" ";
switch (eDirection)
{
case EPrintDirection_Root: std::cout <<"---";
break;
case EPrintDirection_Left: std::cout <<"L--";
break;
case EPrintDirection_Right:std::cout <<"R--";
break;
}
std::cout <std
::endl;
if (node.left !=
nullptr)
_PrintTreeNode(*node.left, depth +
1, EPrintDirection_Left);
if (node.right !=
nullptr)
_PrintTreeNode(*node.right, depth +
1, EPrintDirection_Right);
}
其中定义了一个联合对象来记录当前节点的属性:是左子节点还是右子结点,或者它是根节点。
最后的显示效果还是非常棒的:
四、LeetCode::LCSingleLinkedList:内置单链表
内置单链表的实现其实比较简单,识别输入:
[1, 2, 3, 4, 5]
与前面的 LeetCode::LCArray 是一模一样的,因此正则初始化模块是可以代码复用的。
那么就剩下单链表数据结构的构建了,其实也比较简单:
bool LeetCode::LCSingleLinkedList::_MakeSingleLinkedList(std::vector<int> vecSingleLinkedList)
{
for (auto val : vecSingleLinkedList) {
ListNode newListNode(val);
m_vecSingleLinkedList.push_back(newListNode);
}
for (int i = 0; i if (i != m_vecSingleLinkedList.size() - 1)
m_vecSingleLinkedList[i].next = &m_vecSingleLinkedList[i + 1];
else
m_vecSingleLinkedList[i].next = nullptr;
}
return true;
}
也就是两个循环,第一次全部复制构建所有的链表节点,第二次设置指向,而链表没那么多弯弯绕绕的东西,直接依次指向下一个即可,最后一个节点指向为空即可。
五、欣赏:LeetCode内置数据结构库展示
这里新建另外一个测试项目,静态调用动态链接库 LeetCodeDataStructure,用来测试我们的 LeetCode 内置数据结构库的功能是否正常:
内置数组:LeetCode::LCArray
内置二叉树:LeetCode::LCBinaryTree
内置单链表:LeetCode::LCSingleLinkedList
怎么样,尽管很简略,还是能看够用的吧 ^_^
六、总结
能够开发出来这个一个 LeetCode 内置数据结构库,我很开心。
怎么说呢,第一次为自己的实际需求开发了一个很小型的库,真的成就感爆棚。在开发过程中遇到了不少的麻烦,其中有一个 DLL 编程中调用 std::vector
模板库出现警告的问题,也是琢磨了很久很久,最后选择忽略警告,这个问题同样遇到的同学可以点击这篇博客:
C4251告警“需要有 dll 接口由 class“xxx”的客户端使用”的解释及解决方法
尽管遇到了这么多问题,最后还是一一解决。
创造的快感,无与伦比:)
编程的本质是创造
这是一件那么伟大的事情
以至于我每天都在为此感到自豪
永远相信,更美好的事情即将发生 ^_^
ps: 附上本博客的实验代码的 GitHub 托管地址,感兴趣的同学可以自行查看:
wangying2016/LeetCodeDataStructure