《七月集训》第四日——贪心

这是七月集训的第4日，今日的训练内容是 贪心

2078. 两栋颜色不同且距离最远的房子

街上有 n 栋房子整齐地排成一列，每栋房子都粉刷上了漂亮的颜色。给你一个下标从 0 开始且长度为 n 的整数数组 colors ，其中 colors[i] 表示第  i 栋房子的颜色。

返回 两栋 颜色 不同 房子之间的 最大 距离。

第 i 栋房子和第 j 栋房子之间的距离是 abs(i - j) ，其中 abs(x) 是 x 的绝对值。

这题没有想到贪心的写法，这里使用双指针直接遍历。

int maxDistance(int* colors, int colorsSize){
    int i,j,max=0;
    for(i=0;i
        for(j=i;j
            if(colors[i]!=colors[j]){
                max = max>j-i?max:j-i;
            }
        }
    }
    return max;
}

561. 数组拆分

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

既然需要每一组中的最小值都最大，那直接排序取小的那个加和就可以了。

int cmp(const void*a,const void*b){
    return *(int*)a-*(int*)b;
}
int arrayPairSum(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmp);
    int sum = 0;
    int i;
    for(i = 0;i
        sum+=nums[i];
    }
    return sum;
}

1323. 6 和 9 组成的最大数字

给你一个仅由数字 6 和 9 组成的正整数 num。

你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。

请返回你可以得到的最大数字。

从最大的不是 9 的位开始变为 9即可。

注意，在c语言中，在定义数组的时候，数组的容量必须是定值而不可以是变量，但是使用 malloc();就没有问题了。

int maximum69Number (int num){
    int i;
    int size = 1;
    int tmp=num;
    while(tmp/10!=0){
        size++;
        tmp/=10;
    }
    int* nums = (int*)malloc(sizeof(int)*size);
    memset(nums,0,sizeof(int)*size);
    for(i=size-1;i>=0;--i){
        nums[i]=num%10;
        num/=10;
    }
    for(i=0;i
        if(nums[i]!=9){
            nums[i]=9;
            break;
        }
    }
    num = 0;
    for(i=0;i
        num=num*10+nums[i];
    }
    return num;
}

942. 增减字符串匹配

由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:

如果 perm[i] < perm[i + 1] ，那么 s[i] == ‘I’ 
如果 perm[i] > perm[i + 1] ，那么 s[i] == ‘D’ 
给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有>效排列perm，则返回其中 任何一个 。

直接双指针开贪，出现 D 就从尾端放一个数过来，I 从首段放过来，然后多出来的一个空位放剩下的数。

int* diStringMatch(char * s, int* returnSize){
    int len = strlen(s);
    int* ret = (int*)malloc(sizeof(int)*(len+1));
    int l = 0,r = len;
    int i,j=0;
    for(i = 0;i
        if(s[i]=='D'){
            ret[j++]=r;
            r--;
        }else{
            ret[j++]=l;
            l++;
        }
    }
    ret[j] = l;
    *returnSize = len+1;
    return ret;
}