当前位置： 首页 > news >正文

【蓝桥杯】算法笔记6

news 来源：原创 2025/8/25 23:48:18

1. 可行性剪枝应用

1.1. 题目

题目描述：
给定一个正整数n和一个正整数目标值target，以及一个由不同正整数组成的数组nums。要求从nums中选出若干个数，每个数可以被选多次，使得这些数的和恰好等于target。问有多少种不同的组合方式？

输入：

  • 第一行：n和target，表示数组长度和目标值

  • 第二行：n个不同的正整数，表示数组nums

输出：

  • 一个整数，表示不同的组合方式数量

示例：
输入：

3 4
1 2 3

输出：

4

解释：
组合方式为：
1+1+1+1
1+1+2
1+3
2+2

限制条件：

  • 1 ≤ n ≤ 20

  • 1 ≤ target ≤ 1000

  • 1 ≤ nums[i] ≤ 1000

1.2. 分析

本题主要考察可行性剪枝在回溯算法中的应用。我们需要在搜索过程中及时排除不可能达到目标的分支，从而减少不必要的计算。

1️⃣排序数组：首先将数组排序，这样可以在搜索时按照一定顺序进行，便于剪枝

2️⃣回溯搜索：使用回溯法尝试所有可能的组合

3️⃣可行性剪枝：

  • 当前和超过target时，立即返回

  • 从当前元素开始尝试，避免重复组合（如1+2和2+1被视为相同）

  • 剩余和无法用当前或更大的数达到时，提前终止

1.3. 代码

def combinationSum(nums, target):"""计算可以达到目标值的组合数量:param nums: 正整数数组:param target: 目标值:return: 组合数量"""nums.sort()  # 排序便于剪枝result = 0  # 记录结果数量def backtrack(start, remaining):"""回溯函数:param start: 当前开始位置，避免重复组合:param remaining: 剩余需要凑的值"""nonlocal result# 可行性剪枝1：剩余值为0，找到有效组合if remaining == 0:result += 1return# 可行性剪枝2：从start开始，避免重复组合for i in range(start, len(nums)):num = nums[i]# 可行性剪枝3：当前数已经大于剩余值，后面更大的数更不可能，直接终止if num > remaining:break# 递归尝试选择当前数backtrack(i, remaining - num)backtrack(0, target)return result# 读取输入
n, target = map(int, input().split())
nums

相关文章：

【蓝桥杯】算法笔记6

1. 可行性剪枝应用 1.1. 题目 题目描述： 给定一个正整数n和一个正整数目标值target，以及一个由不同正整数组成的数组nums。要求从nums中选出若干个数，每个数可以被选多次，使得这些数的和恰好等于target。问有多少种不同的组合方式？ 输入： 第一行：n和target，表示数组…...

编程日记 2025/8/25 23:48:18

C++ 中日期类的输入输出操作符重载实践

目录 引言 预备知识 输出流操作符 operator<< 重载 为什么要返回 ostream& 输入流操作符 operator>> 重载 实现思路 测试代码 总结 引言 在 C 编程中&#xff0c;当我们自定义数据类型时&#xff0c;为了让其能像内置类型一样方便地进行输入输出操…...

编程日记 2025/8/25 23:45:06

图论：最小生成树

最小生成树 &#xff08;无向无环图&#xff09; 概念 1.Prim算法 P3366 【模板】最小生成树 - 洛谷 邻接矩阵实现 #include<iostream> #include<cstring> using namespace std; const int INF 0x3f3f3f3f; const int N 5e3 10; int dis[N]; //记录每个结点到…...

编程日记 2025/8/25 23:46:50

linux中CosyVoice声音克隆安装教程——TTS文本转语音（数字人组件）

CosyVoice 作为一款先进的语音合成解决方案&#xff0c;其设计理念在于提供高效、稳定且灵活的语音生成工具。本教程将从环境配置、依赖安装、模型下载到服务部署全流程进行详细介绍&#xff0c;旨在为用户提供前瞻性的技术指导&#xff0c;同时兼顾细节解析和专业名词解释&…...

编程日记 2025/8/21 20:20:32

