【线段树 BFS】LCP 09. 最小跳跃次数-EW帮帮网

本文涉及知识点

LCP 09. 最小跳跃次数

为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机。游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处，通过按动弹簧，可以选择把小球向右弹射 jump[i] 的距离，或者向左弹射到任意左侧弹簧的位置。也就是说，在编号为 i 弹簧处按动弹簧，小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[i]>=N ，则表示小球弹出了机器）。小球位于编号 0 处的弹簧时不能再向左弹。

为了获得奖励，你需要将小球弹出机器。请求出最少需要按动多少次弹簧，可以将小球从编号 0 弹簧弹出整个机器，即向右越过编号 N-1 的弹簧。

示例 1：
输入：jump = [2, 5, 1, 1, 1, 1]
输出：3
解释：小 Z 最少需要按动 3 次弹簧，小球依次到达的顺序为 0 -> 2 -> 1 -> 6，最终小球弹出了机器。
限制：
1 <= jump.length <= $10^6$
1 <= jump[i] <= 10000

线段树

性质一：任意解第一步一定是向右弹射。
性质二：任意最优解一定没有两次连续向左弹射。如果有，取消第一次向左弹射。
性质三：任意符合性质一、性质二的最优解，整个操作一定可以拆分成若干以下两类操作单元：操作一，向右弹射。操作二，向右弹射后，马上向左弹射。下面用数学归纳法证明。如果只有一个操作，显然符合性质三。如果第二个操作是右弹，拆出第一个右弹后，仍然符合性质三。如果第二个是左弹，操作数位2，则整个操作就是操作二。如果操作数>2，拆分出前两个操作后，余下的操作仍然符合性质三。
结论一：小球位于i，无论是执行操作一还是操作二到达j，j必定大于i。故从小到大枚举i，可以保证无后效性。
时间复杂度：O(NlogN)。
$\begin{cases} sg[i]是到达i的最少次数& i< N \\ sg[i]是到达[N...]的最少测试 & i==N\\ \end{cases}$

代码

核心代码

倒数第2个样例超时。剪枝后也是如此。样例用的是python。

template<class TSave, class TSet >
class ISegmentTreeCall
{
public:
	virtual void OnUnion(TSave& unionVal, const TSave& leftVal, const TSave& rVal, int leftIndex, int mid, int rIndex) = 0;
};

template<class TSave, class TSet >
class ISingleSegmentTreeCall : public ISegmentTreeCall<TSave,TSet>
{
public:
	virtual void OnUpdateLeaf(TSave& save, int iSaveIndex, const TSet& update) = 0;
};

template<class TSave, class TSet >
class IRangleSegmentTreeCall : public ISingleSegmentTreeCall<TSave, TSet>
{
public:
	virtual void OnUnionSet(TSet& oldBuff, const TSet& newBuff) = 0;
	virtual void OnUpdateBranch(TSave& save, int iLeftIndex, int iRightIndex, const TSet& update) = 0;
};
template<class TSave, class TSet >
class CSegmentTree {
public:
	CSegmentTree(ISegmentTreeCall<TSave, TSet>& call, TSave tDefault)
		:m_call(call), m_tDefault(tDefault) {}
	TSave Query(int left, int r) {
		return Query(left, r, m_tDefault);
	}
	TSave Query(int left, int r, TSave tDefault) {
		TSave ans = tDefault;
		std::function<void(const TSave&, const int&, const int&)> fun = [&](const TSave& cur, const int& leftIndex, const int& rIndex) {
			m_call.OnUnion(ans, ans, cur, left, leftIndex - 1, rIndex);
		};
		Enum(left, r, fun);
		return ans;
	}
	virtual void Enum(int leftIndex, int leftRight, std::function<void(const TSave&, const int&, const int&)>& fun) = 0;
	virtual TSave QueryAll() = 0;
protected:
	ISegmentTreeCall<TSave, TSet>& m_call;
	const TSave m_tDefault;
};

