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

【每日刷题】Day155

【每日刷题】Day155

🥕个人主页:开敲🍉

🔥所属专栏:每日刷题🍍

🌼文章目录🌼

1. LCR 108. 单词接龙 - 力扣(LeetCode)

2. 675. 为高尔夫球比赛砍树 - 力扣(LeetCode)

3. LCR 107. 01矩阵 - 力扣(LeetCode)

1. LCR 108. 单词接龙 - 力扣(LeetCode)

//思路:本题与 Day154 中的 "最小基因变化" 完全一样

class Solution {

public:

    string total = "abcdefghijklmnopqrstuvwxyz";

    int ladderLength(string beginWord, string endWord, vector<string>& wordList)

    {

        unordered_set<string> hash(wordList.begin(),wordList.end());//标记字典中的单词

        unordered_set<string> se;//标记已经出现过的单词

        if(!hash.count(endWord)||beginWord==endWord) return 0;

        queue<string> qu;

        qu.push(beginWord);

        se.insert(beginWord);

       

        int ans = 0;

        while(!qu.empty())

        {

            ans++;

            int size = qu.size();

            for(int i = 0;i<size;i++)

            {

                string s = qu.front();

                for(int j = 0;j<s.size();j++)

                {

                    for(int m = 0;m<26;m++)

                    {

                        string tmp = s;

                        if(tmp[j]==total[m]) continue;

                        tmp[j] = total[m];

                        if(tmp==endWord) return ans+1;

                        if(se.count(tmp)) continue;

                        se.insert(tmp);

                        if(hash.count(tmp)) qu.push(tmp);

                    }

                }

                qu.pop();

            }

        }

        return 0;

    }

};

2. 675. 为高尔夫球比赛砍树 - 力扣(LeetCode)

//思路:BFS+排序 

//本题可以看作是 Day154 中 "迷宫中离入口最近的出口" 的升级版。

//仔细思考一下,本题要求我们从 (0,0)位置开始砍树,必须按照 由低到高 的顺序进行砍树,那我们首先第一步一定是先把数组中的所有树的高度按照升序排序,并且排序后我们还要保留其原本所在的坐标。

//排好序后,我们要从最低的树开始砍,砍完当前树需要去到下一个更高的树,因此这里我们实际上可以将砍树的动作看作为:从低的树的坐标,去到下一个更高的树的坐标;再从下一个更高的树的坐标,去到下下一个更更高的树的坐标 ...... ,以此类推。

//到这,本题实际上就是多次 从一个坐标去到另一个坐标 的操作,与  "迷宫中离入口最近的出口" 这题的思路就完全一样了。

class Solution {

public:

    int n, m;

    int dx[4] = { 1,-1,0,0 };

    int dy[4] = { 0,0,1,-1 };

    int cutOffTree(vector<vector<int>>& forest)

    {

        n = forest.size(), m = forest[0].size();

        int ans = 0;

        vector<vector<int>> hash;//这里也可以用 pair,如果用pair后面 sort排序的时候就要自己写 lambda 表达式来排序,这里偷懒的方法就是用二维数组。

        for (int i = 0; i < n; i++)

            for (int j = 0; j < m; j++)

                if (forest[i][j] > 1)

                      hash.push_back({forest[i][j],i,j});//0位置放值,也就是树的高度,1、2位置放坐标

        sort(hash.begin(), hash.end());//排序时默认会按照数组第一个元素进行排序,这里刚好就是根据树的高度进行排序

        int bx = 0, by = 0;//从 (0,0)位置开始

        for (int i = 0; i < hash.size(); i++)

        {

            auto a = hash[i];

            int ex = a[1], ey = a[2];//拿到下一个位置的坐标

            int ret = bfs(forest, bx, by, ex, ey);//获得从 bx、by(初始位置)到达ex、ey(目标位置)所需的最少步数

            if (ret == -1) return -1;//没法到达说明一定有至少一棵树没法砍掉,返回-1

            ans += ret;

            bx = ex, by = ey;//更新初始位置

        }

        return ans;

    }

//下面的代码与 "迷宫中离入口最近的出口" 完全一样

