均安建网站,免费网页设计作业文件,成都铁路局贵阳建设指挥部网站,wordpress添加关键词插件1.什么是贪心#xff1f; 比如10张钞票#xff0c;有1#xff0c;5#xff0c;20#xff0c;100等面额#xff0c;取五张#xff0c;如何取得到数额最多的钱#xff1f;每次取面额最大的那张钞票#xff1b;就是每个阶段的局部最优#xff1b;全局最优就是最后拿到的…1.什么是贪心 比如10张钞票有1520100等面额取五张如何取得到数额最多的钱每次取面额最大的那张钞票就是每个阶段的局部最优全局最优就是最后拿到的钞票数最大局部最优推出全局最优 题目描述
int cmp(const void *a,const void *b)
{return *(int *)(a) - *(int *)(b);
}int findContentChildren(int* g, int gSize, int* s, int sSize){// 找最大的饼干去喂胃口最大的孩子 这样不会浪费// 两个数组进行排序qsort(g,gSize,sizeof(int),cmp);qsort(s,sSize,sizeof(int),cmp);int right1 gSize-1;int right2 sSize-1;int count 0;//记录投喂的孩子while(right1 0 right2 0){if(s[right2] g[right1]){count;right1--;right2--;}else{right1--;}}return count;
}题目描述
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){// 下标 0 1 2 3 4// gas 1 2 3 4 5// cos 3 4 5 1 2// cur -2 -2 -2 4 3 (净增) 如果是负数不可能走完一圈只能从下标3不是负数开始才能跑完一圈int cur 0; //每一站剩余的油量int totalSum 0;//所有剩余油量之和 0 不可能跑完一圈int start 0;// 记录cur不是负数的下标for(int i 0;i gasSize;i){cur (gas[i] - cost[i]);totalSum (gas[i] - cost[i]);if(cur 0){start i1;cur 0;//新起点剩余油量归0.重新统计}}if (totalSum 0){return -1;}return start;
}题目描述 分析摆动序列就是前后相减保证一正一负对于复杂的序列比如1175101315105168 对于这种我们只需要记录坡顶和坡底元素中间的101310可以忽略 prediff nums[i] - nums[i-1]; 表示前一个坡度 curdiff nums[i1] - nums[i];;表示后一个坡度 如果 prediff 和 curdiff 一正一负prediff 0 curdiff 0 || prediff 0 curdiff 0表示找到了一个峰值计数 细节分析 1上下坡有平坡1 2 2 2 1 摆动长度应该是3 1 2 1前面加上prediff 或者 curdiff 加等于号即可prediff 0 curdiff 0 || prediff 0 curdiff 0 2首尾元素首尾元素默认都算但是长度为2的时候需要前面加一个元素使有prediff符合我们上面判断逻辑末尾元素我们当作是一个摆动所以res 1,就是末尾的一个 3单调有平坡 1 2 2 4 5 只有两个摆动 每次找到摆动数后prediff curdiff prediff向前移动
int wiggleMaxLength(int* nums, int numsSize){int res 1;if (numsSize 1) {return res;}int prediff 0; // nums[i] - nums[i-1]int curdiff 0; // nums[i1] - nums[i]for (int i 0;i numsSize - 1;i) {// i遍历到倒数第二个curdiff nums[i1] - nums[i];if ((prediff 0 curdiff 0) || (prediff 0 curdiff 0)){res;prediff curdiff;// 只记录变化的坡度遇到摆动记录下一个坡就是遇到平坡不会记录}}return res;
}
