厦门海绵城市建设官方网站,网站内容注意事项,网站建设泉州,宣讲家网站官德修养与作风建设系列综述#xff1a; #x1f49e;目的#xff1a;本系列是个人整理为了秋招面试的#xff0c;整理期间苛求每个知识点#xff0c;平衡理解简易度与深入程度。 #x1f970;来源#xff1a;材料主要源于左程云算法课程进行的#xff0c;每个知识点的修正和深入主要参考… 系列综述 目的本系列是个人整理为了秋招面试的整理期间苛求每个知识点平衡理解简易度与深入程度。 来源材料主要源于左程云算法课程进行的每个知识点的修正和深入主要参考各平台大佬的文章其中也可能含有少量的个人实验自证。 结语如果有帮到你的地方就点个赞和关注一下呗谢谢 【C】秋招实习面经汇总篇 文章目录 面试技巧链表栈和队列递归 参考博客 点此到文末惊喜↩︎
面试技巧
写算法时候也要阐述自己的思路即使写不出来面试的算法必须找到最优的解
链表
单向链表数据结构// 单链表数据结构
struct LinkNode {int val;struct LinkNode *next;LinkNode(int v): val(v), next(nullptr){}
};
// 反转单链表
LinkNode *ReverseLinkList(LinkNode *head) {LinkNode *prev nullptr;LinkNode *next nullptr;while (head ! nullptr) { // head充当cur指针表示每个操作的结点next head-next; // 记录值head-next prev;prev head; // 两个指针的迭代head next;}return prev;
}双向链表数据结构 使用双链表作为底层实现栈和队列 struct LinkNode {int val;struct LinkNode *prev;struct LinkNode *next;LinkNode(int v): val(v), prev(nullptr), next(nullptr){}
};
// 反转双向链表
LinkNode *ReverseLinkList(LinkNode *head) {LinkNode *prev nullptr;LinkNode *next nullptr;while (head ! nullptr) { // head充当cur指针表示每个操作的结点next head-next; // 记录值head-next prev; // key当前双链表结点两个指针反转head-prev next;prev head; // 两个指针的迭代head next;}return prev;
}// 删除指定结点
ListNode *DeleteTarget(ListNode *head, int target) {ListNode *vhead new ListNode(-1);vhead-next head;ListNode *prev vhead;ListNode *cur head;while (cur ! nullptr) {if (cur-val target) {ListNode *p cur;cur cur-next;delete p; // 释放结点jvm会自动释放prev-next cur;} else {prev cur;cur cur-next;}}return vhead-next;
}
设计一个模板双链表可以进行头部和尾部的增删以及改查操作并进行优化栈和队列 双链表实现栈和队列 数组实现栈和队列 数组队列的实现应该是一个环状结构使用 以O(1)时间获取当前栈的最小值 leetcode题目最小栈思路1最小栈同步记录对应的栈内最小值思路2最小栈只记录栈内的最小值只有当前栈和最小栈顶元素相等最小栈栈顶才弹出
class MinStack {
public:/** initialize your data structure here. */MinStack() {min_st.push(INT_MAX);}void push(int x) {cur_st.push(x);int p min_st.top();// 最小栈的栈顶一直记录栈内的最小值if (x p) {min_st.push(x);} else {min_st.push(p);}}void pop() {cur_st.pop();min_st.pop();}int top() {return cur_st.top();}int getMin() {return min_st.top();}
private:// 使用两个栈记录一个记录当前栈另一个栈顶一直为栈内最小元素stackint cur_st; stackint min_st;
};使用栈实现队列 思路两个栈一个记录压入的元素一个记录弹出的元素。
class MyQueue {
public:MyQueue() {}// 弹出栈为空则压入栈全部倒进弹出栈中void PushToPop(){if (pop_st.empty()) {while (!push_st.empty()) {pop_st.push(push_st.top());push_st.pop();}}}// 压入一个则尝试倒栈void push(int x) {push_st.push(x);PushToPop();}// 先倒栈在尝试弹出int pop() {PushToPop();int p pop_st.top();pop_st.pop();return p;}int peek() {PushToPop();return pop_st.top();}bool empty() {return pop_st.empty() push_st.empty();}
private:stackint push_st;stackint pop_st;
};使用队列实现栈 思路将队列头部的元素按序重新添加到队列尾部其中最后一个即栈顶元素
class MyStack {
public:queueint que;/** Initialize your data structure here. */MyStack() { }/** Push element x onto stack. */void push(int x) {que.push(x);}/** Removes the element on top of the stack and returns that element. */int pop() {int size que.size();size--;while (size--) { // 将队列头部的元素除了最后一个元素外 重新添加到队列尾部que.push(que.front());que.pop();}int result que.front(); // 此时弹出的元素顺序就是栈的顺序了que.pop();return result;}// 队列的末尾元素即为栈顶元素int top() {return que.back();}/** Returns whether the stack is empty. */bool empty() {return que.empty();}
};递归
递归的固定参数可以使用全局或者引用其中的可变参数作为参数递归求数组的最大值
int process(vectorint vec, int L, int R) {if (L R) return vec[L];int mid L ((R-L)1);int left_max process(vec, L, mid);int right_max process(vec, mid1, R);return max(left_max, right_max);
}任何递归都可以改成非递归因为递归本质利用了系统栈特殊复杂度 T ( N ) a ∗ T ( N / b ) O ( N c ) T(N) a*T(N/b) O(N^c) T(N)a∗T(N/b)O(Nc)其中a、b和c都是常数a是递归次数b为递归划分分数c 如果 l o g b a d log_ba d logbad复杂度为 O ( N d ) O(N^d) O(Nd)如果 l o g b a d log_ba d logbad复杂度为 O ( N l o g b a ) O(N^{log_ba}) O(Nlogba)如果 l o g b a d log_ba d logbad复杂度为 O ( N d ∗ l o g N ) O(N^d * logN) O(Nd∗logN) 少年我观你骨骼清奇颖悟绝伦必成人中龙凤。 不如点赞·收藏·关注一波 点此跳转到首行↩︎
参考博客 对数器 单调队列 快速链表quicklist《深入理解计算机系统》侯捷C全系列视频 待定引用 待定引用 待定引用
