LeetCode-49. 字母异位词分组【数组 哈希表 字符串 排序】
LeetCode-49. 字母异位词分组【数组 哈希表 字符串 排序】
- 题目描述:
- 解题思路一:哈希表和排序,这里最关键的点是,乱序单词的排序结果必然是一样的(从而构成哈希表的key)。
- 解题思路二:
- 解题思路三:用字符计数数组作为哈希表的key。注意将数组转为tuple因为数组不可作为哈希表的key。
题目描述:
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]
提示:
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母
解题思路一:哈希表和排序,这里最关键的点是,乱序单词的排序结果必然是一样的(从而构成哈希表的key)。
class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:res = []mapping = {}for s in strs:key = str(sorted(s))mapping[key] = mapping.get(key, []) + [s]for key, value in mapping.items():res.append(value)return res
时间复杂度:O(n)
空间复杂度:O(n)
解题思路二:
class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:table = collections.defaultdict(list)for s in strs:key = "".join(sorted(s))table[key].append(s)return list(table.values())
时间复杂度:O(nk logk)
空间复杂度:O(nk) 其中 n 是strs 中的字符串的数量,k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。
解题思路三:用字符计数数组作为哈希表的key。注意将数组转为tuple因为数组不可作为哈希表的key。
class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:mp = collections.defaultdict(list)for st in strs:counts = [0] * 26for ch in st:counts[ord(ch) - ord("a")] += 1# 需要将 list 转换成 tuple 才能进行哈希mp[tuple(counts)].append(st)return list(mp.values())
时间复杂度:O(nk)
空间复杂度:O(nk)
相关文章:
LeetCode-49. 字母异位词分组【数组 哈希表 字符串 排序】
LeetCode-49. 字母异位词分组【数组 哈希表 字符串 排序】 题目描述:解题思路一:哈希表和排序,这里最关键的点是,乱序单词的排序结果必然是一样的(从而构成哈希表的key)。解题思路二:解题思路三…...

