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

图论第5天

 127.单词接龙

 需要cout看一下过程。

#include <iostream>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace ::std;class Solution
{
public:int ladderLength(string beginWord, string endWord, vector<string> &wordList){unordered_set<string> wordSet(wordList.begin(), wordList.end()); // 换成unordered_set后查询速度增加if (wordSet.find(endWord) == wordSet.end())return 0;unordered_map<string, int> visitMap; //<word,查询到的路径长度>queue<string> que;que.push(beginWord);visitMap.insert(pair<string, int>(beginWord, 1));while (!que.empty()){string cur_word = que.front();que.pop();int path = visitMap[cur_word];for (int i = 0; i < cur_word.size(); i++){string new_word = cur_word;for (int j = 0; j < 26; j++){new_word[i] = j + 'a';if (new_word == endWord)return path + 1;if (wordSet.find(new_word) != wordSet.end() && visitMap.find(new_word) == visitMap.end()){visitMap.insert(pair<string, int>(new_word, path + 1));que.push(new_word);}}cout << cur_word << endl;cout << i << endl;for (pair<string, int> x : visitMap){cout << "visitMap[" << x.first << "] = " << x.second << "   ";}cout << endl;}}return 0;}
};int main()
{Solution syz;string beginWord = "hit", endWord = "cog";vector<string> wordList;wordList.push_back("hot");wordList.push_back("dot");wordList.push_back("dog");wordList.push_back("lot");wordList.push_back("log");wordList.push_back("cog");syz.ladderLength(beginWord, endWord, wordList);return 0;
}

cout运行结果需要看一下,理解一下过程:

所有的word的字母都需要执行一次,所以是0、1、2,

hit 改 h是没有单词加入的,改i会有个hot,改t没有单词加入,所以visitMap里不变。hit这时候已经pop()。

hot改h,增加两个dot\lot,改o\t没有,hot.pop()。

竟然是先dot后lot,跟push顺有关。hot会先push “ d ” 后 push " l "

dot,d\o都没有,t改完,出现一个dog,g会继续往下走,dot.pop() 

lot,l\o都没有,出现log.pop()

这时候que里,front 是dog,然后是 log

dog直接知道cog。visitMap[dog] = 4,4 + 1 = 5

hit
0
visitMap[hit] = 1
hit
1
visitMap[hot] = 2   visitMap[hit] = 1
hit
2
visitMap[hot] = 2   visitMap[hit] = 1
hot
0
visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
hot
1
visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
hot
2
visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
dot
0
visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
dot
1
visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
dot
2
visitMap[dog] = 4   visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
lot
0
visitMap[dog] = 4   visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
lot
1
visitMap[dog] = 4   visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
lot
2
visitMap[log] = 4   visitMap[dog] = 4   visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1

广搜更适合这道题,会把所有可能性在起始点周边的可能性,一点点往外扩,不会造成走冤枉路。

图论看来一道题就要很刺激啊。 T _ T。明天摸鱼看能不能做两道吧。

相关文章:

图论第5天

127.单词接龙 需要cout看一下过程。 #include <iostream> #include <queue> #include <stack> #include <unordered_map> #include <unordered_set> #include <vector> using namespace ::std;class Solution { public:int ladderLength(…...

Java开发-面试题-0004-HashMap 和 Hashtable的区别

Java开发-面试题-0004-HashMap 和 Hashtable的区别 更多内容欢迎关注我&#xff08;持续更新中&#xff0c;欢迎Star✨&#xff09; Github&#xff1a;CodeZeng1998/Java-Developer-Work-Note 技术公众号&#xff1a;CodeZeng1998&#xff08;纯纯技术文&#xff09; 生活…...

Swift 序列(Sequence)排序面面俱到 - 从过去到现在(一)

概览 在任何语言中对序列(或集合)元素的排序无疑是一种司空见惯的常规操作,在 Swift 语言里自然也不例外。序列排序看似简单,实则“暗藏玄机”。 要想真正掌握 Swift 语言中对排序的“各种姿势”,我们还得从长计议。不如就先从最简单的排序基本功开始聊起吧。 在本篇博…...

redis 04 redis结构

1.客户端...

【原创】springboot+mysql农业园区管理系统设计与实现

个人主页&#xff1a;程序猿小小杨 个人简介&#xff1a;从事开发多年&#xff0c;Java、Php、Python、前端开发均有涉猎 博客内容&#xff1a;Java项目实战、项目演示、技术分享 文末有作者名片&#xff0c;希望和大家一起共同进步&#xff0c;你只管努力&#xff0c;剩下的交…...

web前端 孙俏:深度探索与实战之路

web前端 孙俏&#xff1a;深度探索与实战之路 在这个数字化、信息化的时代&#xff0c;web前端技术以其独特的魅力&#xff0c;吸引着越来越多的开发者投身其中。今天&#xff0c;我们将跟随孙俏的脚步&#xff0c;一同探索web前端的深度与广度&#xff0c;揭开其神秘的面纱。…...

opencv实战小结-银行卡号识别

实战1-银行卡号识别 项目来源&#xff1a;opencv入门 项目目的&#xff1a;识别传入的银行卡照片中的卡号 难点&#xff1a;银行卡上会有一些干扰项&#xff0c;如何排除这些干扰项&#xff0c;并且打印正确的号码是一个问题 最终效果如上图 实现这样的功能需要以下几个步骤…...

Windows API 开发桌面应用程序,在窗口按下鼠标左键不放可以拖图,并且拖图期间鼠标图标变成手掌

在Windows API中&#xff0c;要实现鼠标左键按下并拖动以移动窗口中的某个图形&#xff0c;并且同时改变鼠标图标为“手掌”形状&#xff08;这通常指的是“拖动”或“移动”的图标&#xff09;&#xff0c;你需要执行几个步骤。 以下是一个基本的步骤指南&#xff0c;用于在W…...

Docker的网络管理

文章目录 一、Docker容器之间的通信1、直接互联&#xff08;默认Bridge网络&#xff09;1.1、Docker安装后默认的网络配置1.2、创建容器后的网络配置1.2.1、首先创建一个容器1.2.2、ip a 列出网卡变化信息1.2.3、查看新建容器后的桥接状态 1.3、容器内安装常见的工具1.4、容器间…...

【数据结构】平衡二叉树左旋右旋与红黑树

平衡二叉树左旋右旋与红黑树 平衡二叉树 定义 平衡二叉树是二叉搜索树的一种特殊形式。二叉搜索树&#xff08;Binary Search Tree&#xff0c;BST&#xff09;是一种具有以下性质的二叉树&#xff1a; 对于树中的每个节点&#xff0c;其左子树中的所有节点都小于该节点的值…...

2024蓝桥杯初赛决赛pwn题全解

蓝桥杯初赛决赛pwn题解 初赛第一题第二题 决赛getting_startedbabyheap 初赛 第一题 有system函数&#xff0c;并且能在bss上读入字符 而且存在栈溢出&#xff0c;只要过掉check函数即可 check函数中&#xff0c;主要是对system常规获取权限的参数&#xff0c;进行了过滤&…...

大模型多轮问答的两种方式

前言 大模型的多轮问答难点就是在于如何精确识别用户最新的提问的真实意图&#xff0c;而在常见的使用大模型进行多轮对话方式中&#xff0c;我接触到的只有两种方式&#xff1a; 一种是简单地直接使用 user 和 assistant 两个角色将一问一答的会话内容喂给大模型&#xff0c…...

【无标题】1877A

足球锦标赛中有 n支球队。每对队伍匹配一次。每场比赛结束后&#xff0c;Pak Chanek收到两个整数作为比赛结果&#xff0c;即两队在比赛中得分的数量。一支球队的效率等于本队每场比赛的总进球数减去对手每场比赛的总进球数。 比赛结束后&#xff0c;Pak Dengklek会计算每支球…...

直播美颜工具解析:美颜SDK核心技术与性能优化方法

本篇文章&#xff0c;小编将深入解析直播美颜SDK的核心技术及其性能优化方法&#xff0c;以期为开发者提供有价值的参考。 一、美颜SDK核心技术 1.实时人脸检测与识别 美颜SDK的核心技术之一是实时人脸检测与识别。这项技术基于深度学习算法&#xff0c;能够快速、准确地识别…...

YOLOv10开源,高效轻量实时端到端目标检测新标准,速度提升46%

前言 实时目标检测在自动驾驶、机器人导航、物体追踪等领域应用广泛&#xff0c;近年来&#xff0c;YOLO 系列模型凭借其高效的性能和实时性&#xff0c;成为了该领域的主流方法。但传统的 YOLO 模型通常采用非极大值抑制 (NMS) 进行后处理&#xff0c;这会增加推理延迟&#…...

如何解决访问网站时IP被限制的问题?

在互联网上&#xff0c;用户可能会面临一个令人困扰的问题——当尝试访问某个特定的网站时&#xff0c;却发现自己的IP地址被该网站屏蔽。 IP地址被网站屏蔽是一个相对常见的现象&#xff0c;而导致这种情况的原因多种多样&#xff0c;包括恶意行为、违规访问等。本文将解释IP地…...

springboot城市美发管理系统的设计与实现-计算机毕业设计源码71715

摘 要 信息化社会内需要与之针对性的信息获取途径&#xff0c;但是途径的扩展基本上为人们所努力的方向&#xff0c;由于站在的角度存在偏差&#xff0c;人们经常能够获得不同类型信息&#xff0c;这也是技术最为难以攻克的课题。针对城市美发管理系统等问题&#xff0c;对城市…...

微软 Windows 10 22H2 发布可选更新 19045.4474,修复窗口显示问题等

微软今天面向 Windows 10 22H2 版本&#xff0c;发布了 KB5037849 非安全可选更新&#xff0c;用户安装后版本号升至 Build 19045.4474。 IT之家 5 月 30 日消息&#xff0c;微软今天面向 Windows 10 22H2 版本&#xff0c;发布了 KB5037849 非安全可选更新&#xff0c;用户安…...

代码随想录算法训练营第五十三天 | 309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费

309.最佳买卖股票时机含冷冻期 视频讲解&#xff1a;动态规划来决定最佳时机&#xff0c;这次有冷冻期&#xff01;| LeetCode&#xff1a;309.买卖股票的最佳时机含冷冻期_哔哩哔哩_bilibili代码随想录 解题思路 1. dp[i][0] 第i天持有股票的状态 dp[i][1]第i天不持股的状…...

Polar Web【中等】反序列化

Polar Web【中等】反序列化 Contents Polar Web【中等】反序列化思路&探索EXPPHP生成PayloadGET传递参数 运行&总结 思路&探索 一个经典的反序列化问题&#xff0c;本文采用PHP代码辅助生成序列字符串的方式生成 Payload 来进行手动渗透。 打开站点&#xff0c;分析…...

STM32从入门到实战:两周速成指南

STM32快速入门指南&#xff1a;从零基础到项目实战1. 项目概述1.1 STM32与8051的对比分析对于已经掌握8051和C语言的开发者而言&#xff0c;STM32的学习曲线并不陡峭。关键在于理解何时需要从8051迁移到STM32平台&#xff1a;计算能力需求&#xff1a;当8051的主频无法满足复杂…...

别再死记硬背了!用Python手把手教你实现数据库闭包自动计算器

用Python实现数据库闭包计算器&#xff1a;从理论到实战的自动化工具 闭包计算是数据库原理中的核心算法&#xff0c;但传统教材往往停留在抽象描述和手工演算阶段。作为曾经被各种箭头符号和递归推导折磨过的开发者&#xff0c;我决定用Python打造一个能自动计算闭包并可视化步…...

SEO_全面介绍SEO从入门到精通的关键知识点

<h2>什么是SEO&#xff1f;</h2> <p>SEO&#xff08;Search Engine Optimization&#xff0c;搜索引擎优化&#xff09;是一套通过优化网站内容和结构&#xff0c;以提高其在搜索引擎结果页面&#xff08;SERP&#xff09;中的自然排名的技术和策略。SEO不仅…...

华为光猫配置解密工具技术架构解析与实现机制

华为光猫配置解密工具技术架构解析与实现机制 【免费下载链接】HuaWei-Optical-Network-Terminal-Decoder 项目地址: https://gitcode.com/gh_mirrors/hu/HuaWei-Optical-Network-Terminal-Decoder 在网络设备运维领域&#xff0c;华为光猫配置文件的安全加密机制为设备…...

springboot交通道路监测感知与车路协同系统可视化大屏

目录技术架构设计数据采集与处理可视化大屏功能模块系统集成与部署关键技术点测试与迭代项目技术支持源码获取详细视频演示 &#xff1a;文章底部获取博主联系方式&#xff01;同行可合作技术架构设计 采用SpringBoot作为后端框架&#xff0c;提供RESTful API接口&#xff1b;…...

Gemma-3-270m量化压缩实战:4位精度模型部署

Gemma-3-270m量化压缩实战&#xff1a;4位精度模型部署 1. 开篇&#xff1a;小模型的大能量 最近在折腾边缘设备部署时&#xff0c;发现一个挺有意思的现象&#xff1a;很多团队还在用"大炮打蚊子"&#xff0c;明明只需要处理一些简单的文本分类任务&#xff0c;却…...

ccmusic-database新手教程:Gradio输出组件定制——增强Top5结果可读性技巧

ccmusic-database新手教程&#xff1a;Gradio输出组件定制——增强Top5结果可读性技巧 1. 项目简介与背景 ccmusic-database是一个基于深度学习的音乐流派分类系统&#xff0c;它能够自动识别音频文件所属的音乐流派。这个系统在计算机视觉预训练模型VGG19_BN的基础上进行微调…...

Realistic Vision V5.1开源镜像部署教程:Docker+Streamlit一体化环境搭建

Realistic Vision V5.1开源镜像部署教程&#xff1a;DockerStreamlit一体化环境搭建 1. 项目概述 Realistic Vision V5.1是目前SD 1.5生态中最顶级的写实风格模型之一&#xff0c;能够生成媲美专业单反相机拍摄的人像照片。本文将带你从零开始&#xff0c;通过Docker容器和St…...

CI/CD 流水线性能优化:从构建到部署

CI/CD 流水线性能优化&#xff1a;从构建到部署 前言 哥们&#xff0c;别整那些花里胡哨的理论。今天直接上硬菜——我在大厂一线优化 CI/CD 流水线性能的真实经验总结。作为一个白天写前端、晚上打鼓的硬核工程师&#xff0c;我对效率的追求就像对鼓点节奏的把控一样严格。 背…...

OpenDroneMap实战指南:从航拍图像到三维模型的完整技术解析

OpenDroneMap实战指南&#xff1a;从航拍图像到三维模型的完整技术解析 【免费下载链接】ODM A command line toolkit to generate maps, point clouds, 3D models and DEMs from drone, balloon or kite images. &#x1f4f7; 项目地址: https://gitcode.com/gh_mirrors/od…...