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

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...