Darlingの妙妙屋

26考研 | 王道 | 数据结构笔记博客总结笔者博客网站 分类: 数据结构 | Darlingの妙妙屋 26考研 | 王道 | 数据结构 | 第一章 数据结构绪论 | Darlingの妙妙屋 26考研 | 王道 | 数据结构 | 第二章 线性表 | Darlingの妙妙屋 26考研 | 王道 | 数据结构 | 第三章 栈和队列 | Darlingの妙妙屋 26考研 | 王道 | 数据结构 | 第四章 串 | Darlingの妙妙屋 26考研 | 王道 | 数据结构 | 第五章 树 | Darlingの妙妙屋 26考研 | 王道 | 数据结构 | 第六章 图 | Darlingの妙妙屋 26考研 | 王道 | 数据结构 | 第七章 查找 | Darlingの妙妙屋 26考研 | 王道 | 数据结构 | 第八章 排序 | Darlingの妙妙屋 CSDN链接 26考研 | 王道 | 数据结构 | 第一章 数据结构绪论_数据结构 王道计算机教育-CSDN博客 26考研 | 王道 |数据结构 | 第二章 线性表-CSDN博客 26考研 | 王道 | 数据结构 | 第三章...

第八章 排序8.0 关于链表能用于链表的： 直接插入排序，冒泡排序，简单选择排序，归并排序 相关题目： 147. 对链表进行插入排序 - 力扣（LeetCode） 148. 排序链表 - 力扣（LeetCode） 148正解是归并排序，但是可以测试写的冒泡直接插入和简单选择排序是否正确 笔者题解： Day109 | 148.排序链表 | 归并排序 | Darlingの妙妙屋 Day108 | 灵神 | 合并两个有序链表 | Darlingの妙妙屋 Day107 | 147.对链表进行插入排序 | 简单选择、冒泡、直接插入 | Darlingの妙妙屋 Day107 | 147.对链表进行插入排序 | 简单选择、冒泡、直接插入-CSDN博客 Day108 | 灵神 | 合并两个有序链表-CSDN博客 Day109 | 灵神 | 148.排序链表 | 归并排序-CSDN博客 8.1 排序的基本概念 排序算法的评价指标：时间复杂度、空间复杂度、稳定性 8.2 插入排序 8.2.1...

