C++面试常考手写题目
C++面试常考手写题目
- vector
- string
- auto_ptr
- shared_ptr
- unique_ptr
- weak_ptr
- singleton
- 快排非递归
- heap
- heap_sort
- merge_sort
vector
#include <bits/stdc++.h>
using namespace std;template<typename T>
class vector {public:typedef T value_type;typedef T* iterator;private:value_type* _data;size_t _size;size_t _capacity;public:vector(): _data(NULL), _size(0), _capacity(0) {}~vector() {delete [] _data;_data = NULL;_size = 0;_capacity = 0;}vector(const vector& vec) {_size = vec._size;_capacity = vec._capacity;_data = new value_type[_capacity];for (int i = 0; i < _size; ++i) {_data[i] = vec._data[i];}}vector& operator=(const vector& vec) {if (this == &vec) return *this;value_type* temp = new value_type[vec._capacity];for (int i = 0; i < vec._size; ++i) {temp[i] = vec._data[i];}delete [] _data;_data = temp;_size = vec._size;_capacity = vec._capacity;return *this;}void push_back(value_type val) {if (0 == _capacity) {_capacity = 1;_data = new value_type[1];} else if (_size + 1 > _capacity) {_capacity *= 2;value_type* temp = new value_type[_capacity];for (int i = 0; i < _size; ++i) {temp[i] = _data[i];}delete [] _data;_data = temp;}_data[_size] = val;++_size;}void pop_back() {--_size;}size_t size() const {return _size;}size_t capacity() const {return _capacity;}bool empty() {return _size == 0;}value_type& operator[](size_t index) {return _data[index];}bool operator==(const vector& vec)const {if (_size != vec._size) return false;for (int i = 0; i < _size; ++i) {if (_data[i] != vec._data[i]) return false;}return true;}value_type front()const {return _data[0];}value_type back() const {return _data[_size - 1];}void insert(iterator it, value_type val) {int index = it - _data;if (0 == _capacity) {_capacity = 1;_data = new value_type[1];_data[0] = val;} else if (_size + 1 > _capacity) {_capacity *= 2;value_type* temp = new value_type[_capacity];for (int i = 0; i < index; ++i) {temp[i] = _data[i];}temp[index] = val;for (int i = index; i < _size; ++i) {temp[i + 1] = _data[i];}delete [] _data;_data = temp;} else {for (int i = _size - 1; i >= index; --i) {_data[i + 1] = _data[i];}_data[index] = val;}++_size;}void erase(iterator it) {size_t index = it - _data;for (int i = index; i < _size - 1; ++i) {_data[i] = _data[i + 1];}--_size;}iterator begin() {return _data;}iterator end() {return _data + _size;}
};
string
#include <iostream>
#include <cstring>class MyString {
public:// 构造函数MyString() {data_ = new char[1];data_[0] = '\0';size_ = 0;}MyString(const char* str) {size_ = strlen(str);data_ = new char[size_ + 1];strcpy(data_, str);}// 拷贝构造函数MyString(const MyString& other) {size_ = other.size_;data_ = new char[size_ + 1];strcpy(data_, other.data_);}// 析构函数~MyString() {delete[] data_;}// 赋值运算符MyString& operator=(const MyString& other) {if (this == &other) {return *this;}delete[] data_;size_ = other.size_;data_ = new char[size_ + 1];strcpy(data_, other.data_);return *this;}// 大小size_t size() const {return size_;}// 清空void clear() {delete[] data_;data_ = new char[1];data_[0] = '\0';size_ = 0;}// 字符串内容的访问const char* c_str() const {return data_;}private:char* data_;size_t size_;
};
auto_ptr
#include <bits/stdc++.h>
using namespace std;template<class T>
class auto_ptr {public:auto_ptr(T* ptr = nullptr) : _ptr(ptr) {}~auto_ptr() {if (_ptr != nullptr) {cout << "delete: " << _ptr << endl;delete _ptr;_ptr = nullptr;}}auto_ptr(auto_ptr<T>& ap): _ptr(ap._ptr) {ap._ptr = nullptr; // 管理权转移后ap被置空}auto_ptr& operator=(auto_ptr<T>& ap) {if (this != &ap) {delete _ptr; // 释放自己管理的资源_ptr = ap._ptr; // 接管ap对象的资源ap._ptr = nullptr; // 管理权转移后ap被置空}return *this;}// 可以像指针一样使用T& operator*() {return *_ptr;}T* operator->() {return _ptr;}private:T* _ptr; //管理的资源
};
shared_ptr
#include <bits/stdc++.h>
using namespace std;template<class T>
class shared_ptr {public:shared_ptr(T* ptr = nullptr): _ptr(ptr), _pcount(new int(1)){}shared_ptr(shared_ptr<T>& sp): _ptr(sp._ptr), _pcount(sp._pcount) {(*_pcount)++;}~shared_ptr() {if (--(*_pcount) == 0) {if (_ptr != nullptr) {cout << "delete: " << _ptr << endl;delete _ptr;_ptr = nullptr;}delete _pcount;_pcount = nullptr;}}shared_ptr& operator=(shared_ptr<T>& sp) {if (_ptr != sp._ptr) { // 管理同一块空间的对象之间无需进行赋值操作if (--(*_pcount) == 0) { // 将管理的资源对应的引用计数--cout << "delete: " << _ptr << endl;delete _ptr;delete _pcount;}_ptr = sp._ptr; // 与sp对象一同管理它的资源_pcount = sp._pcount; // 获取sp对象管理的资源对应的引用计数(*_pcount)++; // 新增一个对象来管理该资源 引用计数++}return *this;}// 获取引用计数int use_count() {return *_pcount;}// 可以像指针一样使用T& operator*() {return *_ptr;}T* operator->() {return _ptr;}private:T* _ptr; // 管理的资源int* _pcount; // 管理的资源对应的引用计数 堆上
};template<class T>
class shared_ptr_with_mutex {private:// ++引用计数void AddRef() {_pmutex->lock();(*_pcount)++;_pmutex->unlock();}// --引用计数void ReleaseRef() {_pmutex->lock();bool flag = false;if (--(*_pcount) == 0) { // 将管理的资源对应的引用计数--if (_ptr != nullptr) {cout << "delete: " << _ptr << endl;delete _ptr;_ptr = nullptr;}delete _pcount;_pcount = nullptr;flag = true;}_pmutex->unlock();if (flag == true) {delete _pmutex;}}public:shared_ptr_with_mutex(T* ptr = nullptr): _ptr(ptr), _pcount(new int(1)), _pmutex(new mutex){}shared_ptr_with_mutex(shared_ptr_with_mutex<T>& sp): _ptr(sp._ptr), _pcount(sp._pcount), _pmutex(sp._pmutex) {AddRef();}~shared_ptr_with_mutex() {ReleaseRef();}shared_ptr_with_mutex& operator=(shared_ptr_with_mutex<T>& sp) {if (_ptr != sp._ptr) { // 管理同一块空间的对象之间无需进行赋值操作ReleaseRef(); // 将管理的资源对应的引用计数--_ptr = sp._ptr; // 与sp对象一同管理它的资源_pcount = sp._pcount; // 获取sp对象管理的资源对应的引用计数_pmutex = sp._pmutex; // 获取sp对象管理的资源对应的互斥锁AddRef(); // 新增一个对象来管理该资源,引用计数++}return *this;}// 获取引用计数int use_count() {return *_pcount;}// 可以像指针一样使用T& operator*() {return *_ptr;}T* operator->() {return _ptr;}private:T* _ptr; // 管理的资源int* _pcount; // 管理的资源对应的引用计数mutex* _pmutex; // 管理的资源对应的互斥锁
};
unique_ptr
#include <bits/stdc++.h>
using namespace std;template<class T>
class unique_ptr {public:unique_ptr(T* ptr = nullptr): _ptr(ptr){}~unique_ptr() {if (_ptr != nullptr) {cout << "delete: " << _ptr << endl;delete _ptr;_ptr = nullptr;}}// 可以像指针一样使用T& operator*() {return *_ptr;}T* operator->() {return _ptr;}// 防拷贝unique_ptr(unique_ptr<T>& up) = delete;unique_ptr& operator=(unique_ptr<T>& up) = delete;private:T* _ptr; // 管理的资源
};
weak_ptr
#include <bits/stdc++.h>
using namespace std;template<class T>
class weak_ptr {public:weak_ptr(): _ptr(nullptr){}weak_ptr(const shared_ptr<T>& sp): _ptr(sp.get()){}weak_ptr& operator=(const shared_ptr<T>& sp) {_ptr = sp.get();return *this;}// 可以像指针一样使用T& operator*() {return *_ptr;}T* operator->() {return _ptr;}private:T* _ptr; // 管理的资源
};
singleton
#include <iostream>
#include <mutex>class Singleton {
private:static Singleton* instance;static std::mutex mtx;Singleton() {} // 私有构造函数,防止外部实例化public:static Singleton* getInstance() {if (instance == nullptr) {std::lock_guard<std::mutex> lock(mtx); // 加锁if (instance == nullptr) {instance = new Singleton();}}return instance;}void showMessage() {std::cout << "Hello, I am a singleton instance!" << std::endl;}
};Singleton* Singleton::instance = nullptr;
std::mutex Singleton::mtx;int main() {Singleton* singleton1 = Singleton::getInstance();singleton1->showMessage();Singleton* singleton2 = Singleton::getInstance();singleton2->showMessage();return 0;
}
快排非递归
#include <bits/stdc++.h>
using namespace std;用一个栈(std::stack)将以下用递归实现的快排函数改成非递归// usage://std::vector<int> v = {3, 2, 1, 5, 6, 9, -1, -2, 0};//QuickSort(&v[0], 0, int(v.size())-1);void QuickSort(int *array, int low, int high){int i = low;int j = high;int pivot = array[(i + j) / 2];while (i <= j){while (array[i] < pivot)++i;while (array[j] > pivot)--j;if (i <= j){std::swap(array[i], array[j]);++i;--j;}}if (j > low)QuickSort(array, low, j);if (i < high)QuickSort(array, i, high);}void QuickSort(int* array, int low, int high) {stack<pair<int, int>> mystack;mystack.push(make_pair(low, high));while (!mystack.empty()) {int _low = mystack.top().first;int _high = mystack.top().second;int i = _low;int j = _high;mystack.pop();int pivot = array[(i + j) / 2];while (i <= j) {while (array[i] < pivot)++i;while (array[j] > pivot)--j;if (i <= j) {std::swap(array[i], array[j]);++i;--j;}}if (j > _low)mystack.push(make_pair(_low, j));if (i < _high)mystack.push(make_pair(i, _high));}
}
void display(vector<int>& a) {for (int& e : a) {cout << e << " ";}cout << endl;
}
heap
#include <iostream>
#include <vector>// 最小堆
class MinHeap {
public:MinHeap() {}void insert(int value) {heap.push_back(value);heapifyUp(heap.size() - 1);}int pop() {if (heap.empty()) {throw std::out_of_range("Heap is empty");}int minValue = heap[0];heap[0] = heap.back();heap.pop_back();heapifyDown(0);return minValue;}bool isEmpty() const {return heap.empty();}private:std::vector<int> heap;void heapifyUp(int index) {int parent = (index - 1) / 2;while (index > 0 && heap[index] < heap[parent]) {std::swap(heap[index], heap[parent]);index = parent;parent = (index - 1) / 2;}}void heapifyDown(int index) {int leftChild = 2 * index + 1;int rightChild = 2 * index + 2;int smallest = index;if (leftChild < heap.size() && heap[leftChild] < heap[smallest]) {smallest = leftChild;}if (rightChild < heap.size() && heap[rightChild] < heap[smallest]) {smallest = rightChild;}if (smallest != index) {std::swap(heap[index], heap[smallest]);heapifyDown(smallest);}}
};int main() {MinHeap heap;heap.insert(10);heap.insert(5);heap.insert(15);heap.insert(20);heap.insert(3);while (!heap.isEmpty()) {std::cout << heap.pop() << " ";}std::cout << std::endl;return 0;
}
heap_sort
#include <iostream>
#include <vector>void heapify(std::vector<int>& arr, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] > arr[largest]) {largest = left;}if (right < n && arr[right] > arr[largest]) {largest = right;}if (largest != i) {std::swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}void heapSort(std::vector<int>& arr) {int n = arr.size();// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 逐个提取最大元素并调整堆for (int i = n - 1; i > 0; i--) {std::swap(arr[0], arr[i]);heapify(arr, i, 0);}
}int main() {std::vector<int> arr = {9, 4, 7, 2, 1, 5, 8, 3, 6};heapSort(arr);std::cout << "排序结果: ";for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;return 0;
}
merge_sort
#include <iostream>
#include <vector>// 合并两个有序数组
void merge(std::vector<int>& arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;std::vector<int> leftArr(n1);std::vector<int> rightArr(n2);for (int i = 0; i < n1; i++) {leftArr[i] = arr[left + i];}for (int j = 0; j < n2; j++) {rightArr[j] = arr[mid + 1 + j];}int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (leftArr[i] <= rightArr[j]) {arr[k] = leftArr[i];i++;} else {arr[k] = rightArr[j];j++;}k++;}while (i < n1) {arr[k] = leftArr[i];i++;k++;}while (j < n2) {arr[k] = rightArr[j];j++;k++;}
}// 递归实现归并排序
void mergeSortRecursive(std::vector<int>& arr, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSortRecursive(arr, left, mid);mergeSortRecursive(arr, mid + 1, right);merge(arr, left, mid, right);}
}// 非递归实现归并排序
void mergeSortIterative(std::vector<int>& arr) {int n = arr.size();int currSize;for (currSize = 1; currSize <= n - 1; currSize = 2 * currSize) {for (int left = 0; left < n - 1; left += 2 * currSize) {int mid = std::min(left + currSize - 1, n - 1);int right = std::min(left + 2 * currSize - 1, n - 1);merge(arr, left, mid, right);}}
}int main() {std::vector<int> arr = {9, 4, 7, 2, 1, 5, 8, 3, 6};std::cout << "递归归并排序结果: ";mergeSortRecursive(arr, 0, arr.size() - 1);for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;std::vector<int> arr2 = {9, 4, 7, 2, 1, 5, 8, 3, 6};std::cout << "非递归归并排序结果: ";mergeSortIterative(arr2);for (int num : arr2) {std::cout << num << " ";}std::cout << std::endl;return 0;
}
相关文章:
C++面试常考手写题目
C面试常考手写题目 vectorstringauto_ptrshared_ptrunique_ptrweak_ptrsingleton快排非递归heapheap_sortmerge_sort vector #include <bits/stdc.h> using namespace std;template<typename T> class vector {public:typedef T value_type;typedef T* iterator;p…...

