【LeetCode】每日一题 2023_12_7 出租车的最大盈利(动态规划)

文章目录

  • 刷题前唠嗑
  • 题目:出租车的最大盈利
    • 题目描述
    • 代码与解题思路

刷题前唠嗑


LeetCode?启动!!!

题目:出租车的最大盈利

题目链接:2008. 出租车的最大盈利

题目描述

代码与解题思路

func maxTaxiEarnings(n int, rides [][]int) int64 {
    type pair struct{ s, p int } // 一个存上车点, 一个存盈利
    group := make([][]pair, n+1) 
    for _, r := range rides {
        start, end, tip := r[0], r[1], r[2]
        group[end] = append(group[end], pair{start, end-start+tip}) // 根据 end 存 pair
    }
    dp := make([]int64, n+1)
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] // 填 dp 数组, 无论有没有更改, 都先把上一个最大盈利继承一下
        for _, v := range group[i] {
            dp[i] = max(dp[i], dp[v.s]+int64(v.p)) // 遍历所有 end 为 i 的情况的最大盈利
        }
    }
    return dp[n]
}

核心思路在于,记录样例中相同 end 的乘客的情况,然后遍历求出最大盈利的情况更新 dp 数组。

还有一种解法是,先 sort 一下,然后根据相同 start 的乘客的情况,然后用也是老办法用 dp 求解,通过 二分/优先级队列(堆) 来优化 dp,具体我就不 CV 了,摆了

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/229393.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

计算机网络:网络层上(数据平面)

文章目录 前言一、概述1.网络服务模型2.连接建立 二、路由器组成1.路由器结构概况输入端口的功能 2.IP&#xff08;Internet Protocol&#xff09;IPV4IPV6 3.通用转发和SDN 总结 前言 网络层分两部分讲解&#xff0c;本篇文章讲解数据平面的内容&#xff1a;路由器组成、IP协…

麻雀1号开发板开箱

麻雀1号是上海睿赛德电子科技有限公司全新推出的一款高性价比音频Wi-Fi开发板&#xff0c;内置RT-Thread&#xff0c;主打 Wi-Fi、音频和摄像头拍照功能&#xff0c;配合丰富的组件及例程&#xff0c;可降低多媒体应用的开发门槛。 开发板介绍 正面&#xff1a; 背面&#x…

目标检测mAP计算以及coco评价标准

这篇是我对哔哩哔哩up主 霹雳吧啦Wz 的视频的文字版学习笔记 感谢他对知识的分享 讲一下目标检测中的一些常见的指标 在我们使用目标检测网络训练时 最后在验证集上会得到一个coco的评价列表 就像我们图中给的这一系列参数列表一样 我们再进一步引入两个概念 第一个叫做precisi…

DBeaver 如何在没有外网的情况下连接数据库(下载驱动)

1.选择自己要连接的数据库 2.编辑驱动 3.选择你自己通过maven或者别的渠道下载的对应数据库的jar

Python并发-线程和进程

一、线程和进程对应的问题 **1.进程&#xff1a;**CPU密集型也叫计算密集型&#xff0c;指的是系统的硬盘、内存性能相对CPU要好很多&#xff0c;此时&#xff0c;系统运作大部分的状况是CPU Loading 100%&#xff0c;CPU要读/写I/O(硬盘/内存)&#xff0c;I/O在很短的时间就可…

论文阅读《Learning Adaptive Dense Event Stereo from the Image Domain》

论文地址&#xff1a;https://openaccess.thecvf.com/content/CVPR2023/html/Cho_Learning_Adaptive_Dense_Event_Stereo_From_the_Image_Domain_CVPR_2023_paper.html 概述 事件相机在低光照条件下可以稳定工作&#xff0c;然而&#xff0c;基于事件相机的立体方法在域迁移时性…

人工麝香市场分析:中国市场年需求量超过15吨

人工麝香作为濒危动物药材麝香的替代品&#xff0c;等同天然麝香配方使用。 是国家重大科研成果和保密品种&#xff0c;用人工麝香生产中成药品种近400种&#xff0c;涵盖中成药常用剂型。 是珍稀动物药材代用品研究的重大突破&#xff0c;为其它珍稀动物药材的应用开辟了一条重…

