广州做网站海珠信科,新手想写小说怎么做网站,郑州装修设计公司,有赞商城商家版一#xff1a;跳跃游戏 55. 跳跃游戏 题目描述#xff1a;给你一个非负整数数组 nums #xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标#xff0c;如果可以#xff0c;返回 true #xff1… 一跳跃游戏 55. 跳跃游戏 题目描述给你一个非负整数数组 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(vectorint 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;}
};二跳跃游戏 II 45. 跳跃游戏 II 题目描述给定一个长度为 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(vectorint 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;}};三、划分字母区间 763. 划分字母区间 题目描述给你一个字符串 s。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s。返回一个表示每个字符片段长度的数组。 示例1
输入s ababcbacadefegdehijhklij输出[9,7,8]解释 划分结果为 ababcbaca, defegde, hijhklij。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的因为划分的片段数较少。 示例2
输入s eccbbdbec输出[10] 注意
1 s.length 500s 仅由小写英文字母组成 解决思路一 ①、首先遍历一遍给定的字符串s记录每个字母出现的次数存放在变量int zm[26]中。 ②、然后进行第二遍遍历在每轮迭代中将当前字符放入map中 map的键选取为字母映射编号0~25,值选取为当前出现次数。并进行判断若map中当前字符出现的次数与第一次遍历时存放在数组zm中的次数相等说明该字符已经全部出现了将其从map表中删除。若map表为空则说明遍历到当前位置处前面出现的所有字符后面均不再出现可以在此处进行切割将个数累计变量进行存储也就是我们所要输出的长度然后将累计量清零继续进行下一轮迭代直至第二遍遍历结束。 上述思路的参考程序如下
class Solution {
public:vectorint partitionLabels(string s) {int zm[26]{0}; unordered_mapint,int map; vectorint ans; int iter0;for(int i0;is.size();i){ zm[s[i]-a];} //第一遍遍历统计各个字母出现次数for(int i0;is.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); iter0;} //当map为空时说明当前已经出现过的元素已经全部出现了}return ans;}
};上述方案的时间复杂度较低属于时间最优的算法之一但由于使用了额外的map表空间复杂度比较高下面介绍一种改进方案不再需要使用额外的map表从而降低空间复杂度。 解决思路二 ①、首先同样是遍历一遍给定的字符串s所不同的是记录的是每个字符最后出现的位置存放在int hash[27]中。 ②、然后进行第二遍遍历最远边界right初始化为0左边界left初始化为0在每轮迭代中对最远边界进行更新若当前字符i的最远边界大于right则对right进行更新。在每轮迭代中会进行判断若当前字符i处于最远边界right处则说明到达了前面出现的所有字符的最远边界处前面出现的所有字符后面均不再出现可以在此处进行切割。right-left1即为当前片段的长度压入结果队列中。并将left更新为i 1。继续进行下一轮迭代直至第二遍遍历结束。 上述思路的参考程序如下
class Solution {
public:vectorint partitionLabels(string S) {int hash[27] {0}; // i为字符hash[i]为字符出现的最后位置for (int i 0; i S.size(); i) { // 统计每一个字符最后出现的位置hash[S[i] - a] i;}vectorint 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表空间复杂度也得到了有效降低。
