数据结构-算法学习C++（入门）

数据结构和算法-左神

03二进制和位运算

04 选择、冒泡、插入排序

// 交换数组中的两个元素
void swap(int arr[], int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;
}void printarr(int arr[], int n) {for (int i = 0; i < n; i++) {cout << arr[i] << " ";}cout << endl;
}// 选择排序
void selectionSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}swap(arr, i, minIndex);}
}// 冒泡排序
void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);}}}
}// 插入排序
void insertionSort(int arr[], int n) {if (arr == nullptr || n < 2) {return;}for (int i = 1; i < n; i++) {for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {swap(arr, j, j + 1);// printarr(arr, n); // 打印当前数组状态}}
}

05 对数器

对数器：实验器，对与两种针对同一种问题的算法进行验证，以判断缩写代码是否正确（提出一易一难进行对比）

// 生成随机数组
vector<int> randomArray(int n, int v) {vector<int> arr(n);for (int i = 0; i < n; i++) {arr[i] = rand() % v + 1; // 生成 [1, v] 范围内的随机整数}return arr;
}// 复制数组
vector<int> copyArray(const vector<int>& arr) {return arr; // 直接返回一个副本
}// 比较两个数组是否相同
bool sameArray(const vector<int>& arr1, const vector<int>& arr2) {return arr1 == arr2; // 使用 vector 的比较运算符
}// 主函数
int main() {// 随机数组最大长度int N = 10;// 随机数组每个值，在1~V之间等概率随机int V = 10;// 测试次数int testTimes = 5;srand(time(0)); // 初始化随机数种子cout << "测试开始" << endl;for (int i = 0; i < testTimes; i++) {// 随机得到一个长度，长度在[0~N-1]int n = rand() % N;// 得到随机数组vector<int> arr = randomArray(n, V);vector<int> arr1 = copyArray(arr);vector<int> arr2 = copyArray(arr);vector<int> arr3 = copyArray(arr);// 转换为普通数组int* arr1_ptr = arr1.data();int* arr2_ptr = arr2.data();int* arr3_ptr = arr3.data();// 排序selectionSort(arr1_ptr, n);bubbleSort(arr2_ptr, n);insertionSort(arr3_ptr, n);// 比较结果if (!sameArray(arr1, arr2) || !sameArray(arr1, arr3)) {cout << "出错了!" << endl;// 打印出错的数组cout << "原始数组: ";for (int num : arr) {cout << num << " ";}cout << endl;cout << "选择排序结果: ";for (int num : arr1) {cout << num << " ";}cout << endl;cout << "冒泡排序结果: ";for (int num : arr2) {cout << num << " ";}cout << endl;cout << "插入排序结果: ";for (int num : arr3) {cout << num << " ";}cout << endl;return 1; // 退出程序}}cout << "测试结束" << endl;return 0;
}

上述是对三种排序算法的检测，如果报错可通过调整数组长度和数据大小，选择容易的数组进行测验，以解决报错

06 二分搜索

1）在有序数组中确定num存在还是不存在
2）在有序数组中找>=num的最左位置
3）在有序数组中找<=num的最右位置
4）二分搜索不一定发生在有序数组上（比如寻找峰值问题）
如果数组长度为n，那么二分搜索搜索次数是log n次，以2为底

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>using namespace std;// 生成随机数组
vector<int> randomArray(int n, int v) {vector<int> arr(n);for (int i = 0; i < n; i++) {arr[i] = rand() % v + 1; // 生成 [1, v] 范围内的随机整数}return arr;
}// 暴力解法：遍历数组查找数字
bool right(const vector<int>& sortedArr, int num) {for (int cur : sortedArr) {// 遍历数组if (cur == num) {return true;}}return false;
}// 二分查找：在有序数组(从小到大)中查找数字
bool exist(const vector<int>& arr, int num) {if (arr.empty()) {return false;}int l = 0, r = arr.size() - 1, m = 0;while (l <= r) {m = (l + r) / 2;//m=l+(r-l)/2; // 防止溢出if (arr[m] == num) {return true;} else if (arr[m] > num) {r = m - 1;} else {l = m + 1;}}return false;
}
int findleft(const vector<int>& arr, int num) {int l = 0, r = arr.size() - 1,m=0;int ans=-1;while (l <= r) {m = (l + r) / 2;if (arr[m] >= num) {ans=m; // 记录当前的左边界r = m - 1; // 继续向左查找} else {l = m + 1;}}return ans; // 返回左边界
}int findright(const vector<int>& arr, int num) {int l = 0, r = arr.size() - 1,m=0;int ans=-1;while (l <= r) {m = (l + r) / 2;if (arr[m] <= num) {ans=m; // 记录当前的右边界l = m + 1; // 继续向右查找} else {r = m - 1;}}return ans; // 返回右边界
}int findpeak(const vector<int>& arr) {int  n = arr.size() - 1;if(arr.size() == 0) {return -1; // 数组为空}if (arr[0] > arr[1]) {return 0; // 第一个元素是峰值}if (arr[n] > arr[n - 1]) {return n; // 最后一个元素是峰值}int l=1,r=n-1,m=0,ans=-1;while (l <= r) {m = (l + r) / 2;if (arr[m] < arr[m + 1]) {l = m + 1;} else if (arr[m] < arr[m - 1]) {r = m - 1;}else {ans = m; // 找到峰值break;}}return ans;
}// 主函数
int main() {// 随机数组最大长度int N = 100;// 随机数组每个值，在1~V之间等概率随机int V = 1000;// 测试次数int testTime = 500000;srand(time(0)); // 初始化随机数种子cout << "测试开始" << endl;for (int i = 0; i < testTime; i++) {// 随机得到一个长度，长度在[0~N-1]int n = rand() % N;// 得到随机数组vector<int> arr = randomArray(n, V);// 排序sort(arr.begin(), arr.end());// 随机生成一个数字int num = rand() % V + 1;// 比较暴力解法和二分查找的结果if (right(arr, num) != exist(arr, num)) {cout << "出错了!" << endl;// 打印出错的数组和数字cout << "数组: ";for (int x : arr) {cout << x << " ";}cout << endl;cout << "查找数字: " << num << endl;return 1; // 退出程序}}cout << "测试结束" << endl;return 0;
}

07 时间复杂度和空间复杂度

复杂度解释

时间复杂度：常数操作（固定时间的操作、执行时间和数据量无关）的次数，只关注最高阶项；针对固定流程，计算最差情况，对于随机行为，选择平均或者期望的时间复杂度；仅根据代码结构无法判断时间复杂度，需要通过算法流程进行判断。

08 算法和数据结构

硬计算类算法、软计算类算法：
硬计算类算法：精确求解。但是某些问题使用硬计算类的算法，可能会让计算的复杂度较高（大厂算法和数据结构笔试、面试题、acm比赛或者和acm形式类似的比赛，考察的都是硬计算类算法）
软计算类算法：更注重逼近解决问题，而不是精确求解。计算时间可控（比如：模糊逻辑、神经网络、进化计算、概率理论、混沌理论、支持向量机、群体智能）

硬计算类算法是所有程序员岗位都会考、任何写代码的工作都会用到的。前端、后端、架构、算法所有岗位都要用到。
但是算法工程师除了掌握硬计算类的算法之外，还需要掌握软计算类的算法。

09 单双链表

09.1单双链表及反转

#include <iostream>
using namespace std;// 单链表节点
class ListNode {
public:int val;ListNode* next;// 构造函数：初始化节点值，下一个节点为 nullptrListNode(int val) : val(val), next(nullptr) {}// 构造函数初始化 val 和 next;或如下放在函数体里// ListNode(int val) {//     this->val = val; // 使用 this 指针访问成员变量//     this->next = nullptr;// }ListNode(int val, ListNode* next) : val(val), next(next) {}
};// 双链表节点
class DoubleListNode {
public:int value;DoubleListNode* last;DoubleListNode* next;DoubleListNode(int v) : value(v), last(nullptr), next(nullptr) {}
};// 反转单链表
static ListNode* reverseList(ListNode* head) {ListNode* pre = nullptr;ListNode* next = nullptr;while (head != nullptr) {next = head->next;head->next = pre;pre = head;head = next;}return pre;}// 反转双链表
static DoubleListNode* reverseDoubleList(DoubleListNode* head) {DoubleListNode* pre = nullptr;DoubleListNode* next = nullptr;while (head != nullptr) {next = head->next;head->next = pre;head->last = next;pre = head;head = next;}return pre;}// 打印链表
void printList(ListNode* head) {ListNode* current = head;while (current != nullptr) {cout << current->val << " -> ";current = current->next;}cout << "nullptr" << endl;
}// 主函数
int main() {// 创建链表 1 -> 2 -> 3 -> nullptrListNode* head = new ListNode(1);head->next = new ListNode(2);head->next->next = new ListNode(3);// 打印链表cout << "链表内容: ";printList(head);ListNode* reversedHead = reverseList(head);cout << "反转后的链表内容: ";printList(reversedHead);// 释放链表内存ListNode* current = reversedHead;while (current != nullptr) {ListNode* temp = current;current = current->next;delete temp;}return 0;
}

09.2合并链表

测试链接

#include <iostream>// 定义链表节点结构
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* next) : val(x), next(next) {}
};// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* head1, ListNode* head2) {if (head1 == nullptr || head2 == nullptr) {return head1 == nullptr ? head2 : head1;}ListNode* head = head1->val <= head2->val ? head1 : head2;ListNode* cur1 = head->next;ListNode* cur2 = head == head1 ? head2 : head1;ListNode* pre = head;while (cur1 != nullptr && cur2 != nullptr) {if (cur1->val <= cur2->val) {pre->next = cur1;cur1 = cur1->next;} else {pre->next = cur2;cur2 = cur2->next;}pre = pre->next;}pre->next = cur1 != nullptr ? cur1 : cur2;return head;
}// 辅助函数：打印链表
void printList(ListNode* head) {while (head != nullptr) {std::cout << head->val << " -> ";head = head->next;}std::cout << "nullptr" << std::endl;
}int main() {// 创建两个链表ListNode* head1 = new ListNode(1, new ListNode(3, new ListNode(5)));ListNode* head2 = new ListNode(2, new ListNode(4, new ListNode(6)));std::cout << "List 1: ";printList(head1);std::cout << "List 2: ";printList(head2);// 合并链表ListNode* mergedHead = mergeTwoLists(head1, head2);std::cout << "Merged List: ";printList(mergedHead);// 释放链表内存（可选）while (mergedHead != nullptr) {ListNode* temp = mergedHead;mergedHead = mergedHead->next;delete temp;}return 0;
}

09.2两数相加

给你两个 非空 的链表，表示两个非负的整数
它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头

测试链接

#include <iostream>// 定义链表节点结构
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* next) : val(x), next(next) {}
};// 实现两个链表数字相加
ListNode* addTwoNumbers(ListNode* h1, ListNode* h2) {ListNode* ans = nullptr; // 用于存储结果链表的头节点ListNode* cur = nullptr; // 用于构建结果链表的当前节点int carry = 0; // 进位for (int sum, val; // 声明变量h1 != nullptr || h2 != nullptr; // 终止条件h1 = (h1 == nullptr ? nullptr : h1->next), // 每一步 h1 的跳转h2 = (h2 == nullptr ? nullptr : h2->next) // 每一步 h2 的跳转) {// 计算当前位的和，包括进位sum = (h1 == nullptr ? 0 : h1->val) + (h2 == nullptr ? 0 : h2->val) + carry;val = sum % 10; // 当前位的值carry = sum / 10; // 更新进位// 构建结果链表if (ans == nullptr) {ans = new ListNode(val);cur = ans;} else {cur->next = new ListNode(val);cur = cur->next;}}// 如果最后还有进位，追加一个新节点if (carry == 1) {cur->next = new ListNode(1);}return ans;
}// 辅助函数：打印链表
void printList(ListNode* head) {while (head != nullptr) {std::cout << head->val << " -> ";head = head->next;}std::cout << "nullptr" << std::endl;
}int main() {// 创建两个链表表示的数字ListNode* h1 = new ListNode(2, new ListNode(4, new ListNode(3))); // 表示数字 342ListNode* h2 = new ListNode(5, new ListNode(6, new ListNode(4))); // 表示数字 465std::cout << "List 1: ";printList(h1);std::cout << "List 2: ";printList(h2);// 计算两个链表数字的和ListNode* result = addTwoNumbers(h1, h2);std::cout << "Sum List: ";printList(result);// 释放链表内存（可选）while (h1 != nullptr) {ListNode* temp = h1;h1 = h1->next;delete temp;}while (h2 != nullptr) {ListNode* temp = h2;h2 = h2->next;delete temp;}while (result != nullptr) {ListNode* temp = result;result = result->next;delete temp;}return 0;
}

09.2分隔链表

给你一个链表的头节点 head 和一个特定值 x
请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置

测试链接

#include <iostream>// 定义链表节点结构
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* next) : val(x), next(next) {}
};// 实现链表分区操作
ListNode* partition(ListNode* head, int x) {ListNode* leftHead = nullptr; // < x 的区域ListNode* leftTail = nullptr;ListNode* rightHead = nullptr; // >= x 的区域ListNode* rightTail = nullptr;ListNode* next = nullptr;while (head != nullptr) {next = head->next; // 保存下一个节点head->next = nullptr; // 断开当前节点的连接if (head->val < x) {if (leftHead == nullptr) {leftHead = head;} else {leftTail->next = head;}leftTail = head;} else {if (rightHead == nullptr) {rightHead = head;} else {rightTail->next = head;}rightTail = head;}head = next; // 移动到下一个节点}if (leftHead == nullptr) {return rightHead; // 如果没有小于 x 的节点，直接返回右分区的头节点}// 将左分区的尾部连接到右分区的头部leftTail->next = rightHead;return leftHead; // 返回左分区的头节点
}// 辅助函数：打印链表
void printList(ListNode* head) {while (head != nullptr) {std::cout << head->val << " -> ";head = head->next;}std::cout << "nullptr" << std::endl;
}int main() {// 创建一个链表：1 -> 4 -> 3 -> 2 -> 5 -> 2ListNode* head = new ListNode(1, new ListNode(4, new ListNode(3, new ListNode(2, new ListNode(5, new ListNode(2))))));std::cout << "Original List: ";printList(head);// 分区操作，x = 3ListNode* partitionedHead = partition(head, 3);std::cout << "Partitioned List: ";printList(partitionedHead);// 释放链表内存（可选）while (partitionedHead != nullptr) {ListNode* temp = partitionedHead;partitionedHead = partitionedHead->next;delete temp;}return 0;
}

013队列、栈、环形队列

013.1队列

Queue1：使用queue容器进行

#include <queue>
#include <iostream>class Queue1 {
private:std::queue<int> queue; // 使用C++ STL中的queue容器public:// 判断队列是否为空bool isEmpty() {return queue.empty();}// 向队列中加入元素，加到队尾void offer(int num) {queue.push(num);}// 从队列中取出元素，从队头取出int poll() {if (queue.empty()) {throw std::out_of_range("Queue is empty"); // 如果队列为空，抛出异常}int front = queue.front(); // 获取队头元素queue.pop(); // 弹出队头元素return front;}// 返回队列头的元素，但不弹出int peek() {if (queue.empty()) {throw std::out_of_range("Queue is empty"); // 如果队列为空，抛出异常}return queue.front();}// 返回队列中元素的数量int size() {return queue.size();}
};int main() {Queue1 q;q.offer(1);q.offer(2);q.offer(3);std::cout << "Queue size: " << q.size() << std::endl; // 输出队列大小std::cout << "Front element: " << q.peek() << std::endl; // 输出队头元素std::cout << "Poll element: " << q.poll() << std::endl; // 弹出队头元素std::cout << "Queue size after poll: " << q.size() << std::endl; // 输出队列大小return 0;
}

queue2：使用数组，但是还是还是利用容器模拟数组

#include <iostream>
#include <vector>class Queue2 {
public:std::vector<int> queue;int l;int r;// 构造函数，初始化队列大小Queue2(int n) : queue(n, 0), l(0), r(0) {}// 判断队列是否为空bool isEmpty() {return l == r;}// 向队列中加入元素void offer(int num) {if (r >= queue.size()) {throw std::out_of_range("Queue is full"); // 如果队列已满，抛出异常}queue[r++] = num;}// 从队列中移除元素int poll() {if (isEmpty()) {throw std::out_of_range("Queue is empty"); // 如果队列为空，抛出异常}return queue[l++];}// 返回队列头部的元素int head() {if (isEmpty()) {throw std::out_of_range("Queue is empty"); // 如果队列为空，抛出异常}return queue[l];}// 返回队列尾部的元素int tail() {if (isEmpty()) {throw std::out_of_range("Queue is empty"); // 如果队列为空，抛出异常}return queue[r - 1];}// 返回队列中元素的数量int size() {return r - l;}
};int main() {Queue2 q(5); // 创建一个大小为5的队列q.offer(1);q.offer(2);q.offer(3);std::cout << "Queue size: " << q.size() << std::endl; // 输出队列大小std::cout << "Head element: " << q.head() << std::endl; // 输出队头元素std::cout << "Tail element: " << q.tail() << std::endl; // 输出队尾元素std::cout << "Poll element: " << q.poll() << std::endl; // 弹出队头元素std::cout << "Queue size after poll: " << q.size() << std::endl; // 输出队列大小return 0;
}

013.2栈

stack1：c++中stack容器

#include <iostream>
#include <stack>class Stack1 {
public:std::stack<int> stack;// 判断栈是否为空bool isEmpty() {return stack.empty();}// 向栈中压入一个元素void push(int num) {stack.push(num);}// 从栈中弹出一个元素int pop() {if (stack.empty()) {throw std::out_of_range("Stack is empty"); // 如果栈为空，抛出异常}int top = stack.top(); // 获取栈顶元素stack.pop(); // 弹出栈顶元素return top;}// 返回栈顶元素但不弹出int peek() {if (stack.empty()) {throw std::out_of_range("Stack is empty"); // 如果栈为空，抛出异常}return stack.top();}// 返回栈中元素的数量int size() {return stack.size();}
};int main() {Stack1 s;s.push(1);s.push(2);s.push(3);std::cout << "Stack size: " << s.size() << std::endl; // 输出栈大小std::cout << "Top element: " << s.peek() << std::endl; // 输出栈顶元素std::cout << "Pop element: " << s.pop() << std::endl; // 弹出栈顶元素std::cout << "Stack size after pop: " << s.size() << std::endl; // 输出栈大小return 0;
}

stack2：

#include <iostream>
#include <vector>
#include <stdexcept> // 用于抛出异常class Stack2 {
public:std::vector<int> stack; // 使用 std::vector 来模拟固定大小的数组int size; // 当前栈中的元素个数// 构造函数，初始化栈的大小Stack2(int n) : stack(n, 0), size(0) {}// 判断栈是否为空bool isEmpty() {return size == 0;}// 向栈中压入一个元素void push(int num) {if (size >= stack.size()) {throw std::out_of_range("Stack is full"); // 如果栈已满，抛出异常}stack[size++] = num;}// 从栈中弹出一个元素int pop() {if (isEmpty()) {throw std::out_of_range("Stack is empty"); // 如果栈为空，抛出异常}return stack[--size];}// 返回栈顶元素但不弹出int peek() {if (isEmpty()) {throw std::out_of_range("Stack is empty"); // 如果栈为空，抛出异常}return stack[size - 1];}// 返回栈中元素的数量int size() {return size;}
};int main() {Stack2 s(5); // 创建一个大小为5的栈s.push(1);s.push(2);s.push(3);std::cout << "Stack size: " << s.size() << std::endl; // 输出栈大小std::cout << "Top element: " << s.peek() << std::endl; // 输出栈顶元素std::cout << "Pop element: " << s.pop() << std::endl; // 弹出栈顶元素std::cout << "Stack size after pop: " << s.size() << std::endl; // 输出栈大小return 0;
}

