首页 > 其他分享 >map|动态规划|单调栈|LeetCode975:奇偶跳

map|动态规划|单调栈|LeetCode975:奇偶跳

时间:2023-12-27 14:34:53浏览次数:43  
标签:奇偶 arr LeetCode975 int 索引 map 跳跃 indexs size


作者推荐

【贪心算法】【中位贪心】.执行操作使频率分数最大

涉及知识点

单调栈 动态规划 map

题目

给定一个整数数组 A,你可以从某一起始索引出发,跳跃一定次数。在你跳跃的过程中,第 1、3、5… 次跳跃称为奇数跳跃,而第 2、4、6… 次跳跃称为偶数跳跃。
你可以按以下方式从索引 i 向后跳转到索引 j(其中 i < j):
在进行奇数跳跃时(如,第 1,3,5… 次跳跃),你将会跳到索引 j,使得 A[i] <= A[j],A[j] 是可能的最小值。如果存在多个这样的索引 j,你只能跳到满足要求的最小索引 j 上。
在进行偶数跳跃时(如,第 2,4,6… 次跳跃),你将会跳到索引 j,使得 A[i] >= A[j],A[j] 是可能的最大值。如果存在多个这样的索引 j,你只能跳到满足要求的最小索引 j 上。
(对于某些索引 i,可能无法进行合乎要求的跳跃。)
如果从某一索引开始跳跃一定次数(可能是 0 次或多次),就可以到达数组的末尾(索引 A.length - 1),那么该索引就会被认为是好的起始索引。
返回好的起始索引的数量。
示例 1:
输入:[10,13,12,14,15]
输出:2
解释:
从起始索引 i = 0 出发,我们可以跳到 i = 2,(因为 A[2] 是 A[1],A[2],A[3],A[4] 中大于或等于 A[0] 的最小值),然后我们就无法继续跳下去了。
从起始索引 i = 1 和 i = 2 出发,我们可以跳到 i = 3,然后我们就无法继续跳下去了。
从起始索引 i = 3 出发,我们可以跳到 i = 4,到达数组末尾。
从起始索引 i = 4 出发,我们已经到达数组末尾。
总之,我们可以从 2 个不同的起始索引(i = 3, i = 4)出发,通过一定数量的跳跃到达数组末尾。
示例 2:
输入:[2,3,1,1,4]
输出:3
解释:
从起始索引 i=0 出发,我们依次可以跳到 i = 1,i = 2,i = 3:
在我们的第一次跳跃(奇数)中,我们先跳到 i = 1,因为 A[1] 是(A[1],A[2],A[3],A[4])中大于或等于 A[0] 的最小值。
在我们的第二次跳跃(偶数)中,我们从 i = 1 跳到 i = 2,因为 A[2] 是(A[2],A[3],A[4])中小于或等于 A[1] 的最大值。A[3] 也是最大的值,但 2 是一个较小的索引,所以我们只能跳到 i = 2,而不能跳到 i = 3。
在我们的第三次跳跃(奇数)中,我们从 i = 2 跳到 i = 3,因为 A[3] 是(A[3],A[4])中大于或等于 A[2] 的最小值。
我们不能从 i = 3 跳到 i = 4,所以起始索引 i = 0 不是好的起始索引。
类似地,我们可以推断:
从起始索引 i = 1 出发, 我们跳到 i = 4,这样我们就到达数组末尾。
从起始索引 i = 2 出发, 我们跳到 i = 3,然后我们就不能再跳了。
从起始索引 i = 3 出发, 我们跳到 i = 4,这样我们就到达数组末尾。
从起始索引 i = 4 出发,我们已经到达数组末尾。
总之,我们可以从 3 个不同的起始索引(i = 1, i = 3, i = 4)出发,通过一定数量的跳跃到达数组末尾。
示例 3:
输入:[5,1,3,4,2]
输出:3
解释:
我们可以从起始索引 1,2,4 出发到达数组末尾。
提示:
1 <= A.length <= 20000
0 <= A[i] < 100000

代码

单调栈

此方法比map巧妙,性能差不多,值得学习。时间复杂度:O(nlogn)。

变量函数解析

indexs

