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

训练营:贪心篇

贪心就是:局部最优

1、
455. 分发饼干

 按照饼干分,从大到小,最大的给胃口最大能满足的

def findContentChildren455(g, s):g = sorted(g,reverse=True)s = sorted(s,reverse=True)j=0c = 0i=0while(i<len(s) and j<len(g)):if s[i]>=g[j]:c = c+1j = j + 1i=i+1else:j = j+1return c

2、
860. 柠檬水找零

这就比较简单了,就是if列举

def lemonadeChange860(bills):res={"5":0,"10":0,"20":0}for i in range(len(bills)):if bills[i]==5:res["5"]=res["5"]+1elif bills[i]==10:if res["5"]>0:res["10"] = res["10"]+1res["5"] = res["5"]-1else:return Falseelse:if res["10"]>0 and res["5"]>0:res["10"] = res["10"]-1res["5"] = res["5"]-1elif res["5"]>2:res["5"] = res["5"]-3else:return Falsereturn True

3、
406. 根据身高重建队列

关键是排序,身高从大到小排,以及第二个数从小到大排,这样能把等于的也算上,然后,第二个数其实就是他在从大到小排的时候,排在第几的位置

def reconstructQueue40602(people):if len(people)<2:return people#people.sort(key=lambda x: (x[0], ~x[1]),reverse=True)people.sort(key=lambda x: (-x[0], x[1]))print(people)res = []for i in range(0,len(people)):tmp = people[i]res.insert(tmp[1],tmp)return res

4、
452. 用最少数量的箭引爆气球

这道题的关键就是更新最小区间,左边界从小到大排序之后,主要就是右边界

我会再申请一个数组记录当前区间,或者记录右区间

  def findMinArrowShots(self, points: List[List[int]]) -> int:points = sorted(points)# print(points)c=1res = points[0][1]for i in range(1,len(points)):tmp = points[i]# if res[1]>= tmp[0]:#     res[0] = tmp[0]#     res[1] = min(res[1],tmp[1])if res >= tmp[0]:res = min(res, tmp[1])else:c=c+1res = tmp[1]return c

5、
435. 无重叠区间

 和上面的题类型,从小到大排序,重叠的话去掉右边界大的,如果直接pop会超时,不需要真的去掉,s不跳到那个数上就行,不重叠的话s=i

def eraseOverlapIntervals43502(intervals):intervals = sorted(intervals)print(intervals)i=1c=0s = 0while i<len(intervals):if intervals[s][1]>intervals[i][0]:if intervals[s][1]>intervals[i][1]:s = ic = c+1else:s = ii=i+1return c

6、
56. 合并区间

右边界的对比,总习惯去新申请一下内存记录当前值,代码随想录里面都是在原数组里面直接改,速度虽然差不多,但是内存会小很多,对比一下

def merge56(intervals):intervals = sorted(intervals)tmp = intervals[0][1]s = intervals[0][0]res=[]for i in range(len(intervals)):if tmp>=intervals[i][0]:tmp = max(tmp,intervals[i][1])else:res.append([s,tmp])s = intervals[i][0]tmp = intervals[i][1]res.append([s, tmp])return res
def merge5602(intervals):intervals = sorted(intervals)res=[]res.append(intervals[0])for i in range(1,len(intervals)):if res[-1][1]>=intervals[i][0]:res[-1][1] = max(res[-1][1],intervals[i][1])else:res.append(intervals[i])#res.append([s, tmp])return res

7、
738. 单调递增的数字

关键是从后往前找,小了就减1,然后后面的都为9,还有int转str,然后切片

def monotoneIncreasingDigits73802(n):n = str(n)for i in range(len(n)-1,0,-1):if n[i-1]>n[i]:#n[i] = n[i]-1a = n[:i-1]b = str(int(n[i-1])-1)c = ("9"*(len(n)-i))n=n[:i-1]+str(int(n[i-1])-1)+("9"*(len(n)-i))return int(n)

8、
714. 买卖股票的最佳时机含手续费

 这题还挺巧妙的,关键是买入之后,新的值为prices[i]-tee,因为有可能存在比它更大的,那这次就不算买入,只收一次手续费

后面只有比他-手续费还小,这次才保留卖出,记录新的买入值

