【2451. 差值数组不同的字符串】
来源:力扣(LeetCode)
描述:
给你一个字符串数组 words ,每一个字符串长度都相同,令所有字符串的长度都为 n 。
每个字符串 words[i] 可以被转化为一个长度为 n - 1 的 差值整数数组 difference[i] ,其中对于 0 <= j <= n - 2 有 difference[i][j] = words[i][j+1] words[i][j] 。注意两个字母的差值定义为它们在字母表中 位置 之差,也就是说 'a' 的位置是 0 ,'b' 的位置是 1 ,'z' 的位置是 25 。
- 比方说,字符串 
"acb"的差值整数数组是[2 - 0, 1 - 2] = [2, -1]。 
words 中所有字符串 除了一个字符串以外 ,其他字符串的差值整数数组都相同。你需要找到那个不同的字符串。
请你返回 words 中 差值整数数组 不同的字符串。
示例 1:
输入:words = ["adc","wzy","abc"]
输出:"abc"
解释:
- "adc" 的差值整数数组是 [3 - 0, 2 - 3] = [3, -1] 。
- "wzy" 的差值整数数组是 [25 - 22, 24 - 25]= [3, -1] 。
- "abc" 的差值整数数组是 [1 - 0, 2 - 1] = [1, 1] 。
不同的数组是 [1, 1],所以返回对应的字符串,"abc"。
 
示例 2:
输入:words = ["aaa","bob","ccc","ddd"]
输出:"bob"
解释:除了 "bob" 的差值整数数组是 [13, -13] 以外,其他字符串的差值整数数组都是 [0, 0] 。
 
提示:
- 3 <= words.length <= 100
 - n == words[i].length
 - 2 <= n <= 20
 - words[i] 只含有小写英文字母。
 
方法:遍历
思路与算法
注意到字符串数组 words 的长度 m 最小为 3,因此我们记 diff0, diff1,diff2 分别是 words0 ,words1,words2 的差值整数数组,基于此分情况讨论:
- 如果 diff0 = diff1 ,那么我们遍历 words2 ∼ wordsm−1 ,找到第一个差值整数数组不等于 diff0 的字符串即可。
 - 否则如果 diff0 ≠ diff1 ,那么我们只需判断 diff0 是否等于 diff2 即可。如果等于则足以说明 words1 是唯一一个与其他字符串的差值整数数组都不相同的字符串,因此直接返回 words1。反之,如果 diff0 不等于 diff2 则返回 words0。
 
代码:
class Solution {
public:vector<int> get(string &word) {vector<int> diff(word.size() - 1);for (int i = 0; i + 1 < word.size(); i++) {diff[i] = word[i + 1] - word[i];}return diff;}string oddString(vector<string>& words) {auto diff0 = get(words[0]);auto diff1 = get(words[1]);if (diff0 == diff1) {for (int i = 2; i < words.size(); i++) {if (diff0 != get(words[i])) {return words[i];}}}return diff0 == get(words[2]) ? words[1] : words[0];}
};
 