013.3循环队列

#include <iostream>
#include <vector>class MyCircularQueue {
public:std::vector<int> queue; // 使用 std::vector 来模拟数组int l, r, size, limit;  // l: 队列头部指针，r: 队列尾部指针，size: 当前队列大小，limit: 队列容量// 构造函数，初始化循环队列的大小MyCircularQueue(int k) : queue(k, 0), l(0), r(0), size(0), limit(k) {}// 如果队列满了，什么也不做，返回false// 如果队列没满，加入value，返回truebool enQueue(int value) {if (isFull()) {return false;} else {queue[r] = value;// r = (r + 1) % limit; // 循环队列的关键操作：尾指针循环移动r=r==limit-1?0:(r+1);size++;return true;}}// 如果队列空了，什么也不做，返回false// 如果队列没空，弹出头部的数字，返回truebool deQueue() {if (isEmpty()) {return false;} else {// l = (l + 1) % limit; // 循环队列的关键操作：头指针循环移动l=l==limit-1?0:(l+1);size--;return true;}}// 返回队列头部的数字（不弹出），如果没有数返回-1int Front() {if (isEmpty()) {return -1;} else {return queue[l];}}// 返回队列尾部的数字（不弹出），如果没有数返回-1int Rear() {if (isEmpty()) {return -1;} else {int last = (r == 0) ? (limit - 1) : (r - 1); // 循环队列的关键操作：计算尾部索引return queue[last];}}// 判断队列是否为空bool isEmpty() {return size == 0;}// 判断队列是否已满bool isFull() {return size == limit;}
};int main() {MyCircularQueue q(5); // 创建一个大小为5的循环队列q.enQueue(1);q.enQueue(2);q.enQueue(3);std::cout << "Front element: " << q.Front() << std::endl; // 输出队头元素std::cout << "Rear element: " << q.Rear() << std::endl;  // 输出队尾元素std::cout << "Dequeue element: " << q.deQueue() << std::endl; // 弹出队头元素std::cout << "Front element after dequeue: " << q.Front() << std::endl; // 输出队头元素return 0;
}

