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

力扣hot 100:49. 字母异位词分组(python C++)

目录

  • 题目描述:
    • 题解(python):(方法一:排序)
      • 代码解析
      • 代码运行解析
    • 题解(C++):(方法一:排序)
      • 代码解析&运行解析

原题目链接

题目描述:

示例 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] 仅包含小写字母

题解(python):(方法一:排序)

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:mp = collections.defaultdict(list)for st in strs:key = "".join(sorted(st))mp[key].append(st)return list(mp.values())

代码解析

这段代码定义了一个名为 Solution 的类,类中包含一个名为 groupAnagrams 的方法。该方法用于将一组字符串按字母异位词(anagram)分组。以下是代码的逐行解析:

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
  • 这段代码定义了一个类 Solution,类中包含一个方法 groupAnagrams。这个方法接收一个参数 strs,它是一个字符串列表(List[str]),返回值是一个列表,列表中的每个元素也是一个字符串列表(List[List[str]])。
        mp = collections.defaultdict(list)
  • 这里定义了一个名为 mp 的变量,它是一个 defaultdict(来自 collections 模块)。defaultdict 是一种字典,它在引用的键不存在时会自动创建键,并将其值初始化为指定的默认值。在这个例子中,默认值是一个空列表。
        for st in strs:key = "".join(sorted(st))mp[key].append(st)
  • 这一段代码遍历输入的字符串列表 strs
    • 对于每个字符串 st,通过 sorted(st) 对字符串的字符进行排序,得到一个排序后的字符列表。
    • 然后通过 ''.join(sorted(st)) 将排序后的字符列表重新组合成一个字符串 key
    • 使用这个 key 作为键,将原始字符串 st 添加到 mp 字典中对应的列表中。
        return list(mp.values())
  • 最后,将字典 mp 中所有的值(即各个字母异位词分组的列表)转换为一个列表,并返回这个列表。

总结:

  • 这个方法的主要作用是将输入的字符串列表按字母异位词分组。字母异位词是指由相同字母组成但顺序不同的字符串。
  • 通过对每个字符串的字符进行排序,可以生成唯一的键(排序后的字符串),用这个键来将原始字符串分组。

