【贪心算法】（第十三篇）
目录
整数替换（medium）
题目解析
讲解算法原理
编写代码
俄罗斯套娃信封问题（hard）
题目解析
讲解算法原理
编写代码
整数替换（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀个正整数 n ，你可以做如下操作：
1. 如果 n 是偶数，则⽤ n / 2 替换 n 。
2. 如果 n 是奇数，则可以⽤ n + 1 或 n - 1 替换 n 。返回 n 变为 1 所需的最⼩替换次数。
⽰例1：
输⼊：n=8
输出：3
解释：8->4->2->1
⽰例2：
输⼊：n=7
输出：4
解释：7->8->4->2->1
或7->6->3->2->1
⽰例3：
输⼊：n=4
输出：2
提⽰：
◦ 1 <= n <= 2^31 - 1
讲解算法原理
解法（贪⼼）：
贪⼼策略：
我们的任何选择，应该让这个数尽可能快的变成 1 。
对于偶数：只能执⾏除 2 操作，没有什么分析的；
对于奇数：
i. 当 n== 1 的时候，不⽤执⾏任何操作；
ii. 当 n == 3 的时候，变成 1 的最优操作数是 2 ；
iii. 当 n > 1 && n % 3 == 1 的时候，那么它的⼆进制表⽰是 ......01 ，最优的⽅
式应该选择 -1 ，这样就可以把末尾的 1 ⼲掉，接下来执⾏除法操作，能够更快的变成1 ；
iv. 当 n > 3 && n % 3 == 3 的时候，那么它的⼆进制表⽰是 ......11 ，此时最优的策略应该是 +1 ，这样可以把⼀堆连续的 1 转换成 0 ，更快的变成 1 。
编写代码
c++算法代码：
class Solution
{
public:
int integerReplacement(int n)
{
int ret = 0;
while(n > 1)
{
// 分类讨论
if(n % 2 == 0)
{
ret++;
n /= 2;
}
else
{
if(n == 3)
{
ret += 2;
n = 1;
}
else if(n % 4 == 1)
{
ret += 2;
n /= 2;
}
else
{
ret += 2;
n = n / 2 + 1;
}
}
}
return ret;
}
};java算法代码：
class Solution
{
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;
}
}俄罗斯套娃信封问题（hard）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个⼆维整数数组 envelopes ，其中 envelopes[i] = [w(i), h(i)] ，表⽰第 i 个信封的宽度和⾼度。
当另⼀个信封的宽度和⾼度都⽐这个信封⼤的时候，这个信封就可以放进另⼀个信封⾥，如同俄罗斯套娃⼀样。
请计算最多能有多少个信封能组成⼀组“俄罗斯套娃”信封（即可以把⼀个信封放到另⼀个信封⾥⾯）。
注意：不允许旋转信封。
⽰例1：
输⼊：envelopes=[[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为3,组合为:[2,3]=>[5,4]=>[6,7]。
⽰例2：
输⼊：envelopes=[[1,1],[1,1],[1,1]]
输出：1
提⽰：
◦ 1 <= envelopes.length <= 10^5
◦ envelopes[i].length == 2
◦ 1 <= w(i), h(i)<= 10^5
讲解算法原理
解法⼀（动态规划）：
将数组按照左端点排序之后，问题就转化成了最⻓上升⼦序列模型，那接下来我们就可以⽤解决最⻓上升⼦序列的经验，来解决这个问题（虽然会超时，但是还是要好好写代码）。
1. 状态表⽰：
dp[i] 表⽰：以 i 位置的信封为结尾的所有套娃序列中，最⻓的套娃序列的⻓度；
2. 状态转移⽅程：
dp[i] = max(dp[j] + 1) 其中 0 <= j < i && e[i][0] > e[j][0] && e[i][1] > e[j][1] ；
3. 初始化：
全部初始化为 1 ；
4. 填表顺序：
从左往右；
5. 返回值：
整个 dp 表中的最⼤值。
解法⼆（重写排序+贪⼼+⼆分）：
当我们把整个信封按照「下⾯的规则」排序之后：
i. 左端点不同的时候：按照「左端点从⼩到⼤」排序；
ii. 左端点相同的时候：按照「右端点从⼤到⼩」排序
我们发现，问题就变成了仅考虑信封的「右端点」，完完全全的变成的「最⻓上升⼦序列」的模型。那么我们就可以⽤「贪⼼+⼆分」优化我们的算法。
编写代码
解法一：
c++算法代码：
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[i][0] > e[j][0] && e[i][1] > e[j][1])
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
ret = max(ret, dp[i]);
}
return ret;
}
};java算法代码：
class Solution
{
public int maxEnvelopes(int[][] e)
{
// 解法⼀：动态规划
Arrays.sort(e, (v1, v2) ->
{
return v1[0] - v2[0];
});
int n = e.length;
int[] dp = new int[n];
int ret = 1;
for(int i = 0; i < n; i++)
{
dp[i] = 1; // 初始化
for(int j = 0; j < i; j++)
{
if(e[i][0] > e[j][0] && e[i][1] > e[j][1])
{
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
ret = Math.max(ret, dp[i]);
}
return ret;
}
}解法二：
c++算法代码：
class Solution
{
public:
int maxEnvelopes(vector<vector<int>>& e)
{
// 解法⼆：重写排序 + 贪⼼ + ⼆分
sort(e.begin(), e.end(), [&](const vector<int>& v1, const vector<int>&
v2)
{
return v1[0] != v2[0] ? v1[0] < v2[0] : v1[1] > v2[1];
});
// 贪⼼ + ⼆分
vector<int> ret;
ret.push_back(e[0][1]);
for(int i = 1; i < e.size(); i++)
{
int b = e[i][1];
if(b > ret.back())
{
ret.push_back(b);
}
else
{
int left = 0, right = ret.size() - 1;
while(left < right)
{
int mid = (left + right) / 2;
if(ret[mid] >= b) right = mid;
else left = mid + 1;
}
ret[left] = b;
}
}
return ret.size();
}
};java算法代码：
class Solution
{
public int maxEnvelopes(int[][] e)
{
// 解法⼆：重写排序 + 贪⼼ + ⼆分
Arrays.sort(e, (v1, v2) ->
{
return v1[0] != v2[0] ? v1[0] - v2[0] : v2[1] - v1[1];
});
// 贪⼼ + ⼆分
ArrayList<Integer> ret = new ArrayList<>();
ret.add(e[0][1]);
for(int i = 1; i < e.length; i++)
{
int b = e[i][1];
if(b > ret.get(ret.size() - 1))
{
ret.add(b);
}
else
{
int left = 0, right = ret.size() - 1;
while(left < right)
{
int mid = (left + right) / 2;
if(ret.get(mid) >= b) right = mid;
else left = mid + 1;
}
ret.set(left, b);
}
}
return ret.size();
}
}