[Algorithm][贪心][整数替换][俄罗斯套娃信封问题]详细讲解

---

1.整数替换

1.题目链接

• 整数替换

---

2.算法原理详解

1.解法一

• 思路：模拟(递归 + 记忆化搜索)
  

---

2.解法二

• 思路：贪心
  • 偶数：只能执行/2操作
  • 奇数：分类讨论
    

---

3.代码实现

1.代码一

class Solution 
{unordered_map<int, int> hash;
public:int integerReplacement(int n) {return DFS(n);}int DFS(long long n){if(hash.count(n)){return hash[n];}if(n == 1){hash[1] = 0;return 0;}if(n % 2 == 0){hash[n] = 1 + DFS(n / 2);}else{hash[n] = 1 + min(DFS(n - 1), DFS(n + 1));}return hash[n];}
};

---

2.代码二

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; // -> (n - 1) / 2ret += 2;}else{n = n / 2 + 1; // -> (n + 1) / 2 -> 防溢出ret += 2;}}}return ret;
}

---

2.俄罗斯套娃信封问题

1.题目链接

• 俄罗斯套娃信封问题

---

2.算法原理详解

• 知识储备：最长递增子序列 --> 动态规划 + 贪心 + 二分

1.解法一

• 解法：常规解法(通用解法) -> 动态规划(该题会超时)
  • 思考历程：乱序 --> 有序 --> 按照左端点排序 --> 最长递增子序列
  • 思路：

    • 状态表示：dp[i]：以i位置的信封为结尾的所有套娃序列中，最长的套娃序列的长度

    • 状态转移方程：
      

    • 返回值：dp表中的最大值

---

2.解法二

• 思路：重写排序 + 贪心 + 二分
  • 重写排序：此时，问题完全转化为最长递增子序列
    • 左端点不同时：左端点从小到大排序
    • 左端点相同时：右端点从大到小排序

---

3.代码实现

1.代码一

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

---

2.代码二

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