    int bfs(vector<vector<int>>& forest, int bx, int by, int ex, int ey)

    {

        if(bx==ex&&by==ey) return 0;

        vector<vector<bool>> hash(n, vector<bool>(m));

        queue<pair<int, int>> qu;

        qu.push({bx,by});

        hash[bx][by] = true;

        int ret = 0;

        while (!qu.empty())

        {

            ret++;

            int size = qu.size();

            while(size--)

            {

                auto a = qu.front();

                qu.pop();

                for (int j = 0; j < 4; j++)

                {

                    int x = a.first + dx[j], y = a.second + dy[j];

                    if (x >= 0 && x < n && y >= 0 && y < m && !hash[x][y] && forest[x][y])

                    {

                        if (x == ex && y == ey) return ret;

                        qu.push({ x,y });

                        hash[x][y] = true;

                    }

                }

            }

        }

        return -1;

    }

};

3. LCR 107. 01矩阵 - 力扣(LeetCode)

//思路:多源BFS

//多源BFS问题相较于单源BFS问题而言,区别仅仅在于:单源BFS初始只将一个起点放入队列向外扩展;多源BFS则是将所有起点同时放入队列进行向外扩展。

//本题我们要从逆向思维来考虑问题:题目让我们找到矩阵中所有位置的 1 到它最近的 0 的距离,并将距离与 1 替换。

//反向思考:我们将所有的 0 看作一个起点向外扩展,每次扩展到 1 时直接记录当前距离,一定是最短距离(因为每个 1 都一定有一个距离最近的 0 ,将所有 0 视为同一个起点同时向外扩展时,距离 某个 1 的某个 0一定先扩展到,因此每次的距离一定是最短的)

class Solution {

public:

    int n,m;

    int dx[4] = {1,-1,0,0};

    int dy[4] = {0,0,1,-1};

    vector<vector<int>> updateMatrix(vector<vector<int>>& mat)

    {

        n = mat.size(),m = mat[0].size();

        vector<vector<bool>> hash(n,vector<bool>(m));

        queue<vector<int>> qu;

        for(int i = 0;i<n;i++)

            for(int j = 0;j<m;j++)

                if(!mat[i][j])

                {

                    qu.push({i,j});//将所有 0 放入队列,视为一个起点,同时向外扩展

                    hash[i][j] = true;

                }

       

        int ret = 0;

        while(!qu.empty())

        {

            ret++;

            int size = qu.size();

            while(size--)

            {

                auto arr = qu.front();

                qu.pop();

                for(int j = 0;j<4;j++)

                {

                    int x = arr[0]+dx[j],y = arr[1]+dy[j];

                    if(x>=0&&x<n&&y>=0&&y<m&&!hash[x][y])

                    {

                        if(mat[x][y]) mat[x][y] = ret;//扩展到 1 时,此时的距离一定是最短的(因为此时一定是距离最近的 0 先扩展到 1)

                        qu.push({x,y});

                        hash[x][y] = true;

                    }

                }

            }

        }

        return mat;

    }

};

相关文章:

【每日刷题】Day155

【每日刷题】Day155 &#x1f955;个人主页&#xff1a;开敲&#x1f349; &#x1f525;所属专栏&#xff1a;每日刷题&#x1f34d; &#x1f33c;文章目录&#x1f33c; 1. LCR 108. 单词接龙 - 力扣&#xff08;LeetCode&#xff09; 2. 675. 为高尔夫球比赛砍树 - 力扣(…...

EXCEL延迟退休公式

如图&#xff1a; A B为手工输入 C2EOMONTH(A2,B2*12) D2EOMONTH(C2,IF(C2>DATEVALUE("2025-1-1"),INT((DATEDIF(DATEVALUE("2025-1-1"),C2,"m")4)/4),0)) E2EOMONTH(A2,B2*12IF(EOMONTH(A2,B2*12)>DATEVALUE("2025-1-1"),INT(…...

开源对象存储新选择:在Docker上部署MinIO并实现远程管理