绘制特征曲线-ROC(Machine Learning 研习十七)
接收者操作特征曲线(ROC)是二元分类器的另一个常用工具。它与精确度/召回率曲线非常相似,但 ROC 曲线不是绘制精确度与召回率的关系曲线,而是绘制真阳性率(召回率的另一个名称)与假阳性率(FPR&a…...

.Net 知识杂记
记录平日中琐碎的.net 知识点。不定期更新 目标框架名称(TFM) 我们创建C#应用程序时,在项目的工程文件(*.csproj)中都有targetFramework标签,以表示项目使用的目标框架 各种版本的TFM .NET Framework .NET Standard .NET5 及更高版本 UMP等 参考文档&a…...

海豚【货运系统源码】货运小程序【用户端+司机端app】源码物流系统搬家系统源码师傅接单
技术栈:前端uniapp后端vuethinkphp 主要功能: 不通车型配置不通价格参数 多城市定位服务 支持发货地 途径地 目的地智能费用计算 支持日期时间 预约下单 支持添加跟单人数选择 支持下单优惠券抵扣 支持司机收藏订单评价 支持订单状态消息通知 支…...

01---java面试八股文——mybatis-------10题
1、什么是MyBatis Mybatis是一个半ORM(对象关系映射)框架,它内部封装了JDBC,开发时只需要关注SQL语句本身,不需要花费精力去处理加载驱动、创建连接、创建statement等繁杂的过程。程序员直接编写原生态sql,…...

增强现实(AR)的开发工具
增强现实(AR)的开发工具涵盖了一系列的软件和平台,它们可以帮助开发者创造出能够将虚拟内容融入现实世界的应用程序。以下是一些在AR领域内广泛使用的开发工具。北京木奇移动技术有限公司,专业的软件外包开发公司,欢迎…...

用Unity制作正六边形拼成的地面
目录 效果演示 1.在Unity中创建正六边形 2.创建一个用于管理正六边形的类 3.创建一个用于管理正六边形地面的类 4.创建一个空对象并将游戏控制脚本挂上 5.设置正六边形碰撞所需组件 6.创建正六边形行为触发脚本并挂上 7.创建圆柱体——田伯光 8.创建圆柱体移动脚本 运…...
Spark部署详细教程
Spark Local环境部署 下载地址 https://dlcdn.apache.org/spark/spark-3.4.2/spark-3.4.2-bin-hadoop3.tgz 条件 PYTHON 推荐3.8JDK 1.8 Anaconda On Linux 安装 本次课程的Python环境需要安装到Linux(虚拟机)和Windows(本机)上 参见最下方, 附: Anaconda On Linux 安装…...

慧天[HTWATER]:创新城市水务科技,引领行业变革
【城市内涝水文水动力模型介绍】 慧天[HTWATER]软件:慧天排水数字化分析平台针对城市排水系统基础设施数据管理的需求,以及水文、水力及水质模拟对数据的需求,实现了以数据库方式对相应数据的存储。可以对分流制排水系统及合流制排水系统进行…...

vscode调试Unity
文章目录 vscode调试UnityC#环境需求开始调试 Lua添加Debugger环境配置联系.txt文件配置Java环境 添加调试代码断点不生效的问题 vscode调试Unity C# 现在使用vscode调试Unity的C#代码很简单,直接在vscode的EXTENSIONS里面搜索“Unity”,第一个就是&am…...
JavaScript是如何实现页面渲染的
JavaScript实现页面渲染主要涉及到对DOM的操作、样式的修改以及与后端数据的交互。以下是JavaScript实现页面渲染的主要步骤和方式: 一、DOM操作 创建和修改元素:JavaScript可以使用document.createElement()来创建新的DOM元素,使用appendC…...

【YOLOv8 代码解读】数据增强代码梳理
1. LetterBox增强 当输入图片的尺寸和模型实际接收的尺寸可能不一致时,通常需要使用LetterBox增强技术。具体步骤是先将图片按比例缩放,将较长的边缩放到设定的尺寸以后,再将较短的边进行填充,最终短边的长度为stride的倍数即可。…...

安卓调试桥ADB
Logcat 命令行工具 | Android Studio | Android Developers 什么是ADB ADB 全称为 Android Debug Bridge ,是 Android SDK (安卓的开发工具)中的一个工具,起到调试桥的作用,是一个 客户端 - 服务器端程序 。其中 …...

深入理解数据结构第一弹——二叉树(1)——堆
前言: 在前面我们已经学习了数据结构的基础操作:顺序表和链表及其相关内容,今天我们来学一点有些难度的知识——数据结构中的二叉树,今天我们先来学习二叉树中堆的知识,这部分内容还是非常有意思的,下面我们…...

面试题:JVM的垃圾回收
一、GC概念 为了让程序员更专注于代码的实现,而不用过多的考虑内存释放的问题,所以,在Java语言中,有了自动的垃圾回收机制,也就是我们熟悉的GC(Garbage Collection)。 有了垃圾回收机制后,程序员只需要关…...

Java8之接口默认方法
Java8之接口默认方法 一、介绍二、代码1、接口2、实现类3、测试代码4、效果 一、介绍 在Java8中,允许为接口方法提供一个默认的实现。必须用default修饰符标记这样一个方法。默认方法也可以调用其他方法 二、代码 1、接口 public interface PersonService {void…...
发挥ChatGPT潜力:高效撰写学术论文技巧
ChatGPT无限次数:点击直达 发挥ChatGPT潜力:高效撰写学术论文技巧 在当今信息爆炸的时代,如何高效撰写学术论文成为许多研究者关注的焦点。而随着人工智能技术的不断发展,如何利用ChatGPT这一先进的技术工具来提升论文写作效率,成…...

国产暴雨AI服务器X3418开启多元自主可控新篇章
在当前数字化转型的大潮中,算力作为新质生产力的重要动力引擎,对推动经济社会发展起着关键作用。尤其在人工智能领域,随着高性能、安全可控的AI算力需求持续攀升,国产化服务器的研发与应用显得尤为迫切。 作为国内专业的算力基础…...
webpack-dev-server 如何直接用IP打开
当你需要使用IP来访问服务器时,可能需要对 webpack-dev-server 进行相关设置; 当你使用PD虚拟机在Windows上调试时,可能会用到; 一、设置 host 通过webpack.config.js设置 devServer: {host: 0.0.0.0, }通过CLI设置 webpack-dev-s…...
Web框架开发-BBS项目预备知识
一、简介 博客系统(cnblog) https://www.cnblogs.com/ 1.django ORM (object relation mapping 对象关系映射) 表 = 类 对象 = 记录跨表查询 分组查询 annotate() 聚合查询 aggregate(*args, **kwargs) 2.bootstrap3.Ajax (jquery javascript) --- javascript 去写…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...

Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...

Unity VR/MR开发-VR开发与传统3D开发的差异
视频讲解链接:【XR马斯维】VR/MR开发与传统3D开发的差异【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...