当前位置: 首页 > news >正文

4-1 Python常用内置算法与数据结构常考题

一、你使用过哪些常用内置算法和数据结构

仔细回想一下你用过哪些内置的算法数据结构?
1.sorted
2.dict/list/set/tuple
3.问题:想的不全或者压根没了解和使用过

数据结构/算法语言内置内置库
线性结构list(列表)/tuple(元组)array(数组,不常用)/collecions.namedtuple
链式结构collections.deque(双端队列)
字典结构dict(字典)collections.Counter(计数器)/OrderedDict(有序字典)
集合结构set(集合)/fronzenset(不可变集合)
排序算法sorted
二分算法bisect模块
堆算法heapq模块
缓存算法functools.lru_cache(Least Recent Used, python3)
二、有用过collections模块吗

collections模块提供了一些内置数据结构的扩展

方法名解释
namedtuple()factory function for creating tuple subclasses with named fields
dequelist-like container with fast appends and pops on either end
Counterdict subclass for counting hashable objecs
OrderedDictdict subclass that remembers the order entries were added
defaultdictdict subclass that calls a factory function to supply missing values

namedtuple代码示例:

import collectionsPoint = collections.namedtuple('Point', 'x, y')
p = Point(1, 2)
print(p.x)  # 1
print(p.y)  # 2print(p[0])  # 1
print(p[1])  # 2
print(p[2])  # IndexError: tuple index out of range
print(p.x == p[0])  # True

说明:namedtupletuple属性可读

deque代码示例:

import collectionsde = collections.deque()de.append(1)   		# 往右边添加值
de.appendleft(0)  	# 往左边添加值
print(de)  			# deque([0, 1])de.pop()  			# 1  取右边的值
de.popleft() 		# 0  取左边的值

说明:deque可以方便地实现queue/stack

Counter代码示例:

import collectionsc = collections.Count('abcab)print(c)  			# Counter({'a': 2, 'b': 2, 'c': 1})
print(c['a'])  		# 2print(c.most_common())  # [('a', 2), ('b', 2), ('c', 1)]  从大到小获取每一个的数量

说明:需要计数器的地方使用Counter

OrderedDict代码示例:

import collectionsod = collections.OrderedDict()
od['c'] = 'c'
od['a'] = 'a'
od['b'] = 'b'print(list(od.keys())   # ['c', 'a', 'b']

说明:
OrderedDictkey顺序是第一次插入的顺序。
使用OrderedDict还可以实现LRUCache

defaultdict代码示例:

import collectionsdd = collections.defaultdict(int)print(dd['a'])  # 0  当不存在时,会返回一个默认值,因为上面定义的 int 类型,所以默认值为 0dd['b'] += 1
print(dd)  # defaultdict(int, {'a': 0, 'b': 1})

说明:defaultdict是带有默认值的字典

三、Python dict底层结构

dict底层使用的是哈希表
1.为了支持快速查找使用了哈希表作为底层结构
2.哈希表平均查找时间复杂度O(1)
3.CPython解释器使用二次探查解决哈希冲突问题

注意:哈希冲突和扩容是常考题
解决哈希冲突通常有两种:
1)、链接法
2)、探查法:分为线性探查二次探查

四、Python list/tuple区别

list VS tuple
1.都是线性结构,支持下标访问
2.list是可变对象,tuple是不可变对象
3.list没没作为字典的 keytuple可以(可变对象不可 hash)

注意,如何tuple里包含list,则里面这个list是可以改变的

代码示例:

t = ([1, 2], 3, 4)
t[0].append(5)
print(t)  # ([1, 2, 5], 3, 4)

保存的引用不可变指的是:你没法替换掉这个对象,但是如果对应那个本身是一个可变对象,是可以修改这个引用指向的可变对象的。

五、什么是 LRUCache?

Least-Recently-Used替换掉最近最少使用的对象
1.缓存剔除策略,当缓存空间不够用的时候需要一种方式剔除key
2.常见的有 LRU, LFU
3.LRU通过使用一个循环双端队列不断把最新访问的key放到表头实现
在这里插入图片描述

六、如何实现LRUCache

字典用来缓存,循环双端链表用来记录访问顺序
1.利用Python内置的dict + collections.OrderedDict实现
2.dict用来当做 k/v键值对的缓存
3.OrderedDict用来实现更新最近访问的 key

代码示例:

