leetcode hot100刷题日记——2.字母异位词分组
涉及知识点:vector、哈希表
- 解答
- 我的解答的时间复杂度分析
- 我的解答的空间复杂度分析
- 复习:排序算法的时间复杂度
和第一题需要的知识点相同,所以知识点复习可见 link1《leetcode hot100刷题日记——1.两数之和》
解题思路:是字母异位词的字符串的组成字母是相同的,所以可以对从strs取出来的字符串按照字母顺序排序,并作为hash表唯一的key。如果是字母异位词,那就放在一个key里。
解答
class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {//建立一个哈希表,哈希表的key是字母串(按照字母顺序排序),value是和字母串字母相同的数组元素unordered_map<string,vector<string>>map;for(string &str:strs){string sorted=str;sort(sorted.begin(),sorted.end());//这里要注意一下字符串内部的字母是咋排序的map[sorted].push_back(str);}vector<vector<string>> res;for(auto &m:map){res.push_back(m.second);//first,second联想一下}return res;}
};
我的解答的时间复杂度分析
- 遍历字符串数组:需要对输入的字符串数组进行一次完整遍历,时间复杂度为 O(n),其中 n 是字符串的数量。
- 排序每个字符串:对每个字符串进行排序的时间复杂度取决于字符串的长度 k。对于每个字符串,排序的时间复杂度为 O(klogk)。因此,对于所有 n 个字符串,总时间复杂度为 O(n⋅klogk)。
- 遍历哈希表构建结果:遍历哈希表并将每个分组添加到结果列表的时间复杂度为 O(m⋅l),其中 m 是哈希表中键值对的数量(即不同字母组合的数量),l 是每个分组的平均字符串数量。在最坏情况下,所有字符串互为不同变位词,此时 m=n 且 l=1,总时间复杂度为 O(n)。
- 综上,整个算法的时间复杂度为 O(n⋅klogk),其中 k 是字符串的平均长度,主导因素为排序操作的耗时。
我的解答的空间复杂度分析
- 哈希表:哈希表需要存储每个排序后的字符串作为键,以及对应的原始字符串列表作为值。
每个键的长度为 k,假设所有键的总数为 m,键的总空间为 O(m⋅k);
每个值存储原始字符串列表,所有值的总空间为 O(n⋅k)(所有原始字符串的总长度)。 - 结果列表:结果列表中包含所有字符串,总空间为 O(n⋅k)。
因此,整个算法的空间复杂度为 O(n⋅k+m⋅k)。在最坏情况下(所有字符串互为不同变位词),m=n,空间复杂度为 O(n⋅k);在最优情况下(所有字符串为同一变位词),m=1,空间复杂度仍为 O(n⋅k)。
复习:排序算法的时间复杂度
排序算法 | 最好情况时间复杂度 | 平均情况时间复杂度 | 最坏情况时间复杂度 |
---|---|---|---|
冒泡排序 (Bubble Sort) | O(n) | O(n^2) | O(n^2) |
选择排序 (Selection Sort) | O(n^2) | O(n^2) | O(n^2) |
插入排序 (Insertion Sort) | O(n) | O(n^2) | O(n^2) |
希尔排序 (Shell Sort) | O(nlogn) | O(n^1.25) | O(n^2) |
归并排序 (Merge Sort) | O(nlogn) | O(nlogn) | O(nlogn) |
快速排序 (Quick Sort) | O(nlogn) | O(nlogn) | O(n^2) |
堆排序 (Heap Sort) | O(nlogn) | O(nlogn) | O(nlogn) |
计数排序 (Counting Sort) | O(n+k) | O(n+k) | O(n+k) |
桶排序 (Bucket Sort) | O(n+k) | O(n+k) | O(n^2) |
基数排序 (Radix Sort) | O(n⋅k) | O(n⋅k) | O(n⋅k) |
相关文章:
leetcode hot100刷题日记——2.字母异位词分组
涉及知识点:vector、哈希表 解答我的解答的时间复杂度分析我的解答的空间复杂度分析复习:排序算法的时间复杂度 和第一题需要的知识点相同,所以知识点复习可见 link1《leetcode hot100刷题日记——1.两数之和》 解题思路:是字母异位词的字符…...
elementUI 单选框存在多个互斥的选项中选择的场景
使用 el-radio-group 来使用单选框组,代码如下: <el-radio-group input"valueChangeHandler" v-model"featureForm.type"><el-radio name"feature" label"feature">业务对象</el-radio><…...
基于区块链技术的智能汽车诊断与性能分析
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 钝感力的“钝”,不是木讷、迟钝,而是直面困境的韧劲和耐力,是面对外界…...
基于区块链技术的供应链溯源系统:重塑信任与透明度
在当今全球化的商业环境中,供应链的复杂性不断增加,产品从原材料采购到最终交付消费者手中的过程涉及多个环节和众多参与者。然而,传统供应链管理面临着诸多挑战,如信息不透明、数据易篡改、追溯困难等,这些挑战不仅影…...
基于OpenCV的实时文档扫描与矫正技术
文章目录 引言一、系统概述二、核心代码解析1. 导入必要库2. 辅助函数定义3. 坐标点排序函数4. 透视变换函数5. 主程序流程 三、完整代码四、结语 引言 在日常工作和学习中,我们经常需要将纸质文档数字化。手动拍摄文档照片常常会出现角度倾斜、透视变形等问题&…...
基于STM32F103与Marvell88W8686的WIFI无线监控视频传输系统研发(论文)
基于STM32F103与Marvell88W8686的WIFI无线监控视频传输系统研发 中文摘要 在当今社会信息化进程不断加速的时代背景下,众多领域对于监控系统的需求日益增长,像车内安全监控、电梯运行监控等场景都离不开监控系统的支持。过去,不少领域普遍采用…...
华为云Astro中各种变量与参数的区别与用法
目录 🧠 华为云 Astro 各类变量与参数详解 🧩 一、变量与参数的核心作用是什么? 🖼️ 二、整体分类与结构图 📘 三、逐一详细解析 + 类比说明 + 使用建议 🔹 1. 输入参数(Input Parameter) 🔹 2. 输出参数(Output Parameter) 🔹 3. 变量(本地变量)…...
数字人技术的核心:AI与动作捕捉的双引擎驱动(210)
**摘要:**数字人技术从静态建模迈向动态交互,AI与动作捕捉技术的深度融合推动其智能化发展。尽管面临表情僵硬、动作脱节、交互机械等技术瓶颈,但通过多模态融合技术、轻量化动捕方案等创新,数字人正逐步实现自然交互与情感表达。…...
华为云Astro轻应用创建业务对象(BO)的概念梳理
目录 一、业务对象(BO)是什么?——【详细概念解释】 二、形象理解业务对象(BO) 🍱 类比方式: 📦 举个具体例子:以做一个“智能烟雾报警系统”应用 三、为什么使用BO很重要? 四、小结: 一、业务对象(BO)是什么?——【详细概念解释】 在华为云Astro轻应用…...
MySQL开发规范
目录 一、建表规约 二、索引规约 三、SQL语句 四、 ORM映射 一、建表规约 强制: 1、表达是与否概念的字段,必须使用is_xxx的方式命名(PoJo中不加is前缀),数据类型是unsigned tinyint(1表示是…...
K8s入门教程(一)
Kubernetes(K8s)入门教程:从零开始掌握容器编排 目录 Kubernetes(K8s)入门教程:从零开始掌握容器编排 1. Kubernetes 简介 1.1 什么是 Kubernetes? 1.2 核心功能 2. 环境搭建与 Minikube 安装 2.1 安装 Minikube 安装步骤(以 macOS 为例): 安装 kubectl(Kub…...
k8s备份namespace
在 Kubernetes 中备份 Namespace 有多种方法,以下是几种常见的备份方式: 1.使用 kubectl 命令备份 通过 kubectl 命令可以导出指定 Namespace 中的资源,生成 YAML 文件进行备份。 备份所有资源: kubectl -n <namespace> ge…...
前端动画库 Anime.js 的V4 版本,兼容 Vue、React
前端动画库 Anime.js 更新了 V4 版本,并对其官网进行了全面更新,增加了许多令人惊艳的效果,尤其是时间轴动画效果,让开发者可以更精确地控制动画节奏。 这一版本的发布不仅带来了全新的模块化 API 和显著的性能提升,还…...
OpenHarmony外设驱动使用 (四),Face_auth
OpenHarmony外设驱动使用 (四) Face_auth 概述 功能简介 人脸识别功能是端侧设备不可或缺的一部分,为设备提供一种用户认证能力,可应用于设备解锁、支付、应用登录等身份认证场景。它是基于人的脸部特征信息进行身份识别的一种…...
【Java ee初阶】jvm(1)
一、JVM Java虚拟机 面试中相关的问题有三块: 1.JVM内存区域划分 2.JVM的类加载机制 3.JVM的垃圾回收机制 JDK、JRE 和 JVM 的关系 JDK(Java Development Kit)是 Java 开发工具包,包含了编写、编译和调试 Java 程序所需的所…...
【Java ee初阶】jvm(2)
类加载机制: JVM从最开始的读取.class文件,到最终构造完成 类 对象的整个过程,也就是把 类 从硬盘 加载到内存中的机制。 Java的类加载机制主要分为五个步骤:加载、验证、准备、解析和初始化。 步骤一 加载(Loading…...
Django 项目创建全攻略
目录 一、环境准备 1. 安装 Python 2. 安装虚拟环境(可选但推荐) 3. 安装 Django 二、创建 Django 项目 1. 使用命令创建项目 2. 运行开发服务器 三、创建 Django 应用 1. 创建应用 2. 注册应用 四、配置项目 1. 数据…...
windows11 安装好后右键没有 git bash 命令
win键 R 键,输出 regedit,打开注册表 找到 \HKEY_CLASSES_ROOT\Directory\Background\shell 新建项 git-bash 然后在 git-bash 下在新建项 Command,默认值设为 "C:\Program Files\Git\git-bash.exe" --cd"%v." 在 …...
Java八股文——Java基础篇
目录 1、你是怎样理解OOP面向对象2、重载和重写的区别3、接口与抽象类的区别4、深拷贝与浅拷贝的理解5、sleep和wait区别主要区别 6、什么是自动拆装箱,int和Integer有什么区别自动拆装箱int和Integer的区别Integer缓存机制 7、和equals区别String特殊情况 8、Strin…...
蓝桥杯19682 完全背包
问题描述 有 N 件物品和一个体积为 M 的背包。第 i 个物品的体积为 vi,价值为 wi。每件物品可以使用无限次。 请问可以通过什么样的方式选择物品,使得物品总体积不超过 M 的情况下总价值最大,输出这个最大价值即可。 输入格式 第一行…...
2025年- H27-Lc135- 239.滑动窗口最大值(自定义双端队列)---java版
1.题目描述 2.思路 (1)双端队列可以移除最左边的元素,也可以移除最右边的元素(两端移除) (2)在最右边插入元素(右边加入) (3)队列单调性…...
EKS 工作节点的集群网络架构
AWS EKS(弹性 Kubernetes 服务)是亚马逊提供的托管 Kubernetes 服务,一旦配置完成,即可像变魔术一样运行。但这通常是 EKS 的默认设置。如果您打算根据组织的设计、合规性标准和隐私要求进行自定义,该怎么办࿱…...
【技海登峰】Kafka漫谈系列(十一)SpringBoot整合Kafka之消费者Consumer
【技海登峰】Kafka漫谈系列(十一)SpringBoot整合Kafka之消费者Consumer spring-kafka官方文档: https://docs.spring.io/spring-kafka/docs/2.8.10/reference/pdf/spring-kafka-reference.pdf KafkaTemplate API: https://docs.spring.io/spring-kafka/api/org/springframe…...
Python字符串格式化(一):三种经典格式化方法
文章目录 一、% operator:C语言风格的初代格式化方案(Python 2.0引入)1. 语法核心:占位符与类型码2. 进阶用法:格式修饰符3. 致命缺陷:类型严格匹配的陷阱4. 适用场景:旧代码维护的兼容性选择 二…...
浅谈无服务器WebSocket的优势
实际上,一个实用的解决方案是将构建业务关键型实时平台的复杂性卸载到专门的云服务中。 完全托管的无服务器 WebSocket 解决方案为事件驱动的消息传递提供了基础结构;它使底层基础设施成为一种商品。客户端使用提供程序服务发送/接收低延迟消息,并专注于…...
10.7 LangChain v0.3架构大升级:模块化设计+多阶段混合检索,开发效率飙升3倍!
LangChain v0.3 技术生态与未来发展 关键词:LangChain Chains, Agents 架构, Retrieval Strategy, LangGraph, 模块化设计 3. LangChain 项目:Chains, Agents, Retrieval Strategy LangChain v0.3 通过 Chains-Agents-Retrieval 三位一体的技术栈,构建起完整的大模型应用开…...
GLPK(GNU线性规划工具包)中建模语言MathProg的使用
GNU MathProg是一种用于描述线性数学规划模型的建模语言。用GNU MathProg语言编写的模型描述由一组语句和数据块组成。 在MathProg中,模型以集合、参数、变量、约束和目标(sets, parameters, variables, constraints, objectives称为模型对象)的形式进行描述。 在Ma…...
系统思考:IT企业项目困境分析
最近遇到一家快速发展的IT技术公司,遭遇了项目进度滞后、团队沟通不畅和资源分配不合理等一系列挑战。虽然他们拥有一支技术强大的团队,但在项目管理和团队协作上却显得力不从心。结果,多个项目超预算、交期延迟,客户满意度直线下…...
计算机网络 - 2.基础协议
1.TCP协议 1.TCP(Transmission Control Protocol):传输控制协议2.TCP协议是一种面向连接的、可靠的、 基于字节流的传输层通信协议 1.面向连接:两个使用TCP协议的应用(通常一个客户和一个服务器)在彼此交换数据包之前必须先建立一个TCP连接2.可靠的 1.数据传输之前都要建立…...
go语法大赏
前些日子单机房稳定性下降,找了好一会才找到真正的原因。这里面涉及到不少go语法细节,正好大家一起看一下。 一、仿真代码 这是仿真之后的代码 package mainimport ("fmt""go.uber.org/atomic""time" )type StopSignal…...
运行vscode编辑器源码
距离上次二次开发vscode已经是三年前的事了,当时是1.60.0版本,目前vscode已升级到了1.99.2版本,里面改动很大,最近下载下来了新版源码跑起来看看 准备node、python 源码里面node版本做了限制 2025-01-27 09:53:00.450 [info] Fo…...
ShenNiusModularity项目源码学习(26:ShenNius.Admin.Mvc项目分析-11)
本文学习并分析ShenNiusModularity项目中商城系统模块的小程序用户页面、用户收货地址页面。 1、小程序用户页面 小程序用户页面用于检索、浏览使用商城系统的用户数据(保存在shop_appuser表内,系统用户保存在sys_user表内),该页…...
C#中的成员常量:编译时的静态魔法
在C#编程中,常量(const)是一个强大而特殊的语言特性,特别是当它们作为类的成员时。本文将深入探讨成员常量的特性、使用场景以及与静态量的区别。 成员常量的基本特性 成员常量是声明在类内部的常量,具有以下核心特点: 声明位置…...
C# 深入理解类(成员常量)
成员常量 成员常量类似前一章所述的局部常量,只是它们被声明在类声明中而不是方法内,如下面的 示例: 与局部常量类似,用于初始化成员肯量的值在编译时必须是可计算的,而且通常是一个预定 义简单类型或由它们组成的表达…...
服务端HttpServletRequest、HttpServletResponse、HttpSession
一、概述 在JavaWeb 开发中,获取客户端传递的参数至关重要。http请求是客户端向服务端发起数据传输协议,主要包含包含请求行、请求头、空行和请求体四个部分,在这四部分中分别携带客户端传递到服务端的数据。常见的http请求方式有get、post、…...
有哪些GIF图片转换的开源工具
以下是关于GIF图片转换的开源工具的详细总结,涵盖功能特点、适用场景及用户评价: 1. FFmpeg 功能特点: 作为开源命令行工具,FFmpeg支持视频转GIF、调整帧率、分辨率、截取片段等操作,可通过脚本批量处理。适用场景: 适合开发者或技术用户进行高效批处理,常用于服务器端自…...
Vue.js教学第五章:计算属性与侦听器详解
Vue.js 之计算属性与侦听器详解 一、计算属性 (一)概念 计算属性(Computed Properties)是 Vue.js 中的一个核心概念。它允许我们基于一个或多个数据属性来定义一个新的属性,该属性的值会根据其依赖的数据属性的变化而自动更新。这就好像是一个 “智能” 属性,它的值不是…...
第三章:UI 系统架构拆解与动态界面管理实录
还记得我们第二章刚跑通主场景,那时候是不是觉得“终于见到界面了”?但请等等,你看到的只是冰山一角,下面藏着的是 UIManager 的地狱之门。 本章我们将深入探讨: UI 界面如何加载(Prefab 动态加载机制&…...
第四章:WebSocket 通信机制全解与客户端发包实录
如果你以为一个游戏启动后只靠本地逻辑运转,那你真是低估了网络通信的存在感。在互动组件项目里,WebSocket 才是真正的灵魂通道——UI 再好看,没包发出去也等于白搭。 本章我们深入讲解 WebSocket 在安卓前端项目中的应用,从封装结…...
pnpm项目内网迁移
pnpm项目内网迁移 文章目录 pnpm项目内网迁移0.前言1.基础环境安装2.构建pnpm离线安装包3.使用pnpm重新安装项目依赖4.项目迁移参考链接: 0.前言 要将一个依赖pnpm的项目迁移到内网离线环境下进行开发。 1.基础环境安装 要保证NodeJS版本一致,否则执行…...
C++23 放宽范围适配器以允许仅移动类型(P2494R2)
文章目录 引言背景与动机提案内容与实现细节提案 P2494R2实现细节编译器支持 对开发者的影响提高灵活性简化代码向后兼容性 示例代码总结 引言 C23 标准中引入了许多重要的改进,其中一项值得关注的特性是放宽范围适配器(range adaptors)以允…...
[ctfshow web入门] web119
信息收集 import requestsurl "http://51a7e437-2e66-4742-bbfe-e4cce44e360b.challenge.ctf.show/" for i in range(255):data {"code": f"{chr(i)}"}response requests.post(url, datadata)# print(len(response.text))# print(response.t…...
vector--OJ3
链接: [link](链接: link) class Solution { public: vector<string> str{ "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };void CB(string& …...
第6章 实战案例:基于 STEVAL-IDB011V1 板级 CI/CD 全流程
在前五章中,我们完成了嵌入式 CI/CD 从环境搭建、编译自动化、测试自动化、发布分发到监控回归的全技术链条。本章将以 STEVAL-IDB011V1(搭载 BlueNRG-355)评估板为实战载体,手把手演示如何在 GitLab CI(或 Jenkins)上,构建一条从 Git Push → 编译 → 测试 → 刷写 → …...
逆变器的输出外特性分析
VSG 并网状态下,考虑到弱电网下线路阻抗不能忽略,VSG 的功率传输模型可以表示为 VSG 的输出电压经过线路阻抗后串联至电网(考虑滤波电感,且忽略滤波电容作用)。设 U 为 VSG 输出电压的幅值,Ug为电网电压的幅…...
如何给PSCAD添加库文件
1、点击Options 2、选择蓝色的选项 3、查看Intel(R) Visual Fortran Compiler XE 的版本 4、打开原文件的Library 5、打开 6、点击这个文件的右键 7、然后选择第一项project setting 9、先把第8步中link里面原有的路径删除,再点browes[A1] ,然后选择 [A…...
基于simulink搭建的模块化多电平MMC仿真模型
1. 模块化多电平换流器的运行原理 1.1模块化多电平换流器的拓扑结构 MMC共由6个桥臂构成。其中每个桥臂由若干个串联且结构相同的子模块(Sub-Module, SM)与一个电抗器L串联…...
基于simulink的LCC-HVDC输电模型
1.本模型基于simulink搭建常规直流输电模型,运行稳定。 有需要交流或者模型的可在CSDN上留言...
PWM整流器双闭环PI参数的整定
1. 整流侧电路拓扑图 整流电路由交流侧电源、线路电阻、线路电抗、整流器、滤波电容以及负载组成。整体电路图如图1所示。 图 1 整流电路拓扑图 其中,IGBT的开关状函数如下式所示 根据图 1 列出 KVL 公式如下,电流的正方向是从左到右 对于每一相的IGBT相…...
柔性直流输电系统介绍及simulink模型的搭建
1. 柔性直流输电的运行原理 柔性直流输电系统由电压源型换流器与直流输电线路构成, 图 1‑1所示为单端电压源型换流器原理图。柔性直流输电系统的功率可以双向流动,即换流器既可以作为整流站将从交流系统接收的功率通过直流线路输送出去,也可以作为逆变站将通过直流…...