第04章 Python算法与数据结构考察点
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了第04章 Python算法与数据结构考察点，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4745字，纯文字阅读大概需要7分钟。
内容图文
Python内置数据结构算法常考
你使用过哪些常用内置算法和数据结构?sorted?dict/ist/set/tuple?问题：想的不全或者压根没了解和使用过常用内置数据结构和算法
collections模块
有用过 collections 模块吗collections模块提供了一些内置数据结构的扩展
Python dict底层结构
dict底层使用的哈希表为了支持快速查找使用了哈希表作为底层结构哈希表平均查找时间复杂度O（1）?CPython解释器使用二次探查解决哈希冲突问题哈希冲突和扩容是常考题
探查法
Python list/tuple区别
list vs tuple都是线性结构，支持下标访问list是可变对象， tuple保存的引用不可变list没法作为字典的key, tuple可以（可变对象不可hash）
保存的引用不可变指的是你没法替换掉这个对象，但是如果对系那个本身是一个可变对象，是可以修改这个引用指向的可变对象的什么是 LRUCache？
Least-Recently-Used替换掉最近最少使用的对象缓存剔除策略，当缓存空间不够用的时候需要一种方式剔除key常见的有LRU,LFU等LRU通过使用一个循环双端队列不断把最新访问的key放到表头实现
如何实现 LRUCache
字典用来缓存，循环双端链表用来记录访问顺序利用 Python内置的dict+ collections.OrderedDict实现dict用来当做k/v键值对的缓存?OrderedDict用来实现更新最近访问的key
循环双端队列
Python算法常考题
算法常考点
排序+查找，重中之重常考排序算法：冒泡排序、快速排序、归并排序、堆排序线性查找，二分查找等能独立实现代码（手写），能够分析时间空间复杂度常用排序算法的时空复杂度
Python数据结构常考题
Python web后端常考数据结构◆常见的数据结构链表、队列、栈、二叉树、堆◆使用内置结构实现高级数据结构，比如内置的? ??list/deque? ??实现栈◆ Leetcode或者《剑指ofer》上的常见题
常考数据结构之链表
链表有单链表、双链表、循环双端链表◆ 如何使用 Python来表示链表结构◆ 实现链表常见操作，比如插入节点，反转链表，合并多个链表等◆ Leetcode练习常见链表题目
常考数据结构之队列
队列（queue）是先进先出结构◆如何使用 Python实现队列？◆实现队列的 apend和pop操作，如何做到先进先出◆使用 Python的list或者 collections.deque实现队列
常考数据结构之栈
栈（stack)是后进先出结构◆如何使用 Python实现栈？◆实现栈的push和pop操作，如何做到后进先出◆同样可以用 Python list或者 collections.deque 实现栈
常考数据结构之字典与集合
Python dict/set底层都是哈希表哈希表的实现原理，底层其实就是一个数组◆根据哈希函数快速定位一个元素，平均査找O（1），非常快◆不断加入元素会引起哈希表重新开辟空间，拷贝之前元素到新数组哈希表如何解决冲突
链接法和开放寻址法◆元素key冲突之后使用一个链表填充相同key的元素◆开放寻址法是冲突之后根据一种方式（二次探査）寻找下一个可用的槽◆ Cpython使用的二次探查
二叉树
先序、中序、后序遍历◆先（根）序：先处理根，之后是左子树，然后是右子树◆中（根）序：先处理左子树，然后是跟，然后是右子树◆后（根）序：先处理左子树，然后是右子树，最后是根
Python数据结构常考题之 堆
堆其实是完全二叉树，有最大堆和最小堆最大堆：对于每个非叶子节点∨，V的值都比它的两个孩子大◆最大堆支持每次pop操作获取最大的元素，最小堆获取最小元素◆常见问题：用堆来完成topk问题，从海量数字中寻找最大的k个
什么是白板编程
传说中的手写算法题，白纸或者白板上手写代码◆对于没有参加过ACM/蓝桥杯之类算法竞赛的同学比较吃亏◆刷题。 LeetCode，《剑指 offer》，看 github题解◆最近某大型互联网公司多年经验跳槽出来因为算法题面挂小公司为啥要手写算法题
工作用不到，为啥还要考？◆有些公司为了筛选编程能力强的同学，近年来对算法要求越来越高◆针对刚出校门的同学问得多，有经验的反而算法考得少（偏工程经验）◆竟争越来越激烈，大家水平差不多的优先选取有算法竞赛经验的如何准备
没有太多好的方式，刷常见题。防止业务代码写多了算法手生◆刷题， LeetCode常见题。看《剑指 offer》之类的面试算法书◆面试之前系统整理之前做过的题目，不要靠记忆而是真正理解掌握◆打好基础是重点，面试可以刷常见题突击，保持手感面试前练习
刷题（ leetcode+剑指 offer+看面经）◆《剑指 offer》上常见题目用 Python实现◆把 leetcode上常见分类题目刷一遍（ github搜 leetcode分类）◆常见排序算法和数据结构能手写? ??快排，归并不会怎么办
针对没有算法竞赛经验的同学- 有些公司是硬性标准，想要筛选参加过算法竞赛的同学
- 问面试官这种题目工作中的使用场景，还是想仅仅刁难你
- 如果不会可以一点一点和面试官交流，解释下自己这方面较薄弱
Python数据结构常考题之——链表
链表
链表涉及到指针操作较为复杂，容易出错，经常用作考题熟悉链表的定义和常见操作常考题：删除一个链表节点常考题：合并两个有序链表多写多练
找到相关的题目，多做一些练习一般可能一次很难写对尝试自己先思考，先按照自己的方式编写代码，提交后发现问题如果实在没有思路或者想参考别人的思路可以搜题解Python数据结构常考题之二叉树
二叉树二叉树涉及到递归和指针操作，常结合递归考察二叉树的操作很多可以用递归的方式解决，不了解递归会比较吃力常考题：二叉树的镜像常考题：如何层序遍历二叉树（广度优先）
数据结构之堆
堆的常考题基本围绕在合并多个有序（数组/链表）；TopK问题理解堆的概念，堆是完全二叉树，有最大堆和最小堆会使用 Python内置的 heapq模块实现堆的操作常考题：合并k个有序链表 leetcode merge-k- sorted-ist
Python字符串常考算法题
字符串题
了解常用的字符串操作?Python内置了很多字符串操作，比如 split, upper, replace等常考题：翻转一个字符串常考题：判断一个数字是否是回文数
反转链表
链表在面试中是一个高频考点（ leetcode reverse-linked-list）如何反转一个单链表？你能使用循环的方式实现吗？能否用递归的方式实现？内容总结
以上是互联网集市为您收集整理的第04章 Python算法与数据结构考察点全部内容，希望文章能够帮你解决第04章 Python算法与数据结构考察点所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】