def maxProfit714( prices, fee):sum = 0t = prices[0]for i in range(1,len(prices)):if prices[i]<t:t = prices[i]elif prices[i]-t-fee>0:sum = sum+prices[i]-t-feet = prices[i]-feereturn sum

总结:

贪心就是局部最优,关键还是思路

相关文章:

训练营:贪心篇

贪心就是&#xff1a;局部最优 1、455. 分发饼干 按照饼干分&#xff0c;从大到小&#xff0c;最大的给胃口最大能满足的 def findContentChildren455(g, s):g sorted(g,reverseTrue)s sorted(s,reverseTrue)j0c 0i0while(i<len(s) and j<len(g)):if s[i]>g[j]:c…...

四、Dubbo扩展点加载机制

四、Dubbo扩展点加载机制 4.1 加载机制概述 Dubbo良好的扩展性与框架中针对不同场景使用合适设计模式、加载机制密不可分 Dubbo几乎所有功能组件都是基于扩展机制&#xff08;SPI&#xff09;实现的 Dubbo SPI 没有直接使用 Java SPI&#xff0c;在它思想上进行改进&#xff…...

[保研/考研机试] KY103 2的幂次方 上海交通大学复试上机题 C++实现

题目链接&#xff1a; KY103 2的幂次方 https://www.nowcoder.com/share/jump/437195121691999575955 描述 Every positive number can be presented by the exponential form.For example, 137 2^7 2^3 2^0。 Lets present a^b by the form a(b).Then 137 is present…...

时序预测 | MATLAB实现基于BP神经网络的时间序列预测-递归预测未来(多指标评价)

时序预测 | MATLAB实现基于BP神经网络的时间序列预测-递归预测未来(多指标评价) 目录 时序预测 | MATLAB实现基于BP神经网络的时间序列预测-递归预测未来(多指标评价)预测结果基本介绍程序设计参考资料 预测结果 基本介绍 Matlab实现BP神经网络时间序列预测未来&#xff08;完整…...

组合模式(C++)

定义 将对象组合成树形结构以表示部分-整体’的层次结构。Composite使得用户对单个对象和组合对象的使用具有一致性(稳定)。 应用场景 在软件在某些情况下&#xff0c;客户代码过多地依赖于对象容器复杂的内部实现结构&#xff0c;对象容器内部实现结构(而非抽象接口)的变化…...

git上传问题记录

unable to access ‘https://github.com/songjiahao-wq/untitled.git/’: Failed to connect to github.com port 443 after 21086 ms: Couldn’t connect to serve 解决办法&#xff1a;修改 Git 的网络设置 打开git Bash运行&#xff0c;clash代理一般是下面的端口 # 注意…...

通过动态IP解决网络数据采集问题

动态地址的作用 说到Python网络爬虫&#xff0c;很多人都会遇到困难。最常见的就是爬取过程中IP地址被屏蔽。虽然大部分都是几个小时内自动解封的&#xff0c;但这对于分秒必争的python网络爬虫来说&#xff0c;是一个关键性的打击&#xff01;当一个爬虫被阻塞时&#xff0c;…...

可重入锁,不可重入锁,死锁的多种情况,以及产生的原因,如何解决,synchronized采用的锁策略(渣女圣经)自适应的底层,锁清除,锁粗化,CAS的部分应用

一、&#x1f49b; 锁策略——接上一篇 6.分为可重入锁&#xff0c;不可重入锁 如果一个线程&#xff0c;针对一把锁&#xff0c;连续加锁两次&#xff0c;会出现死锁&#xff0c;就是不可重入锁&#xff0c;不会出现死锁&#xff0c;就是可重入锁。 如果一个线程&#xff0c;针…...

JSON.parse()和JSON.stringify()用法

JSON.parse() 方法用于将 JSON 格式的字符串转换为 JavaScript 对象&#xff0c;而 JSON.stringify() 方法用于将 JavaScript 对象转换为 JSON 字符串。这两个方法可以组合使用来实现将数据从对象到字符串再到对象的转换。 示例 // 创建一个包含属性的 JavaScript 对象 var pe…...

Android 并发编程--阻塞队列和线程池

