山东泰安为什么那么穷大连做网站优化哪家好

山东泰安为什么那么穷,大连做网站优化哪家好,服装网站建设目的作用是什么,运动服饰网站建设需求分析嵌入式面试中常见的一些编程题目注#xff1a;本文只是代码实现#xff0c;并没有深入讲解实现原理#xff0c;大家可以看一下主要会考什么#xff0c;然后再具体针对性了解原理#xff0c;也更有利于理解。眼看26届秋招接近尾声#xff0c;自己虽然很菜#xff0c;但也…嵌入式面试中常见的一些编程题目注本文只是代码实现并没有深入讲解实现原理大家可以看一下主要会考什么然后再具体针对性了解原理也更有利于理解。眼看26届秋招接近尾声自己虽然很菜但也在激烈的竞争中拿到了几个 offer已经非常满意了希望未来持续学习进步。本文主要总结了嵌入式秋招中问的比较多的编程题目总的来说大部分不会涉及到复杂的算法题我本身非科班也没怎么刷题秋招期间遇到手撕复杂算法的公司也是成功挂掉了比较重要的是一些已有函数的实现主要考察对数据在内存中分布的掌握对C语言在嵌入式场景中理解的深度比如 memcpy() 函数遇到 dest 和 src 空间重合的问题是怎么处理的。其次就是各大排序链表字符串数组的操作二叉树的概念遍历等等。一、链表链表的一些基础操作链表定义struct Node {int data;struct Node* next;}创建节点struct Node* createNode(int value) {struct Node* newNode (struct Node*)malloc(sizeof(struct Node));if(newNode NULL)printf(malloc failed!);newNode-data value;newNode-next NULL;return newNode;}头插法插入节点struct Node* insertAtHead(struct Node* head, int value) {struct Node* newNode createNode(value);newNode-next head;return newNode; // 新的头结点}尾插法插入节点struct Node* insertAtTail(struct Node* head, int value) {struct Node* newNode createNode(value);if(head NULL)return newNode;struct Node* temp head;while(temp-next ! NULL) {temp temp-text;}temp-next newNode;return head;}遍历链表void printList(struct Node* head) {struct Node* temp head;while (temp ! NULL) {printf(%d - , temp-data);temp temp-next;}printf(NULL\n);}1. 实现链表的逆置struct ListNode* reverseList(struct ListNode* head) {if (head NULL || head-next NULL) return NULL;struct LiseNode* former;struct ListNode* latter;struct ListNode* mid head;while (mid ! NULL) {latter mid-next;mid-next former;former mid;mid latter;}}2. 判断单链表中是否存在环struct ListNode* detectCycle(struct ListNode* head) {struct ListNode* fast head;struct ListNode* slow head;while(fast ! NULL fast-next ! NULL) {slow slow-next;fast fast-next-next;if(slow fast) {fast head;while(fast ! slow) {fast fast-next;slow slow-next;}return slow;}}return NULL;}3. 单链表相交如何求交点struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {struct ListNode* p headA;struct ListNode* q headB;while(q ! p) {if (p NULL)p headB;elsep p-next;if (q NULL)q headA;elseq q-next}return q;}4. 求有环链表第一个入环点struct ListNode* detectCycle(struct ListNode* head) {struct ListNode* fast head;struct ListNode* slow head;while(fast ! NULL fast-next ! NULL) {slow slow-next;fast fast-next-next;if(slow fast) {fast head;while(fast ! slow) {fast fast-next;slow slow-next;}return slow;}}return NULL;}5. 写出链表的删除一个节点的程序void deleteNode(Node** headRef, int key) {Node* temp *headRef;Node* prev NULL;if (temp NULL) return;if (temp-data key) {*headRef temp-next; // 头指针后移free(temp); // 释放原头节点return;}while (temp ! NULL temp-data ! key) {prev temp;temp temp-next;}if (temp NULL) return;prev-next temp-next;free(temp);}6. 用递归算法实现两个有序链表的合并struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {// write code hereif (pHead1 NULL) return pHead2;if (pHead2 NULL) return pHead1;if (pHead1-val pHead2-val) {pHead2-next Merge(pHead1, pHead2-next);return pHead2;} else {pHead1-next Merge(pHead1-next, pHead2);return pHead1;}}二、二叉树满二叉树除了最后一层所有的节点都是满的并且所有节点都有两个子节点完全二叉树最后一层可以是单节点所有节点连续几种在左边。二叉搜索数BST左子树中的所有节点值都小于该节点值。右子树中的所有节点值都大于该节点值。平衡二叉树AVL左右子节点的高度不超过1的BST。// 定义二叉树节点结构typedef struct Node {int data; // 存储节点的数据struct Node* left; // 指向左子节点struct Node* right; // 指向右子节点} Node;// 创建新节点Node* createNode(int data) {Node* newNode (Node*)malloc(sizeof(Node));if (newNode NULL) {printf(内存分配失败\n);exit(1);}newNode-data data;newNode-left NULL;newNode-right NULL;return newNode;}// 销毁二叉树void destroyTree(Node* root) {if (root NULL) return;destroyTree(root-left); // 递归释放左子树destroyTree(root-right); // 递归释放右子树free(root); // 释放当前节点}// 二叉树深度int maxDepth(struct TreeNode* root){if (root NULL) return 0;int lenLeft maxDepth(root-left);int lenRight maxDepth(root-right);return lenLeft lenRight ? lenLeft 1 : lenRight 1;}1. 遍历// 中序遍历创建一个数组数组作为传入参数保存遍历的结果/*** returnNum: 保存遍历出的元素* returnSize: 保存二叉树的大小*/void inTra(struct TreeNode* root, int *returnNum, int* returnSize){if(rootNULL) return;inTra(root-left, returnNum, returnSize);returnNum[(*returnSize)] root-val;inTra(root-right, returnNum, returnSize);}int* inorderTraversal(struct TreeNode* root, int* returnSize) {int *returnNum (int *)malloc(sizeof(int)*101);*returnSize 0;if(rootNULL) return NULL;inTra(root,returnNum,returnSize);return returnNum;}不需要保存的遍历// 前序遍历根 - 左 - 右void preorderTraversal(Node* root) {if (root NULL) return;printf(%d , root-data); // 访问根节点preorderTraversal(root-left); // 遍历左子树preorderTraversal(root-right); // 遍历右子树}// 中序遍历左 - 根 - 右void inorderTraversal(Node* root) {if (root NULL) return;inorderTraversal(root-left); // 遍历左子树printf(%d , root-data); // 访问根节点inorderTraversal(root-right); // 遍历右子树}// 后序遍历左 - 右 - 根void postorderTraversal(Node* root) {if (root NULL) return;postorderTraversal(root-left); // 遍历左子树postorderTraversal(root-right); // 遍历右子树printf(%d , root-data); // 访问根节点}2. 深度int maxDepth(struct TreeNode* root) {// 递归结束条件if (root NULL) return 0;int l_depth maxDepth(root-left);int r_depth maxDepth(root-right);return (l_depth r_depth ? l_depth : r_depth) 1;}3. 是否平衡二叉树bool isAVL(struct TreeNode* root){struct TreeNode* left root-left;struct TreeNode* right root-right;int l_dep maxDepth(left);int r_dep maxDepth(right);if (l_dep r_dep) return true;else if (l_dep r_dep) return ((l_dep-r_dep) 1 ? true : false);else return ((r_dep-l_dep) 1 ? true : false);}三、排序查找算法及其改进我想对于每一个经历过秋招的小伙伴们来说十大排序基本都被问过快速排序、归并排序、堆排序、冒泡排序、插入排序、选择排序、希尔排序、桶排序、基数排序。排序名称 最好时间复杂度 平均时间复杂度 最坏时间复杂度 空间复杂度快排归并插入冒泡堆排选择1. 快速排序void quickSort(vectorint arr, int left, int right) {if (left right) return;int pivot arr[right];int l left - 1;int r left;for (; r right; r) {if (arr[r] pivot) {l;swap(arr[l], arr[r]);}}int povitIndex l 1;swap(arr[povitIndex], arr[right]);quickSort(arr, left, povitIndex - 1);quickSort(arr, povitIndex 1, right);}2. 冒泡排序// 双重循环每次循环次数减1.长度为5的数组第一次循环对比4次void bubble_sort(int *arr, int n) {int flag;for (int i 0; i n-1; i) {flag 0;for (int j 0; j n-1-i; j) {if (arr[j] arr[j1]) {swap(arr[j], arr[j1]);flag 1;}}if (flag 0) return;}}3. 归并排序/** 归并排序的思想* 1. merge函数传入一个以m为界限的左右分别排序好的数组然后把这个数组合并* 1.1 首先malloc两个数组LR然后填充然后使用? :填充arr[k]* 2. mergeSort函数递归执行停止条件lr;*/void merge(vectorint arr, int left, int mid, int right) {int n1 mid - left 1;int n2 right - mid;vectorint L(arr.begin() left, arr.begin() left n1); // 或 mid 1vectorint R(arr.begin() mid 1, arr.begin() mid 1 n2); // 或 right 1int i 0, j 0;int k left;while (i n1 j n2) arr[k] L[i] R[j] ? L[i] : R[j];while (i n1) arr[k] L[i];while (j n2) arr[k] R[j];}void mergeSort(vectorint arr, int left, int right) {if (left right) return;int mid left (right - left)/2;mergeSort(arr, left, mid);mergeSort(arr, mid1, right);merge(arr, left, mid, right);}4. 堆排序堆的数组表示对于数组中一个位置为i的节点下标从0开始父节点(i-1)/2左子节点2i1右子节点2i2最后一个非叶子节点的下标是n/2 - 1。n是数组长度。最大堆每个父节点大于子节点。最小堆每个子节点大于父节点。构建最大堆排序/*** brief 堆化函数** 这是堆排序的核心。它将以 i 为根的子树调整为大顶堆。* 假设 i 的左右子树已经是大顶堆。** param arr 待排序的数组* param n 数组的大小也是堆中元素的总数* param i 当前需要堆化的子树的根节点索引*/void heapify(std::vectorint 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 maxHeap(std::vectorint arr) {int n arr.size();for (int i n / 2 - 1; i 0; i--) heapify(arr, n, i);}void heapSort(std::vectorint arr) {int n arr.size();maxHeap(arr);for (int i n - 1; i 0; i--) {std::swap(arr[0], arr[i]);heapify(arr, i, 0);}}使用priority_heap容器适配器实现的堆排列void heapSortUsingPriorityQueue(std::vectorint arr) {if (arr.empty()) {return;}// 1. 创建一个最大堆默认行为// 将数组中的所有元素放入优先队列std::priority_queueint max_heap;for (int val : arr) {max_heap.push(val);}// 2. 依次取出最大元素并存回原数组// 此时元素是按从大到小的顺序被取出的int index 0;while (!max_heap.empty()) {arr[index] max_heap.top(); // 获取最大值max_heap.pop(); // 从堆中移除index;}// 3. 因为得到的是降序序列需要反转数组才能得到升序结果std::reverse(arr.begin(), arr.end());}5. 插入排序// 从第二个数开始往前插入数前面部分是排序好的假如有n5个数据第一次插入a[1]第4次插入a[4]。// 所以外循环n-1次从index1开始。从j i - 1依次向左比较直到比较到最低位或者小于key的数。// 两个关键点i是需要插入的索引keyarr[i]i左边也就是ji-1是排序好的节点然后向左比对当arr[j]key时arr[j1]key。void insertSort(vectorint arr) {for (int i 0; i arr.size(); i){// i2插入到前面排序好的数组跟前面的一一比较int key arr[i];int j i-1;while (j 0 arr[j] key) {arr[j 1] arr[j];j--;}arr[j 1] key;}}6. 选择排序// 选择排序函数升序// 遍历数组第一遍找出最小的放到第一个位置第二遍从[1]开始找出最小的以此类推void selectionSort(std::vectorint arr) {int n arr.size();for (int i 0; i n - 1; i) {int minIndex i;for (int j i 1; j n; j) {if (arr[j] arr[minIndex]) minIndex j;}if (minIndex ! i) swap(arr[i], arr[minIndex]);}}四、数组二分查找法int searchInsert(vectorint nums, int target) {int left 0;int right nums.size() - 1;while (left right) {int mid left (right - left)/2;if (nums[mid] target) return mid;else if (nums[mid] target) left mid 1;else right mid - 1;}return left;}五、字符串1. 字符串复制void mucpy(char *s1, char *s2) {while(*s1 *s2);}2. 字符串翻转//Cstd::reverse(s.begin(), s.end());void swap(char* str, int start, int end) {char temp 0;while (start end) {temp str[start];str[start] str[end];str[end] temp;end--;start;}}void reverseStr(char* str, int n) {int start 0;int end n - 1;swap(str, start, end);}3. 单词翻转// 字符串反转// 1. 使用算法实现 #include algorithmstd::string s hello;std::reverse(s.begin(), s.end());// 2. 手动实现while (left right) {std::swap(s[left], s[right--]);}// 单词反转std::string reverseWords(std::string s) {// 1. 分裂单词存入字符串数组std::stringstream ss; ss.str(s);std::vectorstd::string words;std::string word;while (ss word) {words.push_back(word);}// 2. 反转数组std::reverse(words.begin(), words.end());// 2. 合并单词std::string result;for (int i 0; i words.size(); i) {if (i ! 0) result ;result words[i];}return result;}#include stdio.h#include string.h// 反转字符串的某一部分 [start, end]void reverse(char* s, int start, int end) {while (start end) {char temp s[start];s[start] s[end];s[end] temp;start;end--;}}// 反转字符串中的单词顺序void reverseWords(char* s) {int len strlen(s);if (len 1) return;// 1. 反转整个字符串reverse(s, 0, len - 1);// 2. 逐个反转每个单词int wordStart 0;for (int i 0; i len; i) {if (s[i] || s[i] \0) {reverse(s, wordStart, i - 1);wordStart i 1;}}}int main() {char str[] Hello world;printf(Original: \%s\\n, str);reverseWords(str);printf(Reversed: \%s\\n, str);return 0;}六、图图的几个概念节点顶点vertex边edge有向图/无向图单向边双向边带权图边带有数值权重比如两个城市之间的举例两个任务之间的时间成本图在算法中的经典应用最短路径问题搜索问题BFSDFS。想象你在一个迷宫里要从起点走到终点迷宫有很多岔路口每个岔路口又有多个分支。你可以用两种策略来探索迷宫深度优先搜索DFS一条路走到黑选一条路一直走下去直到走不通了再返回上一个岔路口换另一条路继续使用栈或者递归。广度优先搜索BFS层层推进先走一步看看所有可能再走第二步……像水波一样一圈一圈扩散用队列实现适合找最短路径。假设一个无向图0 -- 1 -- 3| |2 -- 4用邻接表表示为0 - 1, 21 - 0, 3, 42 - 0, 43 - 14 - 1, 2#include iostream#include vector#include queue#include stackusing namespace std;// 图的邻接表表示vectorvectorint graph {{1, 2}, // 0{0, 3, 4}, // 1{0, 4}, // 2{1}, // 3{1, 2} // 4};vectorbool visited(5, false); // 记录节点是否被访问过// 深度优先搜索DFS- 递归实现void dfs(int node) {visited[node] true;cout node ;for (int neighbor : graph[node]) {if (!visited[neighbor]) {dfs(neighbor);}}}// 深度优先搜索DFS- 非递归栈实现void dfs_stack(int start) {fill(visited.begin(), visited.end(), false); // 重置访问状态stackint s;s.push(start);visited[start] true;while (!s.empty()) {int node s.top();s.pop();cout node ;for (int neighbor : graph[node]) {if (!visited[neighbor]) {visited[neighbor] true;s.push(neighbor);}}}}// 广度优先搜索BFS- 队列实现void bfs(int start) {fill(visited.begin(), visited.end(), false); // 重置访问状态queueint q;q.push(start);visited[start] true;while (!q.empty()) {int node q.front();q.pop();cout node ;for (int neighbor : graph[node]) {if (!visited[neighbor]) {visited[neighbor] true;q.push(neighbor);}}}}int main() {cout DFS (递归): ;dfs(0);cout endl;cout DFS (栈): ;dfs_stack(0);cout endl;cout BFS (队列): ;bfs(0);cout endl;return 0;}七、嵌入式常考的函数实现1. memcpyvoid* my_memcpy(const void* dest, const void* src, int n) {char* d (char*)dest;char* s (char*)src;// 判断重叠s在前从后往前拷贝s在后从前往后拷贝if (s d s n d) {for (int i n - 1; i 0; i) {d[i] s[i];}} else {for (int i 0; i n; i) {d[i] s[i];}}return dest;}2. strcpychar *my_strcpy(char *dest, char *src) {if (dest NULL || src NULL) return NULL;char *ret dest;while ((*dest *src) ! \0);return ret;}3. strncpy#include stddef.hchar *my_strncpy(char *dest, char *src, size_t n) {if (dest NULL || src NULL) return NULL;char *ret dest;while (n (*dest *src) ! \0) n--;// n有剩余if (n ! 0) {while (n--) *dest \0;}return dest;}4. strlensize_t my_strlen(const char *str) {if (str NULL) return 0;size_t len 0;while (*str ! \0) len;return len;}5. strcmpint my_strcmp(const char *s1, const char *s2) {if (s1 NULL || s2 NULL) return -1;while (*s1 (*s1 *s2)) {s1;s2;}return *(unsigned char *)s1 - *(unsigned char *)s2;}