智能手表该存什么音频和文本？场景化存储指南

文章目录 为什么需要“场景化存储”&#xff1f;智能手表的定位手机替代不了的场景碎片化的场景存储 音频篇&#xff1a;智能手表该存什么音乐和音频&#xff1f;运动场景通勤场景健康场景 文本篇&#xff1a;哪些文字信息值得放进手表&#xff1f;&#xff08;部分情况可使用图…...

编程日记 2025/8/21 5:33:33

怎么检查网站CDN缓存是否生效

为什么要使用CDN缓存&#xff1f; 网站使用缓存可显著提升加载速度&#xff0c;减少服务器负载和带宽消耗&#xff0c;优化用户体验&#xff0c;增强架构稳定性&#xff0c;助力SEO优化&#xff0c;实现资源高效利用与性能平衡。 通过合理配置 CDN 缓存策略&#xff0c;可降低…...

编程日记 2025/8/25 23:45:07

win10安装gitbash工具

问题描述:在Windows下没有预装bash命令处理工具 # WInR输入cmd回车进入命令行,执行以下命令出现乱码 bash 无法使用bash命令 解决方案&#xff1a;下载安装gitbash命令行工具 Git Bash 是一个在 Windows 上运行的终端仿真器&#xff0c;集成了 Git 和 Bash shell&#xff0…...

编程日记 2025/8/22 4:28:44

买不起了，iPhone 或涨价 40% ？

周知的原因&#xff0c;新关税对 iPhone 的打击&#xff0c;可以说非常严重。 根据 Rosenblatt Securities分析师的预测&#xff0c;若苹果完全把成本转移给消费者。 iPhone 16 标配版的价格&#xff0c;可能上涨43%。 iPhone 16 标配的价格是799美元&#xff0c;上涨43%&am…...

编程日记 2025/8/25 23:47:32

企业级 ClickHouse Docker 离线部署实践指南20250407

企业级 ClickHouse Docker 离线部署实践指南 引言 在数据分析与日志处理日益重要的今天&#xff0c;ClickHouse 凭借其高性能、列式存储架构&#xff0c;成为企业在大数据分析中的首选引擎之一。本文基于一位金融行业从业者在离线网络环境中部署 ClickHouse 的真实实践过程&a…...

编程日记 2025/8/23 1:51:44

多域名​ SSL 证书能保护多少个域名？

一、基础保护数量范围​ 多域名 SSL 证书&#xff0c;顾名思义&#xff0c;可保护多个不同域名。通常情况下&#xff0c;不同证书颁发机构&#xff08;CA&#xff09;设定的基础保护数量有所差异。一般的多域名 SSL 证书能保护2 至 5 个域名&#xff0c;这些域名可以是完全独立…...

编程日记 2025/8/22 18:56:18

Linux系统学习Day04 阻塞特性，文件状态及文件夹查询

知识点4【文件的阻塞特性】 文件描述符 默认为 阻塞 的 比如&#xff1a;我们读取文件数据的时候&#xff0c;如果文件缓冲区没有数据&#xff0c;就需要等待数据的到来&#xff0c;这就是阻塞 当然写入的时候&#xff0c;如果发现缓冲区是满的&#xff0c;也需要等待刷新缓…...

编程日记 2025/8/24 17:37:21

【AI】高效地使用 AI 模型的 Prompt（提示词）

明确任务和目标 在使用 Prompt 之前&#xff0c;要清楚知道自己想要通过 AI 模型完成什么任务&#xff0c;例如生成文本、回答问题、进行翻译或创作故事等。明确的目标有助于构建更有针对性的 Prompt&#xff0c;引导模型生成符合期望的结果。 精准描述问题 提供具体细节&am…...

编程日记 2025/8/25 23:47:32

第二十：mysql——Undo Log、Redo Log和Binlog

二进制日志binlog&#xff08;归档日志&#xff09;、 事务日志redo log&#xff08;重做日志&#xff09; MySQL实例挂了或者宕机了&#xff0c;重启的时候InnoDB存储引擎会使用rede log日志恢复数据&#xff0c;保证事务的持久性和完整性 和undo log&#xff08;回滚日志&a…...