from collections import OrderedDictclass LRUCache:def __init__(self, capacity=128):self.od = OrderedDict()self.capacity = capacity   # 最大容量def get(self, key):		# 每次访问更新最新使用的 keyif key in self.od:val = self.od[key]self.od.move_to_end(key)   # 移动元素到表头return valelse:return -1def put(self, key, value):		# 更新 key/valueif key in self.od:del self.od[key]self.od[key] = value	# 更新 key 到表头,所以上一句要先删除这个key里的valueelse:		# insertself.od[key] = value# 判断当前容量是否已经满了if len(self.od) > self.capacity:self.od.popitem(last=False)  # 删除最早的 key/value

请大家自己实现LRUCache,并编写单元测试

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.exyb.cn/news/show-2835.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

【内网学习笔记】8、powercat 的使用

1、下载安装 powercat powercat 可以视为 nc 的 powershell 版本,因此也可以和 nc 进行连接。 powercat 可在 github 进行下载,项目地址为:https://github.com/besimorhino/powercat 下载下来 powercat.ps1 文件后,直接导入即可…...

栈和队列(二) : 用栈实现队列

leetcode232.用栈实现队列 https://leetcode-cn.com/problems/implement-queue-using-stacks/ 使用栈实现队列的下列操作: push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – 返回队列是否为空。…...

CentOS 配置php环境

一.安装apache 1.安装apache yum install httpd2.修改配置文件 vi /etc/httpd/conf/httpd.conf将#ServerName www.example.com:80前面的#去掉 修改为ServerName localhost:80 3.添加端口,刷新配置,并查看确认 firewall-cmd --permanent --zonepublic --add-port80/tcp fire…...

测试技巧:弱网测试

弱网测试场景 当前APP网络环境比较复杂,网络制式有2G、3G、4G网络,还有越来越多的公共Wi-Fi。不同的网络环境和网络制式的差异,都会对用户使用app造成一定影响。另外,当前app使用场景多变,如进地铁、上公交、进电梯等…...

PMP哪里报名

首先了解下PMP考试时间,一年四次,正常情况是每年3、6、9、12月份考试; 其次了解PMP考试需要两次报名,分别是英文报名和中文报名;且两次报名通过后,才能正常考试。 下面分别介绍PMP英文报名和PMP考试中文报…...

PHP中使用ElasticSearch

PHP中使用ElasticSearch 使用cURL尝试ElasticSearch查看es基本信息列出所有的Index列举每个Index下的Type添加Index删除Index安装中文分词插件ik (安装完需要重启es)创建一个Index,并设置其结构和分词向Index增加记录POST方式(POST方式不需要传id,id随机生成)查看指定条目…...

Thread类的常用方法

Thread类的常用方法 void start(): 启动线程,并执行对象的run()方法run(): 线程在被调度时执行的操作static Thread currentThread(): 返回当前线程。在Thread子类中就 是this,通常用于主线程和Runnable实现类String getName(): 返回线程的名…...

浅谈设计模式(三)

前言 之前详细介绍了几种常用的设计模式,最后总结一下附上所有设计模式的类图以及六大设计原则 一、创建型 1.Factory Method(工厂方法) 定义:定义了一个创建对象的接口,但由子类决定要实例化的类是哪一个。工厂方法…...

AR增强现实让科技贴近生活

AR也叫增强现实,它是在1990年被正式提出的,在时间上要比VR虚拟现实技术晚一些,它的实现主要通过三维空间、场景交融、现实视频等技术相互作用、融合实现的。 AR增强现实技术在工业领域中,有着超强的适用性,假设某件工…...

c++程序设计中虚基类,多继承知识点

