算法入门-贪心1

server/2024/9/20 1:53:01/ 标签: 算法, leetcode, java, 推荐算法

第八部分:贪心

409.最长回文串(简单)

给定一个包含大写字母和小写字母的字符串 s ,返回通过这些字母构造成的最长的回文串 的长度。

在构造过程中,请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

示例 1:

输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

示例 2:

输入:s = "a"
输出:1
解释:可以构造的最长回文串是"a",它的长度是 1。

第一种思路:

看到这种需要统计数量的,不自然的会想到使用字典的数据结构,按照这种思路,我考虑如下:

  1. 空字符串检查

  • 首先检查输入字符串 s 是否为空。如果为空,直接返回0,因为没有字符可以构成回文串。

  1. 字符计数

  • 使用一个 HashMap 来统计字符串中每个字符的出现次数。遍历字符串中的每个字符,更新其在 map 中的计数。

  1. 计算回文串长度

  • 初始化 sum 为0,用于存储可以构成的最长回文串的长度。

  • 遍历map中的每个字符及其出现次数:

    • 如果出现次数是偶数,则可以完全加入到回文串中,直接加到 sum

    • 如果出现次数是奇数,则将其减一后加入到 sum,并标记存在奇数值的键,以便后续可以在回文串的中心添加一个字符。

  1. 中心字符处理

  • 如果存在奇数值的键,说明可以在回文串的中心添加一个字符,因此在 sum 上加1。

  1. 返回结果

  • 最后返回 sum,即为通过给定字符串构造的最长回文串的长度。

java">import java.util.HashMap;  
import java.util.Map;  class Solution {  public int longestPalindrome(String s) {  // 检查字符串是否为空  if (s.length() == 0) {  return 0; // 如果字符串为空,直接返回0  }  int sum = 0; // 用于存储可以构成的最长回文串的长度  boolean hasOddValue = false; // 用于跟踪是否存在奇数值的键  Map<Character, Integer> map = new HashMap<>(); // 创建一个HashMap来存储字符及其出现次数  // 遍历字符串中的每个字符  for (char ch : s.toCharArray()) {  // 更新字符的出现次数  map.put(ch, map.getOrDefault(ch, 0) + 1);  }  // 遍历字符计数的映射  for (Map.Entry<Character, Integer> entry : map.entrySet()) {  int value = entry.getValue(); // 获取当前字符的出现次数  if (value % 2 == 0) { // 如果出现次数是偶数  sum += value; // 偶数部分可以完全加入到回文串中  } else { // 如果出现次数是奇数  sum += (value - 1); // 奇数部分减一后加入到回文串中  hasOddValue = true; // 标记存在奇数值的键  }  }  // 如果存在奇数值的键,则可以在回文串的中心添加一个字符  if (hasOddValue) {  sum += 1; // 增加1以考虑中心字符  }  return sum; // 返回计算得到的最长回文串长度  }  // 辅助方法:检查字符串中的所有字符是否相同  private boolean allCharactersSame(String s) {  char firstChar = s.charAt(0); // 获取第一个字符  for (int i = 1; i < s.length(); i++) {  if (s.charAt(i) != firstChar) {  return false; // 如果发现不同的字符,返回false  }  }  return true; // 所有字符相同,返回true  }  
}

第二种思路: 采用官方的贪心思路(不管我暂时还没有从官方的解释中体会到贪心体现在哪里)

解释:那么我们如何通过给定的字符构造一个回文串呢?我们可以将每个字符使用偶数次,使得它们根据回文中心对称。在这之后,如果有剩余的字符,我们可以再取出一个,作为回文中心。

于每个字符 ch,假设它出现了 v 次,我们可以使用该字符 v / 2 * 2 次,在回文串的左侧和右侧分别放置 v / 2 个字符 ch,其中 / 为整数除法。例如若 "a" 出现了 5 次,那么我们可以使用 "a" 的次数为 4,回文串的左右两侧分别放置 2 个 "a"。

如果有任何一个字符 ch 的出现次数 v 为奇数(即 v % 2 == 1),那么可以将这个字符作为回文中心,注意只能最多有一个字符作为回文中心。在代码中,我们用 ans 存储回文串的长度,由于在遍历字符时,ans 每次会增加 v / 2 * 2,因此 ans 一直为偶数。但在发现了第一个出现次数为奇数的字符后,我们将 ans 增加 1,这样 ans 变为奇数,在后面发现其它出现奇数次的字符时,我们就不改变 ans 的值了。

详情见:409. 最长回文串 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/longest-palindrome/

  1. 字符计数

    • 使用一个长度为128的数组 count 来统计字符串中每个字符的出现次数。数组的索引对应字符的ASCII值。

    • 遍历字符串 s,对于每个字符 c,增加 count[c] 的值。

  2. 计算回文串长度

    • 初始化 ans 为0,用于存储可以构成的最长回文串的长度。

    • 遍历count数组,对于每个字符的出现次数v:

      • 使用 v / 2 * 2 计算出可以组成的偶数部分,并加到 ans 中。这样可以确保回文串的左右两边是对称的。

      • 如果 v 是奇数,并且当前的 ans 是偶数,说明可以在回文串的中心添加一个字符(即使得回文串的长度增加1),因此将 ans 加1。

  3. 返回结果

    • 最后返回 ans,即为通过给定字符串构造的最长回文串的长度。

java">class Solution {  public int longestPalindrome(String s) {  // 创建一个长度为128的数组,用于统计字符的出现次数  int[] count = new int[128];  int length = s.length();  // 遍历字符串,统计每个字符的出现次数  for (int i = 0; i < length; ++i) {  char c = s.charAt(i);  count[c]++; // 增加字符c的计数  }  int ans = 0; // 用于存储最长回文串的长度  // 遍历计数数组,计算可以构成的回文串长度  for (int v : count) {  ans += v / 2 * 2; // 将偶数部分直接加到ans中  // 如果当前字符的出现次数为奇数,并且ans是偶数,则可以加1  if (v % 2 == 1 && ans % 2 == 0) {  ans++; // 可以在回文串的中心添加一个字符  }  }  return ans; // 返回计算得到的最长回文串长度  }  
}

