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

leetcode1219. 黄金矿工(java)

黄金矿工

  • leetcode1219. 黄金矿工
    • 题目描述
    • 回溯算法
    • 代码
  • 回溯算法

leetcode1219. 黄金矿工

难度: 中等
eetcode 1219 黄金矿工

题目描述

你要开发一座金矿,地质勘测学家已经探明了这座金矿中的资源分布,并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量;如果该单元格是空的,那么就是 0。
为了使收益最大化,矿工需要按以下规则来开采黄金:
每当矿工进入一个单元,就会收集该单元格中的所有黄金。
矿工每次可以从当前位置向上下左右四个方向走。
每个单元格只能被开采(进入)一次。
不得开采(进入)黄金数目为 0 的单元格。
矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。

示例 1:
输入:grid = [[0,6,0],[5,8,7],[0,9,0]]
输出:24
解释:
[[0,6,0],
[5,8,7],
[0,9,0]]
一种收集最多黄金的路线是:9 -> 8 -> 7。

示例 2:
输入:grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
输出:28
解释:
[[1,0,7],
[2,0,6],
[3,4,5],
[0,3,0],
[9,0,20]]
一种收集最多黄金的路线是:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。

提示:
1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
最多 25 个单元格中有黄金。

回溯算法

首先了解什么是回溯算法:
解决一个回溯问题,实际上就是一个决策树的遍历过程,站在回溯树的一个节点上,你只需要思考 3 个问题:

  1. 路径:也就是已经做出的选择。
  2. 选择列表:也就是你当前可以做的选择。
  3. 结束条件:也就是到达决策树底层,无法再做选择的条件。

代码框架:

result = []
def backtrack(路径, 选择列表):if 满足结束条件:result.add(路径)returnfor 选择 in 选择列表:做选择backtrack(路径, 选择列表)撤销选择

关于本体的解题思路:
我们首先在 m×nm \times nm×n 个网格内枚举起点。只要格子内的数大于 000,它就可以作为起点进行开采。

记枚举的起点为 (i,j),我们就可以从 (i,j)开始进行递归 + 回溯,枚举所有可行的开采路径。我们用递归函数 dfs(x,y,gold)\进行枚举,其中 (x,y)(x, y)(x,y) 表示当前所在的位置,gold\textit{gold}gold 表示在开采位置 (x,y)(x, y)(x,y) 之前,已经拥有的黄金数量。根据题目的要求,我们需要进行如下的步骤:

我们需要将 gold 更新为 gold+grid[x][y],表示对位置(x,y) 进行开采。由于我们的目标是最大化收益,因此我们还要维护一个最大的收益值 ans,并在这一步使用 gold\textit{gold}gold 更新ans;

我们需要枚举矿工下一步的方向。由于矿工每次可以从当前位置向上下左右四个方向走,因此我们需要依次枚举每一个方向。如果往某一个方向不会走出网格,并且走到的位置的值不为 0,我们就可以进行递归搜索;
在搜索完所有方向后,我们进行回溯。

代码

class Solution {int[][]g;int m,n;//标记已经走过的路线boolean[][]vis;//标记四个方向,矿工每到一个地方,都有四个方向可以选择.int[][]dirs = new int[][]{{1,0},{-1,0},{0,-1},{0,1}};public int getMaximumGold(int[][]gird){g = gird;m = g.length;n = g[0].length;vis = new boolean[m][n];int ans = 0;for (int i = 0; i < m;i++){for (int j = 0; j < n;j++){if (g[i][j] != 0){vis[i][j] = true;ans = Math.max(ans,dfs(i,j));vis[i][j] = false;}}}return ans;}/*** 开始回溯计算,每个点向四个方向开始移动的最大值* @param i* @param j* @return*/public int dfs(int i,int j){int ans = g[i][j];//枚举四个方向for (int[]d : dirs){int ni = i + d[0];int nj = j + d[1];if (ni < 0 || nj < 0 || ni >= m || nj >= n){continue;}if (g[ni][nj] == 0){continue;}//已经走过的不在重复计算if (vis[ni][nj]){continue;}//标记已选vis[ni][nj] = true;ans = Math.max(ans,g[i][j] + dfs(ni,nj));vis[ni][nj] = false;}return ans;}
}

