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

【贪心算法】(第八篇)

目录

分发饼⼲(easy)

题目解析

讲解算法原理

编写代码

最优除法(medium)

题目解析

讲解算法原理

编写代码


分发饼⼲(easy)

题目解析

1.题目链接:. - 力扣(LeetCode)

2.题目描述

假设你是⼀位很棒的家⻓,想要给你的孩⼦们⼀些⼩饼⼲。但是,每个孩⼦最多只能给⼀块饼⼲。对每个孩⼦ i ,都有⼀个胃⼝值 g[i] (,)这是能让孩⼦们满⾜胃⼝的饼⼲的最⼩尺⼨;并且每块
饼⼲ j ,都有⼀个尺⼨ s[j] ()。如果 s[j] >= g[i] ,我们可以将这个饼⼲ j 分配给孩⼦
i ,这个孩⼦会得到满⾜。你的⽬标是尽可能满⾜越多数量的孩⼦,并输出这个最⼤数值。
⽰例1:
输⼊:g=[1,2,3],s=[1,1]
输出:1
解释:
你有三个孩⼦和两块⼩饼⼲,3个孩⼦的胃⼝值分别是:1,2,3。虽然你有两块⼩饼⼲,由于他们的尺⼨都是1,你只能让胃⼝值是1的孩⼦满⾜。所以你应该输出1。
⽰例2:
输⼊:g=[1,2],s=[1,2,3]
输出:2
解释:
你有两个孩⼦和三块⼩饼⼲,2个孩⼦的胃⼝值分别是1,2。你拥有的饼⼲数量和尺⼨都⾜以让所有孩⼦满⾜。
所以你应该输出2.

提⽰:
◦ 1 <= g.length <= 3 * 10(4)
◦ 0 <= s.length <= 3 * 10(4)
◦ 1 <= g[i], s[j] <= 2(31) - 1

讲解算法原理

解法(贪⼼):
既然是很棒的家⻓,为什么不多买⼀些饼⼲呢

贪⼼策略:
先将两个数组排序。
针对胃⼝较⼩的孩⼦,从⼩到⼤挑选饼⼲:
i. 如果当前饼⼲能满⾜,直接喂(最⼩的饼⼲都能满⾜,不要浪费⼤饼⼲);ii. 如果当前饼⼲不能满⾜,放弃这个饼⼲,去检测下⼀个饼⼲(这个饼⼲连最⼩胃⼝的孩⼦都
⽆法满⾜,更别提那些胃⼝⼤的孩⼦了)。

编写代码

c++算法代码:

