澪贰

双链表接口实现这次我们实现的是带头双向循环的链表，不仅有指向前一个节点的prev指针，还有指向下一个节点的next指针，最后一个节点有指向开头的指针next，开头的节点有指向结尾的指针prev，形成循环 双链表定义： 12345678typedef int LTDataType;typedef struct ListNode{ struct ListNode* next; struct ListNode* prev; LTDataType data;}LTNode; 有人问为什么每次都要重新定义数据类型，因为每次的节点数据类型不一定是一样的，定义一下方便修改所有地方的数据类型 双链表节点创建12345678910111213LTNode* BuyListNode(LTDataType x){ LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); return...

链表概念及结构 链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 链式结构的逻辑一般是连续的，但是在物理存储上不一定是连续的，因为每个节点都是从堆上申请来的，从堆上申请的空间要根据实际情况分配空间，两次申请可能是连续的也有可能不是连续的 简单来说，每个节点都存储了下一个节点的地址，即能找到下一个节点，就形成了链表 我们还需要了解几个概念： 🚩头结点 图中的plist就是头结点，位于链表的起始位置，但不存储实际的有效数据(有效数据指的是结构体的内的数据，而不是结构体地址)，主要作用是作为链表的入口，通过它的指针域来指向链表中的第一个实际存储数据的节点 🚩首节点 首节点就是跟在头节点后的链表中第一个存储实际有效数据的节点 🚩哨兵位 哨兵位和头结点类似，通常不存储实际数据，存储地址，哨兵位可以看成一个灵活的节点，可以在链表任何位置方便进行增删查改操作 每个节点的结构体： 1234567typedef int SLTDataType;typedef struct...

线性表 线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。 顺序表概念及结构 顺序表是线性表的一种存储方式，它是用一组连续的存储单元依次存储线性表的数据元素。简单来说，就像是把线性表中的元素一个挨着一个地放在数组中进行增删查改工作，就像在一排连续的小格子里存放东西一样 静态顺序表123456789typedef int SLDataType;//静态开辟（不推荐）#define N 7typedef struct SeqList{ SLDataType array[N];//指向动态开辟的数组 int...

数据结构介绍什么是数据结构？ 数据结构指相互之间存在一种或多种特定关系的数据元素的集合。简单来说，就是组织和存储数据的方式，让数据能被高效地访问、修改、增删...

概念解析🚩什么是分治-快排？ 分治是核心思想，即将大问题拆解成形式相同的小问题来处理，从待排序数组里挑出一个元素当作基准，设置两个指针，一个从数组开头，一个从末尾出发，先把一个无序的数组划分成两个子数组，接着分别处理这两个子数组，随着递归深入，子数组越来越小，最终每个子数组只剩 1 个元素时，天然有序，整个大数组也就完成排序 颜色分类✏️题目描述： ✏️示例： 传送门：颜色分类 题解: 对于排序的题目，根据前些的学习我们一般都是想到冒泡排序等基础算法，但是此类算法对于带有重复性的排序很不友好，还是太慢了，因此对于这道题，也是一道经典的荷兰国旗问题，使用类似双指针算法中的移动零那道题的方法，划分区间比较排序，衍生出来了一种三划分排序算法，也叫作快速排序 💻第一步： 首先我们这题要排序的是0、1、2三个数字，所以划分为三个区间，分别是小于1的区间，等于1的区间，大于1的区间。left表示标记左区间的指针，i表示扫描区间指针，right表示标记右区间的指针 💻第二步： 前提条件left = -1, right =...

概念解析🚩什么是模拟算法？ 简单来说就是照葫芦画瓢，题目说啥就照着写代码就行，所以很考察代码能力 替换所有的问号✏️题目描述： ✏️示例： 传送门：替换所有的问号 题解: 这题很简单，显然是先遍历一遍数组，然后在遍历的时候，如果遇到？就替换为与该位置前后都不相同的数，所以也要对要替换的数遍历一遍，直到发现合适的数 💻细节问题： 注意边界情况，没有两个相邻的数 💻代码实现： 1234567891011121314151617181920212223242526#include <iostream>#include <vector>using namespace std;class Solution {public: string modifyString(string s) { for (int i = 0; i < s.size(); ++i) { if (s[i] == '?') ...

