嵌入式秋招八股文笔记——数据结构和算法
C 中栈的使用:
1.栈中的数据元素遵守“先进后出"原则。
2.限定只能在栈顶进行插入和删除操作。
#include <stack> //头文件
stack<int> sta; //创建一个栈
sta.push(i); //将i压入栈顶
sta.pop(); //将栈顶元素弹出
sta.top(); //查看栈顶元素
sta.empty(); //判断是否栈空
tips:1.栈内没元素时不可使用top和pop
2.pop是没有返回值的,如果想读取栈顶元素得用top
3.力扣232题适合练手
二分查找
二分查找是一种在每次比较之后将查找空间一分为二的算法。每次需要查找集合中的索引或元素时,都应该考虑二分查找。如果集合是无序的,我们可以总是在应用二分查找之前先对其进行排序。
class Solution {
public:
int search(vector<int>& nums, int target) {
if(!nums.size())
return -1;
int left=0,right=nums.size()-1,mid;
while(left<=right)
{
mid=left (right-left)/2;
if(nums[mid]==target)
return mid;
else if(nums[mid]<target)
left=mid 1;
else right=mid-1;
cout<<mid<<endl;
}
return -1;
}
};
tips:1.二分查找中,如果数组长度为偶数,则判断的是中间偏左的那个数的值
2.二分查找的时间复杂度为(log2n)
回溯算法
1.回溯算法属于一种暴力搜索法,一般用于多层for循环搜索复杂度太高的情况
2.常用于排列组合、子集和棋盘等问题
力扣77题 数组的子组合
class Solution {
private:
vector<vector<int>> part;
vector<int> num;
public:
void dfs(int n,int k,int backnum)
{
if(num.size()==k)
{
part.push_back(num);
return;
}
for(int i=backnum;i<=n; i)
{
if(num.size()>=1)
{
if(i>num[num.size()-1])
{
num.push_back(i);
dfs(n,k,backnum 1);
num.pop_back();
}
}
else
{
num.push_back(i);
dfs(n,k,backnum 1);
num.pop_back();
}
}
}
vector<vector<int>> combine(int n, int k) {
int backnum=1;
dfs(n,k,backnum);
return part;
}
};
哈希表
总结一下秋招中常考的两类数据结构:
1.unordered_map
//初始化
unordered_map<int, int> umap = { {2, 10},{1, 20},{3,30} };
//遍历unordered_map
//注意一个用指针一个用点
for (auto &item : umap) {
cout << item.first << " -> " << item.second << endl;
}
for(auto it = umap.begin();it != umap.end(); it) {
cout<<it->first<<" "<<it->second<<endl;
}
//插入元素
//一般插入
umap.insert(pair<int,int>(4,9));
//数组的形式,如果存在就修改,否则插入
umap[3] = 7;
umap[5] = 99;
//按key删除元素
umap.erase(0);
//按迭代器删除元素
umap.erase(umap.begin());
//按key查找元素
auto it = umap.find(3);
if(it != umap.end()){ //查找成功,修改其值
it->second=50;
}
else{ //查找失败,直接插入
umap[3]=88;
}
set是没有键的map,常用STL和map类似。
unordered_set<int> set1; //创建set表
set1.empty();//判断是否为空
set1.find(); //查找
set1.insert(); //插入元素,但是不能存储相同的键值
set1.erase(); //删除
常用小技巧
1.判断一个数二进制1的个数
int count(int n)
{
int res = 0;
while (n != 0) {
n = n & (n - 1);
res ;
}
return res;
}
2.字符串和整形转换
//整形数转字符串
to_string(1);
//字符型转整形
int i=atoi(str.c_str());
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfeagh
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01