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

算法每日一练 (9)

💢欢迎来到张胤尘的技术站
💥技术如江河,汇聚众志成。代码似星辰,照亮行征程。开源精神长,传承永不忘。携手共前行,未来更辉煌💥

文章目录

  • 算法每日一练 (9)
    • 最小路径和
      • 题目描述
      • 解题思路
      • 解题代码
        • `c/c++`
        • `golang`
        • `lua`

官方站点: 力扣 Leetcode

算法每日一练 (9)

最小路径和

题目地址:最小路径和

题目描述

给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明: 每次只能向下或者向右移动一步。

示例 1:

在这里插入图片描述

输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。

示例 2:

输入:grid = [[1,2,3],[4,5,6]]
输出:12

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200

解题思路

  • 首先根据题目要求判断边界条件,当 m == n == 1 时,不需要任何处理,直接返回即可。

  • 由题意可知,在矩阵中任何一个节点只有一种方式可到达:从左边或上边,那么假设 i 是矩阵的横坐标,j 是矩阵的纵坐标,则有如下规则:

    • i == 0 并且 j == 0 时,就是 (0,0) 点,到达当前位置的路径最小和满足如下公式:
      t m p [ i ] [ j ] = g r i d [ i ] [ j ] tmp[i][j] = grid[i][j] tmp[i][j]=grid[i][j]
    • i == 0 时,只能从左边到达,到达当前位置的路径最小和满足如下公式:
      t m p [ i ] [ j ] = g r i d [ i ] [ j ] + t m p [ i ] [ j − 1 ] tmp[i][j] = grid[i][j] + tmp[i][j-1] tmp[i][j]=grid[i][j]+tmp[i][j1]
    • j == 0 时, 只能从上面到达,到达当前位置的路径最小和满足如下公式:
      t m p [ i ] [ j ] = g r i d [ i ] [ j ] + t m p [ i − 1 ] [ j ] tmp[i][j] = grid[i][j] + tmp[i-1][j] tmp[i][j]=grid[i][j]+tmp[i1][j]
    • i != 0 并且 j != 0 时,到达当前位置的路径最小和满足如下公式:
      t m p [ i ] [ j ] = g r i d [ i ] [ j ] + m i n ( t m p [ i − 1 ] [ j ] , t m p [ i ] [ j − 1 ] ) tmp[i][j] = grid[i][j] + min(tmp[i-1][j], tmp[i][j-1]) tmp[i][j]=grid[i][j]+min(tmp[i1][j],tmp[i][j1])
  • 创建临时矩阵 tmp,根据以上的公式依次给矩阵中的每个元素赋值。

  • 返回 tmp[m-1][n-1] 的值,因为 tmp[m-1][n-1] 存储的是就是到达右下角的最小路径和。

golang 的解法采用了上述的解题思路;c/c++lua 的解法采用了一维数组作为临时容器,感兴趣的同学可以作为参考。

解题代码

c/c++
class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();if (m == 1 && n == 1)return grid[0][0];std::vector<int> tmp;tmp.resize(n);for (int j = 0; j < n; j++) {if (j == 0)tmp[j] = grid[0][j];elsetmp[j] = grid[0][j] + tmp[j - 1];}for (int i = 1; i < m; i++) {for (int j = 0; j < n; j++) {if (j == 0)tmp[j] += grid[i][j];elsetmp[j] = grid[i][j] + std::min(tmp[j - 1], tmp[j]);}}return tmp[n - 1];}
};
golang
func minPathSum(grid [][]int) int {m := len(grid)n := len(grid[0])if m == 1 && n == 1 {return grid[0][0]}tmp := make([][]int, m)for i := 0; i < m; i++ {tmp[i] = make([]int, n)for j := 0; j < n; j++ {if i == 0 && j == 0 {tmp[i][j] = grid[i][j]} else if i == 0 {tmp[i][j] = grid[i][j] + tmp[i][j-1]} else if j == 0 {tmp[i][j] = grid[i][j] + tmp[i-1][j]} else {tmp[i][j] = grid[i][j] + min(tmp[i-1][j], tmp[i][j-1])}}}return tmp[m-1][n-1]
}
lua
local function minPathSum(grid)local m, n = #grid, #grid[1]if m == 1 and n == 1 thenreturn grid[1][1]endlocal tmp = {}for j = 1, n doif j == 1 thentmp[j] = grid[1][j]elsetmp[j] = grid[1][j] + tmp[j - 1]endendfor i = 2, m dofor j = 1, n doif j == 1 thentmp[j] = tmp[j] + grid[i][j]elsetmp[j] = grid[i][j] + math.min(tmp[j], tmp[j - 1])endendendreturn tmp[n]
end

