LeetCode 热题 100-49. 字母异位词分组
题目描述
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 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] 仅包含小写字母
思路1
- 题目看起来比较简单,找出字符串数组中字母相同的字符串放在一个列表中,最后把所有列表返回
- 思路就是分两步,第一步找出来,第二步放在列表中
-
首先是怎么找出字母相同的数组,简单思路就是把单词中的每个字母对应的ASCII值加起来,这样做的问题也很明显,会出现单词不一样,但是加起来的值一样,做了改进对字母的ASCII值做平方再相加,目的是为了两个字母的差值更大,减小单词不一样,值加起来一样的概率,但是这个不是正确解决思路,只是一种投机行为,这种方式只能减小但不能完全消除,所以按照这个思路的代码通过了107 / 120个测试用例
-
第二步就是放在列表中,依照上述思路就想到了map,key是单词字母的ASCII值做平方再相加的结果,value就是一个列表里面是结果相同的单词,按照这种思路遍历完字符串数组再遍历map,将map的value添加到列表中返回,以下是代码
public List<List<String>> groupAnagrams(String[] strs) {List<List<String>> res = new ArrayList<>();if (strs.length <= 0) {return res;}if (strs.length <= 1) {res.add(new ArrayList<>(Collections.singleton(strs[0])));return res;}Map<Integer, List<String>> listMap = new HashMap<>();for (String s : strs) {int sum = 0;for (int i = 0; i < s.length(); i++) {sum += s.charAt(i) * s.charAt(i);}Integer integer = Integer.valueOf(sum);List<String> list = listMap.get(integer);if (null == list) {list = new ArrayList<>();}list.add(s);listMap.put(integer, list);}for (Map.Entry<Integer, List<String>> value : listMap.entrySet()) {res.add(value.getValue());}return res;}
-
思路1优化
- 优化的思路就是怎么得到每个单词的那个唯一值,投机的方式就是再放大,平方不行就立方依次往上,果然4次方就通过了,但是这种思路只能减小不能完全解决,而且运算量也会增大。
- 在美版leetcode上看到大神的思路,用质数表示26个字母,把字符串的各个字母相乘,这样可保证字母异位词的乘积必定是相等的。这种原则上可以,但是一些过长的字符串乘积值会溢出。
public static List<List<String>> groupAnagrams(String[] strs) {List<List<String>> res = new ArrayList<>();if (strs.length <= 0) {return res;}if (strs.length <= 1) {res.add(new ArrayList<>(Collections.singleton(strs[0])));return res;}int[] ints = new int[]{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};Map<Long, List<String>> listMap = new HashMap<>();for (String s : strs) {long sum = 1;for (int i = 0; i < s.length(); i++) {sum *= ints[s.charAt(i) - 'a'];}Long integer = Long.valueOf(sum);List<String> list = listMap.get(integer);if (null == list) {list = new ArrayList<>();}list.add(s);listMap.put(integer, list);}for (Map.Entry<Long, List<String>> value : listMap.entrySet()) {res.add(value.getValue());}return res; }
思路2
- 先对每个字符串的从小到大排序,含有相同字母排完序的就一致了,以排完序的作为key,value放未排序的字符串列表
public static List<List<String>> groupAnagrams(String[] strs) {List<List<String>> res = new ArrayList<>();if (strs.length <= 0) {return res;}if (strs.length <= 1) {res.add(new ArrayList<>(Collections.singleton(strs[0])));return res;}Map<String, List<String>> listMap = new HashMap<>();for (String s : strs) {String sort = s.chars().sorted().collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString();List<String> list = listMap.get(sort);if (null == list) {list = new ArrayList<>();}list.add(s);listMap.put(sort, list);}for (Map.Entry<String, List<String>> value : listMap.entrySet()) {res.add(value.getValue());}return res;} - 使用stream流操作
public static List<List<String>> groupAnagrams(String[] strs) {return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(s -> s.chars().sorted().collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString())).values());}```
相关文章:
LeetCode 热题 100-49. 字母异位词分组
题目描述 给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 输入: strs [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“n…...
TensorFlow入门(十九、softmax算法处理分类问题)
softmax是什么? Sigmoid、Tanh、ReLU等激活函数,输出值只有两种(0、1,或-1、1或0、x),而实际现实生活中往往需要对某一问题进行多种分类。例如之前识别图片中模糊手写数字的例子,这个时候就需要使用softmax算法。 softmax的算法逻辑 如果判断输入属于某一个类的概率大于属于其…...
刷题用到的非常有用的函数c++(持续更新)
阅读导航 字符串处理类一、stoi()(将字符串转换为整数类型)二、to_string()(将整数类型转换为字符串类型)三、stringstream函数(将一个字符串按照指定的分隔符进行分词) 字符串处理类 一、stoi()ÿ…...
黑客技术(网络安全)——自学思路
如果你想自学网络安全,首先你必须了解什么是网络安全!,什么是黑客!! 1.无论网络、Web、移动、桌面、云等哪个领域,都有攻与防两面性,例如 Web 安全技术,既有 Web 渗透2.也有 Web 防…...
lNmp安装:
一、LNMP LNMP架构是目前成熟的企业网站应用模式之一,指的是协同工作的一整套系统和相关软件, 能够提供动态Web站点服务及其应用开发环境。LNMP是一个缩写词,具体包括Linux操作系统、nginx网站服务器、MySQL数据库服务器、 PHP(或…...
Fisher辨别分析
问题要求 在UCI数据集上的Iris和Sonar数据上验证算法的有效性。训练和测试样本有三种方式(三选一)进行划分: (一) 将数据随机分训练和测试,多次平均求结果 (二)K折交叉验证 &…...
【Zookeeper专题】Zookeeper选举Leader源码解析
目录 前言阅读建议课程内容一、ZK Leader选举流程回顾二、源码流程图三、Leader选举模型图 学习总结 前言 为什么要看源码?说实在博主之前看Spring源码之前没想过这个问题。因为我在看之前就曾听闻大佬们说过【JavaCoder三板斧:Java,Mysql&a…...
机器学习之自训练协同训练
前言 监督学习往往需要大量的标注数据, 而标注数据的成本比较高 . 因此 , 利用大量的无标注数据来提高监督学习的效果有着十分重要的意义. 这种利用少量标注数据和大量无标注数据进行学习的方式称为 半监督学习 ( Semi…...
ubuntu 通过apt-get快速安装 docker
在使用 apt-get 安装 Docker 之前,你需要确保你的系统已经准备好并且已经更新了软件包列表。以下是在 Ubuntu 系统上使用 apt-get 安装 Docker 的步骤: 更新软件包列表: sudo apt-get update 安装依赖软件包,以确保可以通过 HTTPS 使用存储库: sudo apt-get install apt-t…...
C++医院影像科PACS源码:三维重建、检查预约、胶片打印、图像处理、测量分析等
PACS连接DICOM接口的医疗器械(如CT、MRI、CR、DR、DSA、各种窥镜成像系统设备等),实现图像无损传输,实现DICOM胶片打印机回传打印功能,支持各种图像处理,可以进行窗技术调节,与登记台管理系统共…...
企业聊天应用程序使用 Kubernetes
1. 客户端-服务器工作流程 客户端:在我们的架构中,客户端可以分为三种类型:iOS 和 Android 移动应用程序以及 Web 聊天。移动应用程序首先通过 API 网关服务与服务器进行通信,其中客户端会生成一个访问令牌,该令牌将授…...
记录用命令行将项目打包成war包
记录用命令行将项目打包成war包 找到项目的pom.xml 在当前路径下进入cmd 输入命令 mvn clean package 发现报错了 Failed to execute goal org.apache.maven.plugins:maven-war-plugin:2.2:war (default-war) on project MMS: Error assembling WAR: webxml attribute is req…...
Linux基础知识笔记
Linux基础知识笔记 介绍/dev/null作用2>&1作用 介绍 记录linux基础知识,持续更新中… /dev/null作用 /dev/null 是一个特殊的设备文件,可以将数据重定向到这个文件中,从而实现将输出或错误信息丢弃的效果。在 Linux 系统中…...
Laya3.0 入门教程
点击play箭头 点击右边的开发者工具 就会弹出 chrome的调试窗口 然后定位到你自己的ts文件 直接在ts里断点即可 不需要js文件 如何自动生成代码? 比如你打开一个新项目 里面显示的是当前场景 只需要点击 UI运行时 右边的框就可以了 他会自动弹窗提示你 创建一个文…...
3D全景虚拟样板间展销系统扩展用户市场范围
VR样板间,能够真实还原现场,定制需要的场景。让一切比真实更真实。用户可以720度看房,自由行走在空间里,直观感受各空间的大小,看到自己家中的“未来样子”,同时通过操控手柄,控制整个智能家居系…...
如何编写lua扩展库
很多人都听过lua,也见过lua脚本,但可能不理解为什么lua脚本里面会有这么多没见过的函数, 而且这些函数功能是如此强大,能上天入地,无所不能 其实这些函数并不是lua自带的,都是由程序作者造出来的隐藏在了他们的主程序里 一般运行lua脚本,我们会使用自带的解释器,当你拿到一份…...
Java List 中存不同的数据类型
在最近的实践中,有人突然问了一个问题: 在 Java 的 List 中可以存不同的数据类型吗? 这个问题突然给问到了,我们都知道 Java 中的 List 中存的是对象,通常我们定义都会这样的定义: List<String> t…...
pyqt5:openpyxl 读取 Excel文件,显示在 QTableWidget 中
pip install openpyxl openpyxl-3.1.2-py2.py3-none-any.whl (249 kB) et_xmlfile-1.1.0-py3-none-any.whl (4.7 kB) 摘要:A Python library to read/write Excel 2010 xlsx/xlsm files pip install pyqt5; pip install pyqt5-tools; 编写 openpyxl_pyqt5.py 如…...
在RabbitMQ中使用新的MQTT 5.0功能
MQTT是物联网(IoT)的标准协议,是轻量级的,协议头很小,可以节省网络带宽。MQTT也很有效,与其他消息传递协议相比,客户端通过更短的握手进行连接和身份验证。 以下是本文介绍的MQTT 5.0功能列表&…...
flinkcdc 体验
0 flink版本 踩雷 java代码操作 flink Table/SQL API 和 DataStream API 编写程序后,打成jar包丢到flink集群运行,报错首选需要考虑flink集群版本和 jar包中maven依赖的版本是否一致。 目前网上flink、flinkcdc相关博文绝大部分是基于flink1.13、1.14编…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