014栈-队列的相互转换

014.1用栈实现队列

测试链接

#include <iostream>
#include <stack>class MyQueue {
public:std::stack<int> in;  // 用于存储新加入的元素std::stack<int> out; // 用于存储待弹出的元素MyQueue() {// 构造函数，初始化两个栈}// 从 in 栈倒入 out 栈void inToOut() {if (out.empty()) { // 只有当 out 栈为空时，才从 in 栈倒入数据while (!in.empty()) {out.push(in.top());in.pop();}}}// 向队列中加入元素void push(int x) {in.push(x); // 新元素直接压入 in 栈inToOut();  // 立即进行数据倒置，确保 out 栈始终是待弹出的顺序}// 从队列中弹出元素int pop() {inToOut(); // 确保 out 栈有数据int result = out.top(); // 获取 out 栈的栈顶元素out.pop(); // 弹出 out 栈的栈顶元素return result;}// 返回队列头部的元素（不弹出）int peek() {inToOut(); // 确保 out 栈有数据return out.top(); // 返回 out 栈的栈顶元素}// 判断队列是否为空bool empty() {return in.empty() && out.empty(); // 队列为空当且仅当两个栈都为空}
};int main() {MyQueue q;q.push(1);q.push(2);q.push(3);std::cout << "Front element: " << q.peek() << std::endl; // 输出队头元素std::cout << "Pop element: " << q.pop() << std::endl; // 弹出队头元素std::cout << "Front element after pop: " << q.peek() << std::endl; // 输出队头元素std::cout << "Queue is empty: " << (q.empty() ? "true" : "false") << std::endl; // 判断队列是否为空return 0;
}