LLM建模了什么,为什么需要RAG
LLM近期研究是井喷式产出,如此多的文章该处何处下手,他们到底又在介绍些什么、解决什么问题呢?“为学日增,为道日损”,我们该如何从如此多的论文中找到可以“损之又损以至于无”的更本质道或者说是这个方向的核心模型。…...

为开发GPT-5,OpenAI向微软寻求新融资
11月14日,金融时报消息,OpenAI正在向微软寻求新一轮融资,用于开发超级智能向AGI(通用人工智能)迈进,包括最新模型GPT-5。 最近,OpenAI召开了首届开发者大会,推出了GPT-4 Turbo、自定…...

创邻科技亮相ISWC 2023,国际舞台见证知识图谱领域研究突破
近日,第22届国际语义网大会 ISWC 2023 在雅典希腊召开,通过线上线下的形式,聚集了全球的顶级研究人员、从业人员和行业专家,讨论、发展和塑造语义网和知识图谱技术的未来。创邻科技CEO张晨博士作为知识图谱行业专家受邀参会&#…...

开源博客项目Blog .NET Core源码学习(6:雪花算法)
Blog .NET项目中有多种数据类生成对象实例时需要唯一标识,一般做法要么使用GUID,也可以保存到数据库时使用数据库表的自增长ID,也可以自定义规则以确保产生不重复的唯一标识,而在Blog .NET项目中使用雪花算法生成唯一标识。 关…...

