讨论/综合讨论/【已解决,目前效率与内存最优解法,还能小优化】最小跳跃次数/
【已解决,目前效率与内存最优解法,还能小优化】最小跳跃次数

https://leetcode-cn.com/contest/season/2020-spring/problems/zui-xiao-tiao-yue-ci-shu/

/*
思路是从末尾开始找最优路径,比如2,5,3,1,1
从左向右扫描谁先跳出边界
第一次:边界为6,扫描到第二个位置5,然后第二个位置之后所有的最优跳出次数要么向左经过第二个位置5两次后跳出,要么向右直接跳出
第二次:更新边界为2,扫描到第一个位置2,只能向右跳出边界,循环结束
*/
class Solution {
public:
int minJump(vector<int>& jump) {
	vector<int> step = jump;//记录从当前位置最少需要几步能跳出去 
	int sz = jump.size();
	int Limit = sz;
	while(Limit>0){
		for( int i=0; i<Limit; i++ ){//先找最快能出去的路径 
			int len = jump.at(i);
			if( i+len>=Limit  ){
				step.at(i) = 1;
				if( i+len<sz ){ step.at(i) += step.at(i+len); }
				
				int CurMinStepPos  = i;//记录当前左侧范围内最小跳跃出Limit范围的位置 
				//cout<< "-----" << CurMinStepPos << "   " << step.at(CurMinStepPos) << endl;
				//扫描后续能跳出的位置 
				for( int j=i+1; j<Limit; j++ ){
					int nxtpos = j+jump.at(j);
					if( nxtpos>=Limit ){
						step.at(j) = 1;
						if( nxtpos<sz  ){
							if( step.at(nxtpos) < step.at(CurMinStepPos) ){
								step.at(j) += step.at(nxtpos);
							}else{
								step.at(j) += step.at(CurMinStepPos);
								jump.at(j) = CurMinStepPos-j;//修正为向左的相对距离
							}
						}
						if( step.at(j) < step.at(CurMinStepPos) ){ CurMinStepPos = j; }
						//cout<< "--------------" << j << "   " << step.at(j) << "   " << jump.at(j) << endl;
					}else{//标记不能跳出的
						step.at(j) = -1; 
					}
				}
				
				//扫描不能跳出的
				CurMinStepPos  = i;
				for( int j=i+1; j<Limit; j++ ){
					if( step.at(j)>-1 ){
						if( step.at(j) < step.at(CurMinStepPos) ){ CurMinStepPos = j; }
					}else{
						int nxtpos = j + jump.at(j);
						if( nxtpos<sz && step.at(nxtpos)>-1 && step.at(nxtpos)<step.at(CurMinStepPos) ){//如果能够跳到更小的特殊位置 
							step.at(j) = 1 + step.at(nxtpos);
						}else{
							jump.at(j) = CurMinStepPos-j;//修正为向左的相对距离
							step.at(j) = 1 + step.at(CurMinStepPos);
						}
						if( step.at(j) < step.at(CurMinStepPos) ){ CurMinStepPos = j; }
						//cout<< "--------------" << j << "   " << step.at(j) << "   " << jump.at(j) << endl;
					}
				}
				Limit = CurMinStepPos;
				break;
			}
		}
	}
	

	if(0){
		printf("\r\n");
		vector<int> path;
		path.clear();
		int Pos = 0;
		for( int i=0; i<sz; ){
			printf("%d  ",Pos);//打印路径 
			path.push_back(Pos);
			Pos += jump.at(i);
			if( Pos>=sz ){ break; }
			i=Pos;
	 	}
	} 
	return step.at(0);
}
};
展开讨论
共 1 个讨论

比如
[3,5,5,1,1,3,1,1]
很显然答案是4,你的是5
你的走法是0 3 1 6 5 -
但是可以0 3 2 7 -

1