014.2用队列实现栈

测试链接

#include <iostream>
#include <queue>class MyStack {
public:std::queue<int> queue;MyStack() {// 构造函数，初始化队列}// O(n) 时间复杂度void push(int x) {int n = queue.size();queue.push(x); // 将新元素加入队列for (int i = 0; i < n; i++) {queue.push(queue.front()); // 将队列头部元素移到队尾queue.pop(); // 移除队列头部元素}}int pop() {int result = queue.front(); // 获取队列头部元素queue.pop(); // 移除队列头部元素return result;}int top() {return queue.front(); // 返回队列头部元素}bool empty() {return queue.empty(); // 判断队列是否为空}
};int main() {MyStack stack;stack.push(1);stack.push(2);stack.push(3);std::cout << "Top element: " << stack.top() << std::endl; // 输出栈顶元素std::cout << "Pop element: " << stack.pop() << std::endl; // 弹出栈顶元素std::cout << "Top element after pop: " << stack.top() << std::endl; // 输出栈顶元素std::cout << "Stack is empty: " << (stack.empty() ? "true" : "false") << std::endl; // 判断栈是否为空return 0;
}

015最小栈

测试链接

minstack1：两个栈构成

#include <iostream>
#include <stack>
#include <stdexcept> // 用于抛出异常class MinStack {
public:std::stack<int> data; // 存储所有元素std::stack<int> min;  // 存储当前最小值MinStack() {// 构造函数，初始化两个栈}// 向栈中压入一个元素void push(int val) {data.push(val); // 将元素压入 data 栈if (min.empty() || val <= min.top()) {min.push(val); // 如果 min 栈为空或当前值小于等于 min 栈顶，则压入 min 栈} else {min.push(min.top()); // 否则，将 min 栈顶元素再次压入 min 栈}}// 从栈中弹出一个元素void pop() {if (data.empty()) {throw std::out_of_range("Stack is empty"); // 如果栈为空，抛出异常}data.pop(); // 弹出 data 栈顶元素min.pop();  // 弹出 min 栈顶元素}// 获取栈顶元素int top() {if (data.empty()) {throw std::out_of_range("Stack is empty"); // 如果栈为空，抛出异常}return data.top(); // 返回 data 栈顶元素}// 获取当前栈中的最小值int getMin() {if (min.empty()) {throw std::out_of_range("Stack is empty"); // 如果栈为空，抛出异常}return min.top(); // 返回 min 栈顶元素}
};int main() {MinStack stack;stack.push(3);stack.push(1);stack.push(2);std::cout << "Top element: " << stack.top() << std::endl; // 输出栈顶元素std::cout << "Minimum element: " << stack.getMin() << std::endl; // 输出当前最小值stack.pop();std::cout << "Top element after pop: " << stack.top() << std::endl; // 输出栈顶元素std::cout << "Minimum element after pop: " << stack.getMin() << std::endl; // 输出当前最小值return 0;
}

