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

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. 字母异位词分组

题目描述 给你一个字符串数组&#xff0c;请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 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()&#xff08;将字符串转换为整数类型&#xff09;二、to_string()&#xff08;将整数类型转换为字符串类型&#xff09;三、stringstream函数&#xff08;将一个字符串按照指定的分隔符进行分词&#xff09; 字符串处理类 一、stoi()&#xff…...

黑客技术(网络安全)——自学思路

如果你想自学网络安全&#xff0c;首先你必须了解什么是网络安全&#xff01;&#xff0c;什么是黑客&#xff01;&#xff01; 1.无论网络、Web、移动、桌面、云等哪个领域&#xff0c;都有攻与防两面性&#xff0c;例如 Web 安全技术&#xff0c;既有 Web 渗透2.也有 Web 防…...

lNmp安装:

一、LNMP LNMP架构是目前成熟的企业网站应用模式之一&#xff0c;指的是协同工作的一整套系统和相关软件&#xff0c; 能够提供动态Web站点服务及其应用开发环境。LNMP是一个缩写词&#xff0c;具体包括Linux操作系统、nginx网站服务器、MySQL数据库服务器、 PHP&#xff08;或…...

Fisher辨别分析

问题要求 在UCI数据集上的Iris和Sonar数据上验证算法的有效性。训练和测试样本有三种方式&#xff08;三选一&#xff09;进行划分&#xff1a; &#xff08;一&#xff09; 将数据随机分训练和测试&#xff0c;多次平均求结果 &#xff08;二&#xff09;K折交叉验证 &…...

【Zookeeper专题】Zookeeper选举Leader源码解析

目录 前言阅读建议课程内容一、ZK Leader选举流程回顾二、源码流程图三、Leader选举模型图 学习总结 前言 为什么要看源码&#xff1f;说实在博主之前看Spring源码之前没想过这个问题。因为我在看之前就曾听闻大佬们说过【JavaCoder三板斧&#xff1a;Java&#xff0c;Mysql&a…...

机器学习之自训练协同训练

前言 监督学习往往需要大量的标注数据&#xff0c; 而标注数据的成本比较高 &#xff0e; 因此 &#xff0c; 利用大量的无标注数据来提高监督学习的效果有着十分重要的意义&#xff0e; 这种利用少量标注数据和大量无标注数据进行学习的方式称为 半监督学习 &#xff08; 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接口的医疗器械&#xff08;如CT、MRI、CR、DR、DSA、各种窥镜成像系统设备等&#xff09;&#xff0c;实现图像无损传输&#xff0c;实现DICOM胶片打印机回传打印功能&#xff0c;支持各种图像处理&#xff0c;可以进行窗技术调节&#xff0c;与登记台管理系统共…...

企业聊天应用程序使用 Kubernetes

1. 客户端-服务器工作流程 客户端&#xff1a;在我们的架构中&#xff0c;客户端可以分为三种类型&#xff1a;iOS 和 Android 移动应用程序以及 Web 聊天。移动应用程序首先通过 API 网关服务与服务器进行通信&#xff0c;其中客户端会生成一个访问令牌&#xff0c;该令牌将授…...

记录用命令行将项目打包成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基础知识&#xff0c;持续更新中… /dev/null作用 /dev/null 是一个特殊的设备文件&#xff0c;可以将数据重定向到这个文件中&#xff0c;从而实现将输出或错误信息丢弃的效果。在 Linux 系统中&#xf…...

Laya3.0 入门教程

点击play箭头 点击右边的开发者工具 就会弹出 chrome的调试窗口 然后定位到你自己的ts文件 直接在ts里断点即可 不需要js文件 如何自动生成代码&#xff1f; 比如你打开一个新项目 里面显示的是当前场景 只需要点击 UI运行时 右边的框就可以了 他会自动弹窗提示你 创建一个文…...

3D全景虚拟样板间展销系统扩展用户市场范围

VR样板间&#xff0c;能够真实还原现场&#xff0c;定制需要的场景。让一切比真实更真实。用户可以720度看房&#xff0c;自由行走在空间里&#xff0c;直观感受各空间的大小&#xff0c;看到自己家中的“未来样子”&#xff0c;同时通过操控手柄&#xff0c;控制整个智能家居系…...

如何编写lua扩展库

很多人都听过lua,也见过lua脚本,但可能不理解为什么lua脚本里面会有这么多没见过的函数, 而且这些函数功能是如此强大,能上天入地,无所不能 其实这些函数并不是lua自带的,都是由程序作者造出来的隐藏在了他们的主程序里 一般运行lua脚本,我们会使用自带的解释器,当你拿到一份…...

Java List 中存不同的数据类型

在最近的实践中&#xff0c;有人突然问了一个问题&#xff1a; 在 Java 的 List 中可以存不同的数据类型吗&#xff1f; 这个问题突然给问到了&#xff0c;我们都知道 Java 中的 List 中存的是对象&#xff0c;通常我们定义都会这样的定义&#xff1a; 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) 摘要&#xff1a;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是物联网&#xff08;IoT&#xff09;的标准协议&#xff0c;是轻量级的&#xff0c;协议头很小&#xff0c;可以节省网络带宽。MQTT也很有效&#xff0c;与其他消息传递协议相比&#xff0c;客户端通过更短的握手进行连接和身份验证。 以下是本文介绍的MQTT 5.0功能列表&…...

flinkcdc 体验

0 flink版本 踩雷 java代码操作 flink Table/SQL API 和 DataStream API 编写程序后&#xff0c;打成jar包丢到flink集群运行&#xff0c;报错首选需要考虑flink集群版本和 jar包中maven依赖的版本是否一致。 目前网上flink、flinkcdc相关博文绝大部分是基于flink1.13、1.14编…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]

报错信息&#xff1a;libc.so.6: cannot open shared object file: No such file or directory&#xff1a; #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...