计算奇数跳时,arr[index[i]] 升序,且相等的元素,相对顺序不变。计算偶数跳时,arr[index[i]] 降序,且相等的元素,相对顺序不变。

Next

计算奇(偶)数跳的下一个位置,如果无法跳,则值为m_c

vStatus

记录偶数(奇数)跳能否跳到队尾。vStatus[0][m_c]和vStatus[0][m_c]为false,避免处理边界条件

Next奇数跳为例

令j=index[jj],按jj从小到的顺序,将j入栈,由于arr[index[jj]]是升序,所以:规则一:arr[栈中元素] <=arr[j]。
(sta.top() < j 成立,说明:
规则二:j在sta.top()右边。
规则三:令index[jj2] 为sta.top(),arr[index(jj2,j)]中的数(即大于等于arr[sta.top()] 同时小于等于arr[j]的数)全部在sta.top()的左边,否则出栈了。
结合规则一二三,stat.top()的下一步就是j。

核心代码

class Solution {
public:
	int oddEvenJumps(vector<int>& arr) {
		m_c = arr.size();
		vector<int> indexs(m_c);
		iota(indexs.begin(), indexs.end(), 0);
		sort(indexs.begin(), indexs.end(), [&](const int i1, const int i2) {return (arr[i1] < arr[i2]) || ((arr[i1] == arr[i2]) && (i1 < i2)); });
		const auto& v1 = Next(indexs);
		sort(indexs.begin(), indexs.end(), [&](const int i1, const int i2) {return (arr[i1] > arr[i2]) || ((arr[i1] == arr[i2]) && (i1 < i2)); });
		const auto& v2 = Next(indexs);

		vector<vector<bool>> vStatus(2, vector<bool>(m_c+1));
		int iRet = 1;
		vStatus[0][m_c-1] = true;
		vStatus[1][m_c - 1] = true;
		for (int i = m_c - 1 - 1; i >= 0; i--)
		{
			vStatus[0][i] = vStatus[1][v2[i]];//偶数跳
			vStatus[1][i] = vStatus[0][v1[i]];//奇数跳
			iRet +=  (int)vStatus[1][i];
		}
		return iRet;
	}
	vector<int> Next(const vector<int>& indexs)
	{
		vector<int> vNext(indexs.size(), indexs.size());
		stack<int> sta;
		for (int j : indexs)
		{
			while (sta.size() && (sta.top() < j))
			{
				vNext[sta.top()] = j;
				sta.pop();
			}
			sta.emplace(j);
		}
		return vNext;
	}
	int m_c;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}

int main()
{

	vector<int> arr;
	{
		Solution slu;
		arr = { 10,13,12,14,15 };
		auto res = slu.oddEvenJumps(arr);
		Assert(2, res);
	}
	{
		Solution slu;
		arr = { 2,3,1,1,4 };
		auto res = slu.oddEvenJumps(arr);
		Assert(3, res);
	}
	{
		Solution slu;
		arr = { 5,1,3,4,2 };
		auto res = slu.oddEvenJumps(arr);
		Assert(3, res);
	}
	
	
	//CConsole::Out(res);
}

2023年3月版:map

利用map性能和单调栈差不多,好理解。从后向前遍历各元素,map的键对应arr[i],map的值对应i。如果arr[i],i小的(后加入的)覆盖前面的。
时间复杂度:O(nlogn)。

map

map可以分成有序(单调)map和无序(哈希)map。还可分成单键map和多键map(允许重复的键)。

class Solution {
 public:
	 int oddEvenJumps(vector<int>& arr) {
		 vector<vector<bool>> result;
		 result.assign(arr.size(), vector<bool>(2));
		 result[arr.size() - 1][0] = true;
		 result[arr.size() - 1][1] = true;
		 std::map<int, int> mValueIndex;
		 mValueIndex[arr.back()] = arr.size()-1;
		 for (int i = arr.size() - 2; i >= 0; i--)
		 {
			 {//奇数跳跃
				 auto it = mValueIndex.lower_bound(arr[i]);
				 if (mValueIndex.end() != it)
				 {
					 result[i][0] = result[it->second][1];
				 }
			 }
			 {//偶数跳跃
			 auto it2 = mValueIndex.upper_bound(arr[i]);
			 if (mValueIndex.begin() != it2)
			 {
				 --it2;
				 result[i][1] = result[it2->second][0];
			 }
			 mValueIndex[arr[i]] = i;
		 }
		 }
		 int iNum = 0;
		 for (int i = 0; i < arr.size(); i++)
		 {
			 if (result[i][0])
			 {
				 iNum++;
			 }
		 }
		 return iNum;
	 }
 };



相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版

我想对大家说的话

闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。

子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。

如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法C++ 实现。

map|动态规划|单调栈|LeetCode975:奇偶跳_map


标签:奇偶,arr,LeetCode975,int,索引,map,跳跃,indexs,size
From: https://blog.51cto.com/u_15724537/8999674

相关文章

  • DS/MLE Road map and Courses
    ......
  • nested exception is org.apache.ibatis.type.TypeException: Could not set paramete
    org.mybatis.spring.MyBatisSystemException:nestedexceptionisorg.apache.ibatis.type.TypeException:Couldnotsetparametersformapping:ParameterMapping{property='name',mode=IN,javaType=classjava.lang.String,jdbcType=null,numericScale=nu......
  • springboot项目Mapper注入失败:@org.springframework.beans.factory.annotation.Autowi
    同事发给我一个项目,说启动时,报mapper无法注入,让我帮忙排查一下问题记录一下我自己遇到这个问题的排查顺序首先先排除以下问题:1.mapper类是否加入到ioc容器中(有没有使用@Mapper标签),如果报错是service层,那就看看是不是没有添加server标签2.检查项目是否扫描mapper类所在......
  • HDFS与MapReduce_tyt2023
    1.购买弹性公网IP产品->网络->弹性公网IPEIP计费模式:按需计费区域:华北-北京四线路:全动态BGP公网带宽:按流量计费带宽大小:100IPv6:不开启弹性公网IP名称:eip-bigdata1购买量:12.购买MRS集群产品-》大数据=》MapReduce服务选择“自定义购买”区域:华北—......
  • Basemap改成cartopy。
    因为mac安装不上basemap。画图也是在自己电脑上画图方便些。所以将basemap改成cartopy。由于你不能使用Basemap,我建议使用cartopy库作为替代。cartopy是一个用于绘制地图和进行地理空间数据分析的Python库,与Basemap类似,但得到了更好的维护和支持。修改之前--点击查看代码......
  • 简化属性拷贝插件 MapStructs 使用指北
    MapStruct使用指南1、安装与介绍what?mapstruct是一个代码生成器,可以简化实现javabean之间的转换的配置方法生成的代码使用传统的方法实现getset属性,比起反射更快、更简单、更安全,易于理解why?基于多层的应用经常需要映射不同的对象模型如VO->TDO等;属性转换的代码......
  • ES 修改 Mapping
     https://www.cnblogs.com/ititit111222333/p/16382887.html新建v1indexPUT/test_v1设置v1mappingPOST/test_v1/_mapping{"properties":{"itemId":{"type":"long"},"itemName":{"type":&......
  • Map+函数式接口去掉if-else
    判断条件放在key中对应的业务逻辑放在value中这样子写的好处是非常直观,能直接看到判断条件对应的业务逻辑代码:importcom.wing.service.QueryGrantTypeService;importorg.springframework.beans.factory.annotation.Autowired;importorg.springframework.web.bind.annotation.P......
  • Map+函数式接口去掉if-else
    判断条件放在key中对应的业务逻辑放在value中这样子写的好处是非常直观,能直接看到判断条件对应的业务逻辑代码:importcom.wing.service.QueryGrantTypeService;importorg.springframework.beans.factory.annotation.Autowired;importorg.springframework.web.bind.annotation.P......
  • Roaring bitmaps
    Roaringbitmaps最近看一篇文章,里面涉及到使用roaringbitmaps来推送用户广告并通过计算交集来降低用户广告推送次数。本文给出roaringbitmaps的原理和基本用法,后续给出原文的内容。本文来自:AprimeronRoaringbitmaps:whattheyareandhowtheywork目录Roaringbitmaps......