1 LeetCode45.跳躍游戲II

1.1 題目描述

??與跳躍游戲類似，跳躍游戲II給定長為n的從0開始索引的整數數組nums，nums[i]是你在i處能向右跳躍的最大步數，求到達數組最后一個索引處需要跳躍的最少次數。
??一個示例：nums[2,3,1,1,4]，則到達下標4的位置需要跳至少兩次，即從下標0跳到下標1，再從下標1跳到下標4。

1.2 問題分析及解決

??貪心的思想，即在當前位置所能跳躍的范圍內，選擇跳躍到有最大跳躍長度的位置。例如nums=[2,3,1,1,4]，從下標0可以跳躍到下標1、下標2，但下標1最大跳躍長度為3，比下標2的最大跳躍長度大，因此我們選擇跳躍到下標1。
??像上面的思路我們貌似需要每一次遍歷數組的一小部分決定下一步要走到哪，這樣的話時間復雜度為$O(n^2)$。可以換個角度，但本質上與上述思路相同。
??我們從一個位置跳躍到其能跳遠的最遠長度所在的下標now_right的過程中，記錄下這之間的所有位置能達到的最遠位置的下標max_right，若我們到達了now_right，但仍沒到最后一個下標，此時步數就得+1。因為相當于我們回頭從具有最大跳躍長度的位置開始跳(步數+1)，而回頭不需要步數。
??仍以上述為例，nums=[2,3,1,1,4]，我們從nums[0]開始跳，其最遠可以到達nums[0]+0=2(now_right=2)，并記錄下在其跳躍范圍內的位置能到達的最遠下標nums[1]+1=4(max_right=4)。當我們跳到下標2時，我們無法從nums[0]開始再往右跳，因此需要步數+1，從nums[1]起跳，由于我們記錄了從nums[1]起跳最遠能到達下標4，因此我們只需更新now_right=max_right即可，然后繼續上述操作。注意我們只需要判斷最遠距離能否到達倒數第2個下標，因為若能從某個位置直接到最后一個下標，這不算步數，因此只需判斷能否到達倒數第二個下標，若能則肯定也能到最后一個下標；若不能則步數+1就能到達最后一個下標了。
??具體實現如下：

class Solution {
public:int jump(vector<int>& nums) {int ans=0;//記錄跳躍過程中能到達的最大下標int maxright=0;//記錄從當前位置跳躍能到達的最大下標int nowright=0;for(int i=0;i<nums.size()-1;i++){maxright=max(maxright,nums[i]+i);//如果此時還沒到最后一個下標if(i==nowright){//步數+1，從而才能繼續向前nowright=maxright;ans++;}}return ans;}
};

2 LeetCode763.劃分字母區間

2.1 題目描述

??給定一個字符串s，將字符串劃分為盡可能多的片段，同一字母最多出現在一個片段中。如s="ababcc"，則最終的劃分結果為["abab","cc"]。返回表示每個字符串片段的長度的列表。
??一個示例如下：

2.2 問題分析及解決

??貪心的思想，從第一個字母開始遍歷，定義指針left指向劃分的最左邊，right指向劃分的最右邊，因此right要更新為遍歷字母中最后出現的位置的最大值，直到遍歷位置與right相等，說明left和right之間就是一個劃分。更新left=right+1，繼續上述操作即可。
??具體實現如下：

class Solution {
public:vector<int> partitionLabels(string s) {vector<int> ans;int end_char[26];//記錄每個字母最后出現的位置for(int i=0;i<s.length();i++){end_char[s[i]-'a']=i;}//記錄遍歷過程中每個字母最后一次出現的位置int right=0;//劃分的左邊int left=0;//劃分的右邊int partition=-1;for(int i=0;i<s.length();i++){right=end_char[s[i]-'a'];//劃分右邊為遍歷字母最后一次出現位置的最大值partition=max(partition,right);//如果遍歷到劃分位置，則說明是一個劃分if(i==partition){ans.push_back(partition-left+1);left=right+1;}}return ans;}
};