[Algorithm][贪心][可被三整除的最大和][距离相等的条形码][重构字符串]详细讲解

1.可被三整除的最大和

1.题目链接

• 可被三整除的最大和

2.算法原理详解

• 思路：正难则反 + 贪心 + 分类讨论

  • 先把所有的数累加在一起，根据累加和，删除一些数
    

  • 补充：如何求一堆数中的最小值以及次小值？

    • sort()
    • 分类讨论 --> $O(N)$

3.代码实现

int maxSumDivThree(vector<int>& nums) 
{
    const int INF = 0x3f3f3f3f;

    int sum = 0;
    int x1 = INF, x2 = INF, y1 = INF, y2 = INF;
    for(auto& x : nums)
    {
        sum += x;
        if(x % 3 == 1)
        {
            if(x < x1)
            {
                x2 = x1;
                x1 = x;
            }
            else if(x < x2)
            {
                x2 = x;
            }
        }
        else if(x % 3 == 2)
        {
            if(x < y1)
            {
                y2 = y1;
                y1 = x;
            }
            else if(x < y2)
            {
                y2 = x;
            }
        }
    }

    // 分类讨论
    if(sum % 3 == 0)
    {
        return sum;
    }
    else if(sum % 3 == 1)
    {
        return max(sum - x1, sum - y1 - y2);
    }
    else
    {
        return max(sum - y1, sum - x1 - x2);
    }
}

2.距离相等的条形码

1.题目链接

• 距离相等的条形码

2.算法原理详解

• 解法：贪心 + 模拟
  • 每次处理一批相同的数
    • 摆放的时候，每次隔一个格子
  • 先处理出现次数最多的那个数
    • 剩下的数的处理顺序无所谓

3.代码实现

vector<int> rearrangeBarcodes(vector<int>& b) 
{
    unordered_map<int, int> hash;
    int maxVal = 0, maxCount = 0;
    for(auto x : b)
    {
        if(maxCount < ++hash[x])
        {
            maxCount = hash[x];
            maxVal = x;
        }
    }

    int n = b.size();
    int index = 0;
    vector<int> ret(n);

    // 先处理出现次数最多的那个数
    for(int i = 0; i < maxCount; i++)
    {
        ret[index] = maxVal;
        index += 2;
    }

    // 处理剩下的数
    hash.erase(maxVal);
    for(auto& [x, y] : hash)
    {
        for(int i = 0; i < y; i++)
        {
            if(index >= n)
            {
                index = 1;
            }

            ret[index] = x;
            index += 2;
        }
    }

    return ret;
}

3.重构字符串

1.题目链接

• 重构字符串

2.算法原理详解

• 解法：贪心 + 模拟
  • 前置判断：maxCount > (n + 1) / 2则无解
  • 每次处理一批相同的数
    • 摆放的时候，每次隔一个格子
  • 先处理出现次数最多的那个数
    • 剩下的数的处理顺序无所谓

3.代码实现

string reorganizeString(string s) 
{
    int hash[26] = { 0 };
    char maxChar = ' ';
    int maxCount = 0;

    for(auto ch : s)
    {
        if(maxCount < ++hash[ch - 'a'])
        {
            maxChar = ch;
            maxCount = hash[ch - 'a'];
        }
    }

    int n = s.size();
    if(maxCount > (n + 1) / 2)
    {
        return "";
    }

    int index = 0;
    string ret(n, ' ');
    for(int i = 0; i < maxCount; i++)
    {
        ret[index] = maxChar;
        index += 2;
    }
    hash[maxChar - 'a'] = 0;

    for(int i = 0; i < 26; i++)
    {
        for(int j = 0; j < hash[i]; j++)
        {
            if(index >= n)
            {
                index = 1;
            }

            ret[index] = 'a' + i;
            index += 2;
        }
    }

    return ret;
}