一、阻塞队列 队列是一种特殊的线性表&#xff0c;特殊之处在于它只允许在表的前端&#xff08;front&#xff09;进行删除操作&#xff0c;而在表的后端&#xff08;rear&#xff09;进行插入操作&#xff0c;和栈一样&#xff0c;队列是一种操作受限制的线性表。进行插入操作…...

Playwright快速上手-1

前言 随着近年来对UI自动化测试的要求越来越高&#xff0c;,功能强大的测试框架也不断的涌现。本系列主讲的Playwright作为一款新兴的端到端测试框架,凭借其独特优势,正在逐渐成为测试工程师的热门选择。 本系列文章将着重通过示例讲解 Playwright python开发环境的搭建 …...

PPT颜色又丑又乱怎么办?

一、设计一套PPT时&#xff0c;可以从这5个方面进行设计 二、PPT颜色 &#xff08;一&#xff09;、PPT常用颜色分类 一个ppt需要主色、辅助色、字体色、背景色即可。 &#xff08;二&#xff09;、搭建PPT色彩系统 设计ppt时&#xff0c;根据如下几个步骤&#xff0c;依次选…...

python计算相关系数R

方法一&#xff1a; import numpy as np# 计算相关系数R def r(y_true, y_pred):y_true np.array(y_true)y_pred np.array(y_pred)corr np.corrcoef(y_true, y_pred)[0][1]return corrcorr r(yture, ypred)方法二 import scipy.stats # 计算皮尔逊相关指数&#xff0c;并…...

黑马项目一阶段面试 自我介绍篇

面试官你好&#xff0c;我叫xxx&#xff0c;是来自xxxx的本科毕业生。我通过招聘网站/内推/线下招聘了解到的贵司&#xff0c;我具有扎实的Java后端的基础功底&#xff0c;基本掌握JavaSE、JavaEE流行技术的使用&#xff0c;并且我比较好学&#xff0c;心态也很乐观积极&#x…...

时序预测 | MATLAB实现CNN-BiGRU-Attention时间序列预测

时序预测 | MATLAB实现CNN-BiGRU-Attention时间序列预测 目录 时序预测 | MATLAB实现CNN-BiGRU-Attention时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 MATLAB实现CNN-BiGRU-Attention时间序列预测&#xff0c;CNN-BiGRU-Attention结合注意力机制时…...

开发过程中遇到的问题以及解决方法

巩固基础&#xff0c;砥砺前行 。 只有不断重复&#xff0c;才能做到超越自己。 能坚持把简单的事情做到极致&#xff0c;也是不容易的。 开发过程中遇到的问题以及解决方法 简单易用的git命令 git命令&#xff1a; 查看有几个分支&#xff1a;git branch -a 切换分支&#…...

本地oracle登录账号锁定处理,the account is locked

