【经验贴】数据结构与算法知识点汇总
前言
在这部分分享里面,我只会涉及各部分的考点,但是不会把答案放出来,有一些我遇到的感觉不错的题也会放上来。这么做一方面是我自己也没法保证自己的答案是完全正确的(之前就有过看一个面经,然后里面的答案是错误的,在面试的时候吃过亏);另一方面是希望大家能够自己去查找,在理解的基础上记忆才能记得更牢,而且能对整个原理有一个认知,而不是完完全全靠背答案,这样效果很差,而且经不起面试官深入地问。这里把大部分的要点都总结出来了,就算一点一点去查资料也能在一周左右的时间内复习完。对于过于基础的知识就不提了,只提一些比较不容易注意到的点和比较重要的点。这里提到的知识点都是考察率非常高的,希望大家能把这些知识点弄懂,于此同时也要不断去看其他人的笔经面经,从里面找到自己不会的知识点,不断丰富自己的知识库。
对于嵌入式软件岗位来说,数据结构相对没有那么重要,但还是属于必考的知识点。对于嵌入式岗位,数据结构可以选择性地学习,不用全部都学会,毕竟准备的时间是有限的,当然有充足的时间的话,当然建议都学会了,因为对于顶级大厂来说,数据结构是考核的相对重点。
数据结构对于大多数不冲顶级大厂的同学来说,主要学链表、队列、堆栈就可以了,至于二叉树之类的,在我整个秋招的过程中,几乎没有被问到。可能像是华为这种公司会考到。
算法这部分建议去leetcode或者牛客网刷一下题,起码刷个20道简单题,熟练一下做题的方法,输入输出这些,对字符串的操作这些,因为后面笔试基本上都会考两题大题,基本上刷个20题,稍微总结一下,然后加上平时的积累就问题不大了,如果想进华为那些大厂,就要刷中等甚至困难的算法题了,这个看各位自己的取舍。
数据结构与算法这部分比较多的是考编程大题,所以大家不仅要知道解题的思路,还要会自己编码实现。
链表
- 数组和链表的优缺点有哪些?
- 链表的环
- 怎么判断链表有没有环?
- 如何知道环的长度?
- 如何找出环的连接点?
- 怎么翻转链表?
- 怎么删除链表中间某个节点?(只知道某个被删除节点,不知道其前一个结点地址的情况)
- 怎么删除单链表的重复节点?
- 怎么找出单链表倒数第k个节点?
- 怎么找出链表的中间节点?
- 两个单链表相交,如何求交点?
- 怎么判断一个链表是否回文链表?
- 怎么合并两个有序链表?
- 怎么实现双链表?
- 怎么实现循环链表?
二叉树
- 二叉树的遍历方法有哪些?
- 怎么求二叉树的深度?
- 怎么判断二叉树是否相等?
- 如何判断一棵树是平衡二叉树?
- 完全二叉树一共有n个节点,求叶子节点个数
- 若用n个权值构造一棵最优二叉树(哈夫曼树),则该二叉树的结点总数为
数组
- 给定一个整数数组,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
- 给一个数组和一个值val,原地移除所有数值等于val的元素,并返回移除后数组的新长度
- 合并两个有序数组
- 给定仅有小写字母组成的字符串数组A,返回列表中的每个字符串中都显示的全部字符组成的列表,一个字符出现多少次就要在最终答案中包含多少次
- 寻找数组的中心索引
- 给定一个非负整数数组A,A的所有偶数元素之后跟着所有奇数元素
- 给定一个未经排序的整数数组,找到最长且连续的递增序列
字符串
- 有效的括号(leetcode经典题)
- 翻转字符串
- 翻转字符串中的单词
- 判断是否回文字符串
- 判断字符串中的单词个数
- 库函数复现
- strcp
- strlen
- strcat
排序算法
- 8大排序算法,主要掌握冒泡排序、快速排序、插入排序的实现
- 了解8个排序算法的时间复杂度、空间复杂度、是否为稳定排序及其基本思想
递归
- 递归求1+2+……+n累加
- 递归求n!
- 递归实现斐波那契数列
其他算法
- 一根绳子分成若干份,计算若干份之积,使之成为最大值
- 杨辉三角
- 求一个数的阶乘末尾零的个数
- 输出n以内的素数
- 求数的二进制表示里面的1的个数
- 交换两个变量的值,不使用第三个变量