1. 整数替换
看到这道题目，我们首先能想到的方法就应该是递归解法，我们来画个图
此时我们出现了重复的子问题，就可以使用递归，只要我们遇到偶数，直接将n除以2递归下去，如果是奇数，选出加1和减1中最小步数的那个继续递归下去即可，直接看代码：
class Solution {
public:
int integerReplacement(int n) {
if(n == 1)
return 0;
if(n & 1 == 1) // 奇数
return min(integerReplacement(n+1),integerReplacement(n-1)) + 1;
else
return integerReplacement(n / 2) + 1;
}
};然后我们去运行代码，很遗憾，此时代码没有通过，这是因为的递归过程中出现了大量的重复子问题的，这些重复的子问题其实我们已经计算过了，没必要再计算一次，所以我们可以利用记忆化搜索的备忘录来解决这个问题，此时我们递归的时候，如果此时备忘录立马存在这个值，我们就可以直接返回，如果没有这个值，我们再去递归。
class Solution {
unordered_map<int,int> hash;
public:
int integerReplacement(int n) {
// 先判断是否再在备忘录中
if(hash.count(n))
{
return hash[n];
}
if(n == 1)
{
hash[1] = 0;
return 0;
}
if(n & 1 == 1) // 奇数
{
hash[n] = min(integerReplacement(n+1),integerReplacement(n-1)) + 1;
return hash[n];
}
else
{
hash[n] = integerReplacement(n / 2) + 1;
return hash[n];
}
}
};但是此时我们发现程序没有通过，通过这个测试案例我们可以知道，当n是2147483647的时候，此时是奇数，会去递归2147483647+1，此时就超过了int的范围。
此时我们需要自己来定义一个dfs函数来解决这个问题。
class Solution {
unordered_map<int,int> hash;
public:
int integerReplacement(int n)
{
return dfs(n);
}
int dfs(long long int n){
// 先判断是否再在备忘录中
if(hash.count(n))
{
return hash[n];
}
if(n == 1)
{
hash[1] = 0;
return 0;
}
if(n & 1 == 1) // 奇数
{
hash[n] = min(dfs(n+1),dfs(n-1)) + 1;
return hash[n];
}
else
{
hash[n] = dfs(n / 2) + 1;
return hash[n];
}
}
};此时我们的代码就能通过，我们再来写另一种解法。
直接上手代码：
class Solution {
public:
int integerReplacement(int n) {
return dfs(n);
}
int dfs(long long int n)
{
if(n == 1)
return 0;
if(n % 2 == 0) // 偶数
{
return dfs(n/2) + 1;
}
else
{
if(n == 3)
{
return dfs(n-1) + 1;
}
else if(n % 4 == 1)
{
return dfs(n - 1) + 1;
}
else if(n % 4 == 3)
{
return dfs(n + 1) + 1;
}
}
// 这里有返回值是因为要让所有的路径都有返回值
return 0;
}
};其实我们这里也可以不使用递归来解决这个题目。
class Solution {
public:
int integerReplacement(int n) {
int ret = 0;
while(n > 1)
{
if(n % 2 == 0) // 偶数
{
n /= 2;
ret++;
}
else // 奇数
{
if(n == 3)
{
n = 1;
ret += 2;
}
else if(n % 4 == 1)
{
n -= 1;
n /= 2;
ret += 2;
}
else if(n % 4 == 3)
{
n /= 2; // 这里需要先除2,防止n+1溢出
n += 1;
ret += 2;
}
}
}
return ret;
}
};2. 俄罗斯套娃信封问题
首先我们看到这个题目，就和我们之前的最长递增子序列是一样的，我们需要对左端点进行排序，然后看是否满足俄罗斯套娃的条件，既然是找最长的套娃个数，此时我们可以使用动态规划来解决这个问题，我们可以假设dp[i]位置表示i位置之前的此时最长的套娃个数，当我们到i的位置的时候，我们需要看看0到i-1位置的最长的套娃个数，如果有一个条件满足俄罗斯套娃的条件，那么最长的套娃个数就可以+1，此时就可以使用动态规划来解决这个问题。
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
// 动态规划
sort(envelopes.begin(), envelopes.end());
int n = envelopes.size();
vector<int> dp(n, 1);
int ret = 1;
for(int i = 1; i < n; i++)
{
for(int j = 0; j < i; j++)
{
if(envelopes[i][0] > envelopes[j][0] &&
envelopes[i][1] > envelopes[j][1])
{
dp[i] = max(dp[i], dp[j]) + 1;
}
}
ret = max(ret, dp[i]);
}
return ret;
}
};但是此时我们的代码会超时，所以此时我们就需要来使用另一种策略
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
// 排序
sort(envelopes.begin(), envelopes.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(envelopes[0][1]);
for(int i = 1; i < envelopes.size(); i++)
{
int b = envelopes[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();
}
};3. 可被三整除的最大和
正难则反： 我们可以先把所有的数累加在⼀起，然后根据累加和的结果，贪心的删除⼀些数。
那么我们该如何寻找到最小的和次小的值呢？当然我们可以进行一下sort排序取出最小的和次小的值，但是我们知道sort的底层使用的是快速排序，时间复杂度是O(N*logN)，所以此时并不是最优的选择，我们可以使用O(N)的时间复杂度来解决这个问题：
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
int x1 = 0x3f3f3f3f3f;
int x2 = 0x3f3f3f3f3f;
int y1 = 0x3f3f3f3f3f;
int y2 = 0x3f3f3f3f3f;
int sum = 0;
// 求出总和,最小和次小的值
for(int i = 0; i < nums.size(); i++)
{
sum += nums[i];
if(nums[i] % 3 == 1) // 判断当值余数是否为1
{
if(nums[i] <= x1)
x2 = x1, x1 = nums[i];
else if(nums[i] > x1 && nums[i] < x2)
x2 = nums[i];
}
else if(nums[i] % 3 == 2) // 判断当值余数是否为2
{
if(nums[i] <= y1)
y2 = y1, y1 = nums[i];
else if(nums[i] > y1 && nums[i] < y2)
y2 = nums[i];
}
}
// 分类讨论
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);
}
};4. 距离相等的条形码
这道题目比较简单，我们只需要每次处理一批相同的数字，往 n 个空里面摆放； 每次摆放的时候，隔一个格子摆放一个数，但是我们需要优先处理出现次数最多的那个数，其余的数处理的顺序就没什么要求了。
class Solution {
public:
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
unordered_map<int, int> hash; // 统计每个数出现的次数
int maxVal = 0; // 最大的值
int maxCount = 0; // 最大值的项数
for(auto& e : barcodes)
{
if(maxCount < ++hash[e])
{
maxCount = hash[e];
maxVal = e;
}
}
vector<int> v(barcodes.size(), 0);
// 先处理出现次数最多的数
int index = 0;
for(int i = 0; i < maxCount; i++)
{
v[index] = maxVal;
index += 2;
}
// 处理剩下的数,不用管顺序,直接防即可
hash.erase(maxVal);
for(auto& [x, y] : hash)
{
for(int i = 0; i < y; i++)
{
// 超过最大位置,需要重新从头开始摆放
if(index >= barcodes.size())
index = 1;
v[index] = x;
index += 2;
}
}
return v;
}
};5. 重构字符串
我们读完题目会发现这道题目和上一道题目是类似的，只不过上一道题目是重排数字，而这道题目是重排字符串，思路基本上都是一致的，但是上一个题目明确告诉了我们所有数字都是可以重排列的，但是我们这个题目不一定，因此我们需要先判断一下，如果出现最多的字符的个数大于(n + 1) / 2 就无法重排，其他情况下就可以直接重排列，那我们直接上代码啦！
class Solution {
public:
string reorganizeString(string s) {
unordered_map<char, int> hash;
char maxVal = ' ';
int maxCount = 0;
for(auto& x : s)
{
if(maxCount < ++hash[x])
{
maxCount = hash[x];
maxVal = x;
}
}
if(maxCount > ((s.size() + 1) / 2))
return "";
// 先处理出现次数最多的那个字符
string ret;
ret.resize(s.size());
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 >= ret.size()) index = 1;
ret[index] = x;
index += 2;
}
}
return ret;
}
};
