1671. 得到山形数组的最少删除次数-c语言dp算法加前序后序遍历求解-双百代码
2023-09-14 09:06:52 时间
1671. 得到山形数组的最少删除次数-c语言dp算法加前序后序遍历求解
我们定义 arr 是 山形数组 当且仅当它满足:
arr.length >= 3
存在某个下标 i (从 0 开始) 满足 0 < i < arr.length - 1 且:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
给你整数数组 nums ,请你返回将 nums 变成 山形状数组 的 最少 删除次数。
示例 1:
输入:nums = [1,3,1]
输出:0
解释:数组本身就是山形数组,所以我们不需要删除任何元素。
示例 2:
输入:nums = [2,1,1,5,6,2,3,1]
输出:3
解释:一种方法是将下标为 0,1 和 5 的元素删除,剩余元素为 [1,5,6,3,1] ,是山形数组。
这一题在力扣中难度为困难,事实上难度系数很大了,我的代码可以学习一下,还是不错的:
int minimumMountainRemovals(int* nums, int numsSize){
int predp[numsSize+1];
int epdp[numsSize+1];
predp[0]=0;
epdp[0]=0;
int i;
for(i=0;i<numsSize;i++){
int j;
int max=0;
for(j=0;j<i;j++){
if(nums[j]<nums[i]&&predp[j+1]>max){
max=predp[j+1];
}
}
predp[i+1]=max+1;
// printf("%d ",predp[i+1]);
}
printf("||%d ",numsSize);
for(i=0;i<numsSize;i++){
int j;
int max=0;
for(j=0;j<i;j++){
if(nums[numsSize-1-j]<nums[numsSize-1-i]&&epdp[j+1]>max){
max=epdp[j+1];
}
}
epdp[i+1]=max+1;
// printf("%d ",epdp[i+1]);
}
int max=0;
for(i=0;i<numsSize;i++){
printf("%d %d -",predp[i+1],epdp[numsSize-i]);
int t=predp[i+1]+epdp[numsSize-i]-1;
if(predp[i+1]==1||epdp[numsSize-i]==1){
continue;
}
if(t>max){
//
max=t;
// printf("max %d ",max);
}
}
printf("max %d",max);
return numsSize-max;
}
相关文章
- Java实现 LeetCode 590 N叉树的后序遍历(遍历树,迭代法)
- 重新整理数据结构与算法(c#)—— 图的深度遍历和广度遍历[十一]
- 算法常识——树的遍历
- (算法)是否为二叉查找树的后序遍历数组
- 算法常识——树的遍历
- Leetcode0590: N 叉树的后序遍历(simple, 递归,迭代)
- Open3D 遍历八叉树
- 二叉树遍历高级算法之Morris---莫里斯算法
- Set 遍历的三种方法
- 剑指 Offer II 092. 翻转字符-前缀和+遍历
- 2369. 检查数组是否存在有效划分-dfs深度优先遍历算法
- 二叉搜索树的后序遍历序列
- python 元祖 tuple 遍历
- 785. 判断二分图——本质上就是图的遍历 dfs或者bfs
- 最长绝对文件路径——算法面试刷题1(google),字符串处理,使用tree遍历dfs类似思路
- 树的遍历 迭代算法——思路:初始化stack,pop stack利用pop的node,push new node to stack,可以考虑迭代一颗树 因为后序遍历最后还要要访问根结点一次,所以要访问根结点两次是难点
- 图文详解两种算法:深度优先遍历(DFS)和广度优先遍历(BFS)
- 【霍罗维兹数据结构】二叉树前中后序遍历 | 层序遍历 | 复制二叉树 | 判断两个二叉树全等 | 可满足性问题