回溯算法

leetcode698. 划分为k个相等的子集

leetcode93. 复原 IP 地址

leetcode306. 累加数

相关文章:

leetcode1219. 黄金矿工(java)

黄金矿工 leetcode1219. 黄金矿工题目描述回溯算法代码 回溯算法 leetcode1219. 黄金矿工 难度: 中等 eetcode 1219 黄金矿工 题目描述 你要开发一座金矿&#xff0c;地质勘测学家已经探明了这座金矿中的资源分布&#xff0c;并用大小为 m * n 的网格 grid 进行了标注。每个单元…...

Svelte框架入门

关键词 前端框架、编译器、响应式、模板 介绍 Svelte /svelt/ adj. 苗条的&#xff1b;线条清晰的&#xff1b;和蔼的 Svelte是一个前端组件框架&#xff0c;就像它的英文名字一样&#xff0c;Svelte的目标是打造一个更高性能的响应性前端框架。 Svelte类似于React和Vue框架&am…...

在linux中进行arm交叉编译体验tiny6410裸机程序开发流程

在某鱼上找了一个友善之臂的Tiny6410开发板用来体验一下嵌入式开发。这次先体验一下裸机程序的开发流程&#xff0c;由于这个开发板比较老旧了&#xff0c;官方文档有很多过期的内容&#xff0c;所以记录一下整个过程。 1. 交叉编译器安装 按照光盘A中的文档《04- Tiny6410 L…...

SpringBoot实战(二十三)集成 SkyWalking

目录 一、简介二、拉取镜像并部署1.拉取镜像2.运行skywalking-oap容器3.运行skywalking-ui容器4.访问页面 三、下载解压 agent1.下载2.解压 四、创建 skywalking-demo 项目1.Maven依赖2.application.yml3.DemoController.java 五、构建启动脚本1.startup.bat2.执行启动脚本3.发…...

深度学习实践——卷积神经网络实践:裂缝识别

深度学习实践——卷积神经网络实践&#xff1a;裂缝识别 系列实验 深度学习实践——卷积神经网络实践&#xff1a;裂缝识别 深度学习实践——循环神经网络实践 深度学习实践——模型部署优化实践 深度学习实践——模型推理优化练习 深度学习实践——卷积神经网络实践&#xff…...

linux | vscode | makefile | c++编译和调试

简单介绍环境&#xff1a; vscode 、centos、 gcc、g、makefile 简单来说就是&#xff0c;写好项目然后再自己写makefile脚本实现编译。所以看这篇博客的用户需要了解gcc编译的一些常用命令以及makefile语法。在网上看了很多教程&#xff0c;以及官网也看了很多次&#xff0c;最…...

Spring | Bean 作用域和生命周期

一、通过一个案例来看 Bean 作用域的问题 Spring 是用来读取和存储 Bean&#xff0c;因此在 Spring 中 Bean 是最核心的操作资源&#xff0c;所以接下来我们深入学习⼀下 Bean 对象 假设现在有⼀个公共的 Bean&#xff0c;提供给 A 用户和 B 用户使用&#xff0c;然而在使用的…...

培训(c++题解)

题目描述 某培训机构的学员有如下信息&#xff1a; 姓名&#xff08;字符串&#xff09;年龄&#xff08;周岁&#xff0c;整数&#xff09;去年 NOIP 成绩&#xff08;整数&#xff0c;且保证是 5 的倍数&#xff09; 经过为期一年的培训&#xff0c;所有同学的成绩都有所提…...

ansible-playbook编写 lnmp 剧本

ansible-playbook编写 lnmp 剧本 vim /opt/lnmp/lnmp.yaml执行剧本 ansible-playbook lnmp.yaml...

需求太多处理不过来?MoSCoW模型帮你

一、MoSCoW模型是什么 MoSCoW模型 是在项目管理、软件开发中使用的一种排序优先级的方法&#xff0c;以便开发人员、产品经理、客户对每个需求交付的重要性达成共识。 MoSCoW是一个首字母缩略词&#xff0c;代表&#xff1a; M&#xff08;Must have&#xff09;&#xff1a…...

