【C++ 算法进阶】算法提升十六

背包问题变种 （动态规划）

题目

现在给你一个数组 数组中可能有正数 负数 和零

现在请问 数组中是否存在一个子序列可以让累加和为K

如果数组的长度很大 此题应该如何解？

题目分析

1. 对于问题1

本题和背包问题唯一的不同就是出现了负数

如果说我们的累加和可能为负数到一个最大值 不可能再设置为0~K

这个区间也很容易找 我们只需要将所有负数累加作为一个最小值 将所有正数累加作为一个最大值即可

2. 对于问题2

如果数组的长度很大 则我们可以使用分治的思想来做这道题

将整个数组一分为二 之后查看下面三种可能性

1. 左边的数组能否累加为K
2. 右边的数组能否累加为K
3. 左右两数组之和能否累加为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即可

需要注意的是

1. 每次range数值变化 我们都需要查看是否满足要求 返回count
2. 如果数组内元素都用完了还没有达到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; // 递归调用公式计算
}