leetcode——贪心题 c语言

一 、

在一个 平衡字符串 中，L 和 R 字符的数量是相同的。

给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。

注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。

返回可以通过分割得到的平衡字符串的 最大数量 。

int balancedStringSplit(char * s){
    int ret=0;
    int cout=0;
    for(int i=0;i<strlen(s);i++){
        if(s[i]==L) cout++;
        if(s[i]==R) cout--;
        if(cout==0) ret++; 
    }
    return ret;
}

思路：定义一个cout 记录L（+1） R（-1） 因为为最大数量 每当 cout 为0时 说明平衡 则可以ret++。

二 、

有 n 个筹码。第 i 个芯片的位置是 position[i] 。

我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 i 个芯片的位置从 position[i] 改变为:

position[i] + 2 或 position[i] - 2 ，此时 cost = 0 position[i] + 1 或 position[i] - 1 ，此时 cost = 1 返回将所有筹码移动到同一位置上所需要的 最小代价 。

int minCostToMoveChips(int* position, int positionSize){
    int ret;
    int min=100000;
    for(int i=0;i<positionSize;i++){
        ret=0;
        for(int j=0;j<positionSize;j++){
            if((position[i]-position[j])%2!=0) ret++; 
    }
    if(min>ret) min=ret;
}
        return min;
}

思路：我是这样理解的 首先你只要是我的偶数倍就不需要付出代价 所以可以随便在偶数倍上移动移动。奇数同理移动但肯定要付出代价，那么 就可以遍历 所有数组 每个元素作为初值的最小代价。

三 、

公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [aCosti, bCosti] 。第 i 人飞往 a 市的费用为 aCosti ，飞往 b 市的费用为 bCosti 。

返回将每个人都飞到 a 、b 中某座城市的最低费用，要求每个城市都有 n 人抵达。

输入：costs = [[10,20],[30,200],[400,50],[30,20]] 输出：110 解释： 第一个人去 a 市，费用为 10。 第二个人去 a 市，费用为 30。 第三个人去 b 市，费用为 50。 第四个人去 b 市，费用为 20。

最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。

int twoCitySchedCost(int** costs, int costsSize, int* costsColSize){
    int ret=0;
    for(int i=0;i<costsSize;i++){
        for(int j=0;j<costsSize-1-i;j++){
            if((costs[j][1]-costs[j][0])>(costs[j+1][1]-costs[j+1][0])){
                int t=costs[j+1][0],y=costs[j+1][1];
                costs[j+1][0]=costs[j][0]; costs[j][0]=t;
                 costs[j+1][1]=costs[j][1]; costs[j][1]=y;

            }
        }
    }
    for(int i=0;i<costsSize;i++){
        if(i<costsSize/2) ret+=costs[i][1];
        else ret+=costs[i][0];
    }
    return ret;
}

思路： 先理解题的意思 a b两地都需要去n个人；要求最小的费用，用一个元素b-a的费用差，用来排序 说明 b相比后面之后一半的b 性价更高，所以前一半加b,后一半加a。

四 、

在一个整数数组中，“峰”是大于或等于相邻整数的元素，相应地，“谷”是小于或等于相邻整数的元素。例如，在数组{5, 8, 4, 2, 3, 4, 6}中，{8, 6}是峰， {5, 2}是谷。现在给定一个整数数组，将该数组按峰与谷的交替顺序排序。

int comp(const void*a,const void*b){
    return *(int *)a<*(int *)b;
}
void wiggleSort(int* nums, int numsSize){
    int s[100000];
    qsort(nums,numsSize,sizeof(int),comp);
    int l=0,r=numsSize-1,i=0;
    while(l<r){
        s[i++]=nums[r--];
        s[i++]=nums[l++];
    }
    if(l==r) s[i]=nums[l];
    for(int i=0;i<numsSize;i++){
        nums[i]=s[i];
    }
}

思路 ： 首先将其从小到大的排序， 再建立一个数组，用两个指针分别指向开头，结尾（用以交替峰谷）当 l==r 时 就将最后一个值输入，再遍历输出.

望大家指正...

来自的指导.

所有题来自 ...