面试算法33:变位词组
题目
给定一组单词,请将它们按照变位词分组。例如,输入一组单词[“eat”,“tea”,“tan”,“ate”,“nat”,“bat”],这组单词可以分成3组,分别是[“eat”,“tea”,“ate”]、[“tan”,“nat”]和[“bat”]。假设单词中只包含英文小写字母。
分析
第一种方法是把每个英文小写字母映射到一个质数,如把字母’a’映射到数字2,字母’b’映射到数字3,以此类推,字母’z’映射到第26个质数101。每给出一个单词,就把单词中的所有字母对应的数字相乘,于是每个单词都可以算出一个数字。
例如,单词"eat"可以映射到数字1562(11×2×71)。如果两个单词互为变位词,那么它们中每个字母出现的次数都对应相同,由于乘法满足交换律,因此上述算法把一组变位词映射到同一个数值。例如,单词"eat"、"tea"和"ate"都会映射到数字1562。由于每个字母都是映射到一个质数,因此不互为变位词的两个单词一定会映射到不同的数字。
解
public class Test {public static void main(String[] args) {String[] strs = {"eat","tea","tan","ate","nat","bat"};List<List<String>> result= groupAnagrams(strs);for (List<String> res : result){System.out.println(res);}}public static List<List<String>> groupAnagrams(String[] strs){int[] hash = {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>> groups = new HashMap<>();for (String str : strs){long wordHash =1;for (int i = 0; i < str.length(); i++) {wordHash *= hash[str.charAt(i) - 'a'];}groups.putIfAbsent(wordHash,new LinkedList<>());groups.get(wordHash).add(str);}return new LinkedList<>(groups.values());}
}
分析
第二种方法是把一组变位词映射到同一个单词。由于互为变位词的单词的字母出现的次数分别相同,因此如果把单词中的字母排序就会得到相同的字符串。
例如,把"eat"、“tea"和"ate"的字母按照字母表顺序排序都得到字符串"aet”。因此,可以定义一个哈希表,哈希表的键是把单词字母排序得到的字符串,而值为一组变位词。
解
public class Test {public static void main(String[] args) {String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};List<List<String>> result = groupAnagrams(strs);for (List<String> res : result) {System.out.println(res);}}public static List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> groups = new HashMap<>();for (String str : strs) {char[] charArray = str.toCharArray();Arrays.sort(charArray);String sorted = new String(charArray);groups.putIfAbsent(sorted, new LinkedList<>());groups.get(sorted).add(str);}return new LinkedList<>(groups.values());}
}
相关文章:
面试算法33:变位词组
题目 给定一组单词,请将它们按照变位词分组。例如,输入一组单词[“eat”,“tea”,“tan”,“ate”,“nat”,“bat”],这组单词可以分成3组,分别是[“eat”,“…...
【C语言】每日一题(旋转数组)
旋转数组,链接奉上 目录 方法:创建额外的数组:整体思路:代码实现: 数组反转:整体思路:代码实现:小插曲: 方法: 创建额外的数组: 整体思路: 创建一个额外的…...
系统架构师考试科目一:综合知识
某软件公司欲开发一个 Windows 平台上的公告板系统。在明确用户需求后,该公司的 架构师决定采用 Command 模式实现该系统的界面显示部分,并设计 UML 类图如下 图所示。图中与 Command 模式中的 Invoker 角色相对应的类是( ) ,与 ConcreteComm…...
面向对象与面向过程讲解
目录 简介 面向过程编程(Procedural Programming) 什么是面向过程编程? 特点: 面向对象编程(Object-Oriented Programming) 什么是面向对象编程? 特点: 面向对象 vs. 面向过程…...
【SA8295P 源码分析 (四)】23 - QNX Ethernet MAC 驱动 之 emac1_config.conf 配置文件解析
【SA8295P 源码分析】23 - QNX Ethernet MAC 驱动 之 emac1_config.conf 配置文件解析 系列文章汇总见:《【SA8295P 源码分析 (四)】网络模块 文章链接汇总 - 持续更新中》 本文链接:《【SA8295P 源码分析 (四)】23 - QNX Ethernet MAC 驱动 之 emac1_config.conf 配置文件解…...
Python【list列表去重】
目录 要求: 将list中的重复数据去重,至少使用两种方案 方案一: 方案二: 要求: 将list中的重复数据去重,至少使用两种方案 方案一: 使用set ,可以将list转换为set࿰…...
Leetcode——字符
520. 检测大写字母 class Solution { public:bool detectCapitalUse(string word) {int big 0, small 0, len word.length();for (int i 0; i < len; i) {if (word[i] > 65 && word[i] < 90) {big;}else {small;}}if (big len || small len) {return tr…...
深入解析docker内核网桥
今天做虚拟桌面,朋友问我,为什么vnc 连接另一个docker 容器一直超时,原因是在docker 启动的时候没有组网,那么接下来我就要解析下docker的内核网络。 我们思考几个问题,带你了解linux 中docker 网络实现的基本原理。 文…...
ubuntu18.04服务器双网口配置上外网
记录一下配置服务器过程,本以为简单,结果整了一天。 服务器有2个网口,网口2是用来上外网的,原来用的01-netcfg.yaml进行ip地址设置,主要就用2条命令: vi /etc/netplan/01-netcfg.yaml (打开后…...
【安全体系架构】——防御深度架构
防御深度架构: 防御深度架构是一种多层次的安全模型,旨在通过在网络和系统的各个层次上部署多个安全措施,以抵御不同类型的威胁和攻击。这个模型承认单一的安全措施可能无法全面防御所有潜在威胁,因此采用了多层次的安全防御策略…...
Opencv之RANSAC算法用于直线拟合及特征点集匹配详解
Opencv之RANSAC算法用于直线拟合及特征点集匹配详解 讲述Ransac拟合与最小二乘在曲线拟合上的优缺点 讲述在进行特征点匹配时,最近邻匹配与Ransac匹配的不同之处 另外,Ransac也被用于椭圆拟合、变换矩阵求解等 1. 直线拟合 1.1 原理 RANSAC(RANdom …...
Jenkins环境部署与任务构建
一、CI/CD 1、CI/CD 概念: CI/CD 是一种软件开发和交付方法,旨在加速应用程序的开发、测试和部署过程,以提高软件交付的质量和效率。 (1) 持续集成 (CI Continuous Integration): 持续集成是开发团队频繁集成其代码更改的过程。开发者将其…...
ES6 Class和Class继承
1.class的基本语法 class可以理解为是一个语法糖,将js只能通过构造函数创建实例的方法进行了补充 构造函数: function Person ({ name, age18 }) {this.name namethis.age age } new Person({name: 张三}) Class类: class Person {con…...
C++11 packaged_task
std::packaged_task 把一个方法打包成一个task扔到线程中执行,然后通过packaged_task中的furture等待执行结果。 void test_promise() {std::packaged_task <int()> task([]()->int {std::cout << "packaged_task begin \n" << std…...
delete、drop、truncate三兄弟
比较方面/具体命令deletetruncatedrop删除范围逐行删除(记录行)逐页删除(数据页)整张表(数据表结构)所属范畴数据操作语言(DML)数据定义语言(DDL)数据定义语言…...
C/C++运算优先级
文章目录 前言1.运算优先级表2.举例说明:总结 前言 最近复习C基础知识的时候,发现对这部分还是有些模糊。常用的 - ,括号等运算符对于它们的优先级还是比较明确的。但是涉及到移位运算,逻辑运算这种,再结合四则运算…...
apache搭建静态网站,moongoose搭建网站后台,出现的跨域问题解决
文章目录 1,问题描述1.1,当网页和后台是不同服务时会产生跨域问题1.2,跨域问题 2,nginx端口转发解决跨域问题2.1,下载并安装nginx2.1.1,解压后如下所示2.1.2,进入解压目录后,执行配置…...
LiveQing视频点播流媒体RTMP推流服务功能-支持视频点播分屏大屏展示视频轮巡分组播放RMP推流直播大屏展示
LiveQing支持视频点播分屏大屏展示视频轮播分组播放RMP推流直播大屏展示 1、分屏展示2、轮巡播放3、RTMP推流视频直播和点播流媒体服务 1、分屏展示 LiveQing支持将视频点播、鉴权直播,拉转直播视频流,进行分屏播放。 2、轮巡播放 3、RTMP推流视频直播和…...
tf loss构建常用到函数
1、tf.map_fn tf.map_fn是TensorFlow中的一个函数,用于对给定的函数和输入进行逐元素的映射,其定义如下: tf.map_fn(fn,elems,dtypeNone,parallel_iterationsNone,back_propTrue,swap_memoryFalse,infer_shapeTrue,nameNone,fn_output_sign…...
行为型模式-备忘录模式
备忘录模式保存一个对象的某个状态,以便在适当的时候恢复对象。备忘录模式属于行为型模式。 意图:在不破坏封装性的前提下,捕获一个对象的内部状态,并在该对象之外保存这个状态。 主要解决:所谓备忘录模式就是在不破坏…...
告别移植烦恼:手把手教你用NRF52832的ESB库直连NRF24L01模块(附完整代码)
NRF52832与NRF24L01无缝通信实战指南 1. 理解ESB协议栈的核心机制 NRF52832的增强型 ShockBurst (ESB) 协议栈是实现与NRF24L01兼容通信的关键。这套协议栈通过硬件加速和智能状态管理,为2.4GHz无线通信提供了高效的数据传输机制。 协议栈工作流程解析: …...
量化小白也能懂:用CZSC 0.6.8的Python库,5分钟搞定缠论三买选股
量化小白也能懂:用CZSC 0.6.8的Python库,5分钟搞定缠论三买选股 第一次接触缠论时,那些分型、笔、中枢的概念让我头晕目眩。直到发现CZSC这个Python库,才发现原来用代码实现缠论分析可以如此简单——不需要理解所有理论细节&#…...
JavaScript中判断两个对象深层相等的递归算法
JavaScript深层相等需递归比较:先判同一引用、null/undefined、类型差异;基础类型用;对象/数组校验属性/长度一致后递归;用WeakMap防循环引用;Date、RegExp、Map、Set等特殊对象按语义单独处理。JavaScript中判断两个对…...
告别玄学调参!手把手教你用SX1262 LoRa模块实现5公里稳定通信(附完整代码)
告别玄学调参!手把手教你用SX1262 LoRa模块实现5公里稳定通信(附完整代码) 在物联网设备开发中,LoRa技术因其远距离、低功耗的特性成为许多项目的首选。但当你真正开始使用SX1262这类LoRa模块时,可能会发现实际通信距离…...
终极指南:Switch NAND管理工具NxNandManager的10个核心功能解析
终极指南:Switch NAND管理工具NxNandManager的10个核心功能解析 【免费下载链接】NxNandManager Nintendo Switch NAND management tool : explore, backup, restore, mount, resize, create emunand, etc. (Windows) 项目地址: https://gitcode.com/gh_mirrors/n…...
Python3 WebSocket实战:从基础连接到异步高并发,主流模块选型指南
1. WebSocket基础与Python模块选型指南 第一次接触WebSocket时,我被它和HTTP的长轮询对比惊艳到了。想象一下咖啡馆里两个朋友的对话:HTTP就像每次问"有新消息吗?"都要重新打招呼,而WebSocket则是一次握手后就能持续聊天…...
别再只盯着激光雷达了!聊聊低成本单目摄像头测距在机器人/小车项目里的那些事儿
低成本单目摄像头测距:机器人项目中的实战技巧与避坑指南 在机器人、智能小车和无人机项目中,距离感知一直是核心挑战之一。当大家一窝蜂地追求激光雷达方案时,却忽略了手边最经济实惠的传感器——普通摄像头。单目视觉测距技术,这…...
怎样5分钟完成图片转3D打印:ImageToSTL开源工具高效指南
怎样5分钟完成图片转3D打印:ImageToSTL开源工具高效指南 【免费下载链接】ImageToSTL This tool allows you to easily convert any image into a 3D print-ready STL model. The surface of the model will display the image when illuminated from the left side…...
Kompute安全编程:保护GPU计算免受恶意攻击的7个防护措施
Kompute安全编程:保护GPU计算免受恶意攻击的7个防护措施 【免费下载链接】kompute General purpose GPU compute framework built on Vulkan to support 1000s of cross vendor graphics cards (AMD, Qualcomm, NVIDIA & friends). Blazing fast, mobile-enable…...
