贪心续
加油站
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
思路： 是要遍历整个加油站，从这个加油站能否回到加油站。所以这边有一个循环数组的遍历
代码
int res = -1 ;
for(int i = 0 ; i< gas.size() ; ++ i )
{
int idx = (i % gas.size()) ; // 数组转换为循环数组只需 对数组的大小取模 。
int flag = 0 ; // 作为退出的标志
int left = 0 ;
while(idx != i || flag == 0 )
{
if(left + gas[idx] - cost[idx] >=0)
{
left = left + gas[idx] - cost[idx] ;
cout<<left<<endl ;
}
else
{
break ;
}
idx = (idx+1) % gas.size() ;
if(idx == i && left>= 0 )// 如果到达的下一站是i
{
flag = 1 ;
res = i ;
return res ;
}
}
}
return res ;
分发糖果
是将n个孩子站成一排。和一个rating数组表示每个孩子的评分。
相邻的两个孩子，评分更高的孩子获得更多糖果
从左到右进行一个计算（给孩子分糖果 ）。
和从右到左的（给孩子分糖果。 ）
当然也可以调换顺序 。
局部最优：分数越高的糖果越多。全局最优 评分最高的有最多的糖果
代码
vector<int> nums ;
nums.resize(ratings.size()) ;
for(int i = 0 ; i < nums.size() ; ++ i)
{
nums[i] = 1 ;
}
for(int i = ratings.size() -2; i >=0 ;--i)
{
if(ratings[i] > ratings[i+1]) // 从左到右的依次计算
{
nums[i] = nums[i + 1] + 1 ;
}
}
for(int i = 1 ; i< ratings.size() ; ++i)
{
if(ratings[i] > ratings[i - 1 ]) // 从右到左依次计算 。
{
// nums[i] = max(nums[i] , nums[i-1]+1) ; 还要进行
if(nums[i] > nums[i-1])
{
}
else
{
nums[i] = nums[i-1] +1 ;
}
}
}
int _sum = 0 ;
for(int i = 0 ; i< nums.size() ;++ i)
{
_sum += nums[i] ;
}
return _sum ;
柠檬水找零
思路：使用数组下标代表钱币。 之后按照常理 计算 ； 但是在收到
20美元时要找零的话就 先找10 ， 5 因为 10作为找零的用处没有5块大
代码
vector<int> getmon ;
getmon.resize(25) ;
getmon.clear() ;
for(int i = 0 ; i < bills.size() ; ++ i)
{
if(bills[i] == 5)
{
getmon[5] +=1 ;
}
else if(bills[i] == 10)
{
getmon[10] += 1 ;
if(getmon[5]>0)
{
getmon[5] -- ;
}
else
{
return false ;
}
}
else if(bills[i] == 20)
{
getmon[20] ++ ;
if(getmon[5]> 0 )
{
getmon[5] -- ;
if(getmon[10]> 0 ) // 先把 10 元减了 相对来说对找零没有价值
{
getmon[10] -- ;
}
else
{
if(getmon[5] >=2)
{
getmon[5] -= 2 ;
}
else
return false ;
}
}
else // 5元没有了
{
return false ;
}
}
}
return true ;
根据身高重建队列
题意是将打乱的身高排序， ki是这个人之前有ki个大于或等于 hi 的人。
思路
先进行身高从大到小排序。之后对同一身高的人进行从小到大排序。 因为要解答的话就需要这样排序。 由于ki相当于位置 所以排序后采用插入的方法进行插入
struct comp
{
bool operator()( vector<int> lhs , vector<int> rhs)
{
if(lhs[0] == rhs[0]) return lhs[1] < rhs[ 1] ; // 如果 在两 身高相等的情况， 按照k排序 。
return lhs[0]>rhs[0] ;
}
} ;
vector<vector<int>> reconstructQueue(vector<vector<int>>& people)
{
sort(people.begin() , people.end() , comp() ) ;
// 按照k的大小进行插入
vector<vector<int>> res ;
for(int i = 0 ; i < people.size() ; ++ i )
{
int pos = people[i][1] ; // 将其插入到相应的位置。
res.insert(res.begin() + pos , people[i] );
}
return res ;
}
用最少数量的箭引爆气球
题意是求最少交集的数量 。 那么就需要元素尽可能多的重叠。 这是贪心的所在。
这是用迭代法去求是否是交集。
如果前面的元素和后面的元素没有交集， 那么就需要一支箭去射 。
所以判断前后两个元素没有交集后就增加一支箭。 并且要更新最小右边界。 以便下一迭代使用。
代码
int res = 1 ;
sort(points.begin() , points.end() , comp()) ;
for(int i = 1; i < points.size() ;++ i)
{
if(points[i-1][1]< points[i][0])
{
res++ ;
}
else
{
points[i][1] = min(points[i-1][1], points[i][1]) ;
}
}
return res ;
无重叠区间
仔细想一下：这个跟上一题的联系。 这个是要找到最少要移除的重复区间。等价于去找最多不重叠的区间的个数 。 所以只需要在上一题修改一下代码就好 :主要是将 重叠重定义下，重叠不包括连接点。
sort(intervals.begin() , intervals.end() , comp()) ;
int res = 1 ; // 最大不重叠区域。
for(int i = 1 ; i < intervals.size() ; ++ i)
{
if(intervals[i-1][1] <= intervals[i][0])
{
res++ ;
}
else
{
intervals[i][1] = min(intervals[i-1][1] , intervals[i][1]) ;
}
}
return intervals.size() - res ;
划分字母区间
题意是我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。也就是找到出现最远的字符 如果到达这个字符那么就分割。
核心代码
vector<int> res ;
res.clear() ;
int ch[27] ; // 记录每个元素出现的最远的位置 。
for(int i = 0 ; i < s.size() ; ++ i )
{
ch[s[i] - 'a'] = i ;
}
// 怎么 划分 。 一个left , right 是求片段的长度 。
int left = 0 , right = 0 ;
for(int i = 0 ; i < s.size() ; ++ i)
{
right = max(right , ch[s[i] - 'a']) ; // 求得到的最远的距离
if(i == right)
{
int len = right - left +1 ;
res.push_back(len) ;
left = i+1 ;
}
}
return res ;
