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

752. 打开转盘锁

链接:

752. 打开转盘锁

题解:

class Solution {
public:int openLock(vector<string>& deadends, string target) {std::unordered_set<std::string> table(deadends.begin(), deadends.end());if (table.find("0000") != table.end()|| table.find(target) != table.end()) {return -1;}std::queue<std::string> que;std::unordered_map<std::string, int> distance;que.push(std::string("0000"));distance["0000"] = 0;auto get_next = [](std::string& word)->std::vector<std::string> {std::vector<std::string> result;for (int i = 0; i < word.size(); ++i) {char ch = word[i];if (word[i] == '9') {word[i] = '0';} else {++word[i];}result.push_back(word);word[i] = ch;if (word[i] == '0') {word[i] = '9';} else {--word[i];}result.push_back(word);word[i] = ch;}return result;};while (!que.empty()) {int size = que.size();for (int i = 0; i < size; ++i) {auto f = que.front();que.pop();if (f == target) {return distance[f];}for (auto& next : get_next(f)) {//cout << "next = " << next << endl;if (table.find(next) != table.end()) {continue;}if (distance.find(next) != distance.end()) {continue;}/*if (next == target) {return distance[f] + 1;}*/distance[next] = distance[f] + 1;que.push(next);}}}return -1;}
};
class Solution {
public:int openLock(vector<string>& deadends, string target) {if (target == "0000") {return 0;}unordered_set<string> dead(deadends.begin(), deadends.end());if (dead.count("0000")) {return -1;}auto num_prev = [](char x) -> char {return (x == '0' ? '9' : x - 1);};auto num_succ = [](char x) -> char {return (x == '9' ? '0' : x + 1);};// 枚举 status 通过一次旋转得到的数字auto get = [&](string& status) -> vector<string> {vector<string> ret;string bak = status;for (int i = 0; i < 4; ++i) {char num = status[i];status[i] = num_prev(num);ret.push_back(status);status[i] = num_succ(num);ret.push_back(status);status = bak;}return ret;};queue<pair<string, int>> q;q.emplace("0000", 0);unordered_set<string> seen = {"0000"};int step = 0;while (!q.empty()) {auto [status, step] = q.front();q.pop();for (auto&& next_status: get(status)) {if (!seen.count(next_status) && !dead.count(next_status)) {if (next_status == target) {//return step + 1;return step+1;}q.emplace(next_status, step + 1);seen.insert(move(next_status));}}++step;}return -1;}
};

相关文章:

752. 打开转盘锁

链接&#xff1a; 752. 打开转盘锁 题解&#xff1a; class Solution { public:int openLock(vector<string>& deadends, string target) {std::unordered_set<std::string> table(deadends.begin(), deadends.end());if (table.find("0000") ! t…...

Bearly:基于人工智能的AI写作文章生成工具

【产品介绍】 名称 Bearly 具体描述 Bearly是一个AI人工智能内容创作工具。你可以用Bearly来阅读、写作、创作&#xff0c;提高你的效率。包括使用Bearly来生成网页的摘要、标题、关键点&#xff0c;也可以用Bearly来生成创意内容、艺术图片、文案编辑等。帮助你克…...

详解哈希,理解及应用

全文目录 概念哈希冲突及原因解决哈希冲突的方法闭散列线性探测二次探测扩容 开散列扩容 哈希的应用位图布隆过滤器 概念 通过映射关系将关键字映射到存储位置&#xff0c;并实现增删改查操作。 通过上面的方法构造出来的结构就叫哈希表&#xff08;散列表&#xff09;&#x…...

解决js加减乘除精度丢失问题

公共类, 将科学计数法的数字转为字符串(以下加减乘除依赖该方法) var toNonExponential (num)> {if(num null) {return num;}if(typeof num "number") {var m num.toExponential().match(/\d(?:\.(\d*))?e([-]\d)/);return num.toFixed(Math.max(0, (m[1] …...

八股——const 关键字

1.const作用 作用&#xff1a;const用于保护指针指向数据不被修改 测试代码1 显示数组的函数不小心修改了指针指向的值&#xff0c;这时候没有加const关键字&#xff0c;编译器不会报错 #include <stdio.h> void showar(int ar[]);int main(void) {int ar[4]{2,3,4,5…...

QT object元对象

qt中的元对象系统提供了对象间通信的信号和槽机制、运行时类型 信息和动态属性系统&#xff1b; 1.该类必须继承自QObject类&#xff1b; 2.必须在类的私有声明区声明Q_OBJECT宏&#xff08;在类定义时&#xff0c;如果没有指定&#xff0c;public或private,则默认为private&a…...

互斥锁,条件变量,信号量的三个小demo

仨demo 一、 一个线程读文件&#xff0c;另一个线程将读取的内容输出到终端 1.1 要求 创建两个线程&#xff0c;其中一个线程读取文件中的数据&#xff0c;另外一个线程将读取到的内容打印到终端上&#xff0c;类似实现cat一个文件。 cat数据完毕后&#xff0c;要结束两个线…...

【UE 材质】力场护盾和冲击波效果

目录 效果 步骤 一、制作力场护盾材质 二、制作冲击波材质效果 三、制作冲击波粒子效果 四、制作震动效果 效果 步骤 一、制作力场护盾材质 1. 首先新建一个第一人称角色游戏模板 2. 新建一个材质&#xff0c;用于作为力场护盾的材质&#xff0c;这里命名为“Mat_for…...

类和对象三大特性之多态

全文目录 虚函数虚函数的重写接口继承和实现继承重载、重写&#xff08;覆盖&#xff09;、隐藏&#xff08;重定义&#xff09;C11 override 和 final抽象类 多态的概念多态原理虚函数表 单继承和多继承的虚函数表打印虚函数表单继承的虚函数表多继承的虚函数表 常见面试问答题…...

为何红黑树在B/B+树之上仍然占据重要地位?

为何红黑树在B/B树之上仍然占据重要地位&#xff1f; 引言二、红黑树和B/B树的基本原理2.1、红黑树的特点和性质2.2、B/B树的特点和性质2.3、红黑树和B/B树的比较 三、B/B树相对于红黑树的优势四、红黑树仍然占据重要地位的原因总结 博主简介 &#x1f4a1;一个热爱分享高性能服…...

【算法专题突破】滑动窗口 - 水果成篮(13)

目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后&#xff1a; 1. 题目解析 题目链接&#xff1a;904. 水果成篮 - 力扣&#xff08;Leetcode&#xff09; 题目有很长一段话&#xff0c;但是我们读一遍题目可以提炼转化出题目的要求 &#xff1a; 其实就是找出一个最长…...

Peppercontent.io:人工智能驱动的内容生成工具

【产品介绍】​ 名称 Peppercontent.io 成立时间​ 成立于2017年 具体描述 Peppertype.ai 是一种基于GPT-3的AI辅助工具&#xff0c;而GPT-3则是一种深度学习自回归语言模型。这一技术潜藏着巨大的潜力&#xff0c;可以立刻为企业和创作者提供创意内容&…...

docker镜像管理-实操

一.docker镜像管理 1.拉取镜像 docker image pull <repository>:<tag> 镜像名称和标签使用 : 进行分隔&#xff0c;如果省略了标签&#xff0c;则默认为 latest docker image pull nginx:latest 或者docker pull nginx:latest 拉取下来的镜像默认保存在&#xff1…...

SpringMVC-----JSR303以及拦截器

目录 JSR303 什么是JSR303 JSR303的作用 JSR303常用注解 入门使用 拦截器是什么 拦截器的工作原理 拦截器的作用 拦截器的使用 JSR303 什么是JSR303 JSR303是Java为Bean数据合法性校验提供给的标准框架&#xff0c;已经包含在JavaEE6.0中1。 JSR303通过在Bean属性中标…...

基于若依框架实现markdown在线编辑

基于若依框架实现markdown在线编辑 1. 下载mavon-editor npm install mavon-editor --save2. 打开main.js文件, 添加如下 // markdown组件 import { mavonEditor } from "mavon-editor"; import "mavon-editor/dist/css/index.css";// markdown组件 Vue…...

CentOS7上从0开始搭建Zookeeper集群

CentOS7上搭建Zookeeper集群 环境准备安装jdk安装zookeeper下载zookeeper解压zookeeper修改zookeeper配置文件 搭建zookeeper集群修改zoo.cfg文件添加myid文件启动zookeeper集群 环境准备 首先你需要准备三台zookeeper&#xff08;待会会讲zookeeper的安装流程&#xff09;&am…...

康耐视读码器DataMan软件详细使用步骤

1、 点击桌面已经安装好的 dataman 软件并打开 2、 打开之后,点击刷新,刷出来读码器的图标,双击进行连接,或者选中后,点击右下角 的连接。(也可先进行第 9—(2)步更改读码器的 IP,对应的连接对象也更改到同一网 段)如图 3、 连接之后,在设置 快速设置下面把实时显…...

408强化(番外)文件管理

有点看不下去书&#xff0c;408&#xff0c;哎好久没看了&#xff0c;死磕数学时完全不想看其他科目&#xff0c;数学分数也尚未质变。 突然想到一个好点子&#xff0c;只看大纲尝试回忆一下这章的内容。 文件就是为了方便用户使用&#xff0c;按名访问而提出的&#xff0c;从…...

iptables 防火墙配置

文章目录 iptables 防火墙配置规则链的分类–五链处理的动作iptables 常用参数和作用iptables 防火墙配置查看规则链清空规则链设置默认规则将流入的流量丢弃允许ICMP协议流量通过删除默认策略允许所以流量通过设置将所有流入22端口的流量全部拒绝允许指定网段的22端口通过设置…...

面试官:我们深入聊聊Java虚拟机吧

哈喽&#xff01;大家好&#xff0c;我是奇哥&#xff0c;一位专门给面试官添堵的职业面试员 文章持续更新&#xff0c;可以微信搜索【小奇JAVA面试】第一时间阅读&#xff0c;回复【资料】更有我为大家准备的福利哟&#xff01; 文章目录 前言面试Java虚拟机内存模型垃圾收集器…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

【实施指南】Android客户端HTTPS双向认证实施指南

&#x1f510; 一、所需准备材料 证书文件&#xff08;6类核心文件&#xff09; 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...