minstack2：数组构成

#include <iostream>
#include <stdexcept> // 用于抛出异常class MinStack {
public:static const int MAXN = 8001; // 最大容量int data[MAXN];  // 存储栈中的数据int min[MAXN];   // 存储当前栈中的最小值int size;        // 当前栈的大小MinStack() : size(0) {// 构造函数，初始化栈}// 向栈中压入一个元素void push(int val) {if (size >= MAXN) {throw std::out_of_range("Stack overflow"); // 如果栈已满，抛出异常}data[size] = val;if (size == 0 || val <= min[size - 1]) {min[size] = val;} else {min[size] = min[size - 1];}size++;}// 从栈中弹出一个元素void pop() {if (size == 0) {throw std::out_of_range("Stack underflow"); // 如果栈为空，抛出异常}size--;}// 获取栈顶元素int top() {if (size == 0) {throw std::out_of_range("Stack is empty"); // 如果栈为空，抛出异常}return data[size - 1];}// 获取当前栈中的最小值int getMin() {if (size == 0) {throw std::out_of_range("Stack is empty"); // 如果栈为空，抛出异常}return min[size - 1];}
};int main() {MinStack stack;stack.push(3);stack.push(1);stack.push(2);std::cout << "Top element: " << stack.top() << std::endl; // 输出栈顶元素std::cout << "Minimum element: " << stack.getMin() << std::endl; // 输出当前最小值stack.pop();std::cout << "Top element after pop: " << stack.top() << std::endl; // 输出栈顶元素std::cout << "Minimum element after pop: " << stack.getMin() << std::endl; // 输出当前最小值return 0;
}

