---

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;
}