class Solution
{
public:int findContentChildren(vector<int>& g, vector<int>& s) {// 先排序sort(g.begin(), g.end());sort(s.begin(), s.end());// 利⽤双指针找答案int ret = 0, n = s.size();for(int i = 0, j = 0; i < g.size() && j < n; i++, j++){while(j < n && s[j] < g[i]) j++; // 找饼⼲if(j < n) ret++;}return ret;}
};

java算法代码:

class Solution
{public int findContentChildren(int[] g, int[] s) {// 排序Arrays.sort(g);Arrays.sort(s);// 利⽤双指针找答案int ret = 0, m = g.length, n = s.length;for(int i = 0, j = 0; i < m && j < n; i++, j++){while(j < n && s[j] < g[i]) j++; // 找饼⼲if(j < n) ret++;}return ret;}
}

最优除法(medium)

题目解析

1.题目链接:. - 力扣(LeetCode)

2.题目描述

给定⼀正整数数组 nums , nums 中的相邻整数将进⾏浮点除法。例如,[2,3,4]->2/3/4。• 例如, nums = [2,3,4] ,我们将求表达式的值 "2/3/4" 。
但是,你可以在任意位置添加任意数⽬的括号,来改变算数的优先级。你需要找出怎么添加括号,以便计算后的表达式的值为最⼤值。
以字符串格式返回具有最⼤值的对应表达式。
注意:你的表达式不应该包含多余的括号。

⽰例1:
输⼊:[1000,100,10,2]
输出:"1000/(100/10/2)"
解释:1000/(100/10/2)=1000/((100/10)/2)=200
但是,以下加粗的括号"1000/((100/10)/2)"是冗余的,
因为他们并不影响操作的优先级,所以你需要返回"1000/(100/10/2)"。
其他⽤例:
1000/(100/10)/2=50
1000/(100/(10/2))=50
1000/100/10/2=0.5
1000/100/(10/2)=2

⽰例2:
输⼊:nums=[2,3,4]
输出:"2/(3/4)"
解释:(2/(3/4))=8/3=2.667
可以看出,在尝试了所有的可能性之后,我们⽆法得到⼀个结果⼤于2.667的表达式。
说明:
◦ 1 <= nums.length <= 10
◦ 2 <= nums[i] <= 1000
◦ 对于给定的输⼊只有⼀种最优除法。

讲解算法原理

解法(贪⼼):
贪⼼策略:

在最终的结果中,前两个数的位置是⽆法改变的。
因为每⼀个数的都是⼤于等于 2 的,为了让结果更⼤,我们应该尽可能的把剩下的数全都放在「分⼦」上。

编写代码

c++算法代码:

class Solution
{
public:string optimalDivision(vector<int>& nums) {int n = nums.size();// 先处理两个边界情况if(n == 1){return to_string(nums[0]);}if(n == 2){return to_string(nums[0]) + "/" + to_string(nums[1]);}string ret = to_string(nums[0]) + "/(" + to_string(nums[1]);for(int i = 2; i < n; i++){ret += "/" + to_string(nums[i]);}ret += ")";return ret;}
};

java算法代码:

class Solution
{public String optimalDivision(int[] nums) {int n = nums.length;StringBuffer ret = new StringBuffer();// 先处理两个边界情况if(n == 1){return ret.append(nums[0]).toString();}if(n == 2){return ret.append(nums[0]).append("/").append(nums[1]).toString();}ret.append(nums[0]).append("/(").append(nums[1]);for(int i = 2; i < n; i++){ret.append("/").append(nums[i]);}ret.append(")");return ret.toString();}
}

相关文章:

【贪心算法】(第八篇)

目录 分发饼⼲&#xff08;easy&#xff09; 题目解析 讲解算法原理 编写代码 最优除法&#xff08;medium&#xff09; 题目解析 讲解算法原理 编写代码 分发饼⼲&#xff08;easy&#xff09; 题目解析 1.题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xf…...

立即调用的函数表达式(IIFE)

立即调用的函数表达式&#xff08;IIFE&#xff09;&#xff0c;它会立即执行并返回一个空对象 解析 Plugins: (() > { return {}; })():1、解析 () > { return {}; } 是一个箭头函数&#xff0c;它定义了一个返回空对象的函数。 在定义之后&#xff0c;() 表示立即调用…...

YOLOv11改进-卷积-引入小波卷积WTConv 解决多尺度小目标问题

本篇文章将介绍一个新的改进机制——WTConv&#xff08;小波卷积&#xff09;&#xff0c;并阐述如何将其应用于YOLOv11中&#xff0c;显著提升模型性能。YOLOv11模型相比较于前几个模型在检测精度和速度上有显著提升&#xff0c;但其仍然受卷积核感受野大小的限制。因此&#…...

flask 接口还在执行中,前端接收到接口请求超时,解决方案

在 Flask 中,当某个接口执行时间较长而导致前端请求超时时,需要考虑以下解决方案: 1. 优化接口的响应时间 如果可能,先优化接口中的代码逻辑,减少处理时间。对于查询操作,可以考虑数据库索引优化、缓存机制等手段。2. 增加请求超时时间 如果接口确实需要较长时间完成,前…...

探索 Python 中的 XML 转换利器:xml2dict

文章目录 **探索 Python 中的 XML 转换利器&#xff1a;xml2dict**一、背景介绍二、xml2dict 是什么&#xff1f;三、如何安装 xml2dict&#xff1f;四、基本用法五、实际应用场景六、常见问题及解决方案七、总结 探索 Python 中的 XML 转换利器&#xff1a;xml2dict 一、背景…...

dbt-codegen: dbt自动生成模板代码

dbt项目采用工程化思维&#xff0c;数据模型分层实现&#xff0c;支持描述模型文档和测试&#xff0c;非常适合大型数据工程项目。但也需要用户编写大量yaml描述文件&#xff0c;这个过程非常容易出错且无聊。主要表现&#xff1a; 手工为dbt模型编写yaml文件&#xff0c;这过…...

springboot057洗衣店订单管理系统(论文+源码)_kaic

基于springboot的洗衣店订单管理系统 摘要 随着信息互联网信息的飞速发展&#xff0c;无纸化作业变成了一种趋势&#xff0c;针对这个问题开发一个专门适应洗衣店业务新的交流形式的网站。本文介绍了洗衣店订单管理系统的开发全过程。通过分析企业对于洗衣店订单管理系统的需求…...

南大通用(GBase 8s)数据库在 Spring Boot 中使用 Flyway

db-migration&#xff1a;Flyway、Liquibase 扩展支持达梦&#xff08;DM&#xff09;数据库、南大通用&#xff08;GBase 8s&#xff09;数据库&#xff0c;并支持 Flowable 工作流。 已支持 达梦数据库&#xff08;DM 8&#xff09;。默认支持 flowable 工作流。南大通用数…...

CMakeLists.txt 编写规则

目录 1. 注释 1.1 注释行 1.2 注释块 2. CMakeLists.txt的编写 2.1 同意目录下的源文件 2.2 SET指令 2.3 file和aux_source_directory 2.4 包含头文件 2.5 生成动态库和静态库 2.6 链接库文件 2.7 message指令 2.8 移除操作 2.9 find_library和find_package 3. 常…...

Javascript算法——二分查找

1.数组 1.1二分查找 1.搜索索引 开闭matters&#xff01;&#xff01;&#xff01;[left,right]与[left,right) /*** param {number[]} nums* param {number} target* return {number}*/ var search function(nums, target) {let left0;let rightnums.length-1;//[left,rig…...

node-sass/vendor/linux-x64-72 : Error: EACCES: permission denied, mkdir

npm i --unsafe-perm node-sassgithub解决问题...

uniapp-uniapp + vue3 + pinia 搭建uniapp模板

使用技术 ⚡️uni-app, Vue3, Vite, pnpm &#x1f4e6; 组件自动化引入 &#x1f34d; 使用 Pinia 的状态管理 &#x1f3a8; tailwindcss - 高性能且极具灵活性的即时原子化 CSS 引擎 &#x1f603; 各种图标集为你所用 &#x1f525; 使用 新的 <script setup> …...

深度学习的一些数学基础

数学基础 万丈高楼平地起 怎么说呢&#xff0c;学的数二对于这些东西还是太陌生了&#xff0c;而且当时学的只会做题&#xff0c;不知道怎么使用/(ㄒoㄒ)/~~ 所以记下来一些不太清楚的前置知识点&#xff0c;主要来自《艾伯特深度学习》&#xff0c;书中内容很多&#xff0c…...

自由学习记录(13)

服务端常见的“资源” 在服务端&#xff0c;常见的“资源”指的是服务端提供给客户端访问、使用、处理或操作的各种数据和功能。根据不同类型的服务和应用场景&#xff0c;服务端的资源种类可以非常广泛。以下是一些常见的服务端资源类型&#xff1a; 1. 文件和静态资源 网页…...

低代码可视化-uniapp海报可视化设计-代码生成

在uni-app中&#xff0c;海报生成器通常是通过集成特定的插件或组件来实现的&#xff0c;这些插件或组件提供了生成海报所需的功能和灵活性。我们采用了lime-painter海报组件。lime-painter是一款canvas海报组件&#xff0c;可以更轻松地生成海报。它支持通过JSON及Template的方…...

一次使用LD_DEBUG定位问题的经历

在实际工作中&#xff0c;当遇到段错误&#xff0c;我们会很容易的想到这是非法访问内存导致的&#xff0c;比如访问了已经释放的内存&#xff0c;访问数据越界&#xff0c;尝试写没有写权限的内存等。使用gdb进行调试&#xff0c;查看出异常的调用栈&#xff0c;往往可以定位到…...

数据库安全:如何进行数据库安全审计?

数据库安全:如何进行数据库安全审计? 数据库安全审计是保障数据库安全的重要手段之一,可以帮助企业及时发现潜在的安全风险并采取相应的措施。以下是进行数据库安全审计的步骤和方法: 一、确定审计目标 在进行数据库安全审计之前,首先需要确定审计的目标。这可能包括以…...

【Python】基础语法错误和异常

在Python中&#xff0c;语法错误和异常是两个常见的问题。下面对它们进行简要介绍。 1.语法错误 (Syntax Error) 语法错误是指代码的语法不符合Python的语言规则。当Python解释器读取程序代码时&#xff0c;如果发现语法不正确&#xff0c;就会抛出语法错误。这种错误通常在代…...

获取每个页面的元素,并写入json

获取每个页面的元素&#xff0c;并写入json 想法&#xff1a;如何去记住每个页面的元素&#xff0c;如何实现不同页面的导航&#xff0c;如何从主页面遍历每一个页面的每一个元素 1.创建数据结构存储 2.树状图正好是我们想要的结构体&#xff1a;创建树状图结构体 3.记录每个页…...

【ShuQiHere】深入解析数字电路中的锁存器与触发器

深入解析数字电路中的锁存器与触发器 &#x1f916;&#x1f50c; 在数字电路设计中&#xff0c;**锁存器&#xff08;Latch&#xff09;和触发器&#xff08;Flip-Flop&#xff09;**是实现时序逻辑的基本元件。它们能够存储状态&#xff0c;是构建复杂数字系统的关键。本文将…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

Spring数据访问模块设计

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

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

若依登录用户名和密码加密

/*** 获取公钥&#xff1a;前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...

C# winform教程(二)----checkbox

一、作用 提供一个用户选择或者不选的状态&#xff0c;这是一个可以多选的控件。 二、属性 其实功能大差不差&#xff0c;除了特殊的几个外&#xff0c;与button基本相同&#xff0c;所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...