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

数据结构篇-05:哈希表解决字母异位词分组

本文对应力扣高频100 ——49、字母异位词分组


哈希表最大的特点就是它可以把搜索元素的时间复杂度降到O(1)。这一题就是要我们找到 “字母异位词” 并把它们放在一起。

“字母异位词”就是同一个单词中字母的不同组合形式。判断“字母异位词”有两个视角:1、所含字母数量和种类相等的两个字符串数组互为“字母异位词”,当我们将其排序后,互为异位词的两个字符串应该是相同的;2、字母出现次数相同的两个字符串数组互为“字母异位词”,我们把其中字母出现的次数记录下来,形成的数组应该是相同的。

方法一:以重新排序后的字符串作为哈希表的key

思想:所含字母数量和种类相等的两个字符串数组互为“字母异位词”,当我们将其排序后,互为异位词的两个字符串应该是相同的

public class Solution{public List<List<Integer>> groupAnagrams(String[] strs){//如果字符串strs为空,则返回一个空的数组if(strs == null || str.length == 0){return new ArrayList<>();}Map<String,List<Integer>> map = new HashMap<>();//遍历每一个元素for(String str : strs){//将strs中的元素从String类型转为char类型,便于排序char[] charStr = str.toCharArray();//将转为 字符数组 的元素进行排序Arrays.sort(charStr);//将排序后的字符数组转回String类型,用于哈希比较String sortedStr = new String(charStr);//如果哈希表中不包含当前元素,就将其添加到哈希表中if(!map.containsKey(sortedStr)){map.put(sortedStr,new ArrayList<>());}//相反的,如果哈希表中包含该元素,就将其添加到对应key值的value值中//在本题中,value值是一个数组map.get(sortedStr).add(str);}//返回最终数组return new ArrayList<>(map.values());}
}

