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

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

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

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

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

TJCTF 2025

还以为是天津的。这个比较容易&#xff0c;虽然绕了点弯&#xff0c;可还是把CP AK了&#xff0c;不过我会的别人也会&#xff0c;还是没啥名次。记录一下吧。 Crypto bacon-bits with open(flag.txt) as f: flag f.read().strip() with open(text.txt) as t: text t.read…...

CTF show 数学不及格

拿到题目先查一下壳&#xff0c;看一下信息 发现是一个ELF文件&#xff0c;64位的 ​ 用IDA Pro 64 打开这个文件 ​ 然后点击F5进行伪代码转换 可以看到有五个if判断&#xff0c;第一个argc ! 5这个判断并没有起太大作用&#xff0c;主要是下面四个if判断 ​ 根据题目…...

【java】【服务器】线程上下文丢失 是指什么

目录 ■前言 ■正文开始 线程上下文的核心组成部分 为什么会出现上下文丢失&#xff1f; 直观示例说明 为什么上下文如此重要&#xff1f; 解决上下文丢失的关键 总结 ■如果我想在servlet中使用线程&#xff0c;代码应该如何实现 推荐方案&#xff1a;使用 ManagedE…...

RKNN开发环境搭建2-RKNN Model Zoo 环境搭建

目录 1.简介2.环境搭建2.1 启动 docker 环境2.2 安装依赖工具2.3 下载 RKNN Model Zoo2.4 RKNN模型转化2.5编译C++1.简介 RKNN Model Zoo基于 RKNPU SDK 工具链开发, 提供了目前主流算法的部署例程. 例程包含导出RKNN模型, 使用 Python API, CAPI 推理 RKNN 模型的流程.   本…...