贪心算法简介

贪心算法简介

贪心算法是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而试图获得结果是全局最优的算法。它并不保证在所有情况下都能得到全局最优解，但适用于具有“贪心选择性质”的问题，即局部最优解能导致全局最优解。

例题1：盛最多水的容器

问题描述
给定一个长度为n的整数数组height，每个元素表示垂直线的长度。找出两条线与 x 轴共同构成的容器可以容纳最多的水。容器不能倾斜。

思路讲解
使用双指针法，从数组两端开始。容量由指针间距和较短线的高度决定。贪心策略：每次移动较短线的指针，因为移动较长线不会增加容量（宽度减小，高度受限于短线）。重复直到指针相遇，记录最大容量。

C语言代码实现

intmaxArea(int*height,intheightSize){intleft=0,right=heightSize-1;intmax_water=0;while(left<right){inth=height[left]<height[right]?height[left]:height[right];intwater=h*(right-left);if(water>max_water)max_water=water;if(height[left]<height[right]){left++;}else{right--;}}returnmax_water;}

leetcode原题

例题2：最长回文串

问题描述
给定一个字符串s，用其中的字符构造最长的回文串，返回最大长度。注意：字符可以任意顺序排列，但回文串需对称。

思路讲解
统计每个字符的出现频率。贪心策略：对于每个字符，如果出现偶数次，全部使用；如果出现奇数次，使用偶数部分（即减1），并标记存在奇数字符。最后，如果有奇数字符，长度加1（中心可放一个奇数字符）。

C语言代码实现

intlongestPalindrome(char*s){intcount[128]={0};intlen=strlen(s);for(inti=0;i<len;i++){count[(int)s[i]]++;}intmaxlen=0;inthasodd=0;for(inti=0;i<128;i++){if(count[i]%2==0){maxlen+=count[i];}else{maxlen+=count[i]-1;hasodd=1;}}if(hasodd)maxlen+=1;returnmaxlen;}

leetcode原题

总结

贪心算法适用于局部最优能导致全局最优的问题，如以上例题。在实际应用中，需验证问题是否具有贪心性质，否则可能需动态规划等其他方法。