016双端队列

测试链接

• 使用deque容器

#include <iostream>
#include <deque>class MyCircularDeque {
public:std::deque<int> deque; // 使用 std::deque 作为底层数据结构int size;              // 当前队列的大小int limit;             // 队列的最大容量// 构造函数，初始化队列的最大容量MyCircularDeque(int k) : size(0), limit(k) {}// 在队列前端插入一个元素bool insertFront(int value) {if (isFull()) {return false; // 如果队列已满，返回 false} else {deque.push_front(value); // 在前端插入元素size++;return true;}}// 在队列后端插入一个元素bool insertLast(int value) {if (isFull()) {return false; // 如果队列已满，返回 false} else {deque.push_back(value); // 在后端插入元素size++;return true;}}// 从队列前端删除一个元素bool deleteFront() {if (isEmpty()) {return false; // 如果队列为空，返回 false} else {deque.pop_front(); // 从前端删除元素size--;return true;}}// 从队列后端删除一个元素bool deleteLast() {if (isEmpty()) {return false; // 如果队列为空，返回 false} else {deque.pop_back(); // 从后端删除元素size--;return true;}}// 获取队列前端的元素int getFront() {if (isEmpty()) {return -1; // 如果队列为空，返回 -1} else {return deque.front(); // 返回前端元素}}// 获取队列后端的元素int getRear() {if (isEmpty()) {return -1; // 如果队列为空，返回 -1} else {return deque.back(); // 返回后端元素}}// 判断队列是否为空bool isEmpty() {return size == 0;}// 判断队列是否已满bool isFull() {return size == limit;}
};int main() {MyCircularDeque deque(5); // 创建一个容量为 5 的循环双端队列deque.insertFront(1);deque.insertLast(2);deque.insertFront(3);deque.insertLast(4);std::cout << "Front element: " << deque.getFront() << std::endl; // 输出前端元素std::cout << "Rear element: " << deque.getRear() << std::endl;   // 输出后端元素deque.deleteFront();deque.deleteLast();std::cout << "Front element after delete: " << deque.getFront() << std::endl; // 输出前端元素std::cout << "Rear element after delete: " << deque.getRear() << std::endl;   // 输出后端元素return 0;
}