【Python】集合与字典
按照输入顺序输出 将输入的名字去重,同时按照输入顺序输出 sinput().split(,) blist(set(s)) bsorted(b,keys.index) print(b) 删除集合元素、更新集合 根据操作删除更新集合 update括号里可以是一个集合,add只能是一个元素 discard用于删除元素&#x…...
【LeetCode】88. 合并两个有序数组
88. 合并两个有序数组 难度:简单 题目 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 …...

Linux文件权限
R 代表可读 W 代表可写 X 代表可执行 文档类型有如下表示方法: d - 目录,例如上表档名为『.gconf』的那一行; - - 文档,例如上表档名为『install.log』那一行; l - 链接档(link file); b …...

〖大前端 - 基础入门三大核心之JS篇㉟〗- JavaScript 的DOM简介
说明:该文属于 大前端全栈架构白宝书专栏,目前阶段免费,如需要项目实战或者是体系化资源,文末名片加V!作者:不渴望力量的哈士奇(哈哥),十余年工作经验, 从事过全栈研发、产品经理等工作…...

CentOS中安装常用环境
一、CentOS安装 redis ①:更新yum sudo yum update②:安装 EPEL 存储库 Redis 通常位于 EPEL 存储库中。运行以下命令安装 EPEL 存储库 sudo yum install epel-release③:安装 Redis sudo yum install redis④:启动 Redis 服…...

