【C++ 算法进阶】算法提升十六
目录
背包问题变种 （动态规划）
题目
现在给你一个数组 数组中可能有正数 负数 和零
现在请问 数组中是否存在一个子序列可以让累加和为K
如果数组的长度很大 此题应该如何解？
题目分析
- 对于问题1
本题和背包问题唯一的不同就是出现了负数
如果说我们的累加和可能为负数到一个最大值 不可能再设置为0~K
这个区间也很容易找 我们只需要将所有负数累加作为一个最小值 将所有正数累加作为一个最大值即可
- 对于问题2
如果数组的长度很大 则我们可以使用分治的思想来做这道题
将整个数组一分为二 之后查看下面三种可能性
- 左边的数组能否累加为K
- 右边的数组能否累加为K
- 左右两数组之和能否累加为K
连续可组成数字
题目
假设现在有一个正数数组 这个正数数组中有1这个数
那么请问这个正数数组能组成的最大连续正整数是多少 （1 2 3 4 5 … 这样到哪个数组组成不了 ）
题目分析
我们可以使用range来表示这个数组能组成的最大连续正整数是多少
我们可以先将数组排序
因为数组中肯定有1 所以说range肯定有1~1
接着我们看第二个数 加入第二个数不大于 range + 1 （不大于2）
那么我们的range就变为 range + arr[2]
假设range大于的range + 1的话 我们就无法组成range + 1这个数
第三个数同理 一直加到最后我们就能得出最终的结果是多少了
min-patches
题目 最小补丁问题
题目分析
本题其实就是上一题的一个翻版
我们只需要将数组排序 看是否有1 如果有1则range从1开始叠加
如果没有1我们补上1即可
需要注意的是
- 每次range数值变化 我们都需要查看是否满足要求 返回count
- 如果数组内元素都用完了还没有达到n 则我们需要继续叠加range
代码
class Solution {
public:
int minPatches(vector<int>& nums, int n) {
int count = 0;
unsigned long long range = 0;
sort(nums.begin() , nums.end());
if (nums[0] != 1) {
count++;
range++;
}
if (n == 1) {
return count;
}
for (int i = 0; i < nums.size(); i++) {
while (range + 1 < nums[i]) {
range += range + 1;
count += 1;
if (n <= range) {
return count;
}
}
range += nums[i];
if (n <= range) {
return count;
}
}
while(n >= range + 1) {
range += range + 1;
count += 1;
}
return count;
}
};
逆序对个数 （归并排序）
题目
现在给定一个数组 数组的大小为2的N次方
现在要求你求出该数组的逆序对个数
题目分析
本题为归并排序中的小和问题
可以参考我上面这篇博客
约瑟夫环问题 （公式）
题目
据说著名犹太历史学家Josephus（弗拉维奥·约瑟夫斯）有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏
题目分析
这道题目既可以使用模拟链表来实现也可以使用公式来实现
思路都很简单 我们记住公式即可
#include <iostream>
using namespace std;
// 函数声明
int josephus(int n, int m);
int main() {
int n, m;
cout << "请输入总人数n和报数上限m：";
cin >> n >> m;
int result = josephus(n, m);
cout << "最后剩下的人的编号是：" << result << endl;
return 0;
}
// 约瑟夫环问题的函数实现
int josephus(int n, int m) {
if (n == 1) return 0; // 当只有一个人时，返回其编号0
else return (josephus(n - 1, m) + m) % n; // 递归调用公式计算
}
原文地址：https://blog.csdn.net/meihaoshy/article/details/143825883
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！