1.打开cmd命令窗口 2.打开sqlplus: sqlplus /nolog(加/nolog是不登录服务器的意思&#xff0c;不加就需要输账号密码) 3.切换到管理员&#xff1a;conn / as sysdba; 第2步第3步可以合并&#xff0c;直接使用sysdba登录&#xff1a;sqlplus / as sysdba; 4.解锁账号&#x…...

redission自定义hessian序列化

一。技术改造背景 由于之前的比较陈旧的技术&#xff0c;后面发起了技术改造&#xff0c;redis整体改后使用redisson框架。 二。问题 改造完成后&#xff0c;使用方反馈 缓存获取异常 异常信息如下 Caused by: java.io.CharConversionException: Unexpected EOF in the mid…...

P8642 [蓝桥杯 2016 国 AC] 路径之谜

[蓝桥杯 2016 国 AC] 路径之谜 题目描述 小明冒充 X X X 星球的骑士&#xff0c;进入了一个奇怪的城堡。 城堡里边什么都没有&#xff0c;只有方形石头铺成的地面。 假设城堡地面是 n n n\times n nn 个方格。如图所示。 按习俗&#xff0c;骑士要从西北角走到东南角。 …...

oracle sql developer批量删除某个用户

随着navicate收费&#xff0c;还得破解&#xff0c;pl/sql developer配置麻烦&#xff0c;最近使用oracle sql developer来试试oracle的操作如何&#xff1b; 用着还行&#xff0c;没有卡顿现象&#xff0c; 最近要oracle sql developer批量删除某个用户下所有的表&#xff0…...

vuejs-datepicker高亮日期完全指南:打造智能日历体验

vuejs-datepicker高亮日期完全指南&#xff1a;打造智能日历体验 【免费下载链接】vuejs-datepicker A simple Vue.js datepicker component. Supports disabling of dates, inline mode, translations 项目地址: https://gitcode.com/gh_mirrors/vu/vuejs-datepicker v…...

Globby最佳实践:避免常见陷阱的7个技巧

Globby最佳实践&#xff1a;避免常见陷阱的7个技巧 【免费下载链接】globby User-friendly glob matching 项目地址: https://gitcode.com/gh_mirrors/gl/globby Globby是一个基于fast-glob构建的用户友好的glob匹配库&#xff0c;它为Node.js开发者提供了强大的文件匹配…...

5. 你是怎么理解ES6中 Promise的?使用场景?

一、先给面试官一个结论版如果面试官问 "你怎么理解 Promise&#xff1f;" &#xff0c;不要上来就背 API。 更好的开场是先说本质&#xff1a;Promise 是 ES6 引入的一种用于处理异步操作的解决方案。 它的核心价值是&#xff1a;把异步操作的最终结果&#xff08;成…...

Zig新手必看:如何用zigcli快速构建命令行工具(附完整代码示例)

Zig语言实战&#xff1a;从零构建命令行工具的完整指南 引言&#xff1a;为什么选择Zig开发命令行工具&#xff1f; 在当今编程语言百花齐放的时代&#xff0c;Zig以其独特的魅力吸引着系统级开发者的目光。这门新兴语言融合了C语言的底层控制能力与现代语言的开发体验&#xf…...

从零搭建猫狗识别桌面应用(PyTorch + Tkinter 实战)

1. 环境准备与工具安装 要搭建猫狗识别桌面应用&#xff0c;首先需要配置好开发环境。这里推荐使用Python 3.8版本&#xff0c;因为PyTorch和Tkinter在这个版本上兼容性最好。我实测过多个Python版本&#xff0c;发现3.8在稳定性和性能上表现最均衡。 安装核心依赖库只需要一行…...

【医疗信息化开发者必修课】:C# FHIR SDK实战指南——从零构建符合HL7 FHIR R4规范的患者数据服务

第一章&#xff1a;FHIR标准与医疗信息化开发全景概览 FHIR&#xff08;Fast Healthcare Interoperability Resources&#xff09;是由HL7组织制定的现代医疗数据交换标准&#xff0c;旨在通过RESTful API、结构化资源和开放格式&#xff08;如JSON/XML&#xff09;弥合异构医疗…...

强化学习(3)--最优状态价值最优策略

说明&#xff1a;本系列文章是我在学习了西湖大学赵世钰老师的《Mathematical Foundations of Reinforcement Learning》一书后的学习笔记&#xff0c;在B站上有赵老师的完整课程视频。 课程视频链接 PDF教材链接 本文代码链接 一、最优状态价值和最优策略 定义&#xff1a…...

Redis 服务器:全面解析与应用实践

Redis 服务器:全面解析与应用实践 引言 Redis(Remote Dictionary Server)是一款开源的、高性能的键值存储数据库。它采用内存作为存储介质,能够提供极快的读写速度,常用于缓存、会话管理、消息队列等领域。本文将全面解析Redis服务器的原理、配置、应用场景以及实践操作…...

记录复现多模态大模型论文OPERA的一周工作()投

pagehelper整合 引入依赖com.github.pagehelperpagehelper-spring-boot-starter2.1.0compile编写代码 GetMapping("/list/{pageNo}") public PageInfo findAll(PathVariable int pageNo) {// 设置当前页码和每页显示的条数PageHelper.startPage(pageNo, 10);// 查询数…...

ARM内存操作指令实战:从LDR、STR到LDM、STM的嵌入式开发应用

1. ARM内存操作指令入门&#xff1a;从LDR/STR开始 第一次接触ARM汇编时&#xff0c;看到满屏的LDR和STR指令确实让人头大。但当我真正理解它们的作用后&#xff0c;才发现这些指令就像快递员一样&#xff0c;负责在寄存器和内存之间搬运数据。LDR&#xff08;Load Register&am…...