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

server/2024/11/19 3:29:58/

目录

  • 背包问题变种 (动态规划)
    • 题目
    • 题目分析
  • 连续可组成数字
    • 题目
    • 题目分析
  • 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/server/143064.html

相关文章

JS学习日记(jQuery库)

前言 今天先更新jQuery库的介绍&#xff0c;它是一个用来帮助快速开发的工具 介绍 jQuery是一个快速&#xff0c;小型且功能丰富的JavaScript库&#xff0c;jQuery设计宗旨是“write less&#xff0c;do more”&#xff0c;即倡导写更少的代码&#xff0c;做更多的事&#xf…

【计算机网络】协议定制

一、结构化数据传输流程 这里涉及协议定制、序列化/反序列化的知识 对于序列化和反序列化&#xff0c;有现成的解决方案&#xff1a;①json ②probuff ③xml 二、理解发送接收函数 我们调用的所有发送/接收函数&#xff0c;根本就不是把数据发送到网络中&#xff01;本质都是…

鸿蒙Navigation入门使用

Navigation组件适用于模块内和跨模块的路由切换&#xff0c;通过组件级路由能力实现更加自然流畅的转场体验&#xff0c;并提供多种标题栏样式来呈现更好的标题和内容联动效果。一次开发&#xff0c;多端部署场景下&#xff0c;Navigation组件能够自动适配窗口显示大小&#xf…

Vue2+ElementUI:用计算属性实现搜索框功能

前言&#xff1a; 本文代码使用vue2element UI。 输入框搜索的功能&#xff0c;可以在前端通过计算属性过滤实现&#xff0c;也可以调用后端写好的接口。本文介绍的是通过计算属性对表格数据实时过滤&#xff0c;后附完整代码&#xff0c;代码中提供的是死数据&#xff0c;可…

【MySQL】MySQL中的函数之JSON_REPLACE

在 MySQL 中&#xff0c;JSON_REPLACE() 函数用于在 JSON 文档中替换现有的值。如果指定的路径不存在&#xff0c;则 JSON_REPLACE() 不会修改 JSON 文档。如果需要添加新的键值对&#xff0c;可以使用 JSON_SET() 函数。 基本语法 JSON_REPLACE(json_doc, path, val[, path,…

React--》如何高效管理前端环境变量:开发与生产环境配置详解

在前端开发中&#xff0c;如何让项目在不同环境下表现得更为灵活与高效&#xff0c;是每个开发者必须面对的挑战&#xff0c;从开发阶段的调试到生产环境的优化&#xff0c;环境变量配置无疑是其中的关键。 env配置文件&#xff1a;通常用于管理项目的环境变量&#xff0c;环境…

java 读取 有时需要sc.nextLine();读取换行符 有时不需要sc.nextLine();读取换行符 详解

在 Java 中&#xff0c;使用 Scanner 类读取输入时&#xff0c;换行符的处理行为取决于所用的读取方法。不同方法的工作原理会影响是否需要额外调用 sc.nextLine() 来清理缓冲区中的换行符。 核心问题 根本原因&#xff1a;Scanner 是基于输入流工作的&#xff0c;而换行符&am…

Python中的with语句

with语句和上下文管理器 Python提供了 with 语句的写法&#xff0c;既简单又安全 文件操作的时候使用with语句可以自动调用关闭文件操作&#xff0c;即使出现异常也会自动关闭文件操作。 # 1、以写的方式打开文件 with open(1.txt, w) as f:# 2、读取文件内容f.write(hello wor…