Vue 3:玩一下web前端技术(六)

前言 本章内容为VUE请求后端技术与相关技术讨论。 上一篇文章地址&#xff1a; Vue 3&#xff1a;玩一下web前端技术&#xff08;五&#xff09;_Lion King的博客-CSDN博客 下一篇文章地址&#xff1a; Vue 3&#xff1a;玩一下web前端技术&#xff08;七&#xff09;_Lio…...

【点云处理教程】00计算机视觉的Open3D简介

一、说明 Open3D 是一个开源库&#xff0c;使开发人员能够处理 3D 数据。它提供了一组用于 3D 数据处理、可视化和机器学习任务的工具。该库支持各种数据格式&#xff0c;例如 .ply、.obj、.stl 和 .xyz&#xff0c;并允许用户创建自定义数据结构并在程序中访问它们。 Open3D 广…...

Windows10系统还原操作

哈喽&#xff0c;大家好&#xff0c;我是雷工&#xff01; 复制了下虚拟机的Win10系统&#xff0c;但其中有一些软件&#xff0c;想实现类似手机的格式化出厂操作&#xff0c;下面记录Windows10系统的还原操作。 一、系统环境&#xff1a; 虚拟机内的Windows10&#xff0c;64…...

Django学习笔记-模板(Template)基础

使用模块可以很方便的执行一些数据操作&#xff0c;然后根据传入的数据直接在模板html文件中进行处理。 1.Django中的模板配置 Django的模板引擎在sttings.py文件中&#xff1a; TEMPLATES [{# 模板引擎&#xff0c;默认为django模板BACKEND: django.template.backends.dja…...

使用 NVM(Node Version Manager)管理 Node.js 版本

使用 NVM&#xff08;Node Version Manager&#xff09;管理 Node.js 版本 步骤一&#xff1a;安装 NVM NVM 是一个用于安装和管理不同版本的 Node.js 的工具。首先&#xff0c;你需要确保你的系统上已经安装了 NVM。可以通过以下命令检查 NVM 是否已经安装&#xff1a; nvm …...

(文章复现)梯级水光互补系统最大化可消纳电量期望短期优化调度模型matlab代码

参考文献&#xff1a; [1]罗彬,陈永灿,刘昭伟等.梯级水光互补系统最大化可消纳电量期望短期优化调度模型[J].电力系统自动化,2023,47(10):66-75. 1.基本原理 1.1 目标函数 考虑光伏出力的不确定性&#xff0c;以梯级水光互补系统的可消纳电量期望最大为目标&#xff0c;函数…...

tinkerCAD案例:24. Ruler - Measuring Lengths 标尺 -量勺

tinkerCAD案例&#xff1a;24. Ruler - Measuring Lengths 标尺 - 测量长度 Project Overview: 项目概况&#xff1a; A machine shop, where any idea can become a reality, can cost millions and million of dollars. Still, the most important tool in the shop is the…...

linux系统编程重点复习--线程同步

目录 复习目标&#xff1a; 1 互斥锁 1.1互斥锁的使用步骤 1.2 练习 1.3 死锁 2 读写锁 3 条件变量 4 信号量 复习目标&#xff1a; 熟练掌握互斥量的使用说出什么叫死锁以及解决方案熟练掌握读写锁的使用熟练掌握条件变量的使用理解条件变量实现的生产消费者模型理解…...

【Docker 学习笔记】Windows Docker Desktop 安装

文章目录 一、前言二、Windows Docker 安装1. 基于Hyper-V后端和Windows容器的安装2. 基于WSL2后端的安装&#xff08;推荐&#xff09;3. 安装Docker Desktop on Windows4. 启动并验证Docker Desktop 一、前言 Docker并非是一个通用的容器工具&#xff0c;它依赖于已存在并运…...

getInputStream has already been called for this request 问题记录

问题背景 HttpServletRequest.getReader() HttpServletRequest.getInputStream() 不能在过滤器中读取一次二进制流&#xff08;字符流&#xff09;&#xff0c;又在另外一个Servlet中读取一次&#xff0c;即一个InputSteam(BufferedReader)对象在被读取完成后&#xff0c;将无…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...