文章目录 前言1. Docker 部署MinIO2. 本地访问MinIO3. Linux安装Cpolar4. 配置MinIO公网地址5. 远程访问MinIO管理界面6. 固定MinIO公网地址 前言 MinIO是一个开源的对象存储服务器&#xff0c;可以在各种环境中运行&#xff0c;例如本地、Docker容器、Kubernetes集群等。它兼…...

Spring Cloud生态圈

目录 Spring Cloud生态圈 核心组件 其他组件 总结 Spring Cloud Alibaba生态圈 核心组件 其他特性 Spring Cloud生态圈 Spring Cloud生态圈是一个为微服务架构提供全方位支持的解决方案集合。它涵盖了多个关键组件和服务&#xff0c;旨在帮助开发者快速构建、部署和管理…...

AI视觉小车基础--4.舵机控制(云台控制)

一、实验准备 控制连接在扩展板上的舵机。如下图所示&#xff0c;按键KEY1为板载元器件&#xff0c;所以不需要外接其他设备。 二、运行代码 # Import the Raspbot library import time from Raspbot_Lib import Raspbot from ipywidgets import interact import ipywidgets a…...

【Rust中的项目管理】

Rust中的项目管理 前言Package&#xff0c;Crate&#xff0c;Module &use &#xff0c;Path通过代码示例解释 Crate&#xff0c;Module &#xff0c;use&#xff0c;Path创建一个package&#xff1a;代码组织化skin.rs 中的代码struct & enum 相对路径和绝对路径引用同…...

【原创】如何备份和还原Ubuntu系统,非常详细!!

前言 我在虚拟机装了一个xfce4的Ubuntu桌面版&#xff0c;外加输入法、IDEA等&#xff0c;我想将这个虚拟机里的系统直接搬到物理机中&#xff0c;那我可以省的再重新装一遍、配置xfce4桌面、修改一堆快捷键还有配置idea了&#xff0c;那直接说干就干。 本教程基于Ubuntu24.0…...

成都栩熙酷网络科技抖音小店是真的

近年来&#xff0c;随着短视频平台的崛起&#xff0c;抖音小店作为一种新兴的购物模式&#xff0c;迅速吸引了大量消费者和商家的关注。在这一潮流中&#xff0c;成都栩熙酷网络科技有限公司&#xff08;以下简称“栩熙酷”&#xff09;凭借其敏锐的市场洞察力和强大的技术实力…...

Python 爬虫数据清洗与存储:基础教程

Python 爬虫数据清洗与存储&#xff1a;基础教程 在爬虫数据获取完成后&#xff0c;数据往往是“原始”的&#xff0c;不适合直接使用。清洗和存储是将爬取到的原始数据转化为有用信息的关键步骤。本文将系统地介绍 Python 中进行数据清洗与存储的基本方法&#xff0c;帮助新手…...

ssm122基于Java的高校教学业绩信息管理系统+jsp(论文+源码)_kaic

毕 业 设 计&#xff08;论 文&#xff09; 题目&#xff1a;高校教学业绩信息管理系统设计与实现 摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本高校教学…...

Java 基础知识

一.泛型编程 1. 泛型的概念和作用是什么&#xff1f; 概念&#xff1a;泛型&#xff08;Generics&#xff09;是在 JDK 5.0 引入的新特性&#xff0c;允许在定义类、接口和方法时使用类型参数。类型参数在使用时被具体的类型替换。作用&#xff1a; 类型安全性&#xff1a;避…...

深入探索 React Hooks:原理、用法与性能优化全解

一、引言 在现代 React 开发领域,Hooks 已成为不可或缺的一部分,赋予函数组件强大功能,使其能胜任复杂任务。本文将全面剖析 React Hooks,助您深入理解并熟练运用。 二、React Hooks 是什么 (一)Hooks 出现的背景 早期 React 主要依赖类组件,其通过this.state管理状…...

python中父类和子类继承学习

python为啥要使用继承 1. **代码复用**&#xff1a;子类可以继承父类的方法和属性&#xff0c;避免了重复编写相同的代码&#xff0c;提高了代码的复用性。 2. **建立层次结构**&#xff1a;通过继承可以清晰地表示类之间的层次关系&#xff0c;使代码结构更有条理。 3. **扩展…...