• 使用数组

#include <iostream>
#include <vector>class MyCircularDeque {
public:std::vector<int> deque; // 使用 std::vector 作为底层数组int l, r, size, limit;  // l: 队列前端指针，r: 队列后端指针，size: 当前大小，limit: 最大容量// 构造函数，初始化队列MyCircularDeque(int k) : deque(k), l(0), r(0), size(0), limit(k) {}// 在队列前端插入一个元素bool insertFront(int value) {if (isFull()) {return false; // 如果队列已满，返回 false}if (isEmpty()) {l = r = 0; // 如果队列为空，初始化指针} else {l = (l == 0) ? (limit - 1) : (l - 1); // 循环移动前端指针}deque[l] = value; // 插入元素size++;return true;}// 在队列后端插入一个元素bool insertLast(int value) {if (isFull()) {return false; // 如果队列已满，返回 false}if (isEmpty()) {l = r = 0; // 如果队列为空，初始化指针} else {r = (r == limit - 1) ? 0 : (r + 1); // 循环移动后端指针}deque[r] = value; // 插入元素size++;return true;}// 从队列前端删除一个元素bool deleteFront() {if (isEmpty()) {return false; // 如果队列为空，返回 false}l = (l == limit - 1) ? 0 : (l + 1); // 循环移动前端指针size--;return true;}// 从队列后端删除一个元素bool deleteLast() {if (isEmpty()) {return false; // 如果队列为空，返回 false}r = (r == 0) ? (limit - 1) : (r - 1); // 循环移动后端指针size--;return true;}// 获取队列前端的元素int getFront() {if (isEmpty()) {return -1; // 如果队列为空，返回 -1}return deque[l]; // 返回前端元素}// 获取队列后端的元素int getRear() {if (isEmpty()) {return -1; // 如果队列为空，返回 -1}return deque[r]; // 返回后端元素}// 判断队列是否为空bool isEmpty() {return size == 0;}// 判断队列是否已满bool isFull() {return size == limit;}
};int main() {MyCircularDeque deque(5); // 创建一个容量为 5 的循环双端队列deque.insertFront(1);deque.insertLast(2);deque.insertFront(3);deque.insertLast(4);std::cout << "Front element: " << deque.getFront() << std::endl; // 输出前端元素std::cout << "Rear element: " << deque.getRear() << std::endl;   // 输出后端元素deque.deleteFront();deque.deleteLast();std::cout << "Front element after delete: " << deque.getFront() << std::endl; // 输出前端元素std::cout << "Rear element after delete: " << deque.getRear() << std::endl;   // 输出后端元素return 0;
}

017二叉树实现

先序：任何子树先中后左再右；
中序：左中右；
后序：左右中

017.1递归实现

1、递归序

