【贪心算法】贪心算法七
贪心算法七
1 INTEGER VALUES rather than integers, the algorithm must be adjusted accordingly.
2 The Russian doll envelope problem is a well-known challenge in optimization.
3 The maximum sum divisible by three can be efficiently calculated using dynamic programming.
4 The distribution of equal distances in barcode patterns requires careful analysis.
5 The string reconstruction process involves reorganizing the characters to achieve the desired outcome.
点赞 👍👍收藏 🌟🌟关注 💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃
1.整数替换
题目链接： Number replacement problem 397.
题目描述：
算法原理：
解法一：模拟（递归 + 记忆化搜索）
设n = 18，则我们需要完成的任务是将18转换为1所需最少的步骤。由于18是一个偶数，在处理时我们只能通过除以2来得到9。在处理到数字9时，则后续处理的过程本质上是一样的。
此时这里就存在重复子问题这一情况了，在解决大问题即把数字从18变为1的最小步数时会发现其实在处理完9之后又回到了类似的状态。因此我们可以针对这些重复子问题进行提取并设计出函数头：
int dfs(int n) 用于计算将整数n变为1所需最少步骤的数量。
函数体 实际上就是题目所给定的操作逻辑：如果当前数字n是偶数则将其除以2；如果是奇数则可以选择加1或减1两种操作中选择一种使得到达目标状态所需步骤最少的方式即取两者中较小的那个值。
至于具体的实现细节我们可以通过设置递归终止条件当n等于1时直接返回0来完成整个计算过程。
递归过程中遇到大量重复项时可以用记忆化方法来处理问题。然而由于这道题的数据范围是1 <= n <= 2^31 - 1的原因，在内存上无法为每个可能的数值单独分配空间。于是引入hash<int, int>来记录每个数字n对应的最小步数
class Solution {
unordered_map<int,int> hash;
public:
int integerReplacement(int n) {
return dfs(n);
}
// 递归
int dfs(long long n) // 细节问题 数据范围1 <= n <= 2^31 - 1 加1会越界
{
if(n == 1)
{
return 0;
}
if(n % 2 == 0) // 如果是偶数
{
return 1 + dfs(n / 2);
}
else
{
return 1 + min(dfs(n - 1), dfs(n + 1));
}
}
// 记忆化搜索
int dfs(long long n)
{
if(hash.count(n))
{
return hash[n];
}
if(n == 1)
{
hash[1] = 0;
return hash[1];
}
if(n % 2 == 0)
{
hash[n] = 1 + dfs(n / 2);
return hash[n];
}
else
{
hash[n] = 1 + min(dfs(n - 1), dfs(n + 1));
return hash[n];
}
}
};解法二：贪心
补充知识：二进制
偶然数字：其二进制形式的最低位为零
奇数数字：其二进制形式的最低位为一
/2操作：通过整体右移一个位置来实现
我们这里研究的都是整数。
前两个可以自己举例看看。我们看最后一个
接下来想我们的贪心策略：
如果n是偶数没法贪，只能执行/2操作
如果是奇数，则优先选择加减一的操作。
在模拟过程中我们会尝试采用加一和减一两种操作来观察哪一种更优。
如果能在未进行任何尝试前就判断出哪种操作更为有利，则可以让奇数值朝着更有利的方向发展。
从而让奇数值朝着更有利的方向发展的同时避免不必要的计算。
这样一来算法的时间复杂度将会得到显著提升。
所以我们的贪心就是判断是+1好还是-1好。
如何判断？分情况讨论：
奇数的二进制最后一位是0，所以我们可以把奇数分为两大类
第一类：前面二进制位是 …，最后两个二进制位是 01
第二类：前面二进制位是 …，最后两个二进制位是 11
对于第一类情况，默认设置为n大于1。即该情况中包含一个。如果没有任何一个的情况，则表示为连续的多个零后跟一个，则可以直接返回结果。对于第二类情况，默认设置为n大于3
如果当前状态为…末位为奇数值（即二进制表示为…），则可以选择进行加减运算以改变末位数值的状态。具体而言,+运算会使末位由奇变偶（例如,…→…），而−运算则会使末位变为零（例如,…→…）。那么哪种方式更为优劣？从后续的操作路径来看,这两种运算都会导致系统进入一个偶数值的状态,随后都需进行除法运算以降低数值规模.假设当前状态为…末位奇数值（即二进制表示为…），那么通过加法运算会导致末尾变为零,而减法运算则会使末尾变为一.因此,从后续路径来看,采用减法运算能够更快地将系统引导至最低态（即数值降解速度更快）
所以是奇数二进制最后两位是01，就执行-1操作，然后/2操作，会比较快得到1。
如果是 …11，接下来也是要么执行+1操作，要么执行-1操作，分析过程和上面一样。
然而，在n大于3的情况下出现了一个特殊情况：当n等于3时特别需要进行特殊讨论。在这种情况下，在二进制表示中前导位置均为0的部分后面的部分同样呈现为全1的状态。当我们对数值执行减一操作时会得到...结果转化为...状态；随后立即进行除以2的操作就能得到最终结果为...状态
我们这个贪心不用证明，分类讨论过程本身就是对这个贪心的证明。
那如何写代码呢？
如何确定二进制数的最后两位是0 ¹还是¹¹？可以通过计算n除以4的余数来确定。由于n为奇数，在模4运算中只会得到余数为₁或₃的结果。当余数值为₁时，则二进制表示末尾两位为₀₁；当余数值为₃时，则末尾两位表示为₁₁。
class Solution {
unordered_map<int,int> hash;
public:
int integerReplacement(int n) {
int ret = 0;
while(n > 1)
{
if(n % 2 == 0)
{
n /= 2;
++ret;
}
else
{
if(n == 3)
{
ret += 2;
n = 1;
}
else if(n % 4 == 1)
{
n = n / 2;
ret += 2;
}
else
{
n = n / 2 + 1;
ret += 2;
}
}
}
return ret;
}
};2.俄罗斯套娃信封问题
Russian Doll Envelope Problem 的描述页面
Russian Doll Envelope Problem 的描述页面
题目分析：
给定一个二维数组w_1, h_1, w_2, h_2, ..., w_n, h_n，其中每一行表示一个信封的宽度和高度参数w_i, h_i（i从1到n）。只有当另一个信封的宽度h_j > w_i且高度h_j > h_i时（即h_j > \max(w_i, h_i)），当前这个信封才可以被放入另一个更大的信封装入其中（类似于俄罗斯套娃的方式）。那么问题转化为：最多可以包含多少个这样的嵌套关系链？
算法原理：
解法一：常规解法（通用解法）- > 动态规划
首先进行数组的排序操作，在未进行排序的情况下，在寻找过程中某个阶段需要同时在左方和右方分别查找对象；简单来说，在这种情况下需要遍历整个变量范围一次才能确定每个信封能够包裹的对象。
当我们把序列按照起始点进行有序排列时，在确定哪个信封能够包裹另一个时，在这种情况下只需查看左侧即可完成判断。这是因为要实现包裹关系必须满足两个条件：起始点和结束点都必须各自大于对方。由于我们已经按起始点排序完毕，在右侧的所有起始点都比当前的大了。
当我们面对当前的问题时（当我们面对这个问题时），我们的最长套娃序列（我们的最长套娃序列）非常类似于上一次遇到的最长递增子序列问题（类似于上一次遇到的问题）。最长递增子序列（最长递增子序列）是通过在原始数组（原始数组）中选择一系列数值（一系列数值）来构造一个递增的序列（构造一个递增的序贯），其最大长度是多少？其最大长度是多少？我们这里的问题（我们这里的问题）则是从一组信封（从一组信封）中筛选出一组信封以形成一个嵌套序列（以形成一个嵌套顺序），其最大长度是多少？这两者之间存在极大的相似性（两者之间存在极大的相似性）。
1.状态表示
dp[i] 表示：以 i 位置的信封为结尾的所有套娃序列中，最长套娃序列的长度
2.状态转移方程
根据最近一步，划分情况
i 位置本身就是套娃序列 ，长度是1
以i位置结尾的最长嵌套套娃长度，则需遍历0至i-1区间的所有j位置。观察到i号信封能够嵌入j号信封之外，则可将dp[j]的基础上增加1个单位（即加入i号信封），从而得到以i号信封结尾的一个嵌套序列长度。对于0至i-1区间内所有能够嵌入其他信封的j号位置上dp[j]+1的最大值即为以i号信封结尾时所形成的最长嵌套序列之长度
3初始化
数组初始为1，就可以不用考虑为的1情况
4.填表顺序
从左往右
5.返回值
dp[i] 定义为：以第 i 个位置上的信封结尾的所有嵌套包裹序列中最大的嵌套层数。我们的目标是确定整个区间内能够形成的嵌套包裹的最大层数数量，并因此返回 dp 数组中的最大值。
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& e) {
// 动态规划
sort(e.begin(), e.end());
int n = e.size();
vector<int> dp(n, 1);
int ret = 1;
for(int i = 1; i < n; ++i)
{
for(int j = 0 ; j < i; ++j)
{
if(e[j][0] < e[i][0] && e[j][1] < e[i][1])
dp[i] = max(dp[i], dp[j] + 1);
}
ret = max(ret, dp[i]);
}
return ret;
}
};由于本题的数据规模较大，采用动态规划可能会导致超时。然而动态规划作为一种通用解决方案，在处理此类问题时具有显著的效果。因此本题无法解决并不意味着所有同类问题都无法求解。例如参考链接中的推箱子问题，在该问题中使用动态规划同样能够获得理想的结果。
解法二：重写排序 + 贪心 + 二分
动态超时了，肯定得用贪心 + 二分了，但是为什么多一个重写排序呢?
如果我们仅按左端点进行排序，并随后采用贪心策略配合二分查找，则会发现需要进行分类讨论的原因在于之前的最长递增子序列问题仅有一个限制条件——只能从一堆数中挑选满足条件的最大序列。具体而言，在每次选择时即选择当前可选元素中最小的那个作为保留元素（即每次选择当前可选元素中最小的那个作为保留元素）。例如，在长度为2时选择5作为保留元素，则当引入一个新的元素3后（假设其满足与现有某些数能够形成更长序列），我们需要将原先被选中的较大数5替换掉以适应新的情况（即每次选择当前可选元素中最小的那个作为保留元素）。虽然可行但需进行较为复杂的分类讨论以确保最优解的选择。因此我们需要重新审视并改进排序策略与二分查找的应用方式以适应这种更为复杂的情形。
假设我们已经将所有信封按照左端点从小到大排序完毕。如果每个信封的左右两端都存在差异，则我们可以直接忽略掉这些被排序好的左右两端位置关系（即删除掉这些左右两端）。这是因为经过排序处理后每个信封的位置已经被确定下来，并且在这种情况下其左右两端的位置关系已经被严格确定下来（即每个位置上的左右两端都是唯一存在的）。这样操作后就形成了一个严格递增的序列问题：即在特定的一组数值中寻找最长递增子序列的问题就可以转化为在一个特定序列中寻找最长递增子序列的问题。
但这里可能存在多个相同的起始位置，在这种情况下排序后会出现如下结果：如果我们忽略起始位置进行排序可能会导致选择长度分别为4、6、7和9的连续序列但这不符合实际需求因为我们算法在选择时必须确保后续段落能够与前一个段落形成良好的连接
如何避免出现这种情形呢？其实很简单：只要在同一区间内比较右侧值时将其按降序排列即可；如果我们不再关注左侧值，在选择7时则必须避免选择9（因为当左侧相同时右侧会按由大到小排列）；同样的道理可知，在挑选4时无需考虑前面三个数值
重写排序后就完完全全变成只有一个限制的最长递增序列了。
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& e) {
// 重写排序 + 贪心 + 二分
sort(e.begin(), e.end(),[&](vector<int>& e1, vector<int>& e2)
{
return e1[0] != e2[0] ? e1[0] < e2[0] : e1[1] > e2[1];
});
// 贪心 + 二分
vector<int> ret;
ret.push_back(e[0][1]);
int n = e.size();
for(int i = 1; i < n; ++i)
{
if(e[i][1] > ret.back())
{
ret.push_back(e[i][1]);
}
else
{
int left = 0, right = ret.size() - 1;
while(left < right)
{
int mid = (left + right) >> 1;
if(ret[mid] < e[i][1])
left = mid + 1;
else
right = mid;
}
ret[left] = e[i][1];
}
}
return ret.size();
}
};3.可被三整除的最大和
题目链接： 1262. 能被3整除的最大总和**
题目分析：
题目要求从该数组中选择若干个元素，并且使得所选元素之和能够被3整除，并且所选元素之和最大。
算法原理：
解法一：正难则反 + 贪心 + 分类讨论
题目要求从数组中选出若干个数之和既能被3整除又达到最大值。当这些数之和恰好能被3整除时（即模运算结果为零），无需再做调整；若模运算结果非零，则需从已选集合中剔除部分元素以确保总和满足条件。
先把所有的数累加在一起，根据累加和，删除一些数
假设所有数的和是sum，接下来就分类讨论：
- sum % 3 == 0
直接返回sum
- sum % 3 == 1
我们定义一些数，x ：标记 % 3 == 1 的数，y ： 标记 % 3 == 2 的数
如果%3 == 1，必定有下面几种情况：
第一种情况：
存在一个%3 == 1 的数，剩下所有数的和%3 == 0
四组数字分别取模3等于1的结果；其余所有数字之和取模3等于0；实际上可以把这三个取模结果合并到其余所有数字之和中。
共有七个数字满足%3==1的条件；其余所有数字之和满足%3==0；另外六个满足%3==1条件的数字可以纳入到其余所有数字之和满足%3==0的结果中
剩下的情况不用一一列举了, 我们只需关注第一种情形即可, 其原因在于无论有多少个不同的组合, 只要从第一个组合中删除一个元素x₁, 就可以使剩余元素之和能被3整除.
那么，在贪心策略下，我们应删除哪一个x₁？它必然是最小的那个x₁。因为我们的目标是使总和最大化。
第二种情况：
在模运算结果等于2的情况下存在两组数值分别为（4 mod3=1）以及（6 mod3=0），同样地，在这种情况下也有可能出现另一种情况即有四个或更多这样的数值但在这种情况下我们只需要考虑第一种情况就足够了于是我们需要删除这两个数值以避免重复计算在这种情况下贪心算法的应用就凸显出来了为了最大化总和我们需要删除这两个数值中的最小值及其次小值
因为sum %3 == 1 会分为这两种情况，因此我们取这两种情况的最大值。
- sum % 3 == 2
也是两种情形：一种是存在某个y₁满足sum模3余2；另一种是选取两个数x₁和x₂使得sum模3余2。我们选择这两种情形中的较大者作为结果。
如何找出一组数值中的最小元素及其第二小元素？同样地，要找出一组数值的最大元素及其第二大的元素。
第一种方法：sort排序 O(nlogn)
第二种方法：分类讨论
设定两个变量x₁和x₂，并令其初始值设为正无穷；依次处理每个 incoming x；分别进行判断分析。
- x < x1
- x1 < x < x2
3. x > x2
并不影响最小和次小的。所以不用考虑
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
const int INF = 0x3f3f3f3f;
int sum = 0, 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);
}
};解法二：动态规划
从一堆数字中选择若干个数字,使得所选数字之和能被3整除.实际上这个问题可以归类为典型的0-1背包问题.
1.状态表示
dp[i][j] 表示：从给定的前i个数中选择若干个数，并计算它们取模3等于j的情况下的最大总和是多少
2.状态转移方程
根据最后一个位置，划分情况
避免选择i位置的这个数值，则应在0到i-1这个范围内挑选若干个数值之和模3等于j时的最大值总和，并恰好等于dp[i-1][j]
选i之后转而从0到i-1区间内寻找若干个数之和模3的情况。然而此时就需要重新确定寻找的目标j值因为i位置上的元素nums[i]%3的结果可以是0、1或2中的任何一个值因此在寻找符合条件的情况时需根据nums[i]%3的不同取值来调整目标j的位置
以nums[i]%3 == 1为例，在求解dp[i][0]时需要在0到i-1的区间内寻找符合条件的j值为2的情况。这是因为当nums[i]=1时，在此区间内找到的和加上nums[i]=1后才会使得总和模3等于0。例如，在这种情况下，dp[i][0]=2%3=2；而加上nums[i]=1后得到(2+1)%3=0的结果。同样的方法也适用于计算dp[i][1]和dp[i][2]的情况
我们要求的是最大和，因此取两种情况的最大值
3.初始化
- 多开一行，列开3个
- 里面的值要保证后序的填表是正确的
- 下标的映射关系
第一行为空表示没有可选数值。此时与%3取模结果为0，则直接赋值为0；若不选的话，则直接赋值为该位置的最小可能值即可。为了简化逻辑，在后续处理中只需确保这些状态仅在存在时被引用即可。因此，在初始化时将这些无效状态设为足够小的值（例如-0x3f3f3f3f）。
第一列除了第一格下面的不用初始化。直接放在填表里面就行了。
4.填表顺序
从上往下，从左往右
5.返回值
dp[i][j] 是从前i个数字中选择一些数字的最大总值之和；其中这些被选中的数字之和取模的结果为j（其中j满足条件：0 ≤ j < 3）。我们需要找到一种方法使得从全部数字中选择一些且这些被选中的数字之和取模结果为0的情况下其总值最大；最终的结果即为dp[n][0]
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
// 动态规划
const int INF = 0x3f3f3f3f;
int n = nums.size();
vector<vector<int>> dp(n + 1, vector<int>(3, -INF));
dp[0][0] = 0;
for(int i = 1; i <= n; ++i)
for(int j = 0; j < 3; ++j)
dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j - nums[i -1] % 3 + 3) % 3] + nums[i - 1]);
return dp[n][0];
}
};优化：利用滚动数组做优化
在解决背包问题时，我们通常使用一个数组来充当滚动数组。然而，在当前情况下，则需要使用两个独立的数组来实现滚动效果。这是因为模运算的结果可能为0、1或2；当我们在一个数组中更新下一行的数据时（例如，在处理j=0时），会引用j=1和j=2的位置；同时，在填入j=1时会引用j=2的位置；而当处理其他j值时（如j=3），也会引用前面几个位置的数据；如果前面的操作已经更新了某些位置（如将某个位置设为某个特定值），那么后续计算可能会受到影响并无法获得上一步的状态；为了避免这种信息丢失的问题（即无法回溯到上一个状态），因此决定采用两个独立的滚动数组来进行计算；这样就不会出现数据覆盖的问题了；无论选择从左往右还是从右往左填充表格数据，在这种情况下都能有效解决问题。
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
// 利用滚动数组优化(二个数组)
const int INF = 0x3f3f3f3f;
int n = nums.size();
vector<int> dp(3, -INF);
dp[0] = 0;
for(int i = 1; i <= n; ++i)
{
vector<int> ndp(3);
for(int j = 0; j < 3; ++j)
ndp[j] = max(dp[j], dp[(j - nums[i -1] % 3 + 3) % 3] + nums[i - 1]);
dp = move(ndp);
}
return dp[0];
}
};4.距离相等的条形码
题号链接：1054. 距离相同的条形码
题目分析：
算法原理：
解法：贪心 + 模拟
我们需要解决这个问题：将给定的一组数字进行重新排列
我们依次在偶数位上摆放完成后，在奇数位上继续摆放。经过上述操作后发现，任何相邻的两个数字都不相同。
贪心策略：
- 每次处理一批相同的数
- 摆放的时候，每次隔一个格子
然而该策略还存在一个问题：可能存在让相同数字被放置在相邻位置的情况，还需要增加一个限制条件。
- 先处理出现次数最多的那个数，剩下的数的处理顺序无所谓
证明：
该问题必然存在解，则可将这些元素划分为不相交的子集。进一步地，在这种情况下我们能得出以下结论：在该集合中最多出现次数不超过\frac{n+1}{2}次的元素必定存在。
如果某个数的出现次数最多，并且超过了(n+1)/2个的话，则将这些数组进行配对时必然存在至少一对具有相同元素；然而题目必然存在解，则该特定数值的最大频率不会超过(n+1)/2个。
该方法优先处理频率最高的数值，并不影响其他数值的处理顺序。
在第一种情况下，频率最高的数值恰好达到（n + 1）/2。我们首先筛选出频率最高的那个数值，在剩余的数据中无论如何排列都绝不会相邻。
在第二种情况下：数量最大的数值低于（n+1）/2的限制值时。这时可以推断出这些最大值不会连续出现在序列中。因为如果它们连续排列，则后续的最大值X的数量将超过前面的O的数量；然而根据前提条件，在这种情况下这样的连续排列是不可能发生的。因此，在这种情况下最大值X的数量必然低于设定的限制值；同时由于我们采用优先处理最大频率的方法策略，在填充过程中必须避免将这些最大频率的数值放置在相邻的位置上；因此，在这种情况下若先填充O，则X不可能与其形成相邻关系
class Solution {
public:
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();
vector<int> ret(n);
int index = 0;
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;
}
};5.重构字符串
本题为LeetCode上的经典编程题目：767. 重构字符串
题目分析：
算法原理：
解法：贪心 + 模拟
- 每一批次都会处理相同类型的文本信息
- 在放置时会每隔一定的间隔放置一个文本符号
- 系统将按照字符出现频率排序后优先处理高频字符
这道题并未明确指出是否包含排序信息, 因此我们需要首先判断是否存在排列. 其方法较为简洁明了, 即只要满足出现次数最多的字符个数不超过({n+1})/2即可.
class Solution {
public:
string reorganizeString(string s) {
// 统计每个字符出现的频次
int hash[26] = { 0 };
char maxChar = ' '; int maxCount = 0;
for(auto ch : s)
{
if(maxCount < ++hash[ch - 'a'])
{
maxCount = hash[ch - 'a'];
maxChar = ch;
}
}
// 先判断⼀下
int n = s.size();
if(maxCount > ((n + 1) / 2)) return "";
// 先处理出现次数最多的那个字符
string ret(n,' ');
int index = 0;
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;
}
};