执行用时:0ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗:7 MB, 在所有 C++ 提交中击败了93.75%的用户
复杂度分析
时间复杂度:O(mn),其中 m 是 words 的长度,n 是 words 中字符串的长度。计算每个字符串的差值整数数组复杂度为 O(n),比较两个字符串的差值整数数组是否相同的复杂度为 O(n),过程中最多比较 m 次,因此总体复杂度为 O(mn)。
空间复杂度:O(n)。过程中,最多会同时存在 3 个长度为 n 的差值整数数组,因此空间复杂度为 O(n)。
author:LeetCode-Solution
相关文章:
【2451. 差值数组不同的字符串】
来源:力扣(LeetCode) 描述: 给你一个字符串数组 words ,每一个字符串长度都相同,令所有字符串的长度都为 n 。 每个字符串 words[i] 可以被转化为一个长度为 n - 1 的 差值整数数组 difference[i] &…...
Java面试-每日十题
目录 1.try-catch-finally中的finally的执行机制 2.什么是Exception和Error 3.Throw和Throws的区别 4.Error与Exception区别 5.Java中的I/O流是什么,分为几类 6.I/O与NI/O 7.常用的I/O的类有哪些 8.字符流与字节流的区别 9.Java反射创建对象 10.什么是类的…...
java.awt.datatransfer.Clipboard剪切板获取String字符串文本
java.awt.datatransfer.Clipboard剪切板获取String字符串文本 有两种方法获取 直接从Clipboard获得 (String) systemClipboard.getData(DataFlavor.stringFlavor);从Clipboard获得Transable再获得String (String) systemClipboard.getContents(null).getTransferData(DataFlav…...
HCIA——VLAN
目录 1,什么是VLAN: 2,如何实现VLAN: 3,VLAN的划分方式: 4,交换机接口类型: 1,Access接口: 2,Trunk接口:允许将一个接口划分给多…...
测试分析流程及输出项
测试分析 一、确认测试范围 根据测试项目的不同需求,有大致几类测试项目类型:商户平台功能测试、支付方式接入测试、架构调整类测试、后台优化测试、性能测试、基本功能自动化测试。 测试项目需要按照文档要求进行测试需求分析,并给出对应…...
OO设计原则
OO设计原则:SOLID SOLID SRP(The Single Responsibility Principle,单一责任原则) 不应有多于1个的原因使得一个类发生变化一个类,一个责任 OCP(The Open-Closes Principle,开放-封闭原则&…...
《深入理解计算机系统(CSAPP)》第5章 优化程序性能 - 学习笔记
写在前面的话:此系列文章为笔者学习CSAPP时的个人笔记,分享出来与大家学习交流,目录大体与《深入理解计算机系统》书本一致。因是初次预习时写的笔记,在复习回看时发现部分内容存在一些小问题,因时间紧张来不及再次整理…...
【Spring Boot】033-使用 `@ResponseBody` 注解代替`ServletResponse`?
【Spring Boot】033-使用 ResponseBody 注解代替ServletResponse? 文章目录 【Spring Boot】033-使用 ResponseBody 注解代替ServletResponse?0、全局总结一、ResponseBody 注解与 ServletResponse 比较1、ResponseBody 注解2、ServletResponse3、总结 二…...
【openGauss实战13】闪回技术
📢📢📢📣📣📣 哈喽!大家好,我是【IT邦德】,江湖人称jeames007,10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】!😜&am…...
Top大学教授:青年学者,请避免这些写作问题→
在科研初期,很多作者由于缺乏经验和指导,糊里糊涂地发了一些质量较低的论文。 为了帮助青年科学家提高写作能力,比利时鲁汶大学的Blocken教授(同时也是Building & Environment、Journal of Wind Engineering & Industrial…...
使用midjourney搞出一套三国人物画像!
当下已进入如火如荼的全民AI时代,最近体验了下midjourney,使用它的以图生图功能生成出来一套三国人物画像,和大家分享下使用心得。 使用midjourney的准备工作 下载工具 使用midjourney生产图片依赖的工具和流程,大致如下&#x…...
ELK日志分析系统
ELK日志分析系统 日志主要包括系统日志/var/log 应用日志 安全日志secure, rsyslog远程传输日志进行汇总集中化管理,日志统计和检索又成为一件比较麻烦的事情,、 1、完整日志系统基本特征 收集:能够采集多种来源的日志数据 …...
整型在内存中的存储
目录 一、为什么内存中存储补码? 二、大小端概念 百度笔试试题: 几道小题: 一、为什么内存中存储补码? 上一节我们了解了原码,反码,补码的概念(http://t.csdn.cn/N0grg)ÿ…...
子集-回溯算法
1题目 给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1: 输入:nums [1,2,3] 输出:[[],[1],[2],[1…...
公司study three
ctrlwind:新建桌面 ctrlwin 箭头 切换桌面 WIN CTRL F4 删除桌面 stream foreach遍历 instFormModifytracesList.stream().forEach(s->{ s.setModifyUser(sysUserTemplate.getNameById(s.getModifyUser()));});拼接 String collect2 peopleList.stream()…...
【运维】speedtest测试
目录 docker 布署 布署云端 docker布署 云端放置于已有容器里 librespeed/speedtest: Self-hosted Speedtest for HTML5 and more. Easy setup, examples, configurable, mobile friendly. Supports PHP, Node, Multiple servers, and more (github.com) docker 布署 获取…...
CycloneDDS开源代码在Linux系统上编译生成可执行文件的详细步骤
cyclonedds开源代码在Linux系统上编译生成可执行文件的详细步骤 1 远程仓库CycloneDDS源码下载2 创建build目录3 进入build目录4 指定安装路径前缀5 编译 cmake --build6 编译完成后进行安装7 版本构建并编译7.1 虚拟机网络桥接7.2 镜像源添加7.3 CUnit单元测试工具安装7.4 编译…...
PLL锁相环的一部分--鉴频鉴相器
鉴频鉴相器作为锁相环的一部分也是有相对应的独立芯片. 鉴频鉴相器芯片主要有以下几种: LM565/LM565C 鉴频鉴相器芯片XR2211CP 鉴频鉴相器芯片NE567 比较器、鉴频、鉴相 ICMC1496/LM1496 综合运算放大器与调制/解调器 ICLM567 比较器、鉴频、鉴相 ICMC100EP2100 高…...
CSS实现磨砂玻璃(毛玻璃)效果样式
要实现磨砂玻璃背景,可以使用 CSS3 中的 ::before 伪元素和 backdrop-filter 属性,结合 opacity 属性和 blur() 函数来实现。 具体实现步骤如下: 创建一个具有背景的元素,例如一个 div 元素。 div {background-image: url(&quo…...
Solidity拓展:数学运算过程中数据长度溢出的问题
在数学运算过程中假如超过了长度则值会变成该类型的最小值,如果小于了该长度则变成最大值 数据上溢 uint8 numA 255; numA;uint8的定义域为[0,255],现在numA已经到顶了,numA会使num变成0(由于256已经超过定义域,它会越过256&…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