🌺🌺🌺撒花!

如果本文对你有帮助,就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容,请随时向我提问。

在这里插入图片描述

相关文章:

算法每日一练 (9)

&#x1f4a2;欢迎来到张胤尘的技术站 &#x1f4a5;技术如江河&#xff0c;汇聚众志成。代码似星辰&#xff0c;照亮行征程。开源精神长&#xff0c;传承永不忘。携手共前行&#xff0c;未来更辉煌&#x1f4a5; 文章目录 算法每日一练 (9)最小路径和题目描述解题思路解题代码…...

软考高级信息系统项目管理师笔记-第10章项目进度管理

第10章项目进度管理 10.1 管理基础 10.1.1 项目进度计划的定义和总要求 1、项目进度计划是 一种用于沟通和管理干系人期望的工具,为绩效报告提供依据。 2、项目管理团队编制进度计划的一般步骤为: 首先选择进度计划方法,例如关键路径法; 然后将项目特定数据,如活动、计…...

专门为高速连续扫描设计的TDI工业相机

TDI&#xff08;Time Delay Integration&#xff0c;时间延迟积分&#xff09;工业相机是一种基于特殊CCD&#xff08;电荷耦合器件&#xff09;技术的成像设备&#xff0c;主要用于高速、高灵敏度、高分辨率的图像采集场景。其核心原理是通过多级积分和同步电荷转移技术&#…...

【Vue3】实现一个超过高度后可控制显示隐藏的组件

组件效果图 未达到最大高度 达到设置的最大高度 进行展开 实现代码 组件代码 备注&#xff1a;通过tailwindcss设置的样式&#xff0c;通过element-plus/icons-vue设置的图标&#xff0c;可根据情况进行替换 <template><!-- 限制高度组件 --><div ref"…...

Spring提供的SPEL表达式

SPEL 1. 概述 SpEL是Spring框架中用于表达式语言的一种方式。它类似于其他编程语言中的表达式语言&#xff0c;用于在运行时计算值或执行特定任务。 SpEL提供了一种简单且强大的方式来访问和操作对象的属性、调用对象的方法&#xff0c;以及实现运算、条件判断等操作。它可以…...

JAVA编程【jvm垃圾回收的差异】

jvm垃圾回收的差异 JVM&#xff08;Java Virtual Machine&#xff09;的垃圾回收&#xff08;GC&#xff09;机制是自动管理内存的一种方式&#xff0c;能够帮助开发者释放不再使用的内存&#xff0c;避免内存泄漏和溢出等问题。不同的垃圾回收器&#xff08;GC&#xff09;有…...

Elasticsearch:“Your trial license is expired”

目录标题 问题原因解决方案 问题 原因 ES的X-pack许可证是提供免费一个月的试用&#xff0c;到期之后就会报这个错误。 解决方案 查看license GET _license 开启试用license POST _xpack/license/start_trial?acknowledgetrue修改为基础license POST _xpack/license/start_…...

fmql之Linux WDT

正点原子第52章。 基础知识 正点原子教程 fmql-dts 代码 APP代码&#xff08;不需要编写驱动代码&#xff09; static int dw_wdt_drv_probe(struct platform_device *pdev) {struct device *dev &pdev->dev;struct watchdog_device *wdd;struct dw_wdt *dw_wdt; …...

【算法学习之路】7.链表算法

链表算法 前言一.原地逆置思路一&#xff1a;头插法思路二&#xff1a;双指针法思路3&#xff1a;递归 例题&#xff1a;1.头插法2.双指针法3&#xff0c;递归 二.双指针快慢指针&#xff1a;一个指针快一个指针慢例题1例题2 前言 我会将一些常用的算法以及对应的题单给写完&am…...

IDEA Commit 模态提交界面关闭VS开启对比

