商务汽车网站建设,西宁高端网站制作公司,怎么样才能做好网站建设,企业宣传网站制作综述#xff1a; #x1f49e;目的#xff1a;本系列是个人整理为了秋招算法的#xff0c;整理期间苛求每个知识点#xff0c;平衡理解简易度与深入程度。 #x1f970;来源#xff1a;材料主要源于网上知识点进行的#xff0c;每个代码参考热门博客和GPT3.5#xff0… 综述 目的本系列是个人整理为了秋招算法的整理期间苛求每个知识点平衡理解简易度与深入程度。 来源材料主要源于网上知识点进行的每个代码参考热门博客和GPT3.5其中也可能含有一些的个人思考。 结语如果有帮到你的地方就点个赞和关注一下呗谢谢 【C】秋招实习面经汇总篇 文章目录 编码平台格式ACM模式笔试基础基本代码范式基本算法框架 a l g o r i t h m 常用函数模板 algorithm常用函数模板 algorithm常用函数模板/font 面试基础面试常见手撕题目基本操作 项目基础设计模式高并发相关 场景题目智力题待解决问题 点此到文末惊喜↩︎ 编码平台格式
ACM模式
注意事项 使用long代替int标准规定int 至少 16 位long int 至少 32 位并且 sizeof(int) sizeof(long)所以在不同的编译器下int可能位数不足出现整形溢出问题。奇数判断 (n 1) 1因为奇数的二进制尾数为1二进制速度快。 基础输入要点 引用库需要自己加上对应的库如#include algorithm输入使用while (cin a ){ 算法主体 }输出使用cout注意删除自己的测试输出不能使用return否则会一直报错语法错误输入示例 #include vector
#include iostream
using namespqce std;
int main() {long n 0; // 表示n轮输入cin n;while (n--) { int c 0; // 每轮输入的整数个数cin c;vectorlong vec(c, 0);for (int i 0; i vec.size(); i)cin vec[i];
}二维数组的初始化vectorvectorint dp(rows, vectorint(cols, 0));// 注意要进行初始化
for (int i 0; i rows; i) {for (int j 0; j cols; j) {cin dp[i][j];// 不能使用push_back()进行处理
}输入一行以回车结尾的数字vectorint vec;
int tmp 0;
do {// 不能使用while(){}因为会丢失第一个输入cin tmp;vec.push_back(tmp);
} while (cin.get() ! \n);笔试基础
基本代码范式
基本逻辑范式bool function(){// 1.健壮性检查if (函数形参不符合情况) {doing();return false;}// 2.初始化给工作变量赋初值符合要求的第一次循环条件int initial_value 0;// 会被算法初始化的也应该赋初值// 4.算法逻辑while (工作变量符合算法循环条件) {// 注意考虑最后不足算法增量的部分doing();// 对结果序列操作的函数工作变量的迭代;// 注意工作变量在使用完成后已经被污染}// 5.收尾处理不足最后一次算法增量的部分return true;
}递归逻辑范式void Recursion(vectorint vec,...){// 递归出口if (结束条件) return ;// 递归体Doing();
}基本算法框架
快慢指针 作用可用于线性结构的条件遍历处理如链表、数组等优点可以将两次循环降维成条件筛选一次循环 // 示例删除数组中的元素
int RemoveElement(vectorint nums, int val) {// 健壮性检查if (nums.empty()) return -1;// 初始化操作int slow 0; // 慢指针负责更新处理int fast slow; // 快指针负责拓展选择// 算法部分while(fast nums.size()){ if(nums[fast] ! val){ // 快指针负责条件判断nums[slow] nums[fast];slow;fast;}fast;}return slow;
}
// 示例环形链表的入口滑动窗口 右边界指针负责拓展左边界指针负责收缩 void SlideWindow(vectorint vec) {// 功能函数部分auto slide_windows [](vectorint nums, int left, int right){// 直到到大窗口的右边界// 直到到达窗口右边界停止while(right nums.size()) {// - 扩大右边界并更新窗口状态...right;// - 窗口到达什么状态需要收缩while(需要收缩) {// - 缩小左边界并更新窗口状态...left;}}};// 代码逻辑部分// 健壮性处理if (nums.size() 1) return ;// 初始化int left 0;int right 0;// 算法部分slide_windows(vec, left, right);
}二叉树遍历算法 广度优先遍历深度优先遍历 // 二叉树的基本数据结构
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int v) : val(v), left(nullptr), right(nullptr){}
};
// 深度优先的递归遍历
// 中序遍历
void Traversal(TreeNode *root) {if (root nullptr) return ;Traversal(root-left); // 左Doing(root-val); // 中Traversal(root-right); // 右
}
// 深度优先的非递归遍历
vectorint Traversal(TreeNode* root) {// 初始化vectorint result; // 结果容器stackTreeNode* st; // 深度的栈if (root ! NULL) // 根非空则入栈st.push(root);// 遍历源容器while (!st.empty()) {TreeNode* node st.top(); // if (node ! NULL) {st.pop();// 算法变化的部分遍历的逆序// 中st.push(node); st.push(NULL);// 右if (node-right) st.push(node-right); // 左if (node-left) st.push(node-left); } else {// 对值节点的处理st.pop();// 弹出空值结点node st.top();st.pop();// 结点处理result.push_back(node-val);}}return result;
}
// 广度优先的非递归遍历
vectorvectorint levelOrder(TreeNode* root) {// 初始化vectorvectorint result; // 结果容器queueTreeNode* que; // 广度的队列if(root ! nullptr) // 根非空则入列 que.push(root);// 算法while (!que.empty()) { // 队列非空vectorint vec; // 结果存放TreeNode* node; // 过程记录int size que.size(); // 初始化记录每层要遍历的根节点数量for (int i 0; i size; i) { // que.size()会变化// 处理结点node que.front(); // 记录队首结点que.pop(); // 弹出队首结点if (node-left) que.push(node-left);if (node-right) que.push(node-right);// doing处理结点vec.push_back(node-val);}// 将每层筛选元素压入结果数组中result.push_back(vec);}// 输出return result;
}回溯算法 组合问题 有重复元素的组合无重复元素的组合 排列问题 有重复元素的全排列无重复元素的全排列
// 组合问题
// 无重复元素的组合
class Solution {
private:// 回溯核心算法vectorvectorint result; // 存放符合条件结果的集合vectorint path; // 用来存放符合条件结果void BackTracking(vectorint vec, int start, int target) {// 递归出口满足条件则加入结果集中if (path.size() target) {result.push_back(path); return ;}// 回溯算法for (int i start; i vec.size(); i) {// 剪枝条件if (i vec.size() - (target-path.size())) continue;path.push_back(vec[i]); // 做出选择BackTracking(vec, i 1, target);// 递归path.pop_back(); // 撤销选择}}
public:vectorvectorint combine(vectorintvec, int k) {result.clear(); // 可以不写path.clear(); // 可以不写BackTracking(vec, 0, k);return result;}
};// 有重复元素的组合
class Solution {
public:vectorvectorint combine(vectorint vec, int k) {result.clear(); // 可以不写path.clear(); // 可以不写sort(vec.begin(), vec.end());BackTracking(vec, 0, k);return result;}
};
private:// 回溯核心算法vectorvectorint result; // 存放符合条件结果的集合vectorint path; // 用来存放符合条件结果void BackTracking(vectorint vec, int start, int target) {// 递归出口满足条件则加入结果集中if (path.size() target) {result.push_back(path); return ;}// 回溯算法for (int i start; i vec.size(); i) {// 剪枝重复选择只选一次需要配合sort使用if (i start vec[i] vec[i - 1]) continue;// 回溯步骤path.push_back(vec[i]); // 做出选择BackTracking(vec, i 1, target);// 递归path.pop_back(); // 撤销选择}}
};// 无重复元素的全排列
class Solution {
public:vectorvectorint permute(vectorint nums) {result.clear();path.clear();vectorbool used(nums.size(), false);backtracking(nums, used);return result;}
private:vectorvectorint result;vectorint path;void backtracking (vectorint nums, vectorbool used) {// 此时说明找到了一组if (path.size() nums.size()) {result.push_back(path);return;}for (int i 0; i nums.size(); i) {if (used[i] true) continue; // path里已经收录的元素直接跳过// 增加选择used[i] true;path.push_back(nums[i]);// 回溯backtracking(nums, used);// 撤销选择path.pop_back();used[i] false;}}
};// 有重复元素的全排列
class Solution {
public:vectorvectorint permuteUnique(vectorint nums) {// 重复计数unordered_mapint, int umap;for (auto i : nums) umap[i];backtrace(umap, 0, nums.size());return res;}
private:vectorvectorint res;vectorint path;void backtrace(unordered_mapint, int umap, int k, int total) {if (k total) {res.push_back(path);return;}for (auto p : umap) { // 每轮递归结束会进入循环if (p.second 0) continue;--p.second;path.push_back(p.first);backtrace(umap, k 1, n);p.second;path.pop_back();}}
};
动态规划算法// dp的推导
// - dp[j]为容量为j的背包所背的最大价值
// - 每次物品有两个选择
// - 放入则背包减去重量并增加价值 dp[j - weight[i]] value[i]
// - 不放入则仍为 dp[j]
// 最终递推公式为dp[j] max(dp[j], dp[j - weight[i]] value[i]);
int main() {// 子功能部分auto bag_problem [](vectorint weight, vectorint value, int bag_weight)-int{vectorint dp(bag_weight 1, 0);for (int i 0; i weight.size(); i) {// 倒叙保证物品只添加一次顺序会导致所用数据是刚更新的// 而不是上一层滚动的for (int j bag_weight; j weight[i]; --j) {dp[j] max(dp[j], dp[j-weight[i]] value[i]);}}return dp[bag_weight];};// 逻辑部分vectorint weight {1, 3, 4};vectorint value {15, 20, 30};int bag_weight 4;cout bag_problem(weight, value, bag_weight);
}a l g o r i t h m 常用函数模板 algorithm常用函数模板 algorithm常用函数模板
前提需要包含#includealgorithm头文件常见功能函数使用示例#include iostream
#include algorithm
#include vector
using namespace std;
int main() {vectorint vec{1, 2, 3, 4, 5};// max和min函数int min_val min(a, b); // 返回a和b中较小的值int max_val max(a, b); // 返回a和b中较大的值// sort函数对容器进行自定义的排序sort(vec.begin(), vec.end()); // 默认为升序排序sort(vec.begin(), vec.end(), [](int a, int b){return a b; // 可以进行自定义}); // 降序排序// find函数返回容器中指定值的迭代器如果没有则返回end()auto it find(vec.begin(), vec.end(), 3);if (it ! vec.end()) cout 找到了;// replace函数将容器中的所有a值替换成b值replace(v.begin(), v.end(), 3, 10); // 将所有3替换成10// reverse函数反转vector中的元素reverse(vec.begin(), vec.end());// count函数计算在一个范围内某个值的出现次数int n count(vec.begin(), vec.end(), 3);// 注意若为字符使用3// swap函数交换两个变量的值swap(a, b);// 使用lower_bound函数查找第一个大于等于3的元素位置auto it lower_bound(vec.begin(), vec.end(), 3);cout it - vec.begin() endl;
}面试基础
面试常见手撕题目
快速排序void QuickSort(vectorint vec, int left, int right) {// 功能性函数划分auto partition [](vectorint vec, int left, int right)-int{ int pivot vec[left]; // 定义第一个为枢纽while (left right) {// 从右向前找比枢纽值小的放在左边while (left right vec[right] pivot) --right;vec[left] vec[right];// 从左向后找比枢纽值大的放在右边while (left right vec[left] pivot ) left;vec[right] vec[left];}// 填入枢纽值vec[left] pivot;return left;};// 递归出口需要使用大于等于if (left right) return ;// [left, right]中leftright表示区间有序// 递归体int pivot_index partition(vec, left, right);QuickSort(vec, left, pivot_index-1);QuickSort(vec, pivot_index1, right);
}合并两个有序链表 合并k个有序链表使用合并两个有序链表作为基础进行归并算法 ListNode* MergeList(ListNode* list1, ListNode* list2) {// 健壮性检查if (list1 nullptr || list2 nullptr) return (list1 ! nullptr) ? list1 : list2;// 初始化TreeNode *vhead ListNode(-1);TreeNode *cur vhead;// 算法while (list1 ! nullptr list2 ! nullptr) {if (list1.val list2.val) {cur.next list1;list1 list1.next;} else {cur.next list2;list2 list2.next;}cur cur.next;}// 收尾cur.next (list1 ! nullptr) ? list1 : list2;return vhead;
}求第k大数含有重复数#include algorithm
#include vector
#include algorithm
using namespqce std;int KthLargeElement(vectorint vec, int k) {// 健壮性检查if (k 0 || k vec.size())return INT_MIN;// 初始化sort(vec.begin(), vec.end(), [](int a, int b){return a b;});int count 1;// 算法部分for (int i 1; i vec.size(); i) {// key相邻遍历的方式if (vec[i] ! vec[i-1]) count;if (count k) break;}// 收尾return vec[i];
}基本操作 去重 #include iostream
#include vector
#include unordered_set
using namespace std;
int main() {// 基本去重vectorint vec { 1, 2, 3, 1, 3 };// 使用set去重的天然特性然后再赋值给原容器unordered_setint uset(vec.begin(), vec.end());vec vectorint(uset.begin(), uset.end());// keyreturn 0;
}遍历相邻元素 int sum 0;
for (int i 1; i vec.size(); i) {sum vec[i] - vec[i-1];
}字符串转换 进制转换 删除链表next结点 auto delete_node [](TreeNode *cur){if (cur ! nullptr) {ListNode* tmp cur-next;cur-next cur-next-next;delete tmp;}
};字符串切割 在这里插入代码片项目基础
设计模式
消息队列生产者消费者模式#include iostream
#include condition_variable
#include mutex
#include queue
#include string
#include thread
using namespace std;class MessageQueue {public:MessageQueue() {}// 生产者放入消息队列中void PushMsq(string msg) {unique_lockmutex lock(mtx_);// 1.上锁保证{}范围内的互斥访问que_.push(msg); // 2.生产向消息队列中添加消息 cv_.notify_one();// 3.唤醒唤醒在该条件变量上等待队列优先级最高的一个线程// m_cv.notify_all()会唤醒所有线程但是会造成资源争用要谨慎使用}// 消费者从消息队列中取出信息string PopMsq() {unique_lockmutex lock(mtx_);// 1. 上锁// 2. 队列为空则等待如果队列为空等待生产者添加消息while (que_.empty()) {cv_.wait(lock);// 释放lock锁并阻塞等待}// 3. 消费取出消息并返回string msg que_.front();que_.pop();return msg;}private:// 记住这个顺序先加智能锁然后压入队列最后唤醒条件变量上的线程mutex mtx_; // 互斥锁保证消息队列和条件变量的互斥访问queuestring que_; // 消息队列生产者和消费者的缓冲区condition_variable cv_; // 条件变量保证生产者和消费者的同步
};
// 定义生产者线程函数
void producer(MessageQueue mq) {for (int i 0; i 10; i) {string msg message to_string(i);mq.PushMsq(msg);this_thread::sleep_for(chrono::milliseconds(100)); // 生产者线程休眠一段时间}
}
// 定义消费者线程函数
void consumer(int id, MessageQueue mq) {for (int i 0; i 5; i) {string msg mq.PopMsq();cout consumer id get message: msg std::endl;this_thread::sleep_for(chrono::milliseconds(200)); // 消费者线程休眠一段时间}
}
// 测试生产者消费者模型
int main() {MessageQueue msq;// 线程的创建参数为函数指针函数形参thread t1(producer, ref(msq));thread t2(consumer, 1, ref(msq));thread t3(consumer, 2, ref(msq));thread t4(consumer, 3, ref(msq));// .join()执行完当前线程再向下执行t1.join();t2.join();t3.join();t4.join();return 0;
}线程安全的单例模式// 饿汉式
class SinglePatter {public:static SinglePatter GetInstance() {static SinglePatter instance;return instance;}private:SinglePatter(){};SinglePatter(SinglePatter ) delete;SinglePatter operator(const SinglePatter ) delete;
};// 懒汉式
class SinglePatter {public: static SinglePatter *GetInstance() {unique_lockmutex lock(mtx);if (instance nullptr) {instance new SinglePatter();}return instance;}private:static SinglePatter *instance;static mutex mtx;SinglePatter(){};SinglePatter(SinglePatter ) delete;SinglePatter operator(const SinglePatter ) delete;};
高并发相关
写一个自旋锁// 自旋锁
int xchg(volatile int *addr, int new_val) {int res;asm volatile( // 将lock xchg换位cmpxhg是否就是CAS锁lock xchg %0, %1:m(*addr),a(res):1(new_val):cc);return res;
}int locked 0;
void lock(){while (xchg(locked, 1));
}
void unlock(){xchg(locked, 0);
}场景题目
智力题
数学归纳法动态规划核心公式的推导 推导前三个或者五个简单的输入和输出从而假设递进关系式再使用两个进行验证 组合排列问题
待解决问题 功能性函数auto封装导致的代码优雅性问题字节二面上下左右走格子中使用回溯增加复杂性但是代码优雅易于理解。 匿名函数只是一个对数据的单纯的逻辑处理不应该有健壮性检查和返回值数据的初始化部分应该由实参传输除内部工作变量外其他变量应该由外部提供。