template<class TSave, class TSet >
class CRangSegmentTree :public CSegmentTree<TSave, TSet>
{
public:
	CRangSegmentTree(IRangleSegmentTreeCall<TSave, TSet>& call, TSave tDefault, TSet tRecordNull)
		:m_call(call), CSegmentTree<TSave, TSet>(call, tDefault), m_recordNull(tRecordNull) {}
	virtual void Update(int iLeftIndex, int iRightIndex, TSet value) = 0;
protected:
	IRangleSegmentTreeCall<TSave, TSet>& m_call;
	TSet m_recordNull;
};

template<class TSave, class TSet >
class CRangeVectorSegmentTree : public CRangSegmentTree<TSave, TSet>
{
public:
	CRangeVectorSegmentTree(int iEleSize, IRangleSegmentTreeCall<TSave, TSet>& call, TSave tDefault, TSet tRecordNull) :m_iEleSize(iEleSize), CRangSegmentTree<TSave, TSet>(call, tDefault, tRecordNull)
		, m_save(iEleSize * 4, tDefault), m_record(iEleSize * 4, tRecordNull) {
		CRangSegmentTree<TSave, TSet>::m_recordNull = tRecordNull;
	}
	virtual void Update(int iLeftIndex, int iRightIndex, TSet value) override
	{
		if (max(iLeftIndex, 0) > min(iRightIndex, m_iEleSize - 1)) { return; }//和根节点没交集
		Update(1, 0, m_iEleSize - 1, iLeftIndex, iRightIndex, value);
	}
	virtual void Enum(int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun) override {
		if (max(iQueryLeft, 0) > min(iQueryRight, m_iEleSize - 1)) { return; }//和根节点没交集
		Enum(1, 0, m_iEleSize - 1, iQueryLeft, iQueryRight, fun);
	}
	//void Init() {
	//	Init(1, 0, m_iEleSize - 1);
	//}
	TSave QueryAll() override {
		return m_save[1];
	}
	void swap(CRangeVectorSegmentTree<TSave, TSet>& other) {
		m_save.swap(other.m_save);
		m_record.swap(other.m_record);
		std::swap(CRangSegmentTree<TSave, TSet>::m_recordNull, other.m_recordNull);
		std::swap(CSegmentTree<TSave, TSet>::m_tDefault, other.m_tDefault);
		assert(m_iEleSize == other.m_iEleSize);
	}
protected:
	//void Init(int iNodeNO, int iSaveLeft, int iSaveRight)
	//{
	//	if (iSaveLeft == iSaveRight) {
	//		this->OnInit(m_save[iNodeNO], iSaveLeft);
	//		return;
	//	}
	//	const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
	//	Init(iNodeNO * 2, iSaveLeft, mid);
	//	Init(iNodeNO * 2 + 1, mid + 1, iSaveRight);
	//	this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);
	//}
	void Enum(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun) {
		if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
			fun(m_save[iNodeNO], iSaveLeft, iSaveRight);
			return;
		}
		FreshChild(iNodeNO, iSaveLeft, iSaveRight);
		const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
		if (mid >= iQueryLeft) {
			Enum(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight, fun);
		}
		if (mid + 1 <= iQueryRight) {
			Enum(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight, fun);
		}
	}
	void Update(int iNode, int iSaveLeft, int iSaveRight, int iOpeLeft, int iOpeRight, TSet value)
	{
		if ((iOpeLeft <= iSaveLeft) && (iOpeRight >= iSaveRight))
		{
			UpdateNode(iNode, iSaveLeft, iSaveRight, value);
			return;
		}
		if (iSaveLeft == iSaveRight) {
			return;//没有子节点
		}
		FreshChild(iNode, iSaveLeft, iSaveRight);
		const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
		if (iMid >= iOpeLeft)
		{
			Update(iNode * 2, iSaveLeft, iMid, iOpeLeft, iOpeRight, value);
		}
		if (iMid + 1 <= iOpeRight)
		{
			Update(iNode * 2 + 1, iMid + 1, iSaveRight, iOpeLeft, iOpeRight, value);
		}
		// 如果有后代，至少两个后代
		CRangSegmentTree<TSave, TSet>::m_call.OnUnion(m_save[iNode], m_save[iNode * 2], m_save[iNode * 2 + 1], iSaveLeft, iMid, iSaveRight);
	}
	void UpdateNode(int iNode, int iSaveLeft, int iSaveRight, TSet value) {
		if (iSaveLeft == iSaveRight) {
			CRangSegmentTree<TSave, TSet>::m_call.OnUpdateLeaf(m_save[iNode], iSaveLeft, value);//叶子节点
		}
		else {
			CRangSegmentTree<TSave, TSet>::m_call.OnUpdateBranch(m_save[iNode], iSaveLeft, iSaveRight, value);
			CRangSegmentTree<TSave, TSet>::m_call.OnUnionSet(m_record[iNode], value);
		}
	}
	void FreshChild(int iNode, int iDataLeft, int iDataRight)
	{
		if (CRangSegmentTree<TSave, TSet>::m_recordNull == m_record[iNode])
		{
			return;
		}
		const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;
		UpdateNode(iNode * 2, iDataLeft, iMid, m_record[iNode]);
		UpdateNode(iNode * 2 + 1, iMid + 1, iDataRight, m_record[iNode]);
		m_record[iNode] = CRangSegmentTree<TSave, TSet>::m_recordNull;
	}
	vector<TSave> m_save;
	vector<TSet> m_record;
	const int m_iEleSize;
};

