当前位置: 首页 > 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.…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...

spring Security对RBAC及其ABAC的支持使用

RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型&#xff0c;它将权限分配给角色&#xff0c;再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...

Android写一个捕获全局异常的工具类

项目开发和实际运行过程中难免会遇到异常发生&#xff0c;系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler&#xff0c;它是Thread的子类&#xff08;就是package java.lang;里线程的Thread&#xff09;。本文将利用它将设备信息、报错信息以及错误的发生时间都…...