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

每天一道leetcode:433. 最小基因变化(图论中等广度优先遍历)

今日份题目:

基因序列可以表示为一条由 8 个字符组成的字符串,其中每个字符都是 'A''C''G''T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

  • 例如,"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化,只有基因库中的基因才是有效的基因序列。(变化后的基因必须位于基因库 bank 中)

给你两个基因序列 startend ,以及一个基因库 bank ,请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化,返回 -1

注意:起始基因序列 start 默认是有效的,但是它并不一定会出现在基因库中。

示例1

输入:start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出:1

示例2

输入:start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出:2

示例3

输入:start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
输出:3

提示

  • start.length == 8

  • end.length == 8

  • 0 <= bank.length <= 10

  • bank[i].length == 8

  • startendbank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成

题目思路

这道题广度优先的思路有点暴力搜索的意思,就是遍历所有的可能组合,然后找到最后的结果组合,找不到就返回-1,找得到就返回步数。具体来说,我们需要遍历所有8个位置的所有4个字母的组合,如果某个组合未被遍历过并且能在字典中找到,那么就放入bfs队列中,否则跳过,每层bfs结束step加一,直到找到最后结果。

注意:unodered_set插入使用emplace;使用visited集合标记遍历过的组合;第一个找到的就是最小的step,因为一起加加,所以第一个满足时就是结果了。

代码