template<class TSave = int, class TSet = int >
class CMinMinSegmentTreeCall :public IRangleSegmentTreeCall <TSave, TSet> {
public:
	virtual void OnUpdateLeaf(TSave& save, int iSaveIndex, const TSet& update)
	{
		save = min(save, update);
	}
	virtual void OnUnion(TSave& unionVal, const TSave& leftVal, const TSave& rVal, int leftIndex, int mid, int rIndex) {
		unionVal = min(leftVal, rVal);
	}
	virtual void OnUnionSet(TSet& oldBuff, const TSet& newBuff) {
		oldBuff = min(oldBuff, newBuff);
	}
	virtual void OnUpdateBranch(TSave& save, int iLeftIndex, int iRightIndex, const TSet& update) {
		save = min(save, update);
	}
};

	class Solution {
		public:
			int minJump(vector<int>& jump) {
				const int N = jump.size();
				CMinMinSegmentTreeCall<int, int> call;
				CRangeVectorSegmentTree<int, int> sg(N + 1, call, INT_MAX / 2, INT_MAX / 2);
				sg.Update(0, 0, 0);
				for (int i = 0;i < N;i++) {
					const int iNew = sg.Query(i, i)+1;
					const int iJump = min(N, i + jump[i]);
					sg.Update(iJump, iJump, iNew);
					sg.Update(i+1, iJump - 1, iNew + 1);
				}
				const int ans = sg.Query(N, N);
				return (ans >= INT_MAX / 2) ? -1 : ans;
			}
		};

单元测试

vector<int> jump;
		TEST_METHOD(TestMethod11)
		{
			jump = { 2, 5, 1, 1, 1, 1 };
			auto res = Solution().minJump(jump);
			AssertEx(3, res);
		}

BFS

vis[i]记录到达i需要的次数。
队列leftMove 记录未被访问的位置，采用懒删除法，当左移时判断 vis[队首]是否已经能到达，如果能出队。

class Solution {
		public:
			int minJump(vector<int>& jump) {
				const int N = jump.size();
				vector<int> vis(N + 1, -1);
				queue<int> que, leftMove;
				for (int i = 0;i < N;i++) {
					leftMove.emplace(i);
				}
				auto Add = [&](int cur, int cnt) {
					if (-1 != vis[cur]) { return; }
					vis[cur] = cnt;
					if (N == cur) { return; }
					que.emplace(cur);
				};
				Add(0, 0);
				while (que.size()) {
					const int cur = que.front();que.pop();
					const int iJump = min(N, cur + jump[cur]);
					Add(iJump,vis[cur] + 1);					
					while (leftMove.size() && (leftMove.front() < cur)) {
						Add(leftMove.front(), vis[cur] + 1);
						leftMove.pop();
					}
				}	
				return vis.back();
			}
		};

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
员工说：技术至上，老板不信；投资人的代表说：技术至上，老板会信。
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

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

【线段树 BFS】LCP 09. 最小跳跃次数

本文涉及知识点

LCP 09. 最小跳跃次数

线段树

代码

核心代码

单元测试

BFS

扩展阅读

视频课程

测试环境

网站公告

今日签到

热门文章

最新发布