Day101 | 灵神 | 二叉树 翻转等价二叉树951.翻转等价二叉树951. 翻转等价二叉树 - 力扣（LeetCode） 思路： 一开始笔者的思路就是判断完当前结点相不相等以后再去判断左右子树相不相等，不相等的话用swap翻转之后再次比较，这样太麻烦了，而且写的时候难免出错 笔者就去评论区找大佬了 大佬的思路是：反正是有限次数的翻转，那么只会有两种情况 情况1：不需要翻转，也就是root1的左子树和root2的左子树相同，右子树和右子树相同 情况2：需要翻转，也就是没有翻转之前root1的左子树和root2的右子树相同，root1的右子树和root2的左子树相同 那我还翻转什么了，直接把这两种情况都递归一下，第一次比较左左和右右，第二次比较左右和右左，只要有一次可以比较成功那就是可以翻转，根本不用什么swap 完整代码： 笔者代码：觉得看着复杂可以看下面的等价代码 1234567891011121314class Solution {public: bool flipEquiv(TreeNode* root1, TreeNode* root2)...

第七章 查找7.1 查找概念 **查找：**在数据集合中寻找满足某种条件的数据元素的过程称为查找。 **查找表(查找结构)：**用于查找的数据集合称为查找表，它由同一类型的数据元素 (或记录)组成。 **关键字：**数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。 对查找表的常⻅操作： 查找符合条件的数据元素 插⼊、删除某个数据元素 只需要进行操作1的是静态查找表 1和2都需要进行的是动态查找表 **查找长度：**在查找运算中，需要对比关键字的次数称为查找长度。 平均查找长度(ASL，Average Search Length)： 所有查找过程中进行关键字的比较次数的平均值。 ASL的数量级反应了查找算法时间复杂度 7.2 顺序查找 **顺序查找，**又叫“线性查找”，通常用于线性表算法。 **思想：**从头到尾遍历 代码实现： 123456789101112typedef struct{ //查找表的数据结构（顺序表） ElemType *elem; //动态数组基址 ...

Day100 | 灵神 | 二叉树 单值二叉树965.单值二叉树965. 单值二叉树 - 力扣（LeetCode） 思路： 笔者的思路是后序遍历传入两参数，一个是节点另一个是单值的值，只要一样就是true，不一样就是false，缺点是如果当然节点已经不满足条件了，还是会处理完左右子树再来处理根节点 也可以先序遍历，就是先判断是不是是不是val，是的话就不处理下面的左右子树了 完整代码： 12345678910111213141516class Solution {public: bool tra(TreeNode *t,int val) { if(t==nullptr) return true; bool l=tra(t->left,val); bool r=tra(t->right,val); if(val!=t->val) return false; return l&&r; } ...

Day99 | 灵神 | 二叉树 二叉树的右视图199.二叉树的右视图199. 二叉树的右视图 - 力扣（LeetCode） 思路： 笔者的思路并不敏捷，所以第一时间只能想到层序遍历，然后把每层的最后一个给放到数组里面去 灵神的思路： 按照根右左的顺序遍历，只要当前结点的深度是第一次遍历到，那必然是最右侧的节点 找左视图的话那肯定就是根左右的顺序遍历了 完整代码： 1234567891011121314151617181920212223242526class Solution {public: vector<int> rightSideView(TreeNode* root) { vector<int> res; if(root==nullptr) return res; queue<TreeNode*> q; q.push(root); while(!q.empty()) { ...

Day98 | 灵神 | 二叉树 平衡二叉树110.平衡二叉树110. 平衡二叉树 - 力扣（LeetCode） 思路： 笔者的思路： 就是左右子树高度差不超过1 那就算左子树和右子树高度然后相减，如果超过1就把标记flag变为false即可 灵神的思路： 灵神是失败就返回-1而不使用flag标记 如果最后返回的结果不是-1，那就是true，是的话就是false 完整代码： 笔者的 123456789101112131415161718class Solution {public: bool flag=true; int get_depth(TreeNode* t) { if(t==nullptr) return 0; int l=get_depth(t->left)+1; int r=get_depth(t->right)+1; if(abs(l-r)>1) flag=false; return...

Day97 | 灵神 | 二叉树 对称二叉树101.对称二叉树101. 对称二叉树 - 力扣（LeetCode） 思路： 和上一题的区别就是在p和q值相同的时候递归遍历的下一棵子树不同 上一题是左子树和左子树，右子树和右子树对比 这一题的对称就是左子树的左子树和右子树的右子树，左子树的右子树和右子树的左子树对比 不同的情况是 1.p为空q不为空 2.p不为空q为空 3.pq值不同 相同的情况是 pq均为空 注：pq值相同不能说明是true，还要看pq的左右子树 完整代码： 123456789101112131415161718192021class Solution {public: bool is(TreeNode *l,TreeNode *r) { if(l==nullptr&&r!=nullptr) return false; else if(l!=nullptr&&r==nullptr) return false; ...

Day96 | 灵神 | 二叉树 相同的树100.相同的树100. 相同的树 - 力扣（LeetCode） 思路： 就是个easy题没啥好说的，就是遍历就行 不同的情况是 1.p为空q不为空 2.p不为空q为空 3.pq值不同 相同的情况是 pq均为空 注：pq值相同不能说明是true，还要看pq的左右子树 完整代码： 12345678910111213141516class Solution {public: bool isSameTree(TreeNode* p, TreeNode* q) { if(p==nullptr&&q!=nullptr) return false; else if(p!=nullptr&&q==nullptr) return false; else if(p==nullptr&&q==nullptr) return true; else...

Day95 | 灵神 | 二叉树 二叉树的垂序遍历987.二叉树的垂序遍历987. 二叉树的垂序遍历 - 力扣（LeetCode） 思路： 这道题是个hard题，emm感觉是个mid题 首先这道题难点不在递归，因为递归完成的任务只是标记每个节点的row和col而已 难在对数据的处理，其实也不难，就是把所有顶点的值记录到三元组里面 第一个元素col，第二个元素row，第三个元素节点的值，按照这三个元素排序就行 按照第一个元素大小排，一样的话看第二个，还一样的话看第三个，最后输出出来就行 完整代码： 笔者用的是map<int,vector<pair<int,int>>> 第一个元素大小的排序在插入map时已经完成，因为map底层是红黑树 那就只需要对col相同的vector<pair<int,int>>排序就好了，直接使用sort sort排序pair就是先看第一个元素大小，一样的话看第二个元素 1234567891011121314151617181920212223242526class Solution...