python时间变化与字符串替换技术及读JSON文件等实践笔记
1. 需求描述 根据预测出结果发出指令的秒级时间,使用时间戳,也就是设定时间(字符串)转为数字时间戳。时间计算转换过程中,出现单个整数(例如8点),按字符串格式补齐两位“08”。字符…...

leetcode刷题日记:141. Linked List Cycle(环形链表)
这一题是给我们一个链表让我们判断这是否是一个环形链表,我们知道如果一个链表中有环的话这一个链表是没有办法访问到尾的, 假若有如图所示的带环链表: 我们从图示中很容易看出来这一个链表在访问的时候会在里面转圈,我们再来看看…...

html书本翻页效果,浪漫表白日记本(附源码)
文章目录 1.设计来源1.1 书本正面1.2 界面1-21.3 界面3-41.4 界面5-61.5 界面7-81.6 界面9-101.7 界面11-121.8 书本结尾 2.效果和源码2.1 动态效果2.2 源代码 源码下载 作者:xcLeigh 文章地址:https://blog.csdn.net/weixin_43151418/article/details/1…...

【Mysql】学习笔记
目录 基本操作登录指令:启动、关闭、重启mysql指令(适用于centos7):查看mysql运行状态:删除和创建表 修改密码(ubuntu18.04可行,其余版本行不行不知道)3 使用MYSQL了解数据库和表 4 …...
工作记录-------java文件的JVM之旅(学习篇)---好理解
一个java文件,如何实现功能呢?需要去JVM这个地方。 java文件高高兴兴的来到JVM,想要开始JVM之旅,它确说:“现在的我还不能进去,需要做一次转换,生成class文件才行”。为什么这样呢?…...