455.分发饼干(简单)

题目:假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

对每个孩子 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 和饼干的大小数组 s 进行排序。这是为了能够从最小的胃口和最小的饼干开始进行比较,确保尽可能多的孩子能够得到满足。

  2. 双指针法:使用两个指针 childIndexcookieIndex 分别指向孩子和饼干的当前索引。childIndex 用于遍历孩子,cookieIndex 用于遍历饼干。

  3. 满足条件

    • 如果当前饼干可以满足当前孩子的胃口,即 g[childIndex] <= s[cookieIndex],则增加满足的孩子计数 contentChildrenCount,并同时移动到下一个孩子和下一个饼干。

    • 如果当前饼干不能满足当前孩子,则只移动到下一个饼干,继续尝试满足当前孩子。

  4. 结束条件:当遍历完所有孩子或所有饼干时,循环结束,返回满足的孩子数量。

java">class Solution {  public int findContentChildren(int[] g, int[] s) {  // 对孩子的胃口和饼干的大小进行排序  Arrays.sort(g);  Arrays.sort(s);  int contentChildrenCount = 0; // 记录满足的孩子数量  int childIndex = 0; // 当前孩子的索引  int cookieIndex = 0; // 当前饼干的索引  // 遍历孩子和饼干,直到其中一个数组遍历完  while (childIndex < g.length && cookieIndex < s.length) {  // 如果当前饼干可以满足当前孩子的胃口  if (g[childIndex] <= s[cookieIndex]) {  contentChildrenCount++; // 满足一个孩子  childIndex++; // 移动到下一个孩子  }  // 无论饼干是否满足孩子,都要移动到下一个饼干  cookieIndex++;  }  return contentChildrenCount; // 返回满足的孩子数量  }  
}

后面发现官方的解答和我类似,但是他就是使用双重循环的,想了一下。

贪心算法的贪心在这里面体现在哪?

