贪心算法(新坑)
贪心入门
概述:
贪心算法是一种在每一步选择中都采取当前最优解的策略,希望最终能够得到全局最优解的算法。简单来说,它会不断地做出局部最优的选择,相信通过这种选择最终能够达到全局最优。
举个例子来说明。假设你要从一个迷宫的起点走到终点,每个格子都有一个代价,你要找到一条路径,使得总代价最小。贪心算法会在每一步选择下一步的格子时,选择代价最小的格子,然后继续向着终点移动。这样每一步都选择当前最优的格子,最终就能够找到一条总代价最小的路径。()
不过需要注意的是,贪心算法并不一定能够得到全局最优解,因为它只考虑当前步骤的最优选择,并没有考虑整体的情况。所以在应用贪心算法时,需要仔细分析问题的特征,确保贪心策略适用,并且通过数学证明或实验验证来证明其正确性。
举个简单的例子
有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿?
指定每次拿最大的,最终结果就是拿走最大数额的钱。
即每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。
贪心算法一般分为如下四步:
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
(过于理想化)
引入例题:
分发饼干

若干个子问题就是每个饼淦要怎么分。
最优的是大饼干分给胃口大的,能一口吃饱,或者从小的开始,小饼干喂饱小的,能一口吃饱。
全局最优就是喂饱尽可能多的小孩。
即:
java:
class Solution {// 思路1:优先考虑饼干,小饼干先喂饱小胃口public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);//从小到大排序int start = 0;int count = 0;//嘴不变,饼干变for (int i = 0; i < s.length && start < g.length; i++) {//意思是胃口大就换大一点的饼干,小饼干就直接不要了if (s[i] >= g[start]) {start++;count++;}}return count;}
}
摆动序列