编程日记 2025/8/25 23:45:54

LogicFlow-前端流程图开发

LogicFlow-前端流程图开发 一、安装使用 1、安装logicflow 通过npm安装logicflow npm install logicflow/core --save# 插件包&#xff08;不使用插件时不需要引入&#xff09; npm install logicflow/extension --save2、创建实例 import LogicFlow from "logicflow/…...

编程日记 2025/8/25 23:46:51

第四讲：类与对象（下）

目录 1、再谈构造函数 1.1、构造函数体赋值 1.2、初始化列表 1.3、explicit关键字 2、static成员 3、友元 3.1、友元函数 3.2、友元类 4、内部类 5、匿名对象 6、拷贝对象时的优化&#xff08;了解&#xff09; 7、重新理解类与对象 8、日期类的实现 9、练习题 9…...

编程日记 2025/8/22 9:33:40

ReAct 框架 | 提示词工程（1）

ReAct 框架 1、什么是 ReAct 框架&#xff1f;2、基于 ReAct 框架的提示词3、结合 LangChain 框架使用4、总结 1、什么是 ReAct 框架&#xff1f; ReAct &#xff1a; Reasoning Acting &#xff0c;将推理与外部工具调用结合&#xff0c;通过交互式探索解决复杂问题。 优点…...

编程日记 2025/8/25 13:03:19

第一部分——Docker篇 第一章 Docker容器

关于系统的改造探索 开篇&#xff1a;系统改造的调研报告 第一部分——Docker篇 第一章 Docker容器 第二章 Docker安装 第三章 构建自定义镜像 第四章 搭建镜像仓库 第五章 容器编排 第六章 容器监控 文章目录 关于系统的改造探索第一部分——Docker篇 前言一、就是你了——…...

编程日记 2025/8/25 23:46:50

ubuntu，react的学习（1）

在此目录下&#xff0c;开启命令行 /home/kt/react 如下操作 tkt4028:~/react$ npm create vitelatest task-manager -- --template react Need to install the following packages: create-vite6.3.1 Ok to proceed? (y) y> npx > cva task-manager --template react…...

编程日记 2025/8/25 23:46:50

AR 赋能儿童娱乐：剧本杀与寻宝小程序搭建秘籍​

在科技飞速发展的当下&#xff0c;儿童娱乐领域正经历着一场创新变革。AR&#xff08;增强现实&#xff09;技术的融入&#xff0c;为儿童剧本杀与寻宝游戏带来了前所未有的沉浸式体验。通过搭建专属小程序&#xff0c;孩子们能够在虚拟与现实交织的世界中开启奇幻冒险。接下来…...

编程日记 2025/8/25 23:45:07

2017年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析

2017年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析 全国大学生数学建模竞赛（China Undergraduate Mathematical Contest in Modeling）是国家教委高教司和中国工业与应用数学学会共同主办的面向全国大学生的群众性科技活动，目的在于激励学生学习数学的积极性，提高学…...

编程日记 2025/8/25 16:47:14

密码学基础——分组密码的运行模式

前面的文章中文我们已经知道了分组密码是一种对称密钥密码体制&#xff0c;其工作原理可以概括为将明文消息分割成固定长度的分组&#xff0c;然后对每个分组分别进行加密处理。 下面介绍分组密码的运行模式 1.电码本模式&#xff08;ECB&#xff09; 2.密码分组链接模式&…...

编程日记 2025/8/25 9:27:10

zk源码—2.通信协议和客户端原理一

大纲 1.ZooKeeper如何进行序列化 2.深入分析Jute的底层实现原理 3.ZooKeeper的网络通信协议详解 4.客户端的核心组件和初始化过程 5.客户端核心组件HostProvider 6.客户端核心组件ClientCnxn 7.客户端工作原理之会话创建过程 1.ZooKeeper如何进行序列化 (1)什么是序列化…...

编程日记 2025/8/25 23:44:37

【NLP】Transformer网络结构（2）

