当前位置: 首页 > news >正文

基础数据结构思路写法记录,便于回顾

重思路非代码。基础的思路搞懂了,变形题目顺着思考基本都能写出来!

二分查找

    int binarySearch(vector<int> &nums, int target) {// write your code hereif (nums.empty()) {return -1;}int start = 0;int end = nums.size() - 1;while (start + 1 < end) {int mid = start + (end - start) / 2;if (nums[mid] >= target) { // 有重复的输出第一个end = mid;} else {start = mid;}/*if (nums[mid] <= target) { // 有重复的输出最后一个start = mid;} else {end = mid;}*/}if (nums[start] == target) {return start;}if (nums[end] == target) {return end;}return -1;}

链表逆序

class Solution {
public:ListNode* reverseList(ListNode* head) {if (head == nullptr || head->next == nullptr) {return head;}// 注意的是先画图, 代码自然就能写出来ListNode* prev = nullptr;ListNode* cur = head;    while (cur != nullptr) {ListNode* tmp = cur->next;cur->next = prev;prev = cur;cur = tmp;}return prev;}
};

二叉树遍历

// 前序
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {if (root == nullptr) {return {};}stack<TreeNode*> s;// s.push(root);vector<int> res;while (!s.empty() || root) {if (root) {res.push_back(root->val);s.push(root);root = root->left;} else {root = s.top();s.pop();root = root->right;}}return res;}
};// 中序
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;if (root == nullptr) {res;}stack<TreeNode*> s;// s.push(root);while (!s.empty() || root) {if (root) {s.push(root);root = root->left;} else {root = s.top();res.push_back(root->val);s.pop(); root = root->right;}}return res;}
};// 后序
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {if (root == nullptr) {return {};}vector<int> res;stack<TreeNode*> s;while (!s.empty() || root) {if (root) {s.push(root);res.push_back(root->val);root = root->right;} else {root = s.top();s.pop();root = root->left;}}std::reverse(res.begin(), res.end());return res;}
};// 层序
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if (root == nullptr) {return res;}queue<TreeNode*> q;q.push(root);TreeNode split = TreeNode(INT_MAX);q.push(&split);vector<int> layer;while (!q.empty()) {TreeNode *cur = q.front();q.pop();if (cur == &split) {res.push_back(layer);layer.clear(); // 注意别忘记清理if (!q.empty()) {q.push(&split);}} else {layer.push_back(cur->val);if (cur->left) {q.push(cur->left);}if (cur->right) {q.push(cur->right);}}}return res;}
};

N叉树

class Solution {
public:vector<int> preorder(Node* root) {vector<int> res;if (root == nullptr) {return res;}//helper(root, res); // 递归版本stack<Node*> s;s.push(root);while (!s.empty()) {Node* cur = s.top();s.pop();if (cur != nullptr) {res.push_back(cur->val);}std::reverse(cur->children.begin(), cur->children.end());for (auto &node : cur->children) {s.push(node);}}return res;}/*void helper(Node* root, vector<int>& out) {if (root == nullptr) {return;}out.push_back(root->val);for (int i = 0; i < root->children.size(); ++i) {helper(root->children[i], out);}}*/
};

基础排序

/* 归并排序 */// merge
void merge(vector<int>& nums, int low, int high, vector<int>& tmp) {int mid = (low + high) / 2;int leftIndex = low;int rightIndex = mid + 1;int resLeftIndex = leftIndex;while (leftIndex <= mid && rightIndex <= high) {// leftIndex 135 // rightIndex 246// resLeftIndex 123456if (nums[leftIndex] >= nums[rightIndex]) {tmp[resLeftIndex++] = nums[rightIndex++];}else {tmp[resLeftIndex++] = nums[leftIndex++];}}while (leftIndex <= mid) {tmp[resLeftIndex++] = nums[leftIndex++];}while (rightIndex <= high) {tmp[resLeftIndex++] = nums[rightIndex++];}for (int i = low; i <= high; ++i) { // 易错点 <=nums[i] = tmp[i];}
}// 分治
void divideConquer(vector<int>& nums, int low, int high, vector<int>& tmp) {if (low >= high) {return;}// 分而治之divideConquer(nums, low, (high + low) / 2, tmp);divideConquer(nums, (high + low) / 2 + 1, high, tmp);// 合并有序数组merge(nums, low, high, tmp);
}void mergeSort(vector<int>& nums) {if (nums.empty()) {return;}vector<int> tmp(nums.size());divideConquer(nums, 0, nums.size() - 1, tmp);
}int main()
{vector<int> nums = { 2, -1, 4, 55, 0, 67, -23, 5, 9 };//quickSortNotR(nums, 0, nums.size() - 1);mergeSort(nums);for (auto item : nums) {cout << item << " ";}cout << endl;return 0;
}// 快速排序
int getPartSortIndex(vector<int>& nums, int low, int high) {int tmp = nums[low]; // TODO:随机取值int i = low;int j = high;while (i <j) {while (i < j && nums[j] >= tmp) {j--;}nums[i] = nums[j];while (i < j && nums[i] <= tmp) {i++;}nums[j] = nums[i];}nums[i] = tmp;return i;
}// 递归版本
void quickSort(vector<int>& nums, int low, int high) {if (low >= high) {return;}int index = getPartSortIndex(nums, low, high);quickSort(nums, low, index - 1);quickSort(nums, index + 1, high);
}// 非递归版本
void quickSortNotR(vector<int>& nums, int low, int high) { if (low >= high) {return;}stack<int> s;s.emplace(low);s.emplace(high);while (!s.empty()) {int right = s.top();s.pop();int left = s.top();s.pop();int index = getPartSortIndex(nums, left, right);if (index - 1 > left) {s.emplace(left);s.emplace(index - 1);}if (index + 1 < right) {s.emplace(index + 1);s.emplace(right);}}
}

相关文章:

基础数据结构思路写法记录,便于回顾

重思路非代码。基础的思路搞懂了&#xff0c;变形题目顺着思考基本都能写出来&#xff01; 二分查找 int binarySearch(vector<int> &nums, int target) {// write your code hereif (nums.empty()) {return -1;}int start 0;int end nums.size() - 1;while (star…...

基于AI的量化投资框架Qlib的Python依赖包pyqlib安装问题记录

版权声明&#xff1a;本文为博主原创文章&#xff0c;如需转载请贴上原博文链接&#xff1a;基于AI的量化投资框架Qlib的Python依赖包pyqlib安装问题记录-CSDN博客 前言&#xff1a;最近想使用Qlib来做量化交易的策略研究&#xff0c;但是第一步就卡在了安装pyqlib依赖包&#…...

《语音识别方案选择》

《语音识别方案选择》 一、引言二、语音识别技术概述&#xff08;一&#xff09;语音识别的基本原理&#xff08;二&#xff09;语音识别技术的发展历程&#xff08;三&#xff09;语音识别技术的分类1、基于声学模型的语音识别2、基于语言模型的语音识别3、端到端的语音识别 三…...

目标检测数据集图片及标签同步裁剪

目录 前言 具体方法 使用介绍 完整代码 前言 在目标检测任务中&#xff0c;模型的训练依赖于大量高质量的标注数据。然而&#xff0c;获取足够多的标注数据集往往代价高昂&#xff0c;并且某些情况下&#xff0c;数据集中的样本分布不均衡&#xff0c;这会导致模型的泛化能…...

【设计模式-简单工厂】

定义 简单工厂模式&#xff08;Simple Factory Pattern&#xff09;是一种创建型设计模式&#xff0c;用于通过一个工厂类来创建某个产品类的实例&#xff0c;而不直接在客户端&#xff08;调用方&#xff09;中实例化对象。 这种模式的主要思想是将对象的创建逻辑集中在一个…...

多个版本的GCC(GNU编译器集合)可以同时安装并存

在Ubuntu系统中&#xff0c;多个版本的GCC&#xff08;GNU编译器集合&#xff09;可以同时安装并存。GCC是编译C、C以及其他编程语言程序的重要工具&#xff0c;不同的项目可能需要不同版本的GCC来确保兼容性。 为什么需要多个GCC版本 项目依赖&#xff1a;不同的软件项目可能…...

量子纠错--shor‘s 码

定理1 (量子纠错的条件) C是一组量子编码&#xff0c;P是映射到C上的投影算子。假设是一个算子元素描述的量子操作&#xff0c;那么基于量子编码C&#xff0c;存在一个能对抗描述的噪声的纠错操作R的充要条件是 对某个复元素厄米矩阵成立。 将算子元素称为导致的错误。如果这样…...

机器学习2

一、模型评估方法 1.1 K折交叉验证法&#xff08;K-Fold Cross Validation&#xff09; 1.1.1 定义 K折交叉验证法是一种用于评估模型性能的技术。它将数据集分为K个相等的子集&#xff0c;模型会轮流使用一个子集作为测试集&#xff0c;其余K-1个子集作为训练集。这个过程会…...

二分查找_ x 的平方根搜索插入位置山脉数组的峰顶索引

x 的平方根 在0~X中肯定有数的平方大于X&#xff0c;这是肯定的。我们需要从中找出一个数的平方最接近X且不大于X。0~X递增&#xff0c;它们的平方也是递增的&#xff0c;这样我们就可以用二分查找。 我们找出的数的平方是<或者恰好X&#xff0c;所以把0~X的平方分为<X …...

汽车建模用什么软件最好?汽车建模渲染建议!

在汽车建模和渲染领域&#xff0c;选择合适的软件对于实现精确的设计与高质量的视觉效果至关重要。那么不少的汽车设计师如何选择合适的建模软件与渲染方案呢&#xff0c;一起来简单看看吧&#xff01; 一、汽车建模用软件推荐 1、Alias Autodesk旗下的Alias系列软件是汽车设…...

蘑菇分类识别数据集(猫脸码客 第222期)

蘑菇分类识别文本/图像数据集 蘑菇&#xff0c;作为一种广泛分布于全球的真菌&#xff0c;隶属于伞菌目伞菌亚门蘑菇科蘑菇属&#xff0c;拥有众多别名&#xff0c;如白蘑菇、洋蘑菇等。其不仅是世界上人工栽培最广泛、产量最高、消费量最大的食用菌品种之一&#xff0c;还在许…...

长短期记忆网络(Long Short-Term Memory,LSTM)

简介&#xff1a;个人学习分享&#xff0c;如有错误&#xff0c;欢迎批评指正。 长短期记忆网络&#xff08;Long Short-Term Memory&#xff0c;简称LSTM&#xff09;是一种特殊的循环神经网络&#xff08;Recurrent Neural Network&#xff0c;简称RNN&#xff09;架构&#…...

WHAT - 引入第三方组件或项目使用需要注意什么

目录 1. 功能匹配2. 社区与维护3. 兼容性4. 性能5. 易用性6. 安全性7. 授权和许可证8. 国际化支持9. 依赖性10. 未来维护 在前端开发过程中引入第三方组件或项目时&#xff0c;应该从以下几个方面进行考虑&#xff0c;以确保引入的组件能够有效解决问题并适合长期维护&#xff…...

原生鸿蒙操作系统HarmonyOS NEXT(HarmonyOS 5)正式发布

华为于10月22日19:00举办“原生鸿蒙之夜暨华为全场景新品发布会”。此次发布会推出全新的原生鸿蒙操作系统HarmonyOS NEXT&#xff08;HarmonyOS 5&#xff09;以及nova 13、WATCH Ultimate、MatePad Pro等新品。 据介绍&#xff0c;此前已经发布过的鸿蒙系统&#xff0c;由于系…...

WindTerm配置快捷键Ctrl+C和Ctrl+V

WindTerm配置快捷键CtrlC和CtrlV 平时使用ssh和sftp连接的时候&#xff0c;经常使用windterm&#xff0c; 但是windterm里面找不到相关的快捷键设置&#xff0c; 因为操作习惯&#xff0c;想把CtrlC和CtrlV分别配置为复制和粘贴&#xff0c;其他的快捷键操作可以按照该方法进…...

AOP学习

corol调用serverce不在是直接调用的是调用底层代理对象&#xff0c;由代理对象统一帮我们处理 AOP常见概念 通知类型 切面顺序...

【ubuntu18.04】ubuntu18.04升级cmake-3.29.8及还原系统自带cmake操作说明

参考链接 cmake升级、更新&#xff08;ubuntu18.04&#xff09;-CSDN博客 升级cmake操作说明 下载链接 Download CMake 下载版本 下载软件包 cmake-3.30.3-linux-x86_64.tar.gz 拷贝软件包到虚拟机 cp /var/run/vmblock-fuse/blockdir/jrY8KS/cmake-3.29.8-linux-x86_64…...

利用Docker搭建一套Mycat2+MySQL8一主一从、读写分离的最简单集群(保姆教程)

文章目录 1、Mycat介绍1.1、mycat简介1.2、mycat重要概念1.3、Mycat1.x与Mycat2功能对比1.2、主从复制原理 2、前提准备3、集群规划4、安装和配置mysql主从复制4.1、master节点安装mysql8容器4.2、slave节点安装mysql8容器4.2、配置主从复制4.3、测试主从复制配置 5、安装mycat…...

算法——python实现堆排序

文章目录 堆排序二叉树堆堆排序的过程&#xff1a;代码实现python中的heapq模块 堆排序 二叉树 关于二叉树的操作&#xff0c;其实核心就是 父节点找子节点&#xff0c;子节点找父节点 如果要将二叉树存储到队列中&#xff0c;就需要找出 父子节点之间的规律&#xff1a; 父…...

uniapp-components(封装组件)

<myitem></myitem> 在其他类里面这样调用。...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...