面试算法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…...
行为型模式-备忘录模式
备忘录模式保存一个对象的某个状态,以便在适当的时候恢复对象。备忘录模式属于行为型模式。 意图:在不破坏封装性的前提下,捕获一个对象的内部状态,并在该对象之外保存这个状态。 主要解决:所谓备忘录模式就是在不破坏…...
多核系统缓存一致性与并行编程优化实践
1. 多核系统架构与缓存一致性挑战现代多核处理器通常采用共享内存架构,每个核心拥有独立的L1缓存,而L2缓存可能是独立或共享的设计。以Intel Core i7为例,其典型架构包含:每个物理核心独享32KB L1指令缓存和32KB L1数据缓存256KB私…...
基于Kotti-py312这个项目,帮我写一个AI 交流网站。先帮我规划一下!我的诉求是能实现AI资源的互助,大家互相帮着找点子,一起落地实践!
基于Kotti-py312这个项目,帮我写一个AI 交流网站。先帮我规划一下! 我的诉求是能实现AI资源的互助,大家互相帮着找点子,一起落地实践!Kotti-py312这个项目代码在:G:\dumatework核心理念:AI 资源…...
终极指南:如何用Win_ISO_Patching_Scripts快速制作集成最新补丁的Windows安装镜像
终极指南:如何用Win_ISO_Patching_Scripts快速制作集成最新补丁的Windows安装镜像 【免费下载链接】Win_ISO_Patching_Scripts Win_ISO_Patching_Scripts 项目地址: https://gitcode.com/gh_mirrors/wi/Win_ISO_Patching_Scripts 还在为手动集成Windows补丁而…...
下载数据集
在 Ubuntu 上下载 Hugging Face 数据集,我推荐使用 huggingface-cli 这个官方工具,它稳定且支持断点续传。国内用户配置 hf-mirror.com 镜像站后,下载速度会快很多。下面是完整的命令步骤,你可以逐条复制执行。### 🐧 …...
网盘直链下载助手:八大平台高速下载解决方案
网盘直链下载助手:八大平台高速下载解决方案 【免费下载链接】Online-disk-direct-link-download-assistant 一个基于 JavaScript 的网盘文件下载地址获取工具。基于【网盘直链下载助手】修改 ,支持 百度网盘 / 阿里云盘 / 中国移动云盘 / 天翼云盘 / 迅…...
无需多软件切换, 实现文档、表格、协作工具一体化
前言 每天在办公室里处理各种文件,打开 Word 写文档、切到 Excel 做表格、再开一个窗口做 PPT,中间还要穿插着局域网聊天、思维导图整理思路,白板讨论完还要手动整理纪要。一台电脑屏幕上开满了窗口,任务栏挤得密密麻麻ÿ…...
AI辅助排版:设计领域的应用方法与落地实践
数字化内容生产节奏不断加快,品牌方对内容输出的频率和质量要求同步提升。不少中小设计团队因为排版效率不足,无法承接高频次的内容输出需求。特别是电商大促节点,不少中小团队一周要承接近百套商品详情页、平台活动海报、新媒体种草内容的排…...
私车公用合规区分通勤与办公里程,核算可抵扣账务额度。
一、实际应用场景描述某科技公司实行私车公用报销制度:- 员工使用自有车辆处理公务- 公司按月报销 合理公务里程对应的用车成本- 财务需区分:- ✅ 通勤里程(不可报销)- ✅ 公务里程(可报销 可抵扣进项税)-…...
3分钟掌握阅读APP书源导入:告别书荒,开启全网小说自由阅读之旅
3分钟掌握阅读APP书源导入:告别书荒,开启全网小说自由阅读之旅 【免费下载链接】Yuedu 📚「阅读」自用书源分享 项目地址: https://gitcode.com/gh_mirrors/yu/Yuedu 你是否遇到过这样的情况:深夜追更时突然提示"书源…...
Spring AI Alibaba 快速开始:5分钟跑通第一个应用
Spring AI Alibaba 快速开始:5分钟用智谱 GLM 跑通第一个聊天应用 题外话 最近因为有功能有上线,这几天都忙着在整理投产资料。属实是更新不动了,当然还有一个原因就是之前发库存发的太爽了,现在地主家也没有余粮了。之前学完sp…...