一、Transformer 整体架构 Transformer 由 Encoder 和 Decoder 堆叠组成&#xff0c;每个 Encoder/Decoder 层包含以下核心模块&#xff1a; Encoder 层&#xff1a;Multi-Head Self-Attention → Add & LayerNorm → Feed-Forward → Add & LayerNormDecoder 层&…...

编程日记 2025/8/25 23:45:53

【LeetCode77】组合

题目描述 给定区间 [1, n] 和一个整数 k&#xff0c;需要返回所有可能的 k 个数的组合。 思路 算法选择&#xff1a;回溯算法 回溯算法是一种试探性搜索方法&#xff0c;非常适合用来解决组合问题。基本思想是&#xff1a; 从数字 1 开始&#xff0c;逐步构建组合。当当前组…...

编程日记 2025/8/25 23:44:33

1631. 最小体力消耗路径

文章目录 题意思路代码 题意 题目链接 思路 搜索 代码 class Solution { public:int minimumEffortPath(vector<vector<int>>& heights) {int m heights.size();int n heights[0].size();int x_add[] {0, 0, 1, -1};int y_add[] {1, -1, 0, 0};if (m …...

编程日记 2025/8/25 23:46:51

时间复杂度和空间复杂度

&#x1f31f; 各位看官好&#xff0c;我是maomi_9526&#xff01; &#x1f30d; 种一棵树最好是十年前&#xff0c;其次是现在&#xff01; &#x1f680; 今天来学习C语言的相关知识。 &#x1f44d; 如果觉得这篇文章有帮助&#xff0c;欢迎您一键三连&#xff0c;分享给更…...

编程日记 2025/8/22 21:23:02

Python基于OpenCV和SVM实现中文车牌识别系统GUI界面

说明&#xff1a;这是一个系统实战项目&#xff0c;如需项目代码可以直接到文章最后关注获取。 项目背景 随着智能交通系统和智慧城市的发展&#xff0c;车牌识别技术在车辆管理、交通监控、停车场收费等领域发挥着重要作用。传统的车牌识别系统主要针对英文和数字的识别&…...

编程日记 2025/8/25 23:44:34

用AbortController取消事件绑定

视频教程 React - &#x1f914; Abort Controller 到底是什么神仙玩意&#xff1f;看完这个视频你就明白了&#xff01;&#x1f4a1;_哔哩哔哩_bilibili AbortController的好处之一是事件绑定的函数已无需具名函数,匿名函数也可以被取消事件绑定了 //该代码2秒后点击失效…...

编程日记 2025/8/20 4:54:42

4月7日随笔

晚饭塔斯汀 下了晚自习买了一瓶百香果rio 还有一块五毛钱的老酸奶&#xff0c;这个糖吃的时候是真开心呀 英语课互动感觉越来越少了&#xff0c;我甚至看了十分钟的小排球 解析几何和微积分都听不进去了。就算坐在第三排还是会走神。但是不知道为什么我刷视频和打游戏的时…...

编程日记 2025/8/25 15:16:39

Android使用声网SDK实现音视频互动(RTC)功能

一、前期准备 1、注册声网账号 声网官网 2、创建项目 拿到AppID&#xff0c;主要证书 二、代码部分 先上一下官方提供的demo地址&#xff1a; Agora-RTC-QuickStart: 此仓库包含 Agora RTC Native SDK 的QuickStart示例项目。 - Gitee.comhttps://gitee.com/agoraio-comm…...

编程日记 2025/8/25 2:44:09

【go】slice的浅拷贝和深拷贝

浅拷贝(Shallow Copy) 浅拷贝是指只复制切片本身的结构&#xff08;指针、长度和容量&#xff09;&#xff0c;而不复制底层数组的元素。 实现方式 直接赋值&#xff1a; slice1 : []int{1, 2, 3} slice2 : slice1 // 浅拷贝切片操作&#xff1a; slice1 : []int{1, 2, 3} s…...

编程日记 2025/8/25 23:45:53

哑铃图：让数据对比一目了然【Dumbbell Chart】

没错&#xff0c;当我祭出 “哑铃” 阵列&#xff0c;你当如何破解&#xff0c;哈哈哈哈…此时&#xff0c;你可以适当怀疑笔者的精神状态了。但话说回来&#xff0c;如果稍加想象&#xff0c;把上图竖起来&#xff0c;“大致” 就是我要分享的 “哑铃图” 了。&#x1f611; …...

编程日记 2025/8/20 1:36:59

Spring Boot 集成 MongoDB 时自动创建的核心 Bean 的详细说明及表格总结

以下是 Spring Boot 集成 MongoDB 时自动创建的核心 Bean 的详细说明及表格总结&#xff1a; 核心 Bean 列表及详细说明 1. MongoClient 类型&#xff1a;com.mongodb.client.MongoClient作用&#xff1a; MongoDB 客户端核心接口&#xff0c;负责与 MongoDB 服务器建立连接、…...

编程日记 2025/8/21 8:08:44

水产养殖水下监控无人机推荐-P200PRO

水产养殖水下监控无人机推荐 | 潜 鲛 P200 PRO&#xff1a;您的“水下管家”&#xff0c;养鱼增产、降本增效的终极利器&#xff01; ——上海 棕航电子 科技&#xff0c;用技术守护每一方鱼塘 一、水产养殖的痛点&#xff1a;看不见的水下&#xff0c;才是赚钱的关键 …...

编程日记 2025/8/25 23:45:52

数据结构与算法-数学-基础数学算法（筛质数，最大公约数，最小公倍数，质因数算法，快速幂，乘法逆元，欧拉函数）

一&#xff1a;筛质数&#xff1a; 1-埃氏筛法 该算法核心是从 2 开始&#xff0c;把每个质数的倍数标记为合数&#xff0c;时间复杂度约为 O(nloglogn)。 #include <iostream> #include <vector>u sing namespace std; const int N 1000010; bool st[N]; …...

编程日记 2025/8/25 9:21:31

elasticSearch-搜索引擎

搜索引擎的优势 有了数据库分页查询&#xff0c;为什么还需要搜索引擎&#xff1f; 搜索引擎速度上很快数据库分页查询&#xff0c;随着数据库数据量增大&#xff0c;页数靠后&#xff0c;会导致搜索速度变慢&#xff0c;但是搜索引擎不会搜索引擎支持分词查询&#xff0c;地…...

编程日记 2025/8/21 8:24:32

MQTT-Dashboard-数据集成

sink [sɪŋk] 下沉&#xff1b;沉没&#xff1b;沉降&#xff1b;...

编程日记 2025/8/25 23:47:32

uni-app项目运行在浏览器、微信开发者工具、mumu模拟器

一、安装HBuilder X 1、下载HBuilder X 官网网址&#xff1a;https://dcloud.io/hbuilderx.html 根据电脑系统下载对应的版本&#xff08;我的电脑是Windows 10&#xff09; 2.安装HBuilder X 直接将HBuilderX.4.61.2025040322-alpha.zip解压到自己想要存放的文件夹中 双击…...

编程日记 2025/8/25 1:03:36

从零开始微调Embedding模型：基于BERT的实战教程

文章目录 背景微调实战装包介绍 项目文件介绍微调硬件配置要求 debug 重要代码分析【选看】资源分享参考资料 背景 在理解与学会了Naive RAG的框架流程后&#xff0c;就很自然地关注到embedding模型&#xff0c;与问题相关的文本召回&#xff0c;也有很多论文在做这方面的创新…...

编程日记 2025/8/25 23:47:33

机器学习（神经网络基础篇）——个人理解篇5(梯度下降中遇到的问题)

在神经网络训练中&#xff0c;计算参数的梯度是关键步骤。numerical_gradient 方法旨在通过数值微分&#xff08;中心差分法&#xff09;计算损失函数对网络参数的梯度。然而&#xff0c;该方法的实现存在一个关键问题&#xff0c;导致梯度计算错误。 1、错误代码示例&#xf…...

编程日记 2025/8/25 23:44:34

带label的3D饼图（threejs)

3D饼图 使用three.js实现&#xff0c;选择threejs的原因&#xff1a;label需要实际的显示在具体的饼对应的模块上 “three”: “^0.127.0”, <template><div><div ref"chartContainer" class"chart-container"></div><div clas…...

编程日记 2025/8/21 2:41:54

ragflow开启https访问:使用自签证书还是有不安全警告,如何解决

背景:在ragflow里的使用了自签证书来启动ragflow,在浏览器里访问还是不安全警告,如何解决 在方案2中，证书不会在访问网站时自动下载，需要你手动获取并安装证书文件。以下是具体操作步骤： 详细步骤：手动获取并安装自签名证书 第一步：获取证书文件 找到证书文件 证书文件位…...

编程日记 2025/8/25 19:12:13

条件变量核心要素

条件变量内部实现原理 原子性解锁阻塞机制&#xff1a; // pthread_cond_wait内部伪代码大致如下&#xff1a; int pthread_cond_wait(cond_t *cond, mutex_t *mutex) {atomic {unlock(mutex); // 原子操作中先释放互斥锁block_thread(); // 立即将线程加入等待队列…...

编程日记 2025/8/19 20:13:54

C语言求鞍点

我们先在第一行中找出最大的值&#xff0c;然后在该列中找出最小值看这两个是否相等。 若是相等&#xff0c;那么这个数就是鞍点跳出循环 若是不想等&#xff0c;则继续在下一行寻找&#xff0c;若是一直到整体的循环都结束了还是没有&#xff0c;那么不存在鞍点。 运行结果:…...

编程日记 2025/8/18 0:31:57

XELA机器人多种“形态和玩法”的Uskin磁性阵列式三轴触觉传感器，你使用过了吗？

XELA Robotics为机器人行业提供创新的磁性触觉传感技术&#xff0c;uSkin触觉传感器是一种高密度的三轴触觉传感器&#xff0c;因其轻薄、表面柔软耐用和布线少的结构设计&#xff0c;可以轻松集成到机器人本体&#xff0c;灵巧手&#xff0c;机器人夹爪等部位&#xff0c;使机…...

编程日记 2025/8/17 22:18:49

转换效率高达 96%，12V转5V同步降压WD5030

特点1 宽输入电压范围&#xff1a;能在 7V 至 30V 的宽输入电压范围内工作&#xff0c;可适应多种不同电压等级的供电环境&#xff0c;无论是工业设备中的较高电压输入&#xff0c;还是便携式设备经过初步升压后的电压&#xff0c;都能良好适配&#xff0c;极大地拓展了应用的…...

编程日记 2025/8/25 20:25:53

请你回答一下单元测试、集成测试、系统测试、验收测试、回归测试这几步中最重要的是哪一步？

在软件测试的不同阶段中，每个环节都有其不可替代的价值，但若从工程效率和缺陷防控的全局视角来看，单元测试（Unit Testing） 是质量金字塔的基石，其重要性最为关键。以下是分层解析： 一、从缺陷修复成本看优先级 美国国家标准与技术研究院（NIST）研究显示： 单元测试阶段…...

编程日记 2025/8/24 11:20:27

QML和C++交互

目录 1 QML与C交互基础1.1 全局属性1.2 属性私有化(提供接口访问) 2 QT与C交互&#xff08;C创建自定义对象&#xff0c;qml文件直接访问&#xff09;3 QT与C交互&#xff08;qml直接访问C中的函数&#xff09;4 QT与C交互&#xff08;qml端发送信号 C端实现槽函数&#xff09;…...

编程日记 2025/8/20 7:40:22

2021年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析

2021年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析 全国大学生数学建模竞赛（China Undergraduate Mathematical Contest in Modeling）是国家教委高教司和中国工业与应用数学学会共同主办的面向全国大学生的群众性科技活动，目的在于激励学生学习数学的积极性，提高学…...

编程日记 2025/8/25 8:58:59

mariadb使用docker compose方式安装

问题 本地mac m1上面的mysql和mariadb突然不用使用了&#xff0c;重新安装也不想&#xff0c;最近mac系统也更新了&#xff0c;brew也更新了&#xff0c;重新安装mariadb还是不能正常使用&#xff0c;现在我打算使用docker来安装本地的mariadb了。 默认配置文件my.cnf 从容器…...

编程日记 2025/8/23 10:56:21