以下题目均来自leetcode、poj
分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
注意：
你可以假设胃口值为正。 一个小朋友最多只能拥有一块饼干。
示例 1:
输入: [1,2,3], [1,1]
输出: 1
解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。 所以你应该输出1。 示例 2:
输入: [1,2], [1,2,3]
输出: 2
解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出2.
/*
1.胃口列表和饼干列表小到大排序
2.按照从小到大的顺序使用饼干尝试是否满足某个孩子胃口，每个
饼干只尝试一次，若成功，换一下孩子。只到没有饼干或没有孩子结束。
*/
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
std::sort(g.begin(),g.end());
std::sort(s.begin(),s.end());
int child = 0;
int cookie = 0;
while(child < g.size() && cookie < s.size()){
if(g[child] <= s[cookie]){
child++;
}
cookie++;
}
return child;
}
};
摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 1:
输入: [1,7,4,9,2,5] 输出: 6 解释: 整个序列均为摆动序列。 示例 2:
输入: [1,17,5,10,13,15,10,5,16,8] 输出: 7 解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。 示例 3:
输入: [1,2,3,4,5,6,7,8,9] 输出: 2 进阶: 你能否用 O(n) 时间复杂度完成此题?
/*
连续递增或递减序列中贪心取最大的或者最小的。
*/
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int total = nums.size();
if(total < 2){
return total;
}
static const int BEGIN = 0;
static const int UP = 1;
static const int DOWN = 2;
int state = BEGIN;
int max_length = 1;
for(int i = 1;i < total;i++){
int pre = nums[i-1];
int cur = nums[i];
switch(state){
case BEGIN:
if(pre < cur){
state = UP;
max_length++;
}else if(pre > cur){
state = DOWN;
max_length++;
}
break;
case UP:
if(pre > cur){
state = DOWN;
max_length++;
}
break;
case DOWN:
if(pre < cur){
state = UP;
max_length++;
}
break;
}
}
return max_length;
}
};
移掉K位数字
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 示例 1 :
输入: num = “1432219”, k = 3 输出: “1219” 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。 示例 2 :
输入: num = “10200”, k = 1 输出: “200” 解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。 示例 3 :
输入: num = “10”, k = 2 输出: “0” 解释: 从原数字移除所有的数字，剩余为空就是0。
/*
去掉一个数字后，尽可能让最高位最小，次高位最小，依次下去。
*/
class Solution {
public:
string removeKdigits(string num, int k) {
std::vector<int> s;
std::string result = "";
for(int i = 0;i < num.length();i++){
int number = num[i]- '0';
while(s.size() != 0 && s[s.size()-1] > number && k > 0){
s.pop_back();
k--;
}
if(number != 0 || s.size() != 0){
s.push_back(number);
}
}
while(s.size() != 0 && k > 0){
s.pop_back();
k--;
}
for(int i = 0;i < s.size();i++){
reuslt.append(1,s[i]+'0');
}
if(result == ""){
result = "0";
}
return result;
}
};
跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4] 输出: true 解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。 示例 2:
输入: [3,2,1,0,4] 输出: false 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
class Solution {
public:
bool canJump(vector<int>& nums) {
std:vector<int> index;
for(int i = 0;i< nums.size();i++){
index.push_back(i + nums[i]);
}
int jump = 0;
int max_index = index[0];
while(jump < index.size() && jump <= max_index){
if(max_index < index[jump]){
max_index = index[jump];
}
jump++;
}
if(jump == index.size()){
return true;
}
return false;
}
};
跳跃游戏 II
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 说明:
假设你总是可以到达数组的最后一个位置。
/*
某点i可以跳到最大位置current_max_index之间有个点pre_max_index可以跳的更远，找到后更新跳到更远
*/
class Solution {
public:
int jump(vector<int>& nums) {
if(nums.size() < 2){
return 0;
}
int current_max_index = nums[0];
int pre_max_index = nums[0];
int jump_min = 1;
for(int i = 1;i < nums.size();i++){
if(current_max_index < i){
jump_min++;
current_max_index = pre_max_index;
}
if(pre_max_index < nums[i] + i){
pre_max_index = nums[i] + i;
}
}
return jump_min;
}
};
用最少数量的箭引爆气球
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。
一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
Example:
输入: [[10,16], [2,8], [1,6], [7,12]]
输出: 2
解释: 对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。
/*
1.气球左端点从小到大排序
2.尽可能一次穿多个气球
*/
bool compare(const std::pair<int,int>&a,const std::pair<int,int>&b){
return a.first < b.first;
}
class Solution {
public:
int findMinArrowShots(vector<std::pair<int,int>>& points) {
if(points.size() == 0){
return 0;
}
std::sort(points.begin(),points.end(),compare);
int shootNum = 1;
int shootBegin = points[0].first;
int shootEnd = points[0].second;
for (int i = 1; i < points.size();i++){
if(points[i].first <= shootEnd ){
shootBegin = points[i].first;
if(points[i].second < shootEnd){
shootEnd = points[i].second;
}
}else{
shootNum++;
shootBegin = points[i].first;
shootEnd = points[i].second;
}
}
return shootNum;
}
};
##### [最优加油](http://poj.org/problem?id=2431)
已知有一条公路上有起点和终点距离为L，之间有n个加油站，n个加油站到终点的距离为d，各个加油站加油量为l
起点车油箱有油P，设一个单位油走一个单位距离，油箱没有上限，最少加几次油，能开到终点吗？
```c
bool compare(const std::pair<int,int>&a,const std::pair<int,int>&b){
return a.first > b.first;
}
int getMinStop(int L,int P,vector<pair<int,int>> &stop){//pair<加油站到终点距离,加油站油量>
std::priority_queue<int> Q;//最大堆存储油量
int reuslt = 0;
stop.push_back(std::make_pair(0,0));//终点
std::sort(stop.begin(),stop.end(),compare);//停靠点到终点距离 大到小排序
for (int i = 0; i < stop.size();i++){
int dis = L - stop[i].first;//要走的距离
while(!Q.empty() && P < dis){ //有加油站油加且车的油不够走
P += Q.top();
Q.pop();
result++;
}
if(Q.empty() && P < dis){
return -1;
}
P -= dis;
L = stop[i].first;//更新L为加油站到终点距离
Q.push(stop[i].second);//加油站油量添加到最大堆
}
return result;
}