例如,输入 ["eat", "tea", "tan", "ate", "nat", "bat"],该方法将返回 [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

代码运行解析

当然可以!我们来详细跟踪代码执行的每一步,以理解它是如何处理输入 ["eat", "tea", "tan", "ate", "nat", "bat"] 的。

import collectionsclass Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:mp = collections.defaultdict(list)
  • 创建了一个 defaultdict,初始状态 mp 是空的:mp = {}
        for st in strs:key = "".join(sorted(st))mp[key].append(st)

遍历 strs 列表,并对每个字符串执行以下操作:

  1. 处理 st = "eat":

    • sorted("eat") 结果是 ['a', 'e', 't']
    • key = "".join(['a', 'e', 't']) 结果是 "aet"
    • mp["aet"].append("eat"),更新后的 mp 是:{'aet': ['eat']}
  2. 处理 st = "tea":

    • sorted("tea") 结果是 ['a', 'e', 't']
    • key = "".join(['a', 'e', 't']) 结果是 "aet"
    • mp["aet"].append("tea"),更新后的 mp 是:{'aet': ['eat', 'tea']}
  3. 处理 st = "tan":

    • sorted("tan") 结果是 ['a', 'n', 't']
    • key = "".join(['a', 'n', 't']) 结果是 "ant"
    • mp["ant"].append("tan"),更新后的 mp 是:{'aet': ['eat', 'tea'], 'ant': ['tan']}
  4. 处理 st = "ate":

    • sorted("ate") 结果是 ['a', 'e', 't']
    • key = "".join(['a', 'e', 't']) 结果是 "aet"
    • mp["aet"].append("ate"),更新后的 mp 是:{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan']}
  5. 处理 st = "nat":

    • sorted("nat") 结果是 ['a', 'n', 't']
    • key = "".join(['a', 'n', 't']) 结果是 "ant"
    • mp["ant"].append("nat"),更新后的 mp 是:{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat']}
  6. 处理 st = "bat":

    • sorted("bat") 结果是 ['a', 'b', 't']
    • key = "".join(['a', 'b', 't']) 结果是 "abt"
    • mp["abt"].append("bat"),更新后的 mp 是:{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}
        return list(mp.values())
  • 最终,将 mp 的值转换为列表:list(mp.values())
  • 返回结果是 [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

综上,代码的每一步执行结果如下:

  1. mp = {} (初始状态)
  2. mp = {'aet': ['eat']}
  3. mp = {'aet': ['eat', 'tea']}
  4. mp = {'aet': ['eat', 'tea'], 'ant': ['tan']}
  5. mp = {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan']}
  6. mp = {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat']}
  7. mp = {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}
  8. 返回值:[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

题解(C++):(方法一:排序)

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> mp;for (string& str:strs){string key = str;sort(key.begin(),key.end());mp[key].emplace_back(str);}vector<vector<string>> ans;for (auto it = mp.begin();it != mp.end(); ++ it){ans.emplace_back(it->second);}return ans;}
};

代码解析&运行解析

这段代码定义了一个名为 Solution 的类,类中包含一个名为 groupAnagrams 的方法。这个方法用于将一组字符串按字母异位词(anagram)分组。以下是代码的逐行解析:

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {
  • 这段代码定义了一个类 Solution,类中包含一个公有方法 groupAnagrams。该方法接收一个引用参数 strs,它是一个字符串的向量(vector<string>),返回值是一个二维字符串向量(vector<vector<string>>)。
        unordered_map<string, vector<string>> mp;
  • 这里定义了一个名为 mp 的变量,它是一个 unordered_map,键类型是 string,值类型是 vector<string>。这个哈希映射用于将排序后的字符串(作为键)映射到原始字符串列表(作为值)。
        for (string& str: strs) {string key = str;sort(key.begin(), key.end());mp[key].emplace_back(str);}
  • 这一段代码遍历输入的字符串向量 strs
    • 对于每个字符串 str,将其复制到 key 中。
    • 通过 sort(key.begin(), key.end())key 中的字符进行排序。
    • 使用排序后的 key 作为键,将原始字符串 str 添加到 mp 字典中对应的列表中。
        vector<vector<string>> ans;
  • 创建一个空的二维字符串向量 ans,用于存储结果。
        for (auto it = mp.begin(); it != mp.end(); ++it) {ans.emplace_back(it->second);}
  • 遍历 mp 中的每一个键值对。
    • 对于每一个键值对,将值(即一个字符串列表)添加到 ans 中。
        return ans;}
};
  • 最后,返回 ans,它包含了按字母异位词分组的字符串列表。

总结:

  • 这个方法的主要作用是将输入的字符串向量按字母异位词分组。字母异位词是指由相同字母组成但顺序不同的字符串。
  • 通过对每个字符串的字符进行排序,可以生成唯一的键(排序后的字符串),用这个键来将原始字符串分组。

例如,输入 ["eat", "tea", "tan", "ate", "nat", "bat"],该方法将返回 [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

让我们详细跟踪代码执行的每一步,以理解它是如何处理输入 ["eat", "tea", "tan", "ate", "nat", "bat"] 的。

假设输入是 ["eat", "tea", "tan", "ate", "nat", "bat"],代码的每一步执行结果如下:

  1. 创建 mpmp = {}(初始状态)

  2. 处理 str = "eat"

    • key = "eat"
    • sort(key.begin(), key.end()) 结果是 key = "aet"
    • mp["aet"].emplace_back("eat"),更新后的 mp 是:{"aet": ["eat"]}
  3. 处理 str = "tea"

    • key = "tea"
    • sort(key.begin(), key.end()) 结果是 key = "aet"
    • mp["aet"].emplace_back("tea"),更新后的 mp 是:{"aet": ["eat", "tea"]}
  4. 处理 str = "tan"

    • key = "tan"
    • sort(key.begin(), key.end()) 结果是 key = "ant"
    • mp["ant"].emplace_back("tan"),更新后的 mp 是:{"aet": ["eat", "tea"], "ant": ["tan"]}
  5. 处理 str = "ate"

    • key = "ate"
    • sort(key.begin(), key.end()) 结果是 key = "aet"
    • mp["aet"].emplace_back("ate"),更新后的 mp 是:{"aet": ["eat", "tea", "ate"], "ant": ["tan"]}
  6. 处理 str = "nat"

    • key = "nat"
    • sort(key.begin(), key.end()) 结果是 key = "ant"
    • mp["ant"].emplace_back("nat"),更新后的 mp 是:{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}
  7. 处理 str = "bat"

    • key = "bat"
    • sort(key.begin(), key.end()) 结果是 key = "abt"
    • mp["abt"].emplace_back("bat"),更新后的 mp 是:{"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}

遍历 mp,将每个值(字符串列表)添加到 ans 中:

  • ans = [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

返回 ans,最终结果是:[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

相关文章:

力扣hot 100:49. 字母异位词分组(python C++)

目录 题目描述&#xff1a;题解&#xff08;python&#xff09;&#xff1a;&#xff08;方法一&#xff1a;排序&#xff09;代码解析代码运行解析 题解&#xff08;C&#xff09;&#xff1a;&#xff08;方法一&#xff1a;排序&#xff09;代码解析&运行解析 原题目链接…...

男士内裤什么材质的好?推荐男士内裤的注意事项

天气已经逐渐热了起来&#xff0c;广大男士们在夏天难免会出一身的汗&#xff0c;不少男士朋友都觉得一些吸湿性、透气性不好的内裤会在夏天穿着很不适&#xff0c;想挑选一些比较适合夏天的男士内裤&#xff0c;但现在的男士内裤品牌和材质分类却比较多&#xff0c;看得大家眼…...

Python操作MySQL数据库的工具--sqlalchemy

文章目录 一、pymysql和sqlalchemy的区别二、sqlalchemy的详细使用1.安装库2.核心思想3.整体思路4.sqlalchemy需要连接数据库5.使用步骤1.手动提前创建数据库2.使用代码创建数据表3.用代码操作数据表3.1 增加数据3.2 查询数据3.3 删除数据3.4 修改数据 一、pymysql和sqlalchemy…...

【算法】排序

排序算法在信息学非常常用。Hello&#xff01;大家好&#xff0c;我是学霸小羊&#xff0c;今天讲几个排序算法。 1.“打擂台”排序 思路&#xff1a;a[ i ]和a[ j ]打擂台&#xff08;i<j&#xff09;。 这个方法简单易懂&#xff0c;只需要看看需不需要交换。按从大到小…...

前端开发之xlsx的使用和实例,并导出多个sheet

前端开发之xlsx的使用和实例 前言效果图1、安装2、在页面中引用3、封装工具类&#xff08;excel.js&#xff09;4、在vue中使用 前言 在实现业务功能中导出是必不可少的功能&#xff0c;接下来为大家演示在导出xlsx的时候的操作 效果图 1、安装 npm install xlsx -S npm inst…...

创建数据库数据插入、更新与删除

创建数据库和创建表 一、实验目的 &#xff08;1&#xff09;熟悉和掌握数据库的创建和连接方法&#xff1b; &#xff08;2&#xff09;熟悉和掌握数据库表的建立、修改和删除&#xff1b; &#xff08;3&#xff09;加深对表的实体完整性、参照完整性和用户自定义完整性的…...

【CTF Web】CTFShow web3 Writeup(SQL注入+PHP+UNION注入)

web3 1 管理员被狠狠的教育了&#xff0c;所以决定好好修复一番。这次没问题了。 解法 注意到&#xff1a; <!-- flag in id 1000 -->但是拦截很多种字符。 if(preg_match("/or|\-|\\|\*|\<|\>|\!|x|hex|\/i",$id)){die("id error"); }使用…...

常见API(JDK7时间、JDK8时间、包装类、综合练习)

一、JDK7时间——Date 1、事件相关知识点 2、Date时间类 Data类是一个JDK写好的Javabean类&#xff0c;用来描述时间&#xff0c;精确到毫秒。 利用空参构造创建的对象&#xff0c;默认表示系统当前时间。 利用有参构造创建的对象&#xff0c;表示指定的时间。 练习——时间计…...

Docker数据卷(volume)

数据卷 数据卷是一个虚拟目录&#xff0c;是容器内目录与宿主机目录之间映射的桥梁。&#xff08;容器内目录与宿主机目录对应的桥梁&#xff0c;修改宿主机对应的目录&#xff0c;docker会映射到容器内部&#xff0c;相当于修改了容器内的&#xff0c;反之也一样&#xff09;数…...

30.哀家要长脑子了!---栈与队列

1.388. 文件的最长绝对路径 - 力扣&#xff08;LeetCode&#xff09; 其实看懂了就还好 用一个栈来保存所遍历过最大的文件的绝对路径的长度&#xff0c;栈顶元素是文件的长度&#xff0c;栈中元素的个数是该文件目录的深度&#xff0c;非栈顶元素就是当时目录的长度 检查此…...

多重继承引起的二义性问题和虚基类

多重继承容易引起的问题就是因为继承的成员同名而产生的二义性问题。 例&#xff1a;类A和类B中都有成员函数display和数据成员a,类C是类A和类B的直接派生类 情况一&#xff1a; class A {public:int a;void display(); }; class B {public:int a;void display; }; class C:…...

ciscn

ciscn Crypto部分复现 古典密码 先是埃特巴什密码&#xff08;这个需要进行多次测试&#xff09;&#xff0c;然后base64&#xff0c;再栅栏即可 答案&#xff1a;flag{b2bb0873-8cae-4977-a6de-0e298f0744c3} _hash 题目&#xff1a; #!/usr/bin/python2 # Python 2.7 (6…...

智能的PHP开发工具PhpStorm v2024.1全新发布——支持PHPUnit 11.0

PhpStorm是一个轻量级且便捷的PHP IDE&#xff0c;其旨在提高用户效率&#xff0c;可深刻理解用户的编码&#xff0c;提供智能代码补全&#xff0c;快速导航以及即时错误检查。可随时帮助用户对其编码进行调整&#xff0c;运行单元测试或者提供可视化debug功能。 立即获取PhpS…...

Vue2+Element 封装评论+表情功能

有需要的小伙伴直接拿代码即可&#xff0c;不需要下载依赖&#xff0c;目前是初始版本&#xff0c;后期会进行代码的优化。 评论组件如下&#xff1a; 创建 comment.vue 文件。 表情组件 VueEmoji.vue 在评论组件中使用。 <template><div class"comment"…...

【k8s】存储 pvc 参数列表

相关文章&#xff1a; 【K8s】初识PV和PVC 【k8s】存储 pv 参数列表 【k8s】存储 pvc 参数列表 1. pv概述 2. 参数列表 [rootpaas-controller-3:/home/ubuntu]$ kubectl explain pvc.spec KIND: PersistentVolumeClaim VERSION: v1RESOURCE: spec <Object>DESCRI…...

数据集007:垃圾分类数据集(含数据集下载链接)

数据集简介 本数据拥有 训练集&#xff1a;43685张&#xff1b; 验证集&#xff1a;5363张&#xff1b; 测试集&#xff1a;5363张&#xff1b; 总类别数&#xff1a;158类。 部分代码&#xff1a; 定义数据集 class MyDataset(Dataset):def __init__(self, modetrain, …...

Spring常用注解(超全面)

官网&#xff1a;核心技术SPRINGDOC.CN 提供 Spring 官方文档的翻译服务&#xff0c;可以方便您快速阅读中文版官方文档。https://springdoc.cn/spring/core.html#beans-standard-annotations 1&#xff0c;包扫描组件标注注解 Component&#xff1a;泛指各种组件 Controller、…...

HQL面试题练习 —— 合并活动日期

目录 1 题目2 建表语句3 题解 1 题目 已知有表记录了每个大厅的活动开始日期和结束日期&#xff0c;每个大厅可以有多个活动。请编写一个SQL查询合并在同一个大厅举行的所有重叠的活动&#xff0c;如果两个活动至少有一天相同&#xff0c;那他们就是重叠的&#xff0c;请将他们…...

基于SVm和随机森林算法模型的中国黄金价格预测分析与研究

摘要 本研究基于回归模型&#xff0c;运用支持向量机&#xff08;SVM&#xff09;、决策树和随机森林算法&#xff0c;对中国黄金价格进行预测分析。通过历史黄金价格数据的分析和特征工程&#xff0c;建立了相应的预测模型&#xff0c;并利用SVM、决策树和随机森林算法进行训…...

Host头攻击-使用反向代理服务器或负载均衡器来传递路由信息

反向代理服务器的作用 安全性&#xff1a;反向代理服务器位于Web服务器之前&#xff0c;可以隐藏实际Web服务器的身份和地址&#xff0c;从而增加安全性。它还可以对客户端请求进行过滤和检查&#xff0c;以防止潜在的攻击。负载均衡&#xff1a;反向代理服务器可以将客户端请…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

爬虫基础学习day2

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

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...