題解 | #跳躍游戲(一)#
跳躍游戲(一)
http://fangfengwang8.cn/practice/23407eccb76447038d7c0f568370c1bd
2022.0913算法第57題跳躍游戲(一)
這道題目使用貪心算法,代碼簡單,但是感覺還是挺難想的
每次都要找到當前位置所能跳到的最遠位置,在最遠位置內(nèi)的位置都是能夠到達的,
bool canJump(vector<int>& nums) { //記錄當前位置能夠到達的最遠位置 //i + nums[i]位當前位置能夠到達的最遠位置,這個是一步 //需要記錄的是之前所有位置能夠到達的最遠位置,也就是最終結(jié)果的最遠位置,這個是多步 int end = 0; //遍歷數(shù)組,查看是否能夠到達 for (int i = 0; i < nums.size(); i++) { //當最遠位置小于當前位置時,表明當前位置不能達到,返回false if (i > end) return false; //否則更新最遠邊界,確保最遠邊界始終最遠。 end = max(end, i + nums[i]); } //循環(huán)結(jié)束表明每個位置都能達到 return true; }還是有點懵懂,過段時間還要復習。