 方法二:以字符出现次数作为哈希表的键

思想:字母出现次数相同的两个字符串数组互为“字母异位词”,我们把其中字母出现的次数记录下来,形成的数组应该是相同的。

比如 “abc” 和 “bac” 互为字母异位词,在这两个字符串中,“a”、“b”、“c”各出现一次

public class Solution{public List<List<Integer>> groupAnagrams(String[] strs){Map<String,List<String>> map = new HashMap<>();//遍历字符串数组中的每一个元素for(String str : strs){//定义一个count数组用于记录每个字母出现次数int[] count = new int[26];//遍历元素中的每一个字母,并将其记录到数组中for(char c : str.toCharArray()){count[c - 'a']++;}//将数组转为String类型,便于放入哈希表String key = Arrays.toString(count);//获取哈希表value值中的list数组List<String> list = map.getOrDefault(key,new ArrayList<>());//将原始元素str放入listlist.add(str);//将字母出现次数作为哈希表的key值,list作为value值map.put(key,list);}//最后返回哈希表的valuereturn new ArrayList<>(map.values());}
}

 

相关文章:

数据结构篇-05:哈希表解决字母异位词分组

本文对应力扣高频100 ——49、字母异位词分组 哈希表最大的特点就是它可以把搜索元素的时间复杂度降到O(1)。这一题就是要我们找到 “字母异位词” 并把它们放在一起。 “字母异位词”就是同一个单词中字母的不同组合形式。判断“字母异位词”有两个视角&#xff1a;1、所含字…...

添加了gateway之后远程调用失败

前端提示500&#xff0c;后端提示[400 ] during [GET] to [http://userservice/user/1] 原因是这个&#xff0c;因为在请求地址写了两个参数&#xff0c;实际上只传了一个参数 解决方案&#xff1a;加上(required false)并重启所有相关服务...

C#,哥伦布数(Golomb Number)的算法与源代码

1 哥伦布数&#xff08;Golomb Number&#xff09; 哥伦布数&#xff08;Golomb Number&#xff09;是一个自然数的非减量序列&#xff0c;使得n在序列中正好出现G&#xff08;n&#xff09;次。前几个15的G&#xff08;n&#xff09;值为&#xff1a;1 2 2 3 3 4 4 4 5 5 5 6…...

JVM学习

1.Java虚拟机内部有哪些线程共享&#xff0c;那些线程隔离 程序计数器&#xff1a; 通过改变这个计数器的值来选取下一条需要执行的字节码命令 Java虚拟机栈&#xff1a; 栈&#xff0c;每个方法被执行时&#xff0c;Java虚拟机都会同步的创建一个栈帧用于存储局部变量表&…...

Visual Studio 20XX中utf-8中文在控制台显示乱码

文章目录 在 Visual Studio 20xx中&#xff0c;如果源码文件是 UTF8编码&#xff0c;要打印中文到控制台时&#xff0c;控制台会显示乱码&#xff0c;可以进行以下设置。 包含<Windows.h>头文件。在main函数初始调用SetConsoleOutputCP(CP_UTF8)设置控制台输出字符集为UT…...

拥抱个人成长与社会进步:自我认知与开放心态的相互影响

拥抱个人成长与社会进步&#xff1a;自我认知与开放心态的相互影响 Embracing Personal Growth and Societal Progress: The Interplay of Self-Awareness and Open-mindedness 一、引言 I. Introduction 在当今急速发展的时代&#xff0c;个人成长与社会进步交织在一起&…...

【PostgreSQL内核学习(二十五) —— (DBMS存储空间管理)】

DBMS存储空间管理 概述块&#xff08;或页面&#xff09;PageHeaderData 结构体HeapTupleHeaderData 结构 表空间表空间的作用&#xff1a;表空间和数据库关系表空间执行案例 补充 —— 模式&#xff08;Schema&#xff09; 声明&#xff1a;本文的部分内容参考了他人的文章。在…...

2024年 复习 HTML5+CSS3+移动web 笔记 之CSS遍 第5天

第 五 天 整个网站例 5.1 准备工作 项目目录与版心 base.css 5.2 网页制作思路 5.3 header 区域-整体布局 5.4 header区域-logo 5.5 header区域-导航 index.html <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8">&l…...

SpringBoot使用Kafka详解含完整代码

1. 前言 随着大数据和实时处理需求的增长&#xff0c;Kafka作为一种分布式流处理平台&#xff0c;与Spring Boot的集成变得尤为重要。本文将详细探讨如何在Spring Boot应用程序中设置和使用Kafka&#xff0c;从基础概念到高级特性&#xff0c;通过实际代码示例帮助读者深入理解…...

解决:java -jar 在cmd中运行 程序卡顿,卡死的 问题。BIO和NIO案例保存

解决 怎么解决&#xff0c;就是 日志别输出到 cmd 就行了。就行了。就行了。 java -jar demo.jar > output.log 2>&1 &最近写东西&#xff0c;遇到了 程序偶尔卡死的情况。是java -jar 启动的。具体卡死为&#xff1a;http请求超级卡顿 或 偶尔反应好多个请求&…...

LeetCode第824题 - 山羊拉丁文

题目 解答 String toGoatLatin(String S) {if (S null) {return "";}S S.trim();if (S.isEmpty()) {return "";}StringBuilder sb new StringBuilder();String[] tokens S.split(" ");for (int i 0, j 1, length tokens.length; i <…...

[Python] 什么是逻辑回归模型?使用scikit-learn中的LogisticRegression来解决乳腺癌数据集上的二分类问题

什么是线性回归和逻辑回归&#xff1f; 线性回归是一种用于解决回归问题的统计模型。它通过建立自变量&#xff08;或特征&#xff09;与因变量之间的线性关系来预测连续数值的输出。线性回归的目标是找到一条直线&#xff08;或超平面&#xff09;&#xff0c;使得预测值与观…...

那些不输于乙游男主人设的国漫男主

最近乙游的势头越来越猛&#xff0c;新宠旧爱一起上阵&#xff0c;叫人应接不暇。在二次元的世界里&#xff0c;乙游男主们凭借着超凡的魅力&#xff0c;成为了无数少女心中的理想对象。他们或冷酷、或温柔、或阳光、或神秘&#xff0c;每一个角色都有着独特的性格和故事。 乙游…...

Apache Doris 整合 FLINK CDC + Iceberg 构建实时湖仓一体的联邦查询

1概况 本文展示如何使用 Flink CDC Iceberg Doris 构建实时湖仓一体的联邦查询分析&#xff0c;Doris 1.1版本提供了Iceberg的支持&#xff0c;本文主要展示Doris和Iceberg怎么使用&#xff0c;大家按照步骤可以一步步完成。完整体验整个搭建操作的过程。 2系统架构 我们整…...

关于华为应用市场上架,申请权限未告知目的被驳回问题的简单处理方式

关于华为应用市场上架过程中出现的【您的应用在运行时&#xff0c;未同步告知权限申请的使用目的&#xff0c;向用户索取&#xff08;存储、拍照&#xff09;等权限&#xff0c;不符合华为应用市场审核标准。】 使用方式&#xff1a; 1、引入 import permision from "/m…...

【ElasticSearch】概述

文章目录 ElasticSearch1.基本介绍2.设计理念3.基本架构与核心概念学习参考资料&#xff1a; ElasticSearch 简单整理ES基本概念&#xff0c;设计理念&#xff0c;构建与使用&#xff0c;供回顾。 1.基本介绍 Elasticsearch 是一个基于 Apache Lucene 的开源的分布式搜索引擎…...

十进制转十六进制 C/C++蓝桥杯基础试题BASIC-10

问题描述 十六进制数是在程序设计时经常要使用到的一种整数的表示方式。它有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16个符号&#xff0c;分别表示十进制数的0至15。十六进制的计数方法是满16进1&#xff0c;所以十进制数16在十六进制中是10&#xff0c;而十进制的17在十六进制中是…...

【LVGL环境搭建】

LVGL环境搭建 win模拟器环境搭建一.二.三.四.五. Ubuntu模拟器环境搭建一. 前置准备二. 下载LVGL Source code&#xff1a;三. 安装sdl2&#xff1a;四. 开启VScode执行五. 安装扩展套件六. 按F5执行七. 执行结果 win模拟器环境搭建 一. 二. 三. 四. 五. Ubuntu模拟器环境…...

【c语言】简单贪吃蛇的实现

目录 一、游戏说明 ​编辑 二、地图坐标​ ​编辑 三、头文件 四、蛇身和食物​ 五、数据结构设计​ 蛇节点结构如下&#xff1a; 封装一个Snake的结构来维护整条贪吃蛇&#xff1a;​ 蛇的方向&#xff0c;可以一一列举&#xff0c;使用枚举&#xff1a; 游戏状态&a…...

2023年09月CCF-GESP编程能力等级认证Python编程六级真题解析

Python等级认证GESP(1~6级)全部真题・点这里 一、单选题(共15题,共30分) 第1题 近年来,线上授课变得普遍,很多有助于改善教学效果的设备也逐渐流行,其中包括比较常用的手写板,那么它属于哪类设备?( ) A:输入 B:输出 C:控制 D:记录 答案:A 第2题 以下关于…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

Python网页自动化Selenium中文文档

1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API&#xff0c;让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API&#xff0c;你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...