1936. 新增的最少台阶数-贪心算法加优化
算法 优化 新增 贪心 最少 台阶
2023-09-14 09:06:53 时间
1936. 新增的最少台阶数-贪心算法加优化
给你一个 严格递增 的整数数组 rungs ,用于表示梯子上每一台阶的 高度 。当前你正站在高度为 0 的地板上,并打算爬到最后一个台阶。
另给你一个整数 dist 。每次移动中,你可以到达下一个距离你当前位置(地板或台阶)不超过 dist 高度的台阶。当然,你也可以在任何正 整数 高度处插入尚不存在的新台阶。
返回爬到最后一阶时必须添加到梯子上的 最少 台阶数。
示例 1:
输入:rungs = [1,3,5,10], dist = 2
输出:2
解释:
现在无法到达最后一阶。
在高度为 7 和 8 的位置增设新的台阶,以爬上梯子。
梯子在高度为 [1,3,5,7,8,10] 的位置上有台阶。
示例 2:
输入:rungs = [3,6,8,10], dist = 3
输出:0
解释:
这个梯子无需增设新台阶也可以爬上去。
示例 3:
输入:rungs = [3,4,6,7], dist = 2
输出:1
解释:
现在无法从地板到达梯子的第一阶。
在高度为 1 的位置增设新的台阶,以爬上梯子。
梯子在高度为 [1,3,4,6,7] 的位置上有台阶。
示例 4:
输入:rungs = [5], dist = 10
输出:0
解释:这个梯子无需增设新台阶也可以爬上去。
这题不是很复杂,主要使用贪心算法去解决,不过仍任需要注意一些细节,并进行一些优化
解题代码如下:
int addRungs(int* rungs, int rungsSize, int dist){
int i=0;
int po=0;
int num=0;
for(i;i<rungsSize;i++){
if(rungs[i]-po>dist){
int val=rungs[i]-po;
int n=val/dist;
if(val==n*dist){
num--;
}
po=po+dist*n;
num=num+n;
i--;
}
else{
po=rungs[i];
}
}
return num;
}
相关文章
- C#中使用SHA1算法对密码进行加密
- Java实现 蓝桥杯 算法提高 P0101
- 如何透彻的掌握一门机器学习算法
- spring boot:用redis+lua实现基于ip地址的分布式流量限制(限流/简单计数器算法)(spring boot 2.2.0)
- PCL贪婪投影三角化算法
- Open3D(C++)点云处理算法汇总(C++长期更新版)
- DL之模型调参:深度学习算法模型优化参数之对深度学习模型的超参数采用网格搜索进行模型调优(建议收藏)
- ML之LassoR&RidgeR:基于datasets糖尿病数据集利用LassoR和RidgeR算法(alpha调参)进行(9→1)回归预测
- 软考中级(软件设计师)——数据库设计(下午15分)——数据结构及算法应用(最难的点1个答题15分-程序填空题-目标3-9分)
- 【VRP问题】基于企鹅优化算法求解冷链配送物流车辆调度优化研究
- 基于ABC、PSO和SQP优化算法实现电力变压器绕组的独特电路合成研究(Matlab代码实现)
- 基于GOA蚱蜢优化算法的KNN分类器最优特征选择matlab仿真
- m基于PSO粒子群优化的第四方物流的作业整合算法matlab仿真,对比有代理人和无代理人两种模式下最低运输费用、代理人转换费用、运输方式转化费用和时间惩罚费用
- m基于PSO粒子群优化的Hammerstein模型参数辨识算法matlab仿真,对比LS最小二乘法
- 智能优化算法:协作搜索算法-附代码
- 智能优化算法:白鲸优化算法-附代码
- 智能优化算法:人工大猩猩部队优化算法-附代码
- 智能优化算法:生物地理学优化算法-附代码
- 智能优化算法:帝国主义竞争算法-附代码
- 新型飞蛾火焰优化算法-附代码
- 基于Cat混沌与高斯变异的改进灰狼优化算法-附代码
- 布点算法的原理和实现
- 【Python算法】实验1-求最大公约数
- Greenplum 架构详解 & Hash Join 算法介绍
- Weka Explorer(探索者界面) 详解(4)logistic回归和回归算法