2022-05-27:现在有N条鱼,每条鱼的体积为Ai,从左到右排列,数组arr给出。 每一轮,左边的大鱼一定会吃掉右边比自己小的第一条鱼, 并且每条鱼吃比自己小的鱼的事件是同时发生的。 返回多少轮之

本文主要是介绍2022-05-27:现在有N条鱼,每条鱼的体积为Ai,从左到右排列,数组arr给出。 每一轮,左边的大鱼一定会吃掉右边比自己小的第一条鱼, 并且每条鱼吃比自己小的鱼的事件是同时发生的。 返回多少轮之,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2022-05-27:现在有N条鱼,每条鱼的体积为Ai,从左到右排列,数组arr给出。
每一轮,左边的大鱼一定会吃掉右边比自己小的第一条鱼,
并且每条鱼吃比自己小的鱼的事件是同时发生的。
返回多少轮之后,鱼的数量会稳定。
注意:6 6 3 3。
第一轮过后 :
对于两个6来说,右边比自己小的第一条鱼都是第1个3,所以只有这个3被吃掉,
数组变成 : 6 6 3(第2个3),
第二轮过后 : 6 6。
返回2。
来自bilibili。

答案2022-05-27:

单调栈。

代码用rust编写。代码如下:

use rand::Rng;
fn main() {let len: i32 = 50;let value: i32 = 20;let test_time: i32 = 20000;println!("测试开始");for _i in 0..test_time {let n: i32 = rand::thread_rng().gen_range(0, len) + 1;let mut arr = random_array(n, value);let mut arr2 = arr.clone();let ans1 = min_turns1(&mut arr);let ans2 = min_turns2(&mut arr2);if ans1 != ans2 {println!("出错了!");print!("arr = {:?}", arr);println!("");println!("ans1 = {}", ans1);println!("ans2 = {}", ans2);break;}}println!("测试结束");
}fn min_turns1(arr: &mut Vec<i32>) -> i32 {let mut ans: i32 = 0;loop {let rest = eat_rest(arr);if arr.len() == rest.len() {break;}*arr = rest;ans += 1;}return ans;
}fn eat_rest(arr: &mut Vec<i32>) -> Vec<i32> {if arr.len() == 0 {return vec![0];}let n = arr.len() as i32;let mut delete: Vec<bool> = vec![];for _i in 0..n {delete.push(false);}let mut len = n;for i in 0..n {for j in i + 1..n {if arr[i as usize] > arr[j as usize] {if !delete[j as usize] {delete[j as usize] = true;len -= 1;}break;}}}let mut rest: Vec<i32> = vec![];for _i in 0..len {rest.push(0);}let mut j: i32 = 0;for i in 0..n {if !delete[i as usize] {rest[j as usize] = arr[i as usize];j += 1;}}return rest;
}fn min_turns2(arr: &mut Vec<i32>) -> i32 {let n = arr.len() as i32;let mut stack: Vec<Vec<i32>> = vec![];for i in 0..n {stack.push(vec![]);for _j in 0..2 {stack[i as usize].push(0);}}let mut stack_size: i32 = 0;let mut ans = 0;let mut i = n - 1;while i >= 0 {let mut cur_ans = 0;while stack_size > 0 && stack[(stack_size - 1) as usize][0] < arr[i as usize] {stack_size -= 1;cur_ans = get_max(cur_ans + 1, stack[stack_size as usize][1]);}stack[stack_size as usize][0] = arr[i as usize];stack[stack_size as usize][1] = cur_ans;stack_size += 1;ans = get_max(ans, cur_ans);i -= 1;}return ans;
}fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {if a > b {a} else {b}
}// 为了测试
fn random_array(n: i32, v: i32) -> Vec<i32> {let mut arr: Vec<i32> = vec![];for _i in 0..n {arr.push(rand::thread_rng().gen_range(0, v) - rand::thread_rng().gen_range(0, v));}return arr;
}

执行结果如下:

在这里插入图片描述


左神java代码

这篇关于2022-05-27:现在有N条鱼,每条鱼的体积为Ai,从左到右排列,数组arr给出。 每一轮,左边的大鱼一定会吃掉右边比自己小的第一条鱼, 并且每条鱼吃比自己小的鱼的事件是同时发生的。 返回多少轮之的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

Vue3组件中getCurrentInstance()获取App实例,但是返回null的解决方案

《Vue3组件中getCurrentInstance()获取App实例,但是返回null的解决方案》:本文主要介绍Vue3组件中getCurrentInstance()获取App实例,但是返回nu... 目录vue3组件中getCurrentInstajavascriptnce()获取App实例,但是返回n

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

前端下载文件时如何后端返回的文件流一些常见方法

《前端下载文件时如何后端返回的文件流一些常见方法》:本文主要介绍前端下载文件时如何后端返回的文件流一些常见方法,包括使用Blob和URL.createObjectURL创建下载链接,以及处理带有C... 目录1. 使用 Blob 和 URL.createObjectURL 创建下载链接例子:使用 Blob

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串,目前我找到两种解决问题的思路,具体实现如下:

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

基于Flask框架添加多个AI模型的API并进行交互

《基于Flask框架添加多个AI模型的API并进行交互》:本文主要介绍如何基于Flask框架开发AI模型API管理系统,允许用户添加、删除不同AI模型的API密钥,感兴趣的可以了解下... 目录1. 概述2. 后端代码说明2.1 依赖库导入2.2 应用初始化2.3 API 存储字典2.4 路由函数2.5 应

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

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