基础数据结构思路写法记录,便于回顾
重思路非代码。基础的思路搞懂了,变形题目顺着思考基本都能写出来!
二分查找
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);}}
}相关文章:
基础数据结构思路写法记录,便于回顾
重思路非代码。基础的思路搞懂了,变形题目顺着思考基本都能写出来! 二分查找 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安装问题记录
版权声明:本文为博主原创文章,如需转载请贴上原博文链接:基于AI的量化投资框架Qlib的Python依赖包pyqlib安装问题记录-CSDN博客 前言:最近想使用Qlib来做量化交易的策略研究,但是第一步就卡在了安装pyqlib依赖包&#…...
《语音识别方案选择》
《语音识别方案选择》 一、引言二、语音识别技术概述(一)语音识别的基本原理(二)语音识别技术的发展历程(三)语音识别技术的分类1、基于声学模型的语音识别2、基于语言模型的语音识别3、端到端的语音识别 三…...
目标检测数据集图片及标签同步裁剪
目录 前言 具体方法 使用介绍 完整代码 前言 在目标检测任务中,模型的训练依赖于大量高质量的标注数据。然而,获取足够多的标注数据集往往代价高昂,并且某些情况下,数据集中的样本分布不均衡,这会导致模型的泛化能…...
【设计模式-简单工厂】
定义 简单工厂模式(Simple Factory Pattern)是一种创建型设计模式,用于通过一个工厂类来创建某个产品类的实例,而不直接在客户端(调用方)中实例化对象。 这种模式的主要思想是将对象的创建逻辑集中在一个…...
多个版本的GCC(GNU编译器集合)可以同时安装并存
在Ubuntu系统中,多个版本的GCC(GNU编译器集合)可以同时安装并存。GCC是编译C、C以及其他编程语言程序的重要工具,不同的项目可能需要不同版本的GCC来确保兼容性。 为什么需要多个GCC版本 项目依赖:不同的软件项目可能…...
量子纠错--shor‘s 码
定理1 (量子纠错的条件) C是一组量子编码,P是映射到C上的投影算子。假设是一个算子元素描述的量子操作,那么基于量子编码C,存在一个能对抗描述的噪声的纠错操作R的充要条件是 对某个复元素厄米矩阵成立。 将算子元素称为导致的错误。如果这样…...
机器学习2
一、模型评估方法 1.1 K折交叉验证法(K-Fold Cross Validation) 1.1.1 定义 K折交叉验证法是一种用于评估模型性能的技术。它将数据集分为K个相等的子集,模型会轮流使用一个子集作为测试集,其余K-1个子集作为训练集。这个过程会…...
二分查找_ x 的平方根搜索插入位置山脉数组的峰顶索引
x 的平方根 在0~X中肯定有数的平方大于X,这是肯定的。我们需要从中找出一个数的平方最接近X且不大于X。0~X递增,它们的平方也是递增的,这样我们就可以用二分查找。 我们找出的数的平方是<或者恰好X,所以把0~X的平方分为<X …...
汽车建模用什么软件最好?汽车建模渲染建议!
在汽车建模和渲染领域,选择合适的软件对于实现精确的设计与高质量的视觉效果至关重要。那么不少的汽车设计师如何选择合适的建模软件与渲染方案呢,一起来简单看看吧! 一、汽车建模用软件推荐 1、Alias Autodesk旗下的Alias系列软件是汽车设…...
蘑菇分类识别数据集(猫脸码客 第222期)
蘑菇分类识别文本/图像数据集 蘑菇,作为一种广泛分布于全球的真菌,隶属于伞菌目伞菌亚门蘑菇科蘑菇属,拥有众多别名,如白蘑菇、洋蘑菇等。其不仅是世界上人工栽培最广泛、产量最高、消费量最大的食用菌品种之一,还在许…...
长短期记忆网络(Long Short-Term Memory,LSTM)
简介:个人学习分享,如有错误,欢迎批评指正。 长短期记忆网络(Long Short-Term Memory,简称LSTM)是一种特殊的循环神经网络(Recurrent Neural Network,简称RNN)架构&#…...
WHAT - 引入第三方组件或项目使用需要注意什么
目录 1. 功能匹配2. 社区与维护3. 兼容性4. 性能5. 易用性6. 安全性7. 授权和许可证8. 国际化支持9. 依赖性10. 未来维护 在前端开发过程中引入第三方组件或项目时,应该从以下几个方面进行考虑,以确保引入的组件能够有效解决问题并适合长期维护ÿ…...
原生鸿蒙操作系统HarmonyOS NEXT(HarmonyOS 5)正式发布
华为于10月22日19:00举办“原生鸿蒙之夜暨华为全场景新品发布会”。此次发布会推出全新的原生鸿蒙操作系统HarmonyOS NEXT(HarmonyOS 5)以及nova 13、WATCH Ultimate、MatePad Pro等新品。 据介绍,此前已经发布过的鸿蒙系统,由于系…...
WindTerm配置快捷键Ctrl+C和Ctrl+V
WindTerm配置快捷键CtrlC和CtrlV 平时使用ssh和sftp连接的时候,经常使用windterm, 但是windterm里面找不到相关的快捷键设置, 因为操作习惯,想把CtrlC和CtrlV分别配置为复制和粘贴,其他的快捷键操作可以按照该方法进…...
AOP学习
corol调用serverce不在是直接调用的是调用底层代理对象,由代理对象统一帮我们处理 AOP常见概念 通知类型 切面顺序...
【ubuntu18.04】ubuntu18.04升级cmake-3.29.8及还原系统自带cmake操作说明
参考链接 cmake升级、更新(ubuntu18.04)-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实现堆排序
文章目录 堆排序二叉树堆堆排序的过程:代码实现python中的heapq模块 堆排序 二叉树 关于二叉树的操作,其实核心就是 父节点找子节点,子节点找父节点 如果要将二叉树存储到队列中,就需要找出 父子节点之间的规律: 父…...
uniapp-components(封装组件)
<myitem></myitem> 在其他类里面这样调用。...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...
Vue 模板语句的数据来源
🧩 Vue 模板语句的数据来源:全方位解析 Vue 模板(<template> 部分)中的表达式、指令绑定(如 v-bind, v-on)和插值({{ }})都在一个特定的作用域内求值。这个作用域由当前 组件…...
算法—栈系列
一:删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...