解析:明天写
相关文章:
贪心算法(新坑)
贪心入门 概述: 贪心算法是一种在每一步选择中都采取当前最优解的策略,希望最终能够得到全局最优解的算法。简单来说,它会不断地做出局部最优的选择,相信通过这种选择最终能够达到全局最优。 举个例子来说明。假设你要从一个迷…...
C 语言头文件
C 语言头文件 头文件是扩展名为 .h 的文件,包含了 C 函数声明和宏定义,被多个源文件中引用共享。有两种类型的头文件:程序员编写的头文件和编译器自带的头文件。 在程序中要使用头文件,需要使用 C 预处理指令 #include 来引用它…...
MySQL中自增id用完怎么办?
MySQL中自增id用完怎么办? MySQL里有很多自增的id,每个自增id都是定义了初始值,然后不停地往上加步长。虽然自然数是没有上限的,但是在计算机里,只要定义了表示这个数的字节长度,那它就有上限。比如&#…...
C语言常见算法
算法(Algorithm):计算机解题的基本思想方法和步骤。算法的描述:是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述,包括需要什么数据(输入什么数据、输出什么结果)、采用什么结构、使…...
0-1背包的初始化问题
题目链接 这道题的状态转移方程比较易于确定。dp[i][j]表示能放前i个物品的情况下,容量为j时能放物品的数量(这道题歌曲数量对应物品数量,容量对应时间)。 技巧(收获) 二维dp数组可以视情况优化为一维dp数组…...
API之 要求接口上传pdf 以 合同PDF的二进制数据,multpart方式上传
实现 //时间戳13位毫秒private function getMillisecond() {list($s1,$s2) explode( ,microtime());return (float)sprintf(%.0f,(floatval($s1) floatval($s2)) * 1000);}// 组装参数private function gysscPost1($url,$data){// $data[timestamp] 1694402111964;$data[tim…...
C语言-求阶乘序列前N项和
本题要求编写程序,计算序列 1!2!3!⋯ 的前N项之和。 输入格式: 输入在一行中给出一个不超过12的正整数N。 输出格式: 在一行中输出整数结果。 输入样例: 5输出样例: 153 #include "stdio.h" int main(){int n;int sum 0;scanf("%d",&a…...
3:kotlin 逻辑控制(Control flow)
像其他语言一样,kotlin也有循环和逻辑控制 条件判断(Conditional expressions) kotlin使用if和when来进行条件判断 如果纠结选择if还是when,建议使用when,因为它更能提高程序的健壮性 if 普通写法 fun main() {val…...
Linux系统之一次性计划任务at命令的基本使用
Linux系统之一次性计划任务at命令的基本使用 一、at命令介绍二、at命令的使用帮助2.1 at命令的help帮助信息2.2 at命令的语法解释 三、at命令的日常使用3.1 立即执行一次性任务3.2 指定时间执行一次性任务3.3 查询计划任务3.4 其他指定时间用法3.5 删除已经设置的计划任务3.6 显…...
记录:Unity脚本的编写8.0
目录 需求分析设计GUI包含账号和密码输入栏,包括登录和注册按键添加背景音乐编写脚本控制音乐 退出按钮编写脚本 背景图片完整代码 一个小demo,登录和注册的实现(包括GUI和数据库操控) 需求分析 自行设计GUI,要求 1.包…...
OpenCV | 模版匹配
import cv2 #opencv读取的格式是BGR import numpy as np import matplotlib.pyplot as plt#Matplotlib是RGB %matplotlib inline 模版匹配 模版匹配和卷积原理很像,模版在原图像上从原点开始滑动,计算模版与(图像被模版覆盖的地方ÿ…...
【算法刷题】Day7
文章目录 283. 移动零1089. 复写零 283. 移动零 原题链接 看到题目,首先看一下题干的要求,是在原数组内进行操作,平切保持非零元素的相对顺序 这个时候我们看到了示例一: [ 0, 1, 0, 3,12 ] 这个时候输出成为了 [ 1, 3, 12, 0, …...
前端 | iframe框架标签应用
文章目录 📚嵌入方式📚图表加载显示📚100%嵌入及滑动条问题📚加载动画保留 前情提要: 计划用iframe把画好的home1.html(echarts各种图表组成的html数据大屏)嵌入整合到index.html(搭…...
linux -系统通用命令查询
有时候内网环境下,系统有些命令没有安装因此掌握一些通用的linux 命令也可以帮助我们解决一些问题查看 1.查看系统内核版本 uname -r2.查看系统版本 cat /etc/os-release3. 查看cpu 配置 lscpu4.查看内存信息 free [参数] 中各个数值的解释如下表 数值解释t…...
python炒股自动化(1),量化交易接口区别
要实现股票量化程序化自动化,就需要券商提供的API接口,重点是个人账户小散户可以申请开通,上手要简单,接口要足够全面,功能完善,首先,第一步就是要找对渠道和方法,这里我们不讨论量化…...
LeetCode(35)螺旋矩阵【矩阵】【中等】
目录 1.题目2.答案3.提交结果截图 链接: 54. 螺旋矩阵 1.题目 给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。 示例 1: 输入:matrix [[1,2,3],[4,5,6],[7,8,9]] 输出:…...
BeanUtil.copyProperties的优化与使用(解决copyProperties null值覆盖问题)
BeanUtil.copyProperties的优化与使用 前言一、copyProperties是什么?二、使用步骤1.引入库2.基础使用3.进阶使用4.实用场景 总结 前言 BeanUtil.copyProperties的优化与使用 一、copyProperties是什么? 在java中,我们想要将一个类的值赋值…...
Redis基本操作及使用
📑前言 本文主要是【Redis】——Redis基本操作及使用的文章,如果有什么需要改进的地方还请大佬指出⛺️ 🎬作者简介:大家好,我是听风与他🥇 ☁️博客首页:CSDN主页听风与他 🌄每日一…...
python 继承父类的变量和方法
[root@zz python]# cat a1.py # !/usr/bin/env python # -*- coding: utf-8 -*- class AddrBookEntry(object): ##类定义 def __init__(self,a,b): ##定义构造器 self.var1=a+9 self.var2=b+11 def updatePhone(self, num): # 定义方法 sel…...
ubuntu22.04新机使用(换源,下载软件,安装显卡驱动,锁屏长亮)
换源 国内有很多Ubuntu的镜像源,包括阿里的、网易的,还有很多教育网的源,比如:清华源、中科大源。推荐使用中科大源,快得很。 /etc/apt/sources.list编辑/etc/apt/sources.list文件, 在文件最前面添加以下条目(操作前…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...
