Eg.贪心法，钞票支付问题
有1元、5元、10元、20元、100元、200元的钞票无穷多张。现使用这些钞 票支付X元，最少需要多少张?
例如，X = 628
最佳支付方法: 3张200块的，1张20块的，1张5块的，3张1块的; 共需要3+1+1+3=8张。
直觉告诉我们:尽可能多的使用面值较大的钞票!
贪心法: 遵循某种规律，不断贪心的选取当前最优策略的算法设计方法。
分析：面额为1元、5元、10元、20元、100元、200元，任意面额是比自己小的面额的倍数关系。 所以当使用一张较大面额钞票时，若用较小面额钞票替换，一定需要更多的其他面额的钞票!
#include<stdio.h>
int main(){
const int RMB[]= {200,100,20,10,5,1};
const int NUM = 6;//6种面值
int X = 628;
int count = 0;
for(int i= 0;i< NUM;i++){
int use = X / RMB[i];需要面额为RMB[i]的use张
count + = use；
X = X -RMB[i] * use;
printf("需要面额为%d 的%d张",RMB[i],use);
printf("剩余需要支付金额%d.\n",X);
}
printf("总共需要%d张\n",count);
return 0;
}
分糖果
已知一些孩子和一些糖果，每个孩子有需求因子g，每个糖果有大小s，当 某个糖果的大小s >= 某个孩子的需求因子g时，代表该糖果可以满足该孩子;求使用这 些糖果，最多能满足多少孩子?(注意，某个孩子最多只能用1个糖果满足)
例如，需求因子数组g = [5, 10, 2, 9, 15, 9];糖果大小数组s = [6, 1, 20, 3, 8];最多可以 满足3个孩子。
贪心规律
需求因子数组 g = [2, 5, 9, 9, 10, 15];糖果大小数组 s = [1, 3, 6, 8, 20]。
核心目标:让更多孩子得到满足，有如下规律:
1.某个糖果如果不能满足某个孩子，则该糖果也一定不能满足需求因子更大的孩子。 如，
糖果1(s = 1)不能满足孩子1(g = 2)，则不能满足孩子2、孩子3、...、孩子7;
糖果2(s = 3)不能满足孩子2(g = 5)，则不能满足孩子3、孩子4、...、孩子7;
2.某个孩子可以用更小的糖果满足，则没必要用更大糖果满足，因为可以保留更大的糖果
满足需求因子更大的孩子。(贪心!) 如，
孩子1(g = 2)，可以被糖果2(s = 3)满足，则没必要用糖果3、糖果4、糖果5满足; 孩子2(g = 5)，可以被糖果3(s = 6)满足，则没必要用糖果4、糖果5满足;
3.孩子的需求因子更小则其更容易被满足，故优先从需求因子小的孩子尝试，可以得到正 确的结果。
算法思路
1.对需求因子数组g与糖果大小数组s进行从小到大的排序。
2.按照从小到大的顺序使用各糖果尝试是否可满足某个孩子，每个糖果只尝试1次;若尝试成功，则换下一个孩子尝试;直到发现没更多的孩子或者没更多的 糖果，循环结束。
#include<vector>
#include<algorithm>
class Solution{
public:
int findContentChildren(std::vector<int>& g,std::vector<int> & s){
std::sort(g.begin() , g.end());
std::sort(s.begin(), s.end());//对孩子的需求因子g与糖果大小s俩组数组排序
int child = 0;
int cookie = 0;//child代表满足了几个孩子，cookie代表尝试了几个糖果
while(cookie<=s.size() && child< g.size()){
if(g[child] <= s[cookie]){
child ++;
}
cook ++ ;// 无论成功与否，每个糖果只尝试一次，cookie向后一动
}
}
};
测试与leetcode提交
int main(){
Solution solve;
std::vector<int> s;
std::vector<int> g;
g.push_back(5);
g.push_back(10);
g.push_back(2);
g.push_back(9);
g.push_back(15);
g.push_back(9);
s.push_back(6);
s.push_back(1);
s.push_back(20);
s.push_back(3);
s.push_back(8);
printf("%d\n",solve.findContenChildren)
}
摇摆序列
一个整数序列，如果两个相邻元素的差恰好正负(负正)交替出现，则该序列被称为摇摆序列。一个小于2个元素的序列直接为摇摆序列。
例如:
序列 [1, 7, 4, 9, 2, 5]，相邻元素的差 (6, -3, 5, -7, 3)，该序列为摇摆序列。 序列 [1,4,7,2,5] (3, 3, -5, 3)、 [1,7,4,5,5] (6, -3, 1, 0)不是摇摆序列。
给一个随机序列，求这个序列满足摇摆序列定义的最长子序列的长度。
例如: 输入[1,7,4,9,2,5]，结果为6;输入[1,17,5,10,13,15,10,5,16,8]，结果为7([1,17,10,13,10,16,8] );输入[1,2,3,4,5,6,7,8,9]，结果为2。
LeetCode 376. Wiggle Subsequence
[1, 17, 5, 10, 13, 15, 10, 5, 16, 8]，整体不是摇摆序列: 观察该序列前6位:[1, 17, 5, 10, 13, 15...] ; 橙色部分为上升段:
其中它有3个子序列是摇摆序列: [1, 17, 5, 10, ...]
[1, 17, 5, 13, ...]
[1, 17, 5, 15, ...]
贪心规律
当序列有一段连续的递增(或递减)时，为形成摇摆子序列，我们只需要 保留这段连续的递增(或递减)的首尾元素，这样更可能使得尾部的后一个元素成为摇摆子序列的下一个元素。
算法设计
设置最长摇摆子序列长度max_length，从头至尾扫描原始序列。这个过程中 设置三种状态，即起始、上升、下降;不同的状态中，根据当前数字与前一个数字 的比较结果进行累加max_length计算或者状态切换。
#include<vector>
class Solution{
public:
int wiggleMaxLength(std::vector<int> & nums){
if(nums.size() < 2){
return num.size();//序列个数小于2时直接为摇摆序列
}
static const int BEGIN = 0;
static const int UP = 1;
static const int DOWN = 2;//扫描序列时的三种状态
int STATE = BEGIN;
int max_length = 1;//摇摆序列最大长度至少为1；
for(int i =1; 1<num.size();i++){
switch(STATE){
case BEGIN:
if(nums[i]>nums[i-1]){
STATE = UP;
max_length++;
}
else if(nums[i] < nums[i-1]){
STATE = DOWN;
max_length++
}
break;
case UP:
if(nums[i]>nums[i-1]){
STATE = DOWN;
max_length++;
}
break;
case DOWN:
if(nums[i] < nums[i-1]){
STATE = UP;
max_length++;
}
break;
}
}
return max_length;
}
};
网友评论