数组与贪心算法——605、121、122、561、455、575(5简1中)

2024-09-06 03:12

本文主要是介绍数组与贪心算法——605、121、122、561、455、575(5简1中),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

605. 种花问题(简单)

假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。

给你一个整数数组 flowerbed 表示花坛,由若干 0 和 1 组成,其中 0 表示没种植花,1 表示种植了花。另有一个数 n ,能否在不打破种植规则的情况下种入 n 朵花?能则返回 true ,不能则返回 false 。

 解法一、贪心

先种满,数数满了多出来几朵,再讨论n在不在范围内。对边界要求有点高。。

题解里较完美的一个if条件:

 if ((i == 0 || f[i - 1] == 0) && f[i] == 0 && (i == m - 1 || f[i + 1] == 0))

class Solution {public boolean canPlaceFlowers(int[] flowerbed, int n) {int num = flowerbed.length;int res = 0;if(num == 1){return n==0 || flowerbed[0] == 0 && n == 1 ;}else if(num == 2){return n==0 || ((flowerbed[0] == 0 && flowerbed[1] == 0) && n == 1);}for(int i = 0; i < num;i++){if(i == 0 && flowerbed[0] == 0 && flowerbed[1] == 0){flowerbed[0] = 1;res++;}else if(i == num-1 && flowerbed[i-1] == 0 && flowerbed[i] == 0){res++;}else if(i > 0 && i < num - 1 && flowerbed[i] != 1 && flowerbed[i+1] != 1 && flowerbed[i-1] != 1){flowerbed[i] = 1;res++;}}return n <= res;}
}

121. 买卖股票的最佳时机(简单)

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。 

解法一、暴力(超时)

