力扣（763.56）补9.27
763.划分字母区间
怎么说呢，说是贪心，我依然感受不到。。。
这题难度正常，能做出来，我也没优化时间复杂度，问就是不太会，hhhhh只做了200题的小chicken。
class Solution {
public:
vector<int> partitionLabels(string s) {
int hash[26]={0};
vector<int> a;
for(int i=0;i<26;i++)
hash[i]=-1;
for(int i=0;i<s.size();i++){
hash[s[i]-'a']=i;
}
int left=0,right=0;
while(right<s.size()&&left<s.size()){
right=hash[s[left]-'a'];
for(int i=left;i<=right;i++){
right=max(hash[s[i]-'a'],right);
// printf("%d ",right-left+1);
}
a.push_back(right-left+1);
left=right+1;
}
return a;
}
};
56.合并区间
我是把他当滑动窗口做的。
这题基本思路倒是容易有，但是细节问题还是有tm的一大堆。还好力扣会提供未过的用例，要不然真的不知道哪里会错。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int left=0,right=0,i=0;
vector<vector<int>> ans;
int len=intervals.size();
sort(intervals.begin(),intervals.end());
left=intervals[0][0];
right=intervals[0][1];
// if(intervals.size()==1){
// ans.push_back({left,right});
// return ans;}
if(i==len-1){
ans.push_back({left,right});
return ans;
}
while(i<len-1){
if(len-1&&right>=intervals[i+1][1]){
i++;
if(i==len-1){
ans.push_back({left,right});
}
}
else if(i<len-1&&right>=intervals[i+1][0]){
i++;
right=intervals[i][1];
if(i==len-1){
ans.push_back({left,right});
}
}
else if(i<len-1&&right<intervals[i+1][0]){
ans.push_back({left,right});
// printf("%d %d\\n",left,right);
i++;
left=intervals[i][0];
right=intervals[i][1];
if(i==len-1){
ans.push_back({left,right});
}
}
}
return ans;
}
};