IDEA Commit 模态提交界面关闭VS开启对比 前言开启模态提交界面优点快捷且灵活的选择需要commit文件显示文件修改内容多(主观) 缺点在模态提交界面选择文件&#xff0c;临时关闭模态框重新打开会重置选择的commit文件 关闭模态提交界面优点允许在commit选择文件时查看其它没有修…...

【AI赋能】AI 工具生成视频教材:从创意到成品的全流程指南

AI 工具生成视频教材&#xff1a;从创意到成品的全流程指南 目标 通过本教材&#xff0c;您将学会如何利用 AI 工具&#xff08;Grok、Sora、Speechify 和 CapCut&#xff09;生成一个完整的视频&#xff0c;包括脚本生成、视频片段制作、字幕添加、音频生成以及最终剪辑合成…...

qt 操作多个sqlite文件

qt 操作多个sqlite文件 Chapter1 qt 操作多个sqlite文件1. 引入必要的头文件2. 创建并连接多个SQLite数据库3. 代码说明4. 注意事项 Chapter2 qt 多线程操作sqlite多文件1. 引入必要的头文件2. 创建数据库操作的工作线程类3. 在主线程中创建并启动多个工作线程4. 代码说明5. 运…...

WSL with NVIDIA Container Toolkit

一、wsl 下安装 docker 会提示安装 docekr 桌面版&#xff0c;所以直接安装 docker 桌面版本即可 二、安装 NVIDIA Container Toolkit NVIDIA Container Toolkit仓库 https://github.com/NVIDIA/nvidia-container-toolkit​github.com/NVIDIA/nvidia-container-toolkit 安装…...

Vue 系列之:组件通讯

子组件调用父组件方法 1、直接在子组件中通过 this.$parent.event 来调用父组件的方法 父组件&#xff1a; <template><p><child></child></p> </template> <script>import child from ./child;export default {components: {chi…...

【Linux实践系列】:用c语言实现一个shell外壳程序

&#x1f525;本文专栏&#xff1a;Linux Linux实践项目 &#x1f338;博主主页&#xff1a;努力努力再努力wz 那么今天我们就要进入Linux的实践环节&#xff0c;那么我们之前学习了进程控制相关的几个知识点&#xff0c;比如进程的终止以及进程的等待和进程的替换&#xff0c;…...

STL map 的 lower_bound(x)、upper_bound(x) 等常用函数

【STL map 简介】 ● STL map 是一种关联容器&#xff0c;存储键值对&#xff0c;每个键&#xff08;key value&#xff09;是唯一的&#xff0c;而值&#xff08;mapped value&#xff09;可以重复。构建 STL map 时&#xff0c;无论元素插入顺序如何&#xff0c;STL map 中的…...

【A2DP】SBC 编解码器互操作性要求详解

目录 一、SBC编解码器互操作性概述 二、编解码器特定信息元素(Codec Specific Information Elements) 2.1 采样频率(Sampling Frequency) 2.2 声道模式(Channel Mode) 2.3 块长度(Block Length) 2.4 子带数量(Subbands) 2.5 分配方法(Allocation Method) 2…...

Computational Linguistics期刊全解析:领域顶刊的投稿指南与学术价值

在人工智能与语言学交叉融合的浪潮中&#xff0c;《Computational Linguistics》&#xff08;CL&#xff09;作为该领域的标杆期刊&#xff0c;始终是研究者发表前沿成果的首选平台。本文将从期刊影响力、投稿策略、收稿方向等角度&#xff0c;为学者提供一份全面的指南。 一、…...

【量化科普】Sharpe Ratio,夏普比率

【量化科普】Sharpe Ratio&#xff0c;夏普比率 &#x1f680;量化软件开通 &#x1f680;量化实战教程 在量化投资领域&#xff0c;夏普比率&#xff08;Sharpe Ratio&#xff09;是一个非常重要的风险调整后收益指标。它由诺贝尔经济学奖得主威廉F夏普&#xff08;William…...

运行OpenManus项目(使用Conda)

部署本项目需要具备一定的基础&#xff1a;Linux基础、需要安装好Anaconda/Miniforge&#xff08;Python可以不装好&#xff0c;直接新建虚拟环境的时候装好即可&#xff09;&#xff0c;如果不装Anaconda或者Miniforge&#xff0c;只装过Python&#xff0c;需要确保Python是3.…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...