Leetcode刷题本地debug框架搭建
思路
1. 初版
cmake + 单一.cpp文件
参考:https://blog.songjiahao.com/archives/362
2. 改良版
cmake + 源文件、头文件(含List、Tree等数据结构)分离 + gtest
参考:https://github.com/Pokerpoke/LeetCode
Normal模板
以Leetcode 1 两数之和 为例
#include <iostream> #include <vector> #include <unordered_map> using namespace std; class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { // key代表数字,value代表位置 unordered_map<int, int> hash; vector<int> ans; for (int i = 0; i < nums.size(); ++i) { auto pos = hash.find(target - nums[i]); if (pos == hash.end()) { hash[nums[i]] = i; } else { ans.push_back(pos->second); ans.push_back(i); } } return ans; } }; int main() { //main函数中新建一个类 ,并且调用该类的函数, Solution s; //输入的数据要根据网页提示 自行创建 vector<int> v{ 2,7,11,15 }; s.twoSum(v,9); return 0; }
CMakeLists.txt
# Set the minimum version of CMake that can be used cmake_minimum_required(VERSION 3.9) # Set the project name project (template) # set CMAKE_BUILD_TYPE set(CMAKE_BUILD_TYPE Debug) # Add an executable add_executable(templat_bin leetcode1_TwoSum.cpp)
然后利用vscode中的Cmake插件,点击debug按钮即可断点调试:
链表类
这里只针对出现比较多的单链表,而且沿用了力扣的不带头结点的形式进行定义和操作。力扣中关于单链表的操作,一般要求返回某个节点数值,返回一个链表。因此,主要的处理为将样例提供的数组按照头插的方式创建单链表,以及获取链表程度,打印链表等基本操作。模板代码如下:
#include<bits/stdc++.h> using namespace std; //链表定义 struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; //相关函数的声明 void insertList(ListNode* &head,int x); //头插法在链表头部插入节点 void printList(ListNode *head); //打印链表 int getLenght(ListNode* head); //获取链表长度 ListNode *creatList(int a[],int n); //根据数组创建链表 //在这里放入Solution类 //类开始 class Solution { public: ListNode *removeNthFromEnd(ListNode *head, int n) { // pre指针(快慢指针) ListNode* dummy = new ListNode(0, head); // 应对删掉头结点的情况 ListNode* slow = dummy; ListNode* fast = head; ListNode* ans; for (int i = 0; i < n; ++i) { fast = fast->next; } while (fast) { fast = fast->next; slow = slow->next; } slow->next = slow->next->next; ans = dummy->next; delete dummy; return ans; } }; //类结束 int main(){ ListNode *head=nullptr; int list[]={1,2,3,4,5}; int len=sizeof(list)==0?0:sizeof(list)/sizeof(list[0]); head=creatList(list,len); Solution ans; printList(ans.removeNthFromEnd(head,2)); return 0; } //插入链表,头插,无头结点 void insertList(ListNode* &head,int x){ ListNode *p=new ListNode(x); if(head==nullptr){ head=p; } else{ p->next=head; head=p; } } //打印链表 void printList(ListNode *head){ if(head==nullptr){ //空链表输出空 printf("NULL\n"); return; } while(head){ printf("%d ",head->val); head=head->next; } putchar('\n'); } //获取链表长度 int getLenght(ListNode* head){ int len=0; while(head){ len++; head=head->next; } return len; } //根据一个数组序列,使用头插创建链表,需要知道元素个数 ListNode *creatList(int a[],int n){ ListNode *head=nullptr; if(n>0) reverse(a,a+n); //头插方法创建的链表是给定序列的逆序,这里提前逆置一下 for(int i=0;i<n;i++){ //得到给定序列顺序的链表 insertList(head,a[i]); } return head; }
二叉树类
相比于数组和链表类,二叉树则更麻烦一些,因为二叉树的链式结构在调试过程中很难直观看出树形结构。常见的示例输入,一般都是二叉树的层序遍历序列,我们也无法直接用于函数的调试,想要自己构建二叉树,每次如果都要手动处理则比较麻烦;对于输出而言,常见的结果一般是要求返回数字,数值,或者是一棵处理过的二叉树。对于返回为二叉树的情况,我们能够通过样例测试很容易知道正确与否,但是当出现错误时,我们无法直接知晓中间过程出了什么问题。因此,我编写了将层序序列转化为一个二叉树的方法和可视化输出二叉树树形结构的方法,以供调试时使用样例进行输入,输出时可以使用打印二叉树查看树形结构。
特别说明:由于受到边界条件和输入形式的限制,力扣中给出的序列中空节点使用了null表示,我在程序中使用INT_MAX做了替换,也就是说如果你在填写测试时使用了INT_MAX,则可能出现不可预料的错误,这一点需要注意(一般数值范围的边界条件都能很好的处理,所以我默认不会使用到INT_MAX这样的数值作为自己测试的一部分)。其次,由于显示效果的限制,我将二叉树节点中的数字输出限定了3个字符宽度(同理也使用了3个空格填充了那些没有数字的位置),也就意味着更长的数字可能导致二叉树的结构看起来略微有些不太整齐,再使用时可以根据自己的情况进行调整,我在相应的地方写上了详细的注释。
以226. 翻转二叉树为例,代码模板如下:
#include<bits/stdc++.h> using namespace std; #define null INT_MAX //把力扣给定的null节点定义为int的最大值,用于识别空结点 //二叉树的结构体定义 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; TreeNode *CreatTree(vector<int> &layerorder); //根据给定的层序序列建树的函数 int LayerOfTree(TreeNode *root); //计算树的层数,用于绘制树形 void PrintTreeMatrix(vector<vector<int>> &matrix); //用于打印树形结构专用的二维数组输出函数 void PrintTree(TreeNode *root); //打印树的函数 void PrintMatrix(vector<vector<int>> matrix); //打印一般二维数组的函数 //////////////////// 在这里放入Solution类 ///////////////////////// ///////////////类开始 class Solution { public: TreeNode *invertTree(TreeNode *root) { if (root == NULL) return root; swap(root->left, root->right); root->right = invertTree(root->right); root->left = invertTree(root->left); return root; } }; ///////////////类结束 int main(){ //树的各种序列 //树的各种序列 vector<int> layerorder={4,2,7,1,3,6,9}; vector<int> preoder={}; vector<int> inorder={}; vector<int> postorder={}; vector<vector<int>> matrix; //建树并打印树,可以使用建树来为自己的函数提供输入 TreeNode *root=CreatTree(layerorder); Solution mysolution; //---此处调用你的方法---// root=mysolution.invertTree(root); //可以打印树,查看其树形结构 PrintTree(root); return 0; } TreeNode *CreatTree(vector<int> &layerorder){ //根据层序序列建树 int n=layerorder.size(); if(n==0) return nullptr; //计算序列元素个数,如果空树返回空指针 queue<TreeNode*> q; TreeNode *root=new TreeNode(layerorder[0]); //创建根结点并入队 q.push(root); for(int i=0;i<=(n-1)/2;i++){ //只需处理第一个结点到最后一个非叶子结点 if(layerorder[i]==null) continue; //如果是空结点则跳过 TreeNode* now=q.front(); //从队列中取出当前结点 q.pop(); int left=2*i+1,right=2*(i+1); //计算当前结点的左右孩子的位置 if(left<n&&layerorder[left]!=null){ //如果左孩子存在且不为空时创建左孩子结点并入队 now->left=new TreeNode(layerorder[left]); q.push(now->left); } if(right<n&&layerorder[right]!=null){ //如果右孩子存在且不为空时创建右孩子结点并入队 now->right=new TreeNode(layerorder[right]); q.push(now->right); } } return root; //返回创建好的树 } int LayerOfTree(TreeNode *root){ //层序遍历获取树高 if(root==nullptr) return 0; int layer=0; queue<TreeNode*> q; q.push(root); while(!q.empty()){ layer++; int size=q.size(); for(int i=0;i<size;i++){ TreeNode* now=q.front(); q.pop(); if(now->left) q.push(now->left); if(now->right) q.push(now->right); } } return layer; } void PrintTreeMatrix(vector<vector<int>> &matrix){ //打印填充了树形结构的二维数组 int row=0,col=0; row=matrix.size(); string flag=string(3,' '); //空白位置使用3个空格占用 if(row) col=matrix[0].size(); for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ if(j) putchar(' '); if(matrix[i][j]==null) cout<<flag; //如果是空节点则打印空字符 else printf("%3d",matrix[i][j]); //否则输出三个字符宽度的数字 } cout<<string(2,'\n'); //增大行距以避免树形看起来太扁 } } void PrintTree(TreeNode *root){ //根据树形填充一个二维数组 if(root==nullptr){ //如果是空树则只输出NULL puts("NULL");return; } struct node{ //每一个节点对应二维数组中的一个坐标 int x,y; node(){} node(int x_,int y_):x(x_),y(y_){} }; unordered_map<TreeNode*,node> mp; //节点指针和二维数组坐标的对应关系 int layer=LayerOfTree(root); //获取树高 int rol=(1<<layer)-1; //按照满二叉树的最后一行数量计算(每个元素中间用空格分开,共为奇数个空位) vector<vector<int>> matrix(layer,vector<int>(rol,null)); //用于填充的二维数组,用INT_MAX初始化 int offset=1<<(layer-2); //偏移量,根的孩子与根节点的坐标偏移量为1<<(layer-2) queue<TreeNode*> q; //以层序遍历的方式填充 q.push(root); int i=0,j=rol/2; //根节点所在的坐标为第一行的中间 mp[root]=node(i,j); //填充并记录坐标 matrix[i][j]=root->val; while(!q.empty()){ //层序遍历 int size=q.size(); for(int k=0;k<size;k++){ TreeNode *now=q.front(); q.pop(); i=mp[now].x, j=mp[now].y; //获取队头元素的坐标 if(now->left){ //如果左孩子存在,则左孩子入队并填充 q.push(now->left); int tempi=i+1,tempj=j-offset; //左孩子位于下一行,并且向左偏移 matrix[tempi][tempj]=now->left->val; mp[now->left]=node(tempi,tempj); } if(now->right){ //右孩子同理 q.push(now->right); int tempi=i+1,tempj=j+offset; //右孩子位于下一行,并且向右偏移 matrix[tempi][tempj]=now->right->val; mp[now->right]=node(tempi,tempj); } } offset>>=1; //偏移量每次减半 } PrintTreeMatrix(matrix); //打印最后的结果 return; } void PrintMatrix(vector<vector<int>> matrix){ //用于打印二维数组的函数 int row=0,col=0; row=matrix.size(); if(row) col=matrix[0].size(); for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ if(j) putchar(' '); cout<<matrix[i][j]; } printf("\n"); } }