城市内涝对策,万宾科技内涝积水监测仪使用效果
随着城市化进程的加速,城市道路积水问题明显越来越多,给人们的出行和生活带来更多的不便。内涝积水监测仪作为高科技产品能够实时监测道路积水情况,为城市排水系统的管理和维护提供重要的帮助。 在城市生命线的基础设施规划之中,地…...
android的通知使用
在 Android 中,通知(Notification)是一种在状态栏显示消息的方式,通常用于向用户展示应用程序的重要信息、事件或更新。以下是一个简单的示例,演示如何在 Android 应用程序中使用通知: import android.app…...

001 opencv addWeighted
目录 一、环境 二、addWeighted函数 三、代码演示 一、环境 本文使用环境为: Windows10Python 3.9.17opencv-python 4.8.0.74 二、addWeighted函数 OpenCV中的cv.addWeighted函数是一个用于图像叠加的函数,它可以将两个具有相同尺寸和类型的图像按…...
2311rust,到35版本更新
1.32.0 rustup self update rustup update stablerustup更新自己. dbg宏 打印调试,你需要: let x 5; println!("{:?}", x); //甚至可能是 println!("{:#?}", x);在Rust1.32.0中,为此添加了个新的dbg!宏: fn main() {let x 5;dbg!(x); }如果运行此…...

UniPro提高集成能力 让客户专注于交付价值
一千个哈姆莱特就有一千个读者,一千个开发团队,也会有各不相同的软件工具和工作流程。工具与工具之间,功能上的割裂亦或重叠,都会给企业和团队的协作带来阻塞,结果就会导致团队之间各自为战、信息孤岛的形成以及资源的…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...

【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...

大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

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

windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...

华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...

Java后端检查空条件查询
通过抛出运行异常:throw new RuntimeException("请输入查询条件!");BranchWarehouseServiceImpl.java // 查询试剂交易(入库/出库)记录Overridepublic List<BranchWarehouseTransactions> queryForReagent(Branch…...