class Solution 
{
public:    int minMutation(string start, string end, vector<string>& bank) {unordered_set<string> dict; //存放字典信息unordered_set<string> visited;char chara[4]={'A','C','G','T'};        for(auto &b:bank) {dict.emplace(b);}if(start==end) //剪枝,未变化{return 0;}if(!dict.count(end)) //如果变换后的组合不在字典中,那么无法实现变化,返回-1{return -1;}queue<string> p;p.push(start);visited.emplace(start);int step=1;//bfswhile(!p.empty()) {int n=p.size();for(int i=0;i<n;i++) {string curr=p.front();p.pop();//遍历每位的所有可能的字母情况for(int j=0;j<8;j++) //遍历序列的8个位置{for(int k=0;k<4;k++) //遍历4种字母{if(chara[k]!=curr[j]) //当前不是这个字母{string next=curr;next[j]=chara[k];//在当前组合的基础上,将这个位置的字母改为当前字母if(!visited.count(next)&&dict.count(next)) {//可以加入的条件:在字典中能找到并且没有被遍历过if(next==end) //找到最后的了,返回步数{return step;}//还未找到最后p.push(next);visited.emplace(next);}}}}}step++;//每完成一层就加一,与上个题一样}return -1;}
};

提交结果

欢迎大家在评论区讨论,如有不懂的部分,欢迎在评论区留言!

更新不易,宝子们点个赞支持下,谢谢!

每天一道leetcode,大家一起在评论区打卡呀!

相关文章:

每天一道leetcode:433. 最小基因变化(图论中等广度优先遍历)

今日份题目&#xff1a; 基因序列可以表示为一条由 8 个字符组成的字符串&#xff0c;其中每个字符都是 A、C、G 和 T 之一。 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。 例如&#xff0c;&quo…...

【C++】做一个飞机空战小游戏(十)——子弹击落炮弹、炮弹与飞机相撞

[导读]本系列博文内容链接如下&#xff1a; 【C】做一个飞机空战小游戏(一)——使用getch()函数获得键盘码值 【C】做一个飞机空战小游戏(二)——利用getch()函数实现键盘控制单个字符移动【C】做一个飞机空战小游戏(三)——getch()函数控制任意造型飞机图标移动 【C】做一个飞…...

去除UI切图边缘上多余的线条

最近接到UI切图&#xff0c;放进项目&#xff0c;显示边缘有多余线条&#xff0c;影响UI美观。开始以为切图没切好&#xff0c;实则不是。如图&#xff1a; ->解决&#xff1a; 将该图片资源WrapMode改为Clamp...

Spring高手之路13——BeanFactoryPostProcessor与BeanDefinitionRegistryPostProcessor解析

文章目录 1. BeanFactoryPostProcessor 概览1.1 解读 BeanFactoryPostProcessor1.2. 如何使用 BeanFactoryPostProcessor 2. BeanDefinitionRegistryPostProcessor 深入探究2.1 解读 BeanDefinitionRegistryPostProcessor2.2 BeanDefinitionRegistryPostProcessor 的执行时机2.…...

【LeetCode动态规划】详解买卖票I~IV,经典dp题型买

给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票&#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。…...

【深入探究人工智能】:常见机器学习算法总结

文章目录 1、前言1.1 机器学习算法的两步骤1.2 机器学习算法分类 2、逻辑回归算法2.1 逻辑函数2.2 逻辑回归可以用于多类分类2.3 逻辑回归中的系数 3、线性回归算法3.1 线性回归的假设3.2 确定线性回归模型的拟合优度3.3线性回归中的异常值处理 4、支持向量机&#xff08;SVM&a…...

设计模式之解释器模式详解及实例

1、解释器设计模式概述&#xff1a; 解释器模式&#xff08;Interpreter Pattern&#xff09;是一种设计模式&#xff0c;它主要用于描述如何构建一个解释器以解释特定的语言或表达式。该模式定义了一个文法表示和解释器的类结构&#xff0c;用于解释符合该文法规则的语句。解…...

Nodejs沙箱逃逸--总结

一、沙箱逃逸概念 JavaScript和Nodejs之间有什么区别&#xff1a;JavaScript用在浏览器前端&#xff0c;后来将Chrome中的v8引擎单独拿出来为JavaScript单独开发了一个运行环境&#xff0c;因此JavaScript也可以作为一门后端语言&#xff0c;写在后端&#xff08;服务端&#…...

No115.精选前端面试题,享受每天的挑战和学习

文章目录 变量提升和函数提升的顺序Event Loop封装 FetchAPI&#xff0c;要求超时报错的同时&#xff0c;取消执行的 promise&#xff08;即不继续执行&#xff09;强缓存和协商缓存的区别token可以放在cookie里吗&#xff1f; 变量提升和函数提升的顺序 在JavaScript中&#…...

Elasticsearch:语义搜索 - Semantic Search in python

当 OpenAI 于 2022 年 11 月发布 ChatGPT 时&#xff0c;引发了人们对人工智能和机器学习的新一波兴趣。 尽管必要的技术创新已经出现了近十年&#xff0c;而且基本原理的历史甚至更早&#xff0c;但这种巨大的转变引发了各种发展的“寒武纪大爆炸”&#xff0c;特别是在大型语…...

Flink学习笔记(一)

流处理 批处理应用于有界数据流的处理&#xff0c;流处理则应用于无界数据流的处理。 有界数据流&#xff1a;输入数据有明确的开始和结束。 无界数据流&#xff1a;输入数据没有明确的开始和结束&#xff0c;或者说数据是无限的&#xff0c;数据通常会随着时间变化而更新。 在…...

[Raspberry Pi]如何用VNC遠端控制樹莓派(Ubuntu desktop 23.04)?

之前曾利用VMware探索CentOS&#xff0c;熟悉Linux操作系統的指令和配置運作方式&#xff0c;後來在樹莓派價格飛漲的時期&#xff0c;遇到貴人贈送Raspberry Pi 4 model B / 8GB&#xff0c;這下工具到位了&#xff0c;索性跳過樹莓派官方系統(Raspberry Pi OS)&#xff0c;直…...

17.HPA和rancher

文章目录 HPA部署 metrics-server部署HPA Rancher部署Rancherrancher添加集群仪表盘创建 namespace仪表盘创建 Deployments仪表盘创建 service 总结 HPA HPA&#xff08;Horizontal Pod Autoscaling&#xff09;Pod 水平自动伸缩&#xff0c;Kubernetes 有一个 HPA 的资源&…...

VS2022远程Linux使用cmake开发c++工程配置方法

文章目录 远程连接CMakePresets.json的配置Task.vs.json配置launch.vs.json配置最近使用别人在VS2015上使用visualgdb搭建的linux开发环境,各种不顺手,一会代码不能调转了,一会行号没了,调试的时候断不到正确的位置,取消的断点仍然会进。因此重新摸索了一套使用vs的远程开…...

《强化学习:原理与Python实战》——可曾听闻RLHF

前言&#xff1a; RLHF&#xff08;Reinforcement Learning with Human Feedback&#xff0c;人类反馈强化学习&#xff09;是一种基于强化学习的算法&#xff0c;通过结合人类专家的知识和经验来优化智能体的学习效果。它不仅考虑智能体的行为奖励&#xff0c;还融合了人类专家…...

STM32——RTC实时时钟

文章目录 Unix时间戳UTC/GMT 时间戳转换BKP简介BKP基本结构读写BKP备份寄存器电路设计关键代码 RTC简介RTC框图RTC基本结构硬件电路RTC操作注意事项读写实时时钟电路设计关键代码 Unix时间戳 Unix 时间戳&#xff08;Unix Timestamp&#xff09;定义为从UTC/GMT的1970年1月1日…...

webSocket 开发

1 认识webSocket WebSocket_ohana&#xff01;的博客-CSDN博客 一&#xff0c;什么是websocket WebSocket是HTML5下一种新的协议&#xff08;websocket协议本质上是一个基于tcp的协议&#xff09;它实现了浏览器与服务器全双工通信&#xff0c;能更好的节省服务器资源和带宽…...

c#设计模式-结构型模式 之 代理模式

前言 由于某些原因需要给某对象提供一个代理以控制对该对象的访问。这时&#xff0c;访问对象不适合或者不能直接 引用目标对象&#xff0c;代理对象作为访问对象和目标对象之间的中介。在学习代理模式的时候&#xff0c;可以去了解一下Aop切面编程AOP切面编程_aop编程…...

openpnp - 自动换刀的设置

文章目录 openpnp - 自动换刀的设置概述笔记采用的openpnp版本自动换刀库的类型选择自动换刀设置前的注意事项先卸掉吸嘴座上所有的吸嘴删掉所有的吸嘴设置自动换刀的视觉识别设置吸嘴座为自动换刀 - 以N1为例备注补充 - 吸嘴轴差个0.3mm, 就有可能怼坏吸嘴END openpnp - 自动换…...

《HeadFirst设计模式(第二版)》第十章代码——状态模式

如下图所示&#xff0c;这是一个糖果机的状态机图&#xff0c;要求使用代码实现&#xff1a; 初始版本&#xff1a; package Chapter10_StatePattern.Origin;/*** Author 竹心* Date 2023/8/19**/public class GumballMachine {final static int SOLD_OUT 0;final static int…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...

stm32wle5 lpuart DMA数据不接收

配置波特率9600时&#xff0c;需要使用外部低速晶振...