#include <iostream>// 定义二叉树节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};// 递归函数，用于遍历二叉树
void f(TreeNode* head) {if (head == nullptr) {return;}// 1：第一次到所在节点f(head->left); // 递归遍历左子树// 2：第二次到所在节点f(head->right); // 递归遍历右子树// 3：第三次到所在节点
}// 辅助函数：创建一个简单的二叉树
TreeNode* createTree() {TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);root->right->left = new TreeNode(6);root->right->right = new TreeNode(7);return root;
}// 辅助函数：释放二叉树内存
void deleteTree(TreeNode* root) {if (root == nullptr) {return;}deleteTree(root->left);deleteTree(root->right);delete root;
}

按照递归序，上述顺序为：1，2，4，4，4，2，5，5，5，2，1，3，6，6，6，3，7，7，7，3，1；可以看出在每个节点都经过三次。之后的先序、中序、后序可以看作在递归序中的三次停靠分别打印所在节点。

时间复杂度O(n)，额外空间复杂度O(h)，h是二叉树的高度；

2、先序

// 前序遍历：递归版
void preOrder(TreeNode* head) {if (head == nullptr) {return;}std::cout << head->val << " "; // 访问当前节点preOrder(head->left);          // 递归遍历左子树preOrder(head->right);         // 递归遍历右子树
}

3、中序

// 中序遍历：递归版
void inOrder(TreeNode* head) {if (head == nullptr) {return;}inOrder(head->left);           // 递归遍历左子树std::cout << head->val << " "; // 访问当前节点inOrder(head->right);          // 递归遍历右子树
}

4、后序

// 后序遍历：递归版
void posOrder(TreeNode* head) {if (head == nullptr) {return;}posOrder(head->left);          // 递归遍历左子树posOrder(head->right);         // 递归遍历右子树std::cout << head->val << " "; // 访问当前节点
}

017.2 非递归实现

先序测试链接
中序测试链接

1.先序、中序

#include <iostream>
#include <stack>// 定义二叉树节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};// 先序遍历：非递归版
void preOrder(TreeNode* head) {if (head != nullptr) {std::stack<TreeNode*> stack; // 使用 std::stack 来模拟递归stack.push(head);while (!stack.empty()) {head = stack.top(); // 获取栈顶元素stack.pop();        // 弹出栈顶元素std::cout << head->val << " "; // 访问当前节点// 先将右子节点入栈（如果存在）if (head->right != nullptr) {stack.push(head->right);}// 再将左子节点入栈（如果存在）if (head->left != nullptr) {stack.push(head->left);}}std::cout << std::endl;}
}// 中序遍历：非递归版
void inOrder(TreeNode* head) {if (head != nullptr) {std::stack<TreeNode*> stack; // 使用 std::stack 来模拟递归while (!stack.empty() || head != nullptr) {// 将当前节点的所有左子节点压入栈while (head != nullptr) {stack.push(head);head = head->left;}// 弹出栈顶节点并访问head = stack.top();stack.pop();std::cout << head->val << " ";// 转向右子节点head = head->right;}std::cout << std::endl;}
}// 辅助函数：创建一个简单的二叉树
TreeNode* createTree() {TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);root->right->left = new TreeNode(6);root->right->right = new TreeNode(7);return root;
}// 辅助函数：释放二叉树内存
void deleteTree(TreeNode* root) {if (root == nullptr) {return;}deleteTree(root->left);deleteTree(root->right);delete root;
}int main() {TreeNode* root = createTree(); // 创建一个简单的二叉树std::cout << "PreOrder (Non-Recursive): ";preOrder(root); // 非递归先序遍历std::cout << "inOrder (Non-Recursive): ";inOrder(root); // 非递归先序遍历deleteTree(root); // 释放二叉树内存return 0;
}

2.后序

测试链接

• 使用两个栈

#include <iostream>
#include <stack>struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};void posOrderTwoStacks(TreeNode* head) {if (head != nullptr) {std::stack<TreeNode*> stack; // 用于模拟递归std::stack<TreeNode*> collect; // 用于收集节点stack.push(head);while (!stack.empty()) {head = stack.top();stack.pop();collect.push(head);if (head->left != nullptr) {stack.push(head->left);}if (head->right != nullptr) {stack.push(head->right);}}while (!collect.empty()) {std::cout << collect.top()->val << " ";collect.pop();}std::cout << std::endl;}
}

• 使用一个栈

void posOrderOneStack(TreeNode* h) {if (h != nullptr) {std::stack<TreeNode*> stack;stack.push(h);TreeNode* lastPrinted = nullptr; // 上一次打印的节点while (!stack.empty()) {TreeNode* cur = stack.top();if (cur->left != nullptr && lastPrinted != cur->left && lastPrinted != cur->right) {// 有左子树且左子树未处理stack.push(cur->left);} else if (cur->right != nullptr && lastPrinted != cur->right) {// 有右子树且右子树未处理stack.push(cur->right);} else {// 左子树和右子树都已处理或不存在std::cout << cur->val << " ";lastPrinted = stack.top();stack.pop();}}std::cout << std::endl;}
}