《六月集训》第四天——贪心

• 前言
• 一、题目一
• • 1.题目描述
  • 2.解题思路
  • 3.代码详解
• 二、题目二
• • 1.题目描述
  • 2.解题思路
  • 3.代码详解
• 三、题目三
• • 1.题目描述
  • 2.解题思路
  • 3.代码详解
• 四、题目四
• • 1.题目描述
  • 2.解题思路
  • 3.代码详解
• 五、星球推荐

        
刷题坚持每一天，以下题目引用自：力扣（LeetCode）

原题链接：1221. 分割平衡字符串

        在一个 平衡字符串 中，‘L’ 和 ‘R’ 字符的数量是相同的。
        给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
        注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。
        返回可以通过分割得到的平衡字符串的 最大数量 。

示例 1：
输入：s = “RLRRLLRLRL”
输出：4
解释：s 可以分割为 “RL”、“RRLL”、“RL”、“RL” ，每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’ 。

思路：

​         栈思想，R进栈L出栈，栈空统计加一。

int balancedStringSplit(char * s){
    int sSize = 0;
    int flag = 0;
    int cout = 0;
    while(s[sSize] != ''){
        (s[sSize++] == 'R') ? flag++ : flag--;
        if(flag == 0){
            cout++;
        }
    }
    return cout;
}

原题链接：1217. 玩筹码

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

• position[i] + 2 或 position[i] - 2 ，此时 cost = 0
• position[i] + 1 或 position[i] - 1 ，此时 cost = 1

返回将所有筹码移动到同一位置上所需要的 最小代价 。

示例 1：

输入：position = [1,2,3]
输出：1
解释：第一步:将位置3的芯片移动到位置1，成本为0。
第二步:将位置2的芯片移动到位置1，成本= 1。
总成本是1。

思路：

​          偶数传偶数和奇数传奇数代价都为零，偶数传奇数和奇数传偶数代价都为一，然后统计奇偶分别出现的次数，返回小的次数就是最小代价。

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

原题链接：1029. 两地调度

        公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [aCosti, bCosti] 。第 i 人飞往 a 市的费用为 aCosti ，飞往 b 市的费用为 bCosti 。
        返回将每个人都飞到 a 、b 中某座城市的最低费用，要求每个城市都有 n 人抵达。

示例 1：
输入：costs = [[10,20],[30,200],[400,50],[30,20]]
输出：110
解释：
第一个人去 a 市，费用为 10。
第二个人去 a 市，费用为 30。
第三个人去 b 市，费用为 50。
第四个人去 b 市，费用为 20。
最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。

思路：

​        对a - b的价格进行排序，然后一半去a地一半去b地，返回花费少的值。

int cmp(const void** q1, const void** q2){
    return (*(int**)q1)[0] - (*(int**)q1)[1] >  (*(int**)q2)[0] - (*(int**)q2)[1];
}
int twoCitySchedCost(int** costs, int costsSize, int* costsColSize){
    qsort(costs, costsSize, sizeof(int*), cmp);
    int n = costsSize/2;
    int cost1 = 0, cost2 = 0;
    for(int i = 0; i < n; ++i){
        cost1 += costs[i][0] + costs[i+n][1];
        cost2 += costs[i][1] + costs[i+n][0];
    }
    return cost1 > cost2 ? cost2 : cost1;
}

原题链接：面试题 10.11. 峰与谷

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

示例 1：
输入: [5, 3, 1, 2, 3]
输出: [5, 1, 3, 2, 3]

思路：

​         把数组值进行递增排序，使用双指针把值大小交替放到新数组内，然后在放到nums中，返回nums。

int cmp(const void* q1, const void* q2){
    return *(int*)q1 - *(int*)q2;
}
void wiggleSort(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), cmp);
    int* ret = (int*)malloc(sizeof(int)*numsSize);
    int idx = 0;
    int i = 0, j = numsSize-1;
    while(i <= j){
        ret[idx++] = nums[j];
        if(i == j) break;
        ret[idx++] = nums[i];
        --j;
        ++i;
    }
    for(int i = 0; i < numsSize; ++i) nums[i] = ret[i];
    return nums;
}

        星球链接：英雄算法联盟

星球里有什么?
        【朋友圈】一个极致精准的自律、编程、算法的小圈子。
        【算法集训】以月为单位组织算法集训，每天四题，风雨无阻。
        【排行榜】每天、每周都会有榜单，激励大家不断进步，不断成长。
        【个人规划】每个人都写好自己的规划，也可以查看他人的规划，时刻警醒自己不掉队。
        【打卡挑战】每日一题打卡、每日早起打卡、算法集训打卡、规划完成情况打卡。
在星球里做什么?
        目前星球人数达到510+，在星球里你能够遇到一群志同道合之人，因为都是花钱进来的，你不会看到任何浑水摸鱼的人，每个人都有自己的每月规划，星主每月都会组织算法集训，每天一起刷题，你可以看到别人的解题报告，取其之长，补己之短。