常见位运算总结基础位运算符号这六个位运算符是实现位运算算法的重要运算符，在C语言阶段有详细的介绍过 传送门：关于我、重生到500年前凭借C语言改变世界科技vlog.10——进制转化&&操作符进阶 记法如图所示，强调一下什么是无进位相加？ 异或运算的规则决定了它天然契合无进位相加的概念异或运算在比较两个二进制位时，0 ^ 0 = 0，0 ^ 1 = 1 ，1 ^ 0 = 1， 1 ^ 1 = 0只是单纯对比两个数在每一位上的值，将不同的视为 1，相同的视为 0 ，不涉及向高位进位 给一个数 n，确定它的二进制表示中的第 x 位是 0 还是 1 约定二进制位从右到左，为最低位到最高位，定义为从0到31，为的就是对应右移x位刚好对应第x位。所以将要比较的数 n 的第x位右移x位，与1按位与&，如果是0，第x位为0；如果是1，第x位是1 将一个数 n 的二进制表示的第 x 位修改成 1 要修改数n第x位为1就不能破坏原来的数，所以将1移动x位，与1按位或|，只修改了我们想要修改的那一位 将一个数 n...

山脉数组的峰顶索引✏️题目描述： ✏️示例： 传送门：山脉数组的峰顶索引 题解:💻第一步： 首先确定二段性，把顶峰放到左区间还是右区间取决于你自己，会根据取法不同而导致代码不同，但是都能求出顶峰索引，这里我们放到左区间 💻第二步： 按照我们的划分方式，要确保左边区间不会越过分界，右边区间同理，就要用mid和mid-1这种划分方式。如果在左区间，那么mid会有等于峰顶索引，即left = mid；如果在右区间，mid及其后面的值都不可能是峰顶索引，即right = mid - 1 💻细节问题: 对于二分查找进阶模版，如果在if语句的函数体里有减法操作时，那么计算mid的公式就要+1 💻代码实现: 12345678910111213141516171819202122232425#include <iostream>#include <vector>using namespace std;class Solution {public: int...

概念解析s🚩什么是二分查找算法？ 每次比较中间元素，通过判断中间元素与目标元素的大小关系，将搜索区间缩小一半，持续这个过程，直至找到目标元素或者确定目标元素不存在 二分查找的简单模版✏️题目描述： ✏️示例： 传送门：二分查找 题解: 在一个无论是有序还是无序的数列里，一般最先想到的就是暴力解法遍历一遍，然后符合条件则成立，这种方法固然是好用，但是一般在搜索数据的过程中，数据量庞大，O(n)的时间复杂度还是太大了，那么这时候就要使用时间复杂度为O(log n)的二分查找 💻第一步： 二分查找说的就是折中查找，那么二段性就是重要的第一步，找出左右区间不同的地方 比如这题就是 target 的左区间小于它，右区间大于它，根据这个特性不断调整left和right的位置，接下来看一下具体实现 💻第二步： 不断循环算出mid的值，与target作比较，如果大于target，说明mid所指位置及后面的数都不是符合target的数，right = mid - 1；如果小于target，说明mid所指位置及前面的数都不是符合target的数， left = mid +...

水果成篮✏️题目描述： ✏️示例： 传送门：水果成篮 题解: 首先解读题意，简单来说就是找到一个区间，其中的果树种类用数字表示，种类不超过两种，题目默认是能找到至少两种水果，所以求在此前提下能找到的最长区间是多少？ 💻第一步： 或许该题可以使用暴力解法解决，但明显时间复杂度太高无法通过示例因此根据前些题目的经验，由于是找区间，而且要统计种类数量，滑动窗口＋哈希表 💻第二步： 具体的窗口滑动如图所示 先让第一个数据录入，即进窗口，判断不断循环，然后right依次向后移并不断往哈希表录入每个位置种类和更新数据，直到哈希表内的键值对大于2，即种类大于2；此时left减去第一个数据，即出窗口，判断不断循环，然后不断向后移直到哈希表里的一个种类数据变为0，对其进行erase操作减少一个种类，再次开始更新数据 💻代码实现: 1234567891011121314151617181920212223242526272829#include <iostream>#include <vector>#include...