在这个问题中,贪心算法的贪心策略体现在以下几个方面:

  1. 局部最优选择

    • 每次选择当前最小的饼干来满足当前最小的孩子的胃口。这种选择是基于局部最优的原则,即在每一步中都选择能够立即满足当前孩子的最小饼干。通过这种方式,尽可能多的孩子能够得到满足。

  2. 排序

    • 通过对孩子的胃口和饼干的大小进行排序,确保我们可以从最小的开始进行比较。这种排序使得我们能够有效地找到最小的满足条件的饼干,从而实现贪心选择。

  3. 不回溯

    • 一旦选择了一个饼干来满足一个孩子,就不会回头去尝试用这个饼干去满足其他孩子。每次都向前推进,确保每个孩子都尽可能得到满足,而不去重新考虑之前的选择。

  4. 全局最优解的构建

    • 通过不断地做出局部最优选择(即用当前最小的饼干满足当前最小的孩子),最终构建出全局最优解(即最大数量的孩子得到满足)。这种策略在许多贪心算法中都是常见的。

总结

贪心算法在这个问题中的核心思想是通过局部最优选择(最小饼干满足最小胃口)来达到全局最优解(最大数量的孩子得到满足)。这种方法简单高效,适合解决此类问题。


http://www.ppmy.cn/server/119224.html

相关文章

计算机毕业设计选题推荐-在线拍卖系统-Java/Python项目实战

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…

24年蓝桥杯及攻防世界赛题-MISC-3

21 reverseMe 复制图片&#xff0c;在线ocr识别&#xff0c;https://ocr.wdku.net/&#xff0c;都不费眼睛。 22 misc_pic_again ┌──(holyeyes㉿kali2023)-[~/Misc/tool-misc/zsteg] └─$ zsteg misc_pic_again.png imagedata … text: “$$KaTeX parse error: Undefined…

it基础软件运维管理:从操作系统到数据库,再到中间件和应用系统

在当今的信息化时代&#xff0c;基础软件的运维管理对于企业的稳定运营至关重要。从操作系统到数据库&#xff0c;再到中间件和应用系统&#xff0c;每一个环节都需要精细化的管理和维护。本文将深入探讨基础软件运维管理的关键方面&#xff0c;并结合监控易一体化运维软件&…

二十三种设计模式之建造者模式(类比汽车制造厂好理解一些)

目录 1. 设计模式的分类 2. 定义 3. 建造者模式通常包含以下几个角色 4. 示例代码 5. 建造者模式的主要优点 1. 设计模式的分类 创建型模式(五种)&#xff1a;工厂方法模式、单例模式、抽象工厂模式、原型模式、建造者模式。 结构型模式(七种)&#xff1a;适配器模式、代…

Redis模拟消息队列实现异步秒杀

目录 一、消息队列含义 二、Redis实现消息队列 1、基于List的结构模拟实现消息队列 2、基于PubSub的消息队列 3、基于Stream的消息队列 4、基于Stream的消息队列- 消费者组 一、消息队列含义 消息队列&#xff08;Message Queue&#xff09;&#xff0c;字面意思就是存放…

2024.9.19

[ABC266F] Well-defined Path Queries on a Namori 题面翻译 题目描述 给定一张有 N N N 个点、 N N N 条边的简单连通无向图和 Q Q Q 次询问&#xff0c;对于每次询问&#xff0c;给定 x i , y i x_i,y_i xi​,yi​&#xff0c;表示两点的编号&#xff0c;请你回答第 x i …

docker容器中的内存占用高的问题分析

文章目录 问题描述原因分析分析1分析2验证猜想 结论和经验 问题描述 运维新增对某服务的监控后发现&#xff1a;内存不断上涨的现象。进一步确认&#xff0c;是因为有多个导出日志操作导致的内存上涨问题。 进一步的测试得出的结果是&#xff1a;容器刚启动是占用内存约为50M…

干货:分享6款ai论文写作助手,一键生成原创论文(步骤+工具)

写一篇论文是一个复杂的过程&#xff0c;涉及多个步骤&#xff0c;包括选题、研究、撰写、编辑和校对。AI可以在其中的一些步骤中提供帮助&#xff0c;但最终的论文还是需要人类作者的深入思考和创造性输入。以下是六款值得推荐的AI论文写作助手&#xff0c;其中特别推荐千笔-A…

Oracle从入门到放弃

Oracle从入门到放弃 左连接和右连接Where子查询单行子查询多行子查询 from子句的子查询select子句的子查询oracle分页序列序列的应用 索引PL/SQL变量声明与赋值select into 赋值变量属性类型 异常循环游标存储函数存储过程不带传出参数的存储过程带传出参数的存储过程 左连接和…

