嵌入式秋招八股文笔记——数据结构和算法

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;
}

力扣77题

2.unordered_set

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());

这篇好文章是转载于：学新通技术网