一.前言 如上 二.题目 分别声明Teacher(教师)类和Cadre(干部)类,采用多重继承方式由这两个类派 生出新类Teacher_Cadre(教师兼干部)类。要求: (1)在两个基类中都包含姓名、年龄、性别、地址、电话等数据成员。 (2&a…...

FFmpeg:avcodec_encode_video()

本文简单分析FFmpeg的avcodec_encode_video2()函数。该函数用于编码一帧视频数据。avcodec_encode_video2()函数的声明位于libavcodec\avcodec.h,如下所示。 /*** Encode a frame of video.** Takes input raw video data from frame and writes the next output p…...

SpringBoot中必须掌握的45个注解

1.SpringBoot/spring SpringBootApplication: 包含Configuration、EnableAutoConfiguration、ComponentScan通常用在主类上; Repository: 用于标注数据访问组件,即DAO组件; Service: 用于标注业务层组件; RestController: …...

侯捷CPP---面向对象(上)

侯捷CPP---面向对象(上)前言头文件防卫式声明class 分类不带指针的class(complex)成员变量私有化inline function(内联函数)构造函数常量成员函数参数传递返回值传递友元函数操作符重载临时对象带指针的cla…...

使用注解开发

1; 2.mapper 2.测试...

苏宁易购启动六一宝宝节,首提“共情消费”

5月26日晚8点,苏宁易购六一宝宝节掰头大会在多个平台播出。六一宝宝节全面启动。 六一宝宝节定位于打破营销套路,打破传统电商促销节奏。它是大促,更是一场成年人释放压力、共情消费的盛典。 掰头大会灵魂辩题 开启宝宝节 六一宝宝节的启…...

设计一个windows应用程序,定义一个Student类,包含学号和姓名两个字段,并定义一个班级类ClassList

设计一个windows应用程序,定义一个Student类,包含学号和姓名两个字段,并定义一个班级类ClassList,该类包含一个Student集合,使用索引器访问该集合。 (1)创建一个Windows应用程序Myproject6_1。 …...

HTML表单标签,已拿offer附真题解析

前言 校招 -1 年 这个阶段还属于成长期,更需要看重的是你的基础和热情。对于 JS 基础,计算机基础,网络通信,算法等部分的要求会相对高一些。毕竟这个阶段比较难考察你的业务项目中的沉淀,所以只能从基础部分入手考察。…...

python笔记19年8月23日

-------------py打包exe教程------------ 准备好需要转换的py文件和一张用于做图标.ico的照片 将他们存放于同一个文件夹中,文件的路径全部为英文路径 1.利用cmd窗口安装pyinstaller插件 指令 :pip install pyinstaller 2.使用cd指令到py文件夹 3.执行命令 pyinstaller -F -i X…...

系统集成模拟3-55分

1、合同法律关系是指由合同法律法规调整的在民事流转过程中形成的(权利义务关系) 2、当已经采取了多种沟通方式还未能与用户达成一致时,应考虑沟通升级原则-双方高层沟通 3、数据域安全包括:行级数据域安全,数据域安全…...

Centos7 配置DHCP

实验内容及步骤 1、实验背景 某企业计划构建一台 DHCP服务器来解决IP地址动态分配的问题,要求能够分配 IP地址以及网关、DNS等其它网络属性信息。同时要求DHCP服务器为DNS、WEB、Samba服务器分配固定IP 地址。 2、网络拓扑 略. 3、实验环境 假设企业DHCP服务器…...

【CSS进阶】使用CSS gradient制作绚丽渐变纹理背景效果

前言 一直对渐变背景这块比较感兴趣,但是因为每天加班实在太忙了,任务也比较多。所以就只能下班的时间研究渐变背景这方面的知识,一来满足了自己的好奇心,二来可以更加了解这方面的知识。跟更多不断学习的小伙伴们一起进步&#…...

JAVA 基础学习之 继承与方法覆写

1 继承引入​​​​​​​ 三个类都有重复的代码,可以把这共同的代码抽出去,抽出去放到另外一个类里面;下面的3个类和上面的类需要发生一点关系(继承),上面的类叫做 父类(超类,基类&…...

秒杀系统 - 实现用户登录(两次MD5,JSR303参数检验,全局异常处理器)和分布式session功能

文章目录用户登录数据库设计明文密码两次MD5处理加密思路安全性加密过程导入MD5依赖封装MD5Utils实现登录页面JSR303参数检验简介流程导入依赖常用注解自定义注解测试全局异处理器原因流程GlobalException类GlobalExceptionHandler类接口测试分布式sessionsession和 cookie流程…...

测试为什么不够敏捷?美团资深软测工程师为你解答

测试是为了保证软件的质量,敏捷测试关键是保证可以持续、及时的对软件质量情况进行全面的反馈。由于在敏捷开发过程中每个迭代都会增加功能、修复缺陷或重构代码,所以在完成当前迭代新增特性测试工作的同时,还要通过回归测试来保证历史功能不…...

First Day | Web前端 | 实训笔记~

注释 解释说明代码&#xff0c;隐藏代码 注释不能嵌套 语法实现&#xff1a;<!--注释内容--> 常用标签&#xff1a; 1、<p>段落</p> 2、<a>链接</a> ①href&#xff1a;创建指向另一个文档的链接 <a href"/index.html">本…...

【Laravel3.0.0源码阅读分析】会话驱动类driver.php

<?php namespace Laravel\Session\Drivers;interface Driver {/*** Load a session from storage by a given ID.* 通过给定的ID从存储加载会话。* If no session is found for the ID, null will be returned.** param string $id* return array*/public function load(…...

抢占式优先权调度算法

在这种方式下&#xff0c;系统同样是把处理机分配给优先权最高的进程&#xff0c;使之执行。但在其执行期间&#xff0c;只要又出现了另一个其优先权更高的进程&#xff0c;进程调度程序就立即停止当前进程(原优先权最高的进程)的执行&#xff0c;重新将处理机分配给新到的优先…...

以GraalVM原生镜像的方式运行Spring Boot应用程序

Spring Boot &GraalVM–系列共有3个部分&#xff1a; 第1部分&#xff1a;以GraalVM原生镜像运行Spring Boot应用程序第2部分&#xff1a;使用Docker&Heroku容器运行Spring BootGraalVM原生镜像第3部分&#xff1a;使用原生镜像maven插件简化Spring Boot GraalVM原生镜…...

实训第一天以及第二天所学记录

实训第一天以及第二天所学记录 浏览器内核 IE&#xff1a;Trident Firefox&#xff1a;Gecko Chrome&#xff1a;Webkit / Blink Safari&#xff1a;Webkit Opera&#xff1a;Presto / Blink 在VScode中使用注释的快捷键 按住键盘的Ctrl/ 元素 &#xff08;标签 标记&…...

jvm对象

1.对象的创建 对象的创建大概可以分为5步&#xff0c;流程如下图所示 1.类加载检查 虚拟机遇到一条new指令时&#xff0c;首先在常量池中定位到这个类的符号引用&#xff0c;然后检查这个符号引用代表的类是否已经被加载过、解析和初始化过&#xff0c;如果没有&#xff0c;…...

关于TUN/TAP网卡二三事以及物理网卡Ring buffer

初识TUN/TAP虚拟网卡是因为OpenVPN&#xff0c;至今已有八个年头了&#xff0c;后来断断续续跟这块网卡打交道&#xff0c;从OpenVPN&#xff0c;到用户态协议栈&#xff0c;再到packetdrill。不管怎么说&#xff0c;我觉得这块虚拟网卡是那种可以让人眼前一亮的东西&#xff0…...

SD-WAN、MPLS 、IPsec 和物理专线的区别

目前主流的专线解决方案常见有SD-WAN、MPLS VPN、IPsec VPN和物理专线这四种&#xff0c;对绝大多数公司来说&#xff0c;自己花钱拉一根专有的网线或光纤&#xff0c;把总公司和分公司的网络连接起来&#xff0c;是一件不可能的事情&#xff0c;工程量和成本造价是个天文数字&…...

OSChina 周三乱弹—— No papapa,no hahaha

2019独角兽企业重金招聘Python工程师标准>>> 周三&#xff0c;前不着店后不着村&#xff0c;但是小小编就是喜欢周三&#xff0c;可以打打羽毛球蹦达蹦达&#xff0c;就像小小编喜欢春天一样&#xff0c;满园春色&#xff0c;嘿嘿 该名称不存在 &#xff1a;1111111…...

ExpressRoute 常见问题

什么是 ExpressRoute&#xff1f; ExpressRoute 是一项 Azure 服务&#xff0c;允许在 Microsoft 数据中心与本地环境或共同租用设施中的基础结构之间创建专用连接。 ExpressRoute 连接不通过公共 Internet&#xff0c;与通过 Internet 的典型连接相比&#xff0c;提供更高的安…...

浅谈Linux系统信息与资源

大家将来应用开发Linux程序&#xff0c;无论是ARM架构的板子&#xff0c;还是在Linux上开发应用程序&#xff0c;相信大家都会用到到一些系统相关的信息&#xff0c;譬如时间、日期、以及其它一些系统相关信息&#xff0c;今天带大家了解一下如何通过 Linux 系统调用或 C 库函数…...

传奇服是怎样架设的,怎样搭建一个属于自己的游戏服 10分钟学会游戏架设 玩转云服务器搭建游戏

战神引擎-寒刀沉默 ---------------------------------------------------------------------------------------------------- 服务器要求&#xff1a;2核4G/5M 系统要求&#xff1a;win2008/win2012 云服务器系统安装要到购买服务器的官网控制台安装指定系统&#xff01; …...

饿了么三面:让你怀疑人生的Spring Boot夺命连环40问

饿了么三面&#xff1a;让你怀疑人生的Spring Boot夺命连环40问 1 、什么是springboot &#xff1f; 用来简化spring应用的初始搭建以及开发过程 使用特定的方式来进行配置&#xff08;properties或yml文件&#xff09; 创建独立的spring引用程序 main方法运行 嵌入的Tomca…...

如何零基础制作一款自己的游戏!(一)

如何零基础制作一款游戏&#xff08;一&#xff09; 文章目录如何零基础制作一款游戏&#xff08;一&#xff09;前言一、软件下载以及创建工程二、使用步骤1.进入工程2.设置更改3.更改界面4.脚本更改5.下载插件6.如何设置障碍总结前言 今天闲着无事逛朋友圈&#xff0c;发现我…...

瓢城Web俱乐部

网址:http://www.ycku.com/course/ 一个不错的在线视频教程网站&#xff0c;部分教程还在更新&#xff0c;在手机或者iPad上扫描网页上的二维码可以在移动端打开课程&#xff0c;还是很方便的&#xff0c;每节课的时间比较长&#xff0c;讲的很详细&#xff0c;也可以下载观看。…...

运维人生攻城狮的第一次搬家

工作以来搬家都搬了好多趟了&#xff0c;今天再次搬家&#xff0c;下面开始回忆并记录下来&#xff0c;用于缅怀我们攻城狮的青春人生。 刚开始上班第一间公司&#xff0c;福利还不错&#xff0c;先住在公司宿舍&#xff0c;一间宿舍几间房&#xff0c;和几个前辈程序员住一起…...

html静态页面案例

前言 开始学习前端时适用的静态网页小案例 htmlcss 一、效果 二、页面分布 分为五个基础页面 index.html information.html scenery.html ticket.html about.html 1.index.html <!DOCTYPE html> <html><head><meta charset"utf-8">…...

前端框架——BootStrap学习

BootStrap简单总结下&#xff1a;1.栅格系统&#xff0c;能够很好的同时适应手机端和PC端&#xff08;及传说中的响应式布局&#xff09; 2.兼容性好接下来是对BootStrap学习的一些基础案例总结和回顾: 首先引入&#xff1a;bootstrap.min.css&#xff0c;jquery.js&#xff0…...

(项目实战五)响应式案例和关于

一、案例 案例页面的代码如下&#xff1a;<nav class"navbar navbar-default navbar-fixed-top"><div class"container"><div class"navbar-header"><a href"#" class"navbar-brand logo"><img …...

[jQuery知识]jQuery之知识十一-Ajax初级

前言 1.Ajax 概述 2.load()方法 3..get()和.post() Ajax 全称为:“Asynchronous JavaScript and XML”(异步 JavaScript 和 XML)&#xff0c; 它并不是 JavaScript 的一种单一技术&#xff0c;而是利用了一系列交互式网页应用相关的技术所形 成的结合体。使用 Ajax&#xff0…...

[09]项目实战-PC 端固定布局(9)

一&#xff0e;资讯内容 和首页一样&#xff0c;只不过这里&#xff0c;布局方式有所不同&#xff0c;具体如下&#xff1a; 二&#xff0e;代码详解 //全部代码 <figure class"tour"><img src"img/tour1.jpg" alt"曼谷-芭提雅6 日游"…...

Ajax 整理总结(入门)

Ajax 学习要点&#xff1a;1.Ajax 概述2.load()方法3.$.get()和$.post()4.$.getScript()和$.getJSON()5.$.ajax()方法6.表单序列化一&#xff0e;Ajax 概述 1.JavaScript&#xff0c;通过用户或其他与浏览器相关事件捕获交互行为&#xff1b; 2.XMLHttpRequest 对象&#xff0c…...

三千弱水,总有一瓢知我冷暖

红尘太喧嚣&#xff0c;非我所恋&#xff1b;世间太繁华&#xff0c;非我所羡&#xff1b;情感太易淡&#xff0c;非我所控。曾经受过的伤已是寻常&#xff0c;曾经爱过的人已成篇章&#xff0c;那个渴望在诗酒年华&#xff0c;与伊策马天涯的我&#xff0c;如今&#xff0c;只…...

[11]项目实战-PC 端固定布局(11)

一&#xff0e;风景欣赏 预览图和首页差不多。具体代码如下&#xff1a; //风景欣赏 HTML 部分<div class"list scenery"><section><h2>风景欣赏</h2><figure><img src"img/s1.jpg" alt"曼谷-芭提雅"><…...

完善1

1〉题目避免重复&#xff1a;可以先看计算结果对于计算结果相同的式子比较x&#xff0c;y的值&#xff0c;看是否相同。 2〉题目数量&#xff1a;通过一个for循环语句for&#xff08;int i ,i<num,i&#xff09;,num为要计算的题目的数量 3〉打印方式&#xff1a;直接竖排的…...

项目实战--响应式导航[1]

一&#xff0e;响应式导航 .logo { padding:0; } #myCarousel { margin: 50px 0 0 0; //轮播图和导航不会重叠 } #navbar-collapse ul { margin-top:0; } .carousel-inner img { margin: 0 auto; //让轮播器的图片自动居中 } .carousel-control { font-size: 100…...