Python+PyCharm安装(最新)

目录 1.Python和PyCharm简介 2.环境检测 3.Python下载与安装 3.1Python下载 3.2Python安装 3.3python测试 4.PyCharm下载与安装 4.1PyCharm下载 4.2PyCharm安装 4.3PyCharm测试 4.4PyCharm应用 5.注意事项 5.1更新pip 5.2安装库 ​5.3查看已安装的库 6.总结 1.Py…

【读书笔记-《30天自制操作系统》-22】Day23

本篇内容比较简单&#xff0c;集中于显示问题。首先编写了应用程序使用的api_malloc&#xff0c;然后实现了在窗口中画点与画线的API与应用程序。有了窗口显示&#xff0c;还要实现关闭窗口的功能&#xff0c;于是在键盘输入API的基础上实现了按下按键关闭窗口。最后发现用上文…

【IP网址正则表达式匹配】java,IPv4网址正则表达式匹配

参考链接&#xff1a; https://blog.csdn.net/weixin_39370315/article/details/126141872?ops_request_misc%257B%2522request%255Fid%2522%253A%252256555201-0570-4C72-BD8A-DDAC115282D3%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&…

Vue3: setup语法糖

一. setup语法糖 在 Vue 3 中&#xff0c;setup 语法糖是一种简化组件内部状态和方法管理的特性。它允许你将组件的逻辑直接编写在组件的定义中&#xff0c;而不是像 Vue 2 那样需要在 methods 和 data 属性中管理。setup 语法糖基于 ES6 的类的静态方法&#xff0c;允许你更灵…

【iOS】——JSONModel源码

JSONModel用法 基本用法 将传入的字典转换成模型&#xff1a; 首先定义模型类&#xff1a; interface Person : JSONModel property (nonatomic, copy) NSString *name; property (nonatomic, copy) NSString *sex; property (nonatomic, assign) NSInteger age; end接…

Linux6-vi/vim

1.vi与vim vi是Linux操作系统下的标准编辑器&#xff0c;类似Windows下的记事本 vim是vi的升级版&#xff0c;包括vi的所有功能&#xff0c;而且支持shell 2.vi/vim下的三种模式 vi/vim有三种模式&#xff1a;命令模式&#xff0c;插入模式和底行模式 命令模式&#xff1a…

UE5安卓项目打包安装

Android studio安装 参考&#xff1a;https://docs.unrealengine.com/5.2/zh-CN/how-to-set-up-android-sdk-and-ndk-for-your-unreal-engine-development-environment/ 打开android studio的官网&#xff1a;Download Android Studio & App Tools - Android Developers …

一文读懂:如何将广告融入大型语言模型(LLM)输出

本文是我翻译过来的&#xff0c;讨论了在线广告行业的现状以及如何将大型语言模型&#xff08;LLM&#xff09;应用于在线广告。 原文请参见”阅读原文“。 在2024年&#xff0c;预计全球媒体广告支出的69%将流向数字广告市场。这个数字预计到2029年将增长到79%。在Meta的2024…

python植物大战僵尸项目源码【免费】

植物大战僵尸是一款经典的塔防游戏&#xff0c;玩家通过种植各种植物来抵御僵尸的进攻。 源码下载地址&#xff1a; 植物大战僵尸项目源码 提取码: 8muq

C++——求3个数中最大的数(分别考虑整数、双精度数、长整数的情况),用函数模板来实现。

没注释的源代码 #include <iostream> using namespace std; template<typename T> T max(T a,T b,T c) { if(b>a) ab; if(c>a) ac; return a; } int main() { int a,b,c; double x,y,z; long m,n,p; cout<<"请输入…

实用类工具分享!值得尝试的6款好用AI智能写作论文软件

在探索了20多款AI写作工具后&#xff0c;我根据不同的写作需求&#xff0c;精心挑选了4款推荐给大家。这些工具不仅能够帮助你提升写作效率&#xff0c;还能在特定场景下产出高质量的文案。 以下是六款推荐的AI智能写作论文软件&#xff0c;其中特别推荐千笔-AIPassPaper。 一…