一开始确实想不动脑子来着(

public class Solution {public int maxProfit(int[] prices) {int maxprofit = 0;for (int i = 0; i < prices.length - 1; i++) {for (int j = i + 1; j < prices.length; j++) {int profit = prices[j] - prices[i];if (profit > maxprofit) {maxprofit = profit;}}}return maxprofit;}
}

解法二、类dp

但不需要维护一个dp数组,只需要维护一个从0-k(0<=k<n)的最小买入值就好

class Solution {public int maxProfit(int[] prices) {int min = prices[0];int profit = 0;for(int i = 1;i < prices.length;i++){profit = Math.max(prices[i] - min,profit);min = Math.min(min,prices[i]);}return profit;}
}

122. 买卖股票的最佳时机 II(中等)

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。

返回 你能获得的 最大 利润 。

解法一、贪心

本质思想就是一旦有钱赚马上买入卖出。注意:贪心只能模拟思想过程,不是实际交易过程。如对于[1,3,4],贪心是1买3卖、3买4卖,交易过程是1买4卖。两者利益等价,行为不等价。

本题还有很多其他类型,尤其是dp/递增栈,但果然还是放在dp专题里做比较好吧~这方面就不贪心了!

class Solution {public int maxProfit(int[] prices) {int profit = 0;if(prices.length < 2)return 0;for(int i = 1;i < prices.length;i++){if(prices[i] > prices[i-1])profit += prices[i] - prices[i-1];}return profit;}
}

561. 数组拆分(简单) 

给定长度为 2n 的整数数组 nums ,你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ,使得从 1 到 n的 min(ai, bi) 总和最大。

返回该 最大总和 。

解法一、排序

要取最大,也就是尽量把小的和小的堆一起,大的和大的堆一起。所以先排序,排序后数组偶数位置的和就是所求。

class Solution {public int arrayPairSum(int[] nums) {Arrays.sort(nums);int n = nums.length,sum = 0;for(int i = 0;i < n;i +=2){sum+=nums[i];}return sum;}
}

解法二、数组排序

从代码示例那边看到的。这个和之前看到的那个取maxSum、minSum然后/2的技法其实有点像,桶排序虽然麻烦但是耗时真的很低。这里直接取gpt的解释吧。

  • index 用来追踪当前已经遍历的数值的累计个数。

  • res 是用于存储最终的结果。

每当 arr[i] > 0,意味着索引 i 对应的数值在 nums 中出现过,代码会根据当前的 index 和 arr[i] 的值来计算部分结果:

  • ((index + 1) % 2 + arr[i]) / 2 这个表达式与确定中位数位置相关,它用于决定是否将该数值纳入 res的计算。

  • (i - 10000) 将索引 i 转换回原来的数值范围(因为我们之前对 nums 的数值进行了偏移处理)。

最后,index = index + arr[i] 用于更新累计的数值个数。

((index + 1) % 2 + arr[i]) / 2 这个表达式的作用是用于控制在遍历过程中,是否选择将当前 i 对应的数值 (即 i - 10000) 贡献给最终的 res 结果。让我们一步一步拆解它的含义:

1. index + 1

index 是用来记录遍历到当前位置之前,总共处理过的元素的个数。index + 1 表示当前的元素是所有已经遍历过的元素中的第几个。

2. % 2

对 index + 1 取模 2 的作用是确定当前这个元素是偶数还是奇数。它会返回两种情况:

  • 当 index + 1 是奇数时,(index + 1) % 2 = 1

  • 当 index + 1 是偶数时,(index + 1) % 2 = 0

这个结果决定了后续表达式的一个偏移调整。

3. arr[i]

arr[i] 表示当前索引 i 对应的数值在 nums 数组中出现的次数。

4. ((index + 1) % 2 + arr[i])

这一步是把 (index + 1) % 2 和 arr[i] 的值加起来:

  • 如果当前是奇数个元素 ((index + 1) % 2 = 1),那么结果就是 1 + arr[i]

  • 如果当前是偶数个元素 ((index + 1) % 2 = 0),那么结果就是 0 + arr[i]

这相当于调整了 arr[i] 的数值,使得某些条件下它多加 1 或不变,这和计算中位数的位置有关系。

5. / 2

这一步是对整个表达式进行除以 2:

  • 如果 arr[i] 是偶数或者 (index + 1) % 2 是 0,那么 (index + 1) % 2 + arr[i] 是偶数,除以 2 后返回一个整数。

  • 如果 arr[i] 是奇数,并且 (index + 1) % 2 = 1,这会使得奇数变为偶数的一半。

总体意义

这个表达式的作用在于,在遍历过程中,根据当前遍历的元素顺序(index)以及该元素的出现次数(arr[i]),判断要不要取一半的数值(除以 2),这样就可以控制贡献给 res 的数值。在处理中位数相关的算法时,这个操作可以帮助判断中位数所在位置以及应取多少值。

举例

假设:

  • arr[i] = 3 表示当前这个数出现了 3 次,

  • index + 1 = 5 表示当前是第 5 个元素,

那么:

  • (index + 1) % 2 = 1,所以 ((index + 1) % 2 + arr[i]) = 1 + 3 = 4

  • / 2 后结果是 2,表示将当前的数值贡献 2 次。

这个操作对中位数或者其他与位置相关的统计操作有帮助。

class Solution {public int arrayPairSum(int[] nums) {if (nums.length <= 1800) {Arrays.sort(nums);int sum = 0;for (int i = 0; i < nums.length; i = i + 2) {sum = sum + nums[i];}return sum;} else {// 在该用数组排序的时候又把这件事忘了个干净int[] arr = new int[20001];for (int i = 0; i < nums.length; i++) {arr[nums[i] + 10000]++;}int index = 0;int res = 0;for (int i = 0; i < arr.length; i++) {if (arr[i] > 0) {res = res + ((index + 1) % 2 + arr[i]) / 2 * (i - 10000);index = index + arr[i];}}return res;}}
}

455. 分发饼干(简单)

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

对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是满足尽可能多的孩子,并输出这个最大数值。

解法一、排序+双指针

先排序。如果饼干比当前孩子胃口值小,那么饼干值往后挑。否则,i++,j++,计入结果。

class Solution {public int findContentChildren(int[] g, int[] s) {int i = 0,j = 0,res = 0;Arrays.sort(g);Arrays.sort(s);while(i < g.length && j < s.length){while(i < g.length && j < s.length && s[j] < g[i])j++;if(i < g.length && j < s.length && s[j] >= g[i]){i++;j++;res++;}}return res;}
}

稍微改善一些(2ms)的情况。在这次的循环里,以孩子都吃到为前提条件,如果饼干用完,则结束,减少了反复判断。

 public int findContentChildren0(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int result = 0;int j = 0;for (int i = 0; i < g.length; i++) {while (j < s.length && g[i] > s[j]) {j++;}if (j >= s.length) {break;}j++;result++;}return result;}

575. 分糖果(简单) 

Alice 有 n 枚糖,其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长,所以前去拜访了一位医生。

医生建议 Alice 要少摄入糖分,只吃掉她所有糖的 n / 2 即可(n 是一个偶数)。Alice 非常喜欢这些糖,她想要在遵循医生建议的情况下,尽可能吃到最多不同种类的糖。

给你一个长度为 n 的整数数组 candyType ,返回: Alice 在仅吃掉 n / 2 枚糖的情况下,可以吃到糖的 最多种类数

解法一、枚举

只要品种不同就过,如果达到满值就break 

class Solution {public int distributeCandies(int[] candyType) {int res = 0,n2 = candyType.length;Arrays.sort(candyType);for(int i = 0;i < n2;i++){if(res == n2/2)return n2/2;res++;while(i < n2-1 && candyType[i]==candyType[i+1])i++;}return res;}
}

解法二、数据结构去重

 本质上就是统计种类,然后返回Math.min(n/2,m)的东西,只要能够统计种类,什么方法都可以。

class Solution {public int distributeCandies(int[] candyType) {Set<Integer> set = new HashSet<Integer>();for (int candy : candyType) {set.add(candy);}return Math.min(set.size(), candyType.length / 2);}
}作者:力扣官方题解
链接:https://leetcode.cn/problems/distribute-candies/solutions/1072396/fen-tang-guo-by-leetcode-solution-l4f6/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

碎碎念

  • 605需要转换思维,121、122是一个系列,考察dp还蛮有意思的。其中122的贪心做法比其他想法都要简单。感觉贪心里目前用到排序的次数很多

这篇关于数组与贪心算法——605、121、122、561、455、575(5简1中)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1140834

相关文章

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::