赞
踩
题目描述:给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。
示例 1:
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1,然后从下标 1 跳 3 步到达最后一个下标。
示例 2:
输入:nums = [3,2,1,0,4]
输出:false
解释:无论你怎么跳,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ,所以永远不可能到达最后一个下标。
提示:
* 1 <= nums.length <= 10⁴
* 0 <= nums[i] <= 10⁵
解题思路:
这道题最关键的地方就是不要去想在当前位置,我应该跳到哪里去,而是只需要记录当前能到达的最远位置,就可以了,遍历一遍给定的数组,若发现遍历到的当前位置i大于最远可达距离,则说明无法到达,直接返回false,若数组遍历完了,没有返回false,说明遍历到每一个i处时,均小于当时的最远距离,即均可达,返回true。
参考程序:
class Solution {
public:
bool canJump(vector<int>& nums) {
int k = 0;
for (int i = 0; i < nums.size(); i++) {
if (i > k) return false;
k = max(k, i + nums[i]);
}
return true;
}
};
题目描述:给定一个长度为 n 的 0 索引整数数组 nums ,初始位置为 nums[0] 。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1] 。
示例 1:
输入:nums = [2,3,1,1,4]
输出:2
解释:跳到最后一个位置的最小跳跃次数是 2。
从下标为 0 跳跃下标为 1 的位置,跳 1 步,然后再跳 3 步到达数组的最后一个位置。
示例 2:
输入:nums = [2,3,0,1,4]
输出:2
提示:
* 1 <= nums.length <= 10⁴
* 0 <= nums[i] <= 1000
* 题目保证可以到达 nums[n-1]
解题思路:
这道题最关键的地方同样是不要去想在当前位置,我应该跳到哪里去。而且根据每次跳跃所能到达的最远距离,将给定数组划分为很多区间,遍历当前区间中所有值,得到的最远距离,作为下一个区间的右界限,划分的区间数-1即为所需的最少跳跃次数。这么说可能有点懵,下面举一个例子,大家就明白了
例如,对于[2,3,1,1,4,2,1,1,3],起始的时候,只能从索引为0的2处起跳,
则[2,3,1,1,4,2,1,1,3] 划分为 [2] [3,1,1,4,2,1,1,3]
从索引为0的2处起跳,其最远可以到达的索引为2的1处,按最远可到达的区域,划分数组
[2] [3,1,1,4,2,1,1,3] 划分为 [2] [3,1] [1,4,2,1,1,3]
遍历新得到的区间[3,1],记录最远距离,若从3处起跳,最远可到达索引为4的4处,若从1处起跳,则只能到达4前面索引为3的1处,所以当前区间[3,1]起跳,最远可到达索引为4的4处,因此
[2] [3,1] [1,4,2,1,1,3] 划分为 [2] [3,1] [1,4] [2,1,1,3]
同理,遍历新得到的区间[1,4],记录最远距离,若从1处起跳,最远可到达索引为4的4处,若从4处起跳,则最远可以到达后面索引为8的3处,所以当前区间[3,1]起跳,最远可到达索引为8的3处,因此
已经超过或恰好到达最后一个元素,不需要继续划分了,即
起始位置: [2]
第一次跳跃,新的可达区域 [3,1]
第二次跳跃,新的可达区域 [1,4]
第三次跳跃,新的可达区域 [2,1,1,3]
上面过程中遍历当前区间,记录从当前区间起跳可到达的最远距离的过程对应下面程序中的
maxPos = max(nums[i] + i, maxPos);
上面每个区间的右界限,即对应下面程序中的end变量,当遍历完当前区间后,遍历当前区间时得到的最远可达距离maxPos,即为下一个区间的右界限,即end = maxPos;
参考程序:
class Solution {
public:
int jump(vector<int>& nums)
{
int ans = 0,end = 0,maxPos = 0;
for (int i = 0; i < nums.size() - 1; i++)
{
maxPos = max(nums[i] + i, maxPos);
if (i == end){ end = maxPos; ans++;}
}
return ans;
}
};
题目描述:给你一个字符串 s
。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s
。返回一个表示每个字符片段长度的数组。
示例1:
s = "ababcbacadefegdehijhklij"
[9,7,8]
"ababcbaca", "defegde", "hijhklij"
。示例2:
s = "eccbbdbec"
[10]
注意:
1 <= s.length <= 500
s
仅由小写英文字母组成解决思路一:
①、首先,遍历一遍给定的字符串s,记录每个字母出现的次数,存放在变量int zm[26]中。
②、然后,进行第二遍遍历,在每轮迭代中,将当前字符放入map中, map的键选取为字母映射编号(0~25),值选取为当前出现次数。并进行判断,若map中当前字符出现的次数与第一次遍历时存放在数组zm中的次数相等,说明该字符已经全部出现了,将其从map表中删除。若map表为空,则说明,遍历到当前位置处,前面出现的所有字符,后面均不再出现,可以在此处进行切割,将个数累计变量进行存储(也就是我们所要输出的长度),然后将累计量清零,继续进行下一轮迭代,直至第二遍遍历结束。
上述思路的参考程序如下:
class Solution { public: vector<int> partitionLabels(string s) { int zm[26]={0}; unordered_map<int,int> map; vector<int> ans; int iter=0; for(int i=0;i<s.size();i++){ zm[s[i]-'a']++;} //第一遍遍历,统计各个字母出现次数 for(int i=0;i<s.size();i++) //第二遍遍历,统计切割段数 { map[s[i]-'a']++; // 键选取为字母映射编号(0~25),值选取为当前出现次数 auto it = map.begin(); while (it != map.end()) { if (it->second == zm[it->first]) it = map.erase(it); else break; } iter++; if(map.empty()) {ans.push_back(iter); iter=0;} //当map为空时,说明当前已经出现过的元素,已经全部出现了 } return ans; } };
上述方案的时间复杂度较低,属于时间最优的算法之一,但由于使用了额外的map表,空间复杂度比较高,下面介绍一种改进方案,不再需要使用额外的map表,从而降低空间复杂度。
解决思路二:
①、首先,同样是遍历一遍给定的字符串s,所不同的是,记录的是每个字符最后出现的位置,存放在int hash[27]中。
②、然后,进行第二遍遍历,最远边界right初始化为0,左边界left初始化为0,在每轮迭代中,对最远边界进行更新,若当前字符i的最远边界大于right,则对right进行更新。在每轮迭代中,会进行判断,若当前字符i处于最远边界right处,则说明,到达了前面出现的所有字符的最远边界处,前面出现的所有字符,后面均不再出现,可以在此处进行切割。right-left+1,即为当前片段的长度,压入结果队列中。并将left更新为i + 1。继续进行下一轮迭代,直至第二遍遍历结束。
上述思路的参考程序如下:
class Solution { public: vector<int> partitionLabels(string S) { int hash[27] = {0}; // i为字符,hash[i]为字符出现的最后位置 for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置 hash[S[i] - 'a'] = i; } vector<int> result; int left = 0; int right = 0; for (int i = 0; i < S.size(); i++) { right = max(right, hash[S[i] - 'a']); // 找到字符出现的最远边界 if (i == right) { result.push_back(right - left + 1); left = i + 1; } } return result; } }
上述方案的时间复杂度同样较低,属于时间最优的算法之一,且无需使用额外的map表,空间复杂度也得到了有效降低。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。