贪心
2022/6/4 23:20:19
本文主要是介绍贪心,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
概念:
1.整体与局部,贪心算法以局部最优解为目的,做出局部上的最佳选择,希望以此来得到,整体的最优解。
2.贪心算法的难点在于 【 证明 】 ,你怎么知道局部最优,就是整体最优的?有时候,可能只是想当然。
3.贪心和动态规划,目的都是取得最优解,不一定哪个难,因为,贪心压根就没固定解法,,,挺玄学。
例题1 最值贪心:
给定字符串NUM,求,NUM中,所有非空子字符串的,最大奇数
以字符串类型返回,没找到回空
char * largestOddNumber(char * num){
int i; // (1)
int len = strlen(num); // (2)
for(i = len-1; i >= 0; --i) { // (3)
if((num[i] - '0') & 1) { // (4)
num[i+1] = '\0'; // (5)
return num; // (6)
}
}
num[i+1] = '\0'; // (7)
return num;
}
代码1.1最值贪心
从后往前遍历,找最先发现的奇数
***
例题2 分割贪心
给定一个字符串,这个字符串中,含有相同数量的,‘L','R' ,称这个字符串为【平衡字符串】
尽可能多的分割这个字符串,求,最多能得到多少平衡字符串
int balancedStringSplit(char * s){
int i;
int sum = 0; // (1)
int ans = 0; // (2)
for(i = 0; s[i]; ++i) {
sum += (s[i] == 'L') ? 1 : -1; // (3)
if(sum == 0) {
++ans; // (4)
}
}
return ans; // (5)
}
代码1.2分割贪心
定义一个计数器,出现一对L,R,就+1
例题3:排序贪心
给定一个长度小于1000的,非负整数数组,求这个数组中,最多能,组成多少个三角形。
int cmp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
int triangleNumber(int* nums, int numsSize){
int i, j, k;
int ans = 0;
qsort(nums, numsSize, sizeof(int), cmp); // (1)
for(i = 0; i < numsSize; ++i) {
j = i + 1;
k = j + 1; // (2)
while(j < numsSize) {
while(k < numsSize) {
if(nums[i] + nums[j] <= nums[k]) {
break; // (3)
}
++k;
}
ans += k-j-1; // (4)
++j; // (5)
if(k == j) k++;
}
}
return ans;
}
代码1.3排序贪心
练习题1 玩筹码 1217
class Solution: def minCostToMoveChips(self, position: List[int]) -> int:cost = 65533 mincost = 65533 for i in range(len(position)): cost = 0 for j in range(len(position)): if(position[j] - position[i] & 1): cost += 1 mincost = min(mincost,cost); return mincost 奇偶相同的抵消,剩下的加起来。
这篇关于贪心的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)