案例060:基于微信小程序考试系统

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;SSM JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.5.4 小程序框架&#xff1a;uniapp 小程序开发软件&#xff1a;HBuilder X 小程序…

深度学习还可以从如下方面进行创新!!

文章目录 一、我认为可以从如下5个方向进行创新总结 一、我认为可以从如下5个方向进行创新 新的模型结构&#xff1a;尽管现在的深度学习模型已经非常强大&#xff0c;但是还有很多未被探索的模型结构。探索新的模型结构可以带来更好的性能和更低的计算成本。 新的优化算法&a…

基于ssm家庭理财系统源码和论文

基于ssm家庭理财系统源码和论文743 idea 数据库mysql5.7 数据库链接工具&#xff1a;navcat,小海豚等 环境&#xff1a; jdk8 tomcat8.5 开发技术 ssm 摘要 随着Internet的发展&#xff0c;人们的日常生活已经离不开网络。未来人们的生活与工作将变得越来越数字化&#xff…

力扣面试题 08.12. 八皇后(java回溯解法)

Problem: 面试题 08.12. 八皇后 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路 八皇后问题的性质可以利用回溯来解决&#xff0c;将大问题具体分解成如下待解决问题&#xff1a; 1.以棋盘的每一行为回溯的决策阶段&#xff0c;判断当前棋盘位置能否放置棋子 2.如何判…

表单小程序作用体现在哪

表单的用途非常广泛&#xff0c;它是线上收集信息或用户预约/需求服务的重要方式&#xff0c;对商家来说如今线上平台非常多&#xff0c;生意开展的形式也越来越多&#xff0c;比如常见的预约、报名、收款、产品支付等都可以通过表单实现。 接下来啊让我们看看通过【雨科】平台…

.NET使用分布式网络爬虫框架DotnetSpider快速开发爬虫功能

前言 前段时间有同学在微信群里提问&#xff0c;要使用.NET开发一个简单的爬虫功能但是没有做过无从下手。今天给大家推荐一个轻量、灵活、高性能、跨平台的分布式网络爬虫框架&#xff08;可以帮助 .NET 工程师快速的完成爬虫的开发&#xff09;&#xff1a;DotnetSpider。 注…

发布“最强”AI大模型,股价大涨,吊打GPT4的谷歌股票值得投资吗?

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 谷歌在AI领域的最新进展&#xff0c;引发投资者关注 在谷歌-C(GOOGL)谷歌-A&#xff08;GOOG&#xff09;昨日发布了最新的AI大模型Gemini后&#xff0c;其股价就出现了大幅上涨&#xff0c;更是引发了投资者的密切关注&a…

基于Java的招聘系统的设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是 目录…

扩展学习|商业智能和分析:从大数据到大影响

文献来源&#xff1a;Chen H, Chiang R H L, Storey V C. Business intelligence and analytics: From big data to big impact[J]. MIS quarterly, 2012: 1165-1188. 下载链接&#xff1a;https://pan.baidu.com/s/1JoHcTbwdc1TPGnwXsL4kIA 提取码&#xff1a;a8uy 在不同的组…

12月8日作业

题目&#xff1a; 使用手动连接&#xff0c;将登录框中的取消按钮使用qt4版本的连接到自定义的槽函数中&#xff0c;在自定义的槽函数中调用关闭函数 将登录按钮使用qt5版本的连接到自定义的槽函数中&#xff0c;在槽函数中判断ui界面上输入的账号是否为"admin"&am…

TCP流套接字编程

文章目录 TCP流套接字编程ServerSocket APISocket API示例&#xff1a;回显服务器服务器端客户端 利用线程池实现并发编程 TCP流套接字编程 TCP和UDP差距是很大的&#xff0c;在数据传输方面&#xff0c;UDP是面向数据报的&#xff0c;而TCP是面向字节流的的&#xff0c;下面列…

Windows磁盘管理中硬盘无法初始化怎么办?

硬盘未出现在“此电脑”选项下的情况并不少见&#xff0c;当您打开磁盘管理&#xff0c;它要么显示为磁盘未知&#xff0c;要么显示为未分配的空间&#xff0c;或者只是不显示磁盘容量。为了访问您的硬盘并充分利用它&#xff0c;您需要对其进行初始化。不幸的是&#xff0c;您…

基于SSM的社区管理系统

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是 目录…