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

devtools/2024/11/19 4:07:04/

目录

  • 背包问题变种 (动态规划)
    • 题目
    • 题目分析
  • 连续可组成数字
    • 题目
    • 题目分析
  • min-patches
    • 题目 最小补丁问题
    • 题目分析
    • 代码
  • 逆序对个数 (归并排序)
    • 题目
    • 题目分析
  • 约瑟夫环问题 (公式)
    • 题目
    • 题目分析

背包问题变种 (动态规划)

题目

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

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

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

题目分析

  1. 对于问题1

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

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

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

  1. 对于问题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; // 当只有一个人时,返回其编号0else return (josephus(n - 1, m) + m) % n; // 递归调用公式计算
}

http://www.ppmy.cn/devtools/135112.html

相关文章

Http常⻅见请求/响应头content-type内容类型讲解(笔记)

常见的 Content-Type 媒体类型 text类型&#xff1a; text/html&#xff1a;HTML格式&#xff0c;常用于网页内容。text/plain&#xff1a;纯文本格式&#xff0c;未进行任何格式化。text/xml&#xff1a;XML格式&#xff0c;表示以 XML 格式传输的数据。 image类型&#xff08…

实战:深入探讨 MySQL 和 SQL Server 全文索引的使用及其弊端

在数据库中处理大量文本数据时,包含搜索(例如查找包含特定单词的文本)往往是必需的。然而,直接使用 LIKE %text% 的方式在大数据量中进行模糊查询会造成性能瓶颈。为了解决这一问题,MySQL 和 SQL Server 提供了全文索引(Full-Text Indexing)功能,可以显著加速文本数据的…

基于Python的仓库管理系统设计与实现

背景&#xff1a; 基于Python的仓库管理系统功能介绍 本仓库管理系统采用Python语言开发&#xff0c;利用Django框架和MySQL数据库&#xff0c;实现了高效、便捷的仓库管理功能。 用户管理&#xff1a; 支持员工和管理员角色的管理。 用户注册、登录和权限分配功能&#x…

[NSSCTF Round#16 Basic]了解过PHP特性吗 详细题解

知识点: MD5 弱类型比较绕过 intval()函数 is_numeric() 函数 array_search 弱类型比较 create_function 绕过 源码: <?php error_reporting(0); highlight_file(__FILE__); include("rce.php"); $checker_1 FALSE; $checker_2 FALSE; $checker_3 FALS…

大语言模型通用能力排行榜(2024年11月8日更新)

数据来源SuperCLUE 榜单数据为通用能力排行榜 排名 模型名称 机构 总分 理科 文科 Hard 使用方式 发布日期 - o1-preview OpenAI 75.85 86.07 76.6 64.89 API 2024年11月8日 - Claude 3.5 Sonnet&#xff08;20241022&#xff09; Anthropic 70.88 82.4…

Python绘制雪花

文章目录 系列目录写在前面技术需求完整代码代码分析1. 代码初始化部分分析2. 雪花绘制核心逻辑分析3. 窗口保持部分分析4. 美学与几何特点总结 写在后面 系列目录 序号直达链接爱心系列1Python制作一个无法拒绝的表白界面2Python满屏飘字表白代码3Python无限弹窗满屏表白代码4…

QT_CONFIG宏使用

时常在Qt代码中看到QT_CONFIG宏&#xff0c;之前以为和#define、DEFINES 差不多&#xff0c;看了定义才发现不是那么回事&#xff0c;定义如下&#xff1a; 看注释就知道了QT_CONFIG宏&#xff0c;其实是&#xff1a;实现了一个在编译时期安全检查&#xff0c;检查指定的Qt特性…

OBOO鸥柏“触摸屏广告一体机交互”亮相2024中国珠海航展

2024年11月12日&#xff0c;第十五届中国国际航空航天博览会&#xff08;简称中国航展或珠海航展&#xff09;在珠海拉开帷幕。展会现场&#xff0c;既有OBOO鸥柏一大批高精尖液晶显示产品集体亮相&#xff0c;也有航天相关科技领域及飞行表演队炫技蓝天等。在中国航展的各个科…