贪心算法思想和题解

今天的内容是贪心算法

贪心算法思想

贪心思想就是，每次在局部取最优解，最后整体就应该是最优解。有时候贪心会失效。

举个例子：这里有很多堆饼干和很多个小孩子，每个小孩子有一个饥饿度，只有当吃到的饼干数大于等于饥饿度，小孩子才会饱，请你用这几堆饼干喂饱最多的孩子，利用贪心思想就是，每次选最优解，将每堆饼干按照数目进行升序排序，将小孩子按照饥饿度进行升序排序，然后遍历小孩子的饥饿度，和饼干数，先用最少的饼干喂饱饥饿度最小的孩子，直到饼干不足以喂饱那个饥饿度较大的孩子的时候，就得到了一个最优解。

最值贪心

思想是，每次取最大值或者最小值，使得总体更接近你所要求的结果。每部分都是最大或最小，总体就是最大或最小，但是你有时候很难证明。

分割贪心

思想是：使用一个标准来分割问题，满足该标准进行一次分割。例如求平衡字符串问题，要求平衡度为0，就是平衡状态，那就用这个状态分割。每次满足就记一次。

排序贪心

思想是：先将数组排序，然后按照题目要求，选取最优解即可。
举例：给定一个数组，求出数组内所有元素，能组成的最多的三角形的个数。
思想是：先将数组排序，然后定义i，j ，k，分别代表三条边，用三层循环，因为三角形满足i+j>k,所以当i+j<= k之后就跳出第三层循环，然后记录这之间二元组的个数。

1221. 分割平衡字符串

思想：定义一个平衡度，然后如果是L那平衡度+1，不是那就-1，平衡度为0，即是一个平衡字符串，计数器+1；

int balancedStringSplit(char * s){
    int ever = 0;
    int count = 0;
    int len = strlen(s);
    for(int i =0;i<len;i++)
    {
        ever += (s[i]=='L')?1:-1;
        if(ever ==0)
        {
            count++;
        }
    }
    return count;
}

1217. 玩筹码

思想：统计奇数位置和偶数位置的筹码分别有多少，因为从偶数位置移动到奇数位置cost为1，从奇数位置移动到偶数位置消耗也是cost，所以偶数少我们就选择移动偶数，奇数少就移动奇数，这就是最优解。

int minCostToMoveChips(int* position, int positionSize){
    int odd = 0;
    int even = 0;
    for(int i =0;i<positionSize;i++)
    {
        if(position[i]&1)
        {
            odd++;
        }
        else
        {
            even++;
        }
    }
    return odd<even?odd:even;
}

1029. 两地调度

思路是：假设所有人先去b市，花费priceb，如果有n个人不去b市区a市那么花费就是 pricea - priceb。就将数组按照pricea-priceb排序，这个表达式相当于，去a市比去b市更有性价比对于总花费来说。所以数组前n个就去a市，后n个就去b市

//第一种写法。
int cmp(const void** str1,const void** str2)
{
    return ((*(int**)str1)[0] - (*(int**)str1)[1]) - ((*(int**)str2)[0] - (*(int**)str2)[1]);
}

int twoCitySchedCost(int** costs, int costsSize, int* costsColSize){
    int sum = 0;
    qsort(costs,costsSize,sizeof(int*),cmp);
    for(int i =0;i<costsSize;i++)
    {
        if(i<costsSize/2)
        {
            sum+=costs[i][0];
        }
        else
        {
            sum+=costs[i][1];
        }
    }
    return sum;
}

//第二种写法，就是先求出所有人去b市的金额总和，然后再将n人分配到a市，这些人不用去b市，直接去a市，总金额就-priceb然后+pricea。
int cmp(const void** str1,const void** str2)
{
    return ((*(int**)str1)[0] - (*(int**)str1)[1]) - ((*(int**)str2)[0] - (*(int**)str2)[1]);
}

int twoCitySchedCost(int** costs, int costsSize, int* costsColSize){
    int sum = 0;
    for(int i =0;i<costsSize;i++)
    {
        sum+=costs[i][1];
    }
    qsort(costs,costsSize,sizeof(int*),cmp);
    for(int i =0;i<costsSize/2;i++)
    {
        sum+=costs[i][0]-costs[i][1];
    }
    return sum;
}

思想总结，其实就是先将去不同城市花费差别大的先分配，让他们去花钱少的那个城市，剩下的去两个城市花费都差不多的就去人数不够的城市。

面试题 10.11. 峰与谷

先排序，然后第一次选最小，第二次选最大，两个指针遍历数组，向中间移动即可。要注意两个指针相等的时候，就特殊处理，最后将数组拷贝回去。

int cmp(const void* str1,const void* str2)
{
    return *(int*)str1 - *(int*)str2;
}

void wiggleSort(int* nums, int numsSize){
    if(numsSize==0)
    return;
    int ans[numsSize];
    int left = 0;
    int right = numsSize-1;
    int i =0;
    qsort(nums,numsSize,sizeof(int),cmp);
    while(left<right)
    {
        ans[i++] = nums[left++];
        ans[i++] = nums[right--];
    }
    if(left ==right)
    {
        ans[i] = nums[left];
    }
    memcpy(nums,ans,sizeof(int)*numsSize);
}

补充：题解
1400. 构造 K 个回文字符串

思路：用所有字符，构造回文串，当然最多是长度len个啦，这就是定义为回文串的右边界，最少次数，根据观察发现，如果所有字符都出现偶数次，那么最少就是1个，也就是奇数个数为0，如果奇数出现1次，就需要把这个奇数个字符放到一个回文串中心，所有奇数字符有几个，回文串就最少有几个。这个左边界就是奇数次字符的个数，如果为0，就是1.

bool canConstruct(char * s, int k){
    int hash[26] = {0};
    int odd = 0;
    int len = strlen(s);
    for(int i =0;i<len;i++)
    {
        ++hash[s[i]-'a'];
    }
    for(int j = 0;j<26;j++)
    {
        if(hash[j]&1)
        {
            odd++;
        }
    }
    odd = odd>1?odd:1;
    return k>=odd && k<=len;
}