Linux——GPIO输入输出裸机实验

学习了正点原子Linux环境下的GPIO的输入输出的裸机实验学习&#xff0c;现在进行一下小结&#xff1a; 启动文件start.S的编写 .global _start .global _bss_start _bss_start:.word __bss_start.global _bss_end _bss_end:.word __bss_end_start:/*设置处理器进入SVC模式*/m…...

华为鸿蒙HarmonyOS NEXT升级HiCar:打造未来出行新体验

随着科技的不断进步&#xff0c;智能出行已成为我们生活中不可或缺的一部分。华为凭借其在智能科技领域的深厚积累&#xff0c;推出了全新的鸿蒙HarmonyOS NEXT系统&#xff0c;旨在为用户打造一个“人车家”的无缝协同出行体验。这一系统的核心亮点之一&#xff0c;就是其内置…...

【项目组件】第三方库——websocketpp

目录 第三方协议&#xff1a;websocket websocket简介 websocket特点 websocket协议切换 websocket协议格式段 websocketpp库介绍 endpoint server connection websocketpp库搭建服务器流程 基本框架实现 业务处理回调函数的实现 http_callback open_callback …...

计算机23级数据结构上机实验(第3-4周)

A 二叉树删除子树 编写程序对给定二叉树执行若干次删除子树操作&#xff0c;输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于0的整数。每次删除操作是在上一次删除操作后剩下的二叉树上执行。 输入格式: 输入第1行为一组用空格间隔的整数&#xff0c;表…...

【大数据学习 | HBASE高级】region split机制和策略

1. region split机制 ​ HRegionServer拆分region的步骤是&#xff0c;先将该region下线&#xff0c;然后拆分&#xff0c;将其子region加入到hbase:meta表中&#xff0c;再将他们加入到原本的HRegionServer中&#xff0c;最后汇报Master。 split前&#xff1a;hbase:meta表有…...

flink实战 -- flink SQL 实现列转行

在 SQL 任务里面经常会遇到一列转多行的需求,下面就来总结一下在 Flink SQL 里面如何实现列转行的,先来看下面的一个具体案例. 需求 原始数据格式如下: namedatatest[{"content_type":"flink","url":"111"},{"content_type&quo…...

React中右击出现自定弹窗

前言 在react中点击右键,完成阻止浏览器的默认行为,完成自定义的悬浮框(Menu菜单). 版本 "react": "^18.2.0", "umijs/route-utils": "^4.0.1", "antd": "^5.18.1", "ant-design/pro-components": &q…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

CSS 工具对比:UnoCSS vs Tailwind CSS,谁是你的菜?

在现代前端开发中&#xff0c;Utility-First (功能优先) CSS 框架已经成为主流。其中&#xff0c;Tailwind CSS 无疑是市场的领导者和标杆。然而&#xff0c;一个名为 UnoCSS 的新星正以其惊人的性能和极致的灵活性迅速崛起。 这篇文章将深入探讨这两款工具的核心理念、技术差…...

用鸿蒙HarmonyOS5实现国际象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的国际象棋小游戏的完整实现代码&#xff0c;使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├── …...

[QMT量化交易小白入门]-六十二、ETF轮动中简单的评分算法如何获取历史年化收益32.7%

本专栏主要是介绍QMT的基础用法,常见函数,写策略的方法,也会分享一些量化交易的思路,大概会写100篇左右。 QMT的相关资料较少,在使用过程中不断的摸索,遇到了一些问题,记录下来和大家一起沟通,共同进步。 文章目录 相关阅读1. 策略概述2. 趋势评分模块3 代码解析4 木头…...

机器学习复习3--模型评估

误差与过拟合 我们将学习器对样本的实际预测结果与样本的真实值之间的差异称为&#xff1a;误差&#xff08;error&#xff09;。 误差定义&#xff1a; ①在训练集上的误差称为训练误差&#xff08;training error&#xff09;或经验误差&#xff08;empirical error&#x…...