训练营:贪心篇
贪心就是:局部最优
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
总结:
贪心就是局部最优,关键还是思路
相关文章:
训练营:贪心篇
贪心就是:局部最优 1、455. 分发饼干 按照饼干分,从大到小,最大的给胃口最大能满足的 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几乎所有功能组件都是基于扩展机制(SPI)实现的 Dubbo SPI 没有直接使用 Java SPI,在它思想上进行改进ÿ…...
[保研/考研机试] KY103 2的幂次方 上海交通大学复试上机题 C++实现
题目链接: 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神经网络时间序列预测未来(完整…...
组合模式(C++)
定义 将对象组合成树形结构以表示部分-整体’的层次结构。Composite使得用户对单个对象和组合对象的使用具有一致性(稳定)。 应用场景 在软件在某些情况下,客户代码过多地依赖于对象容器复杂的内部实现结构,对象容器内部实现结构(而非抽象接口)的变化…...
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 解决办法:修改 Git 的网络设置 打开git Bash运行,clash代理一般是下面的端口 # 注意…...
通过动态IP解决网络数据采集问题
动态地址的作用 说到Python网络爬虫,很多人都会遇到困难。最常见的就是爬取过程中IP地址被屏蔽。虽然大部分都是几个小时内自动解封的,但这对于分秒必争的python网络爬虫来说,是一个关键性的打击!当一个爬虫被阻塞时,…...
可重入锁,不可重入锁,死锁的多种情况,以及产生的原因,如何解决,synchronized采用的锁策略(渣女圣经)自适应的底层,锁清除,锁粗化,CAS的部分应用
一、💛 锁策略——接上一篇 6.分为可重入锁,不可重入锁 如果一个线程,针对一把锁,连续加锁两次,会出现死锁,就是不可重入锁,不会出现死锁,就是可重入锁。 如果一个线程,针…...
JSON.parse()和JSON.stringify()用法
JSON.parse() 方法用于将 JSON 格式的字符串转换为 JavaScript 对象,而 JSON.stringify() 方法用于将 JavaScript 对象转换为 JSON 字符串。这两个方法可以组合使用来实现将数据从对象到字符串再到对象的转换。 示例 // 创建一个包含属性的 JavaScript 对象 var pe…...
Android 并发编程--阻塞队列和线程池
一、阻塞队列 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作…...
Playwright快速上手-1
前言 随着近年来对UI自动化测试的要求越来越高,,功能强大的测试框架也不断的涌现。本系列主讲的Playwright作为一款新兴的端到端测试框架,凭借其独特优势,正在逐渐成为测试工程师的热门选择。 本系列文章将着重通过示例讲解 Playwright python开发环境的搭建 …...
PPT颜色又丑又乱怎么办?
一、设计一套PPT时,可以从这5个方面进行设计 二、PPT颜色 (一)、PPT常用颜色分类 一个ppt需要主色、辅助色、字体色、背景色即可。 (二)、搭建PPT色彩系统 设计ppt时,根据如下几个步骤,依次选…...
python计算相关系数R
方法一: 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 # 计算皮尔逊相关指数,并…...
黑马项目一阶段面试 自我介绍篇
面试官你好,我叫xxx,是来自xxxx的本科毕业生。我通过招聘网站/内推/线下招聘了解到的贵司,我具有扎实的Java后端的基础功底,基本掌握JavaSE、JavaEE流行技术的使用,并且我比较好学,心态也很乐观积极&#x…...
时序预测 | MATLAB实现CNN-BiGRU-Attention时间序列预测
时序预测 | MATLAB实现CNN-BiGRU-Attention时间序列预测 目录 时序预测 | MATLAB实现CNN-BiGRU-Attention时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 MATLAB实现CNN-BiGRU-Attention时间序列预测,CNN-BiGRU-Attention结合注意力机制时…...
开发过程中遇到的问题以及解决方法
巩固基础,砥砺前行 。 只有不断重复,才能做到超越自己。 能坚持把简单的事情做到极致,也是不容易的。 开发过程中遇到的问题以及解决方法 简单易用的git命令 git命令: 查看有几个分支:git branch -a 切换分支&#…...
本地oracle登录账号锁定处理,the account is locked
1.打开cmd命令窗口 2.打开sqlplus: sqlplus /nolog(加/nolog是不登录服务器的意思,不加就需要输账号密码) 3.切换到管理员:conn / as sysdba; 第2步第3步可以合并,直接使用sysdba登录:sqlplus / as sysdba; 4.解锁账号&#x…...
redission自定义hessian序列化
一。技术改造背景 由于之前的比较陈旧的技术,后面发起了技术改造,redis整体改后使用redisson框架。 二。问题 改造完成后,使用方反馈 缓存获取异常 异常信息如下 Caused by: java.io.CharConversionException: Unexpected EOF in the mid…...
P8642 [蓝桥杯 2016 国 AC] 路径之谜
[蓝桥杯 2016 国 AC] 路径之谜 题目描述 小明冒充 X X X 星球的骑士,进入了一个奇怪的城堡。 城堡里边什么都没有,只有方形石头铺成的地面。 假设城堡地面是 n n n\times n nn 个方格。如图所示。 按习俗,骑士要从西北角走到东南角。 …...
oracle sql developer批量删除某个用户
随着navicate收费,还得破解,pl/sql developer配置麻烦,最近使用oracle sql developer来试试oracle的操作如何; 用着还行,没有卡顿现象, 最近要oracle sql developer批量删除某个用户下所有的表࿰…...
坐标系工艺参数的设定
在一台专机机床上模拟圆弧程序时,发现G2和G3的方向是反的,G2轴按逆时针方向运行,G3轴按顺时针方向运行。测试程序如下:G19G0 G90 Y0 Z0G2 Y100 Z100 CR100 F500M30G2指令时,圆弧为逆时针方向G3指令时,圆弧为…...
2024版:从零到一,手把手教你完成UniApp支付宝支付功能配置
1. 为什么需要UniApp支付宝支付功能? 移动应用开发中,支付功能几乎是必备模块。作为国内主流支付方式之一,支付宝支付覆盖了超过10亿用户,接入支付宝意味着你的应用可以触达绝大多数国内用户。UniApp作为跨平台开发框架࿰…...
STM32总线架构解析与性能优化实战
1. STM32单片机内部总线架构概述作为嵌入式开发者,理解STM32单片机的内部总线结构是优化代码性能的关键。在Cortex-M3架构的STM32F1系列中,总线系统就像一座精心设计的立交桥网络,各司其职又相互配合。我第一次调试DMA传输卡顿时,…...
从LLM到A2A:AI工程师必备7大核心概念解析,掌握AI未来!
从 LLM 到 A2A:AI 工程师必须掌握的七个核心概念 大模型 API Agent MCP Skill A2A 全景解析 你是否曾经困惑:调用一个大模型 API 和「部署一个 Agent」到底有什么本质区别?MCP 和 Skill 都是「能力扩展」,为什么需要两套机制…...
DB1-05S05D 与 B0505D-1WR3 适配性实测|工业电源选型无改板替换指南
在工业控制、仪器仪表、通信设备等场景的电源选型中,DB1-05S05D和B0505D-1WR3两款隔离型DC-DC电源模块,因相同的电压规格与封装形式,均成为工程师的常用选择。两者核心电气参数与应用场景高度契合,均可适配各类常规工业设备的供电…...
别再手动敲代码了!我用GitHub Copilot+Python Django,10分钟搞定电商用户注册模块
用GitHub Copilot和Django十分钟搭建电商用户注册系统 最近在重构一个老旧的电商项目时,我面临着一个看似简单却极其耗时的任务:重写用户注册模块。按照传统方式,我需要手动创建Django表单、编写验证逻辑、设计数据库模型,整个过程…...
终极mdp教程:如何用命令行轻松创建精美Markdown幻灯片
终极mdp教程:如何用命令行轻松创建精美Markdown幻灯片 【免费下载链接】mdp A command-line based markdown presentation tool. 项目地址: https://gitcode.com/gh_mirrors/md/mdp mdp是一款基于命令行的Markdown演示工具,它让你能够直接在终端中…...
Topit:重新定义macOS窗口管理,开启效率革命
Topit:重新定义macOS窗口管理,开启效率革命 【免费下载链接】Topit Pin any window to the top of your screen / 在Mac上将你的任何窗口强制置顶 项目地址: https://gitcode.com/gh_mirrors/to/Topit 在数字化工作环境中,多任务处理已…...
从“开盲盒”到“当导演”:我是如何用ControlNet的8个模型,把AI绘画变成精准设计工具的
从“开盲盒”到“当导演”:我是如何用ControlNet的8个模型,把AI绘画变成精准设计工具的 作为一名UI设计师,我曾经对AI绘画又爱又恨。爱的是它能瞬间生成几十种风格的概念图,恨的是这些图总像开盲盒——你永远不知道下一张是惊喜还…...
ROS新手必看:5分钟搞定usb_cam相机标定(附棋盘格下载)
ROS实战:从零完成USB摄像头标定的完整指南 在机器人视觉系统中,相机标定是确保测量精度的基础步骤。许多ROS初学者往往在第一步就遇到障碍——要么找不到合适的标定工具,要么被复杂的参数配置搞得晕头转向。本文将带你用最直接的方式完成整个…...
