kotlin实现ArrayDeque
Deque双端队列,一直在使用,却从未了解过源码。
内部逻辑其实很简单
- 可扩容数组
- 循环队列,循环栈
- 扩容倍数1.5,size=size+(size shr 1)
- 只从两端存取元素
fun main() {val deque = MyArrayDeque()repeat(16) {deque.addLast(it)}while (deque.isNotEmpty()) {println(deque.removeLast())}}class MyArrayDeque {// 存元素,不能存null,初始容量为16,避免频繁扩容,一次扩容1.5倍private var arr = arrayOfNulls<Int>(16)// 头尾节点,tail一直为nullprivate var head: Int = 0private var tail: Int = 0// 实际容量private var size: Int = 0fun addFirst(value: Int) {// 扩容grow()head = dec(head)arr[head] = valuesize++}fun addLast(value: Int) {// 扩容grow()arr[tail] = valuetail = inc(tail)size++}fun removeFirst(): Int {if (isEmpty()) {return -1}val res = arr[head]!!head = inc(head)size--return res}fun removeLast(): Int {if (isEmpty()) {return -1}tail = dec(tail)size--return arr[tail]!!}// 加一fun inc(i: Int) = if (i == arr.lastIndex) 0 else i + 1// 减一fun dec(i: Int) = if (i == 0) arr.lastIndex else i - 1// 扩容,内部不一定扩容private fun grow() {// 至少还有一个容量if (size < arr.size - 1) {return}// 一次扩容1.5倍val newArr = arrayOfNulls<Int>(arr.size + (arr.size shr 1))// 从0开始if (head < tail) {for (i in head..<tail) {newArr[i - head] = arr[i]}} else {// 临时下标var index = 0// 现存头部for (i in head..arr.lastIndex) {newArr[index++] = arr[i]}// 尾部移动后面for (i in 0..<tail) {newArr[index++] = arr[i]}}// 扩容后,head和tail重新计算arr = newArrhead = 0tail = size}fun size() = sizefun isEmpty() = size() == 0fun isNotEmpty() = size() > 0override fun toString(): String {if (size == 0) {return ""}val sb = StringBuilder()if (head < tail) {for (i in head..<tail) {if (sb.isNotEmpty()) {sb.append(", ")}sb.append(arr[i])}} else {for (i in head..arr.lastIndex) {if (sb.isNotEmpty()) {sb.append(", ")}sb.append(arr[i])}for (i in 0..<tail) {// 此时一定有至少一个元素,不用判断sb.append(", ").append(arr[i])}}return sb.toString()}
}
相关文章:
kotlin实现ArrayDeque
Deque双端队列,一直在使用,却从未了解过源码。 内部逻辑其实很简单 可扩容数组循环队列,循环栈扩容倍数1.5,sizesize(size shr 1)只从两端存取元素 fun main() {val deque MyArrayDeque()repeat(16) {deque.addLast(it)}while …...
java时间格式化
1,CST时间格式化,这个一般是返回值的类型为 Date 类型,如果不做处理,返给前端的就是时间戳,当然也可以更改返回值类型为 String,这样就不用处理了。方法如下: /*** 格式化时间* param date Thu…...
ArduPilot开源飞控之AP_Baro_SITL
ArduPilot开源飞控之AP_Baro_SITL 1. 源由2. back-end抽象类3. 方法实现3.1 AP_Baro_SITL3.2 _timer3.3 temperature_adjustment3.4 wind_pressure_correction3.5 update 4. 参考资料 1. 源由 鉴于ArduPilot开源飞控之AP_Baro中涉及Sensor Driver有以下总线类型: …...
基于Java的病人跟踪治疗管理系统设计与实现(源码+lw+部署文档+讲解等)
文章目录 前言具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序(小蔡coding)有保障的售后福利 代码参考源码获取 前言 💗博主介绍:✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作…...
RCD吸收电路的工作原理及参数计算方法详解
在电子电力技术和自动化控制领域内,RCD吸收电路非常重要,它的作用是吸收瞬间过电压和过电路免受电压波动的影响,因此被广泛应用在各种设备及系统中,今天凡亿将带领小伙伴们来了解下RCD吸收电路的工作原理及计算方法。 1、RCD吸收电…...
leetcode做题笔记169. 多数元素
给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入:nums [3,2,3] 输出:3 示例 …...
FATFS f_printf 如何支持写入浮点数据。
参考原子和网上的移植最新的fatfs系统后,挂载打开文件始终返回13错误代码,在自己的项目中移植最新的fatfs0.15版本解决问题,使用f_printf能成功进行浮点数据写入了 参考的文章如下: https://zhuanlan.zhihu.com/p/444427537 问题描述 在使用fatfs的f_printf向文件.csv中写入…...
postman忘记密码提交没响应
现象:通过客户端进到账户页面一直无响应,可copy the url 到浏览器进入页面,使用浏览器提交几次还是没响应。 实测有用方法: 1、通过手机进入官网 https://www.getpostman.com ,找到忘记密码入口。 2、多提交几次后&…...
初学vue,想自己找个中长期小型项目练练手,应该做什么?
前言 可以试着做一两个完整的后台管理项目后再去做其他的,下面推荐一些github上的vue后台管理的项目,可以自己选择性的练一下手 Vue2 1、iview-admin Star: 16.4k 基于 iview组件库开发的一款后台管理系统框架,提供了一系列的强大组件和基…...
【牛客面试必刷TOP101】Day11.BM63 跳台阶和 BM67 不同路径的数目(一)
作者简介:大家好,我是未央; 博客首页:未央.303 系列专栏:牛客面试必刷TOP101 每日一句:人的一生,可以有所作为的时机只有一次,那就是现在!!!&…...
[NOIP 2022] 建造军营 题解
题目 P1 边双缩点 观察样例二,可以发现边双内的边可选可不选。由此考虑边双缩点,Tarjan 找桥即可,缩点后变成一棵树。 P2 设计状态 用最终合法答案形态截这颗树,设计 f u f_u fu 表示 u u u 子树内非空,且子树…...
射频识别技术(RFID)在智能制造模具管理中的应用
背景介绍 模具是工业生产的核心装备,被誉为“工业之母”,广泛应用于机械、汽车、轻工、电子、化工、冶金、建材等各个行业,是制造加工企业的重要资产,然而,传统的人工纸质记录方式已无法满足模具管理的需求࿰…...
奖品定制经营商城小程序的作用是什么
奖品是激励人员团体很好的方式,也是荣誉象征,奖牌、奖杯、高端礼盒等,同时市场中团体非常多,其需求也是很多,尤其定制方面,就更是不用说。 对奖品定制企业来说,除了线下门店获客经营外…...
深度学习常用脚本总结
👨💻个人简介: 深度学习图像领域工作者 🎉工作总结链接:https://blog.csdn.net/qq_28949847/article/details/128552785 链接中主要是个人工作的总结,每个链接都是一些常用demo,…...
hive数据表创建
目录 分隔符 分区表 二级分区 分桶表 外部表 分隔符 CREATE TABLE emp( userid bigint, emp_name array<string>, emp_date map<string,date>, other_info struct<deptname:string, gender:string>) ROW FORMAT DELIMITED FIELDS TERMINATED BY \t COL…...
查看本机Arp缓存,以及清除arp缓存
查看Arp缓存目录 Windows 系统使用 winR,输入cmd 在命令窗口输入 arp -a 删除Arp缓存目录 在命令窗口输入 arp -d * 查看主机路由表...
Unity MRTK Hololens2眼动交互
/** ** UnityVersion : 2021.3.6f1* Description : 眼部交互基类* Author: * CreateTime : 2023-10-11 09:43:20* Version : V1.0.0* * */using System.Collections.Generic; using Microsoft.MixedReality.Toolkit.Input; using UnityEngine;namespace MRTKExtend.EyeTrackin…...
接口自动化测试 —— 协议、请求流程
一、架构 CRM客户关系管理系统 SAAS Software As A Service 软件即服务 PAAS Platform AS A Service 平台即服务 快速交付→ 快:自己去干、有结果、事事有回音、持续改进 单体架构——》垂直架构——》面向服务架构——》微服务架构(分布式…...
JDK安装详细教程
JDK安装详细教程 国内大多数使用的是1.8的版本,对于初学者来说这个版本很友善,不过由于我安装过了1.8,所以我这里演示JDK21 的安装,过程并无区别,只在下载时注意选择1.8版本。1.8就是JDK8. 文章目录 JDK安装详细教程一…...
vulnhub_Fowsniff靶机渗透测试
Fowsniff靶机 靶机地址:https://www.vulnhub.com/entry/fowsniff-1,262/ 文章目录 Fowsniff靶机信息收集web渗透密码碰撞POP3邮件服务器渗透获取权限权限提升靶机总结 信息收集 通过nmap扫描,靶机开放22 80 110 143端口,110是pop3邮件服务…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果 API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的:a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...
