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

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

news 2026/3/27 6:45:05

目录标题

  • 抽牌概率问题 （动态规划）
    • 动态规划
    • 题目分析
    • 代码
  • 洗衣机问题 （贪心）
    • 题目
    • 题目分析

抽牌概率问题 （动态规划）

动态规划

假设现在有1~N N张牌 每张牌的序号就代表着他的大小 （1 2 … N）

现在假设你从该牌组中等概率的抽出一张之后放回

当累加和小于a的时候 你将一直抽牌

当累加和大于等于a 小于等于b的时候你赢

当累加和大于b的时候你输

现在请你返回你能获胜的概率

题目分析

这是谷歌的一道面试题 实际上是一道非常简单的动态规划题目

我们只需要考虑三种条件即可

  1. 假设当前值大于等于a 小于等于b 我们只需要返回1.0即可
  2. 假设当前值大于b 我们只需要返回0即可
  3. 假设当前值小于a 则我们需要返回所有可能性的和除以N

只要想到这三种可能性 代码其实并不难写

关键在于如何想到

一是要多练 练多了这种题目基本上看一眼就知道要使用什么解法

二是根据题目找信息 题目中给出了三种范围 那么我们肯定可以很自然的想到这三种范围代表什么呢？

显然 可能性1 2 代表边界条件 3代表可能性 之后写出递归代码即可

代码

double process(int cur, int N, int a, int b) {if (cur > b) {return 0.0;}if (cur >= a || cur <= b) {return 1.0;}double ans = 0;for (int i = 1; i <= N; i++) {ans += process(cur + i , N , a , b);}ans /= N;return ans;
}

洗衣机问题 （贪心）

题目

本题为阿里面试题

题目为 有N台洗衣机 有 X件衣服在各个洗衣机内 现在要求洗衣机平分衣服

每台洗衣机内存放着的衣服不固定 现在可以从左到右移动 每次移动每台洗衣机可以将一件衣服向左或者向右移动

现在请问至少要移动多少轮才能让每个洗衣机平分衣服

题目分析

本题是典型的贪心 你见过就会 没见过就不会

它的思路其实跟动态规划的样本对应模型有些类似

都是找出一个特殊点 之后分析左右两测的可能性

比如说我们假设中间点为X 左边洗衣机总共多出了12件衣服 右边少了17件衣服

那么我们就需要至少17轮才能平分 （求最大值）

又比如 左边少了12件 右边也少了12件 这说明都集中在当前位置了 那么就需要12 + 12轮才能平分

之后我们从左到右遍历即可 这里的代码很简单就不给出了

这一题我们主要需要学习到一个从一个点到整体的思路

相关文章：

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

目录标题 抽牌概率问题 &#xff08;动态规划&#xff09;动态规划题目分析代码 洗衣机问题 &#xff08;贪心&#xff09;题目题目分析 抽牌概率问题 &#xff08;动态规划&#xff09; 动态规划 假设现在有1~N N张牌 每张牌的序号就代表着他的大小 &#xff08;1 2 … N&am…...

编程日记 2024/11/12 3:17:18

【计网不挂科】计算机网络期末考试（综合）——【选择题＆填空题＆判断题＆简述题】完整试卷

前言 大家好吖&#xff0c;欢迎来到 YY 滴计算机网络 系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过C的老铁 本博客主要内容&#xff0c;收纳了一部门基本的计算机网络题目&#xff0c;供yy应对期中考试复习。大家可以参考 本章是去答案版本。带答案的版本在下…...

编程日记 2024/11/12 3:15:15

2024年11月中旬记录

11.11 pigz的使用 压缩文件夹命令&#xff1a; tar -cvf - dir_name | pigz > xxx.tar.gz 解压分两步&#xff0c;pigz解压和tar解压&#xff1a; pigz -d xxx.tar.gz tar -xf xxx.tar...

编程日记 2024/11/12 3:14:15

单体架构 IM 系统之长轮询方案设计

在上一篇技术短文&#xff08;单体架构 IM 系统之核心业务功能实现&#xff09;中&#xff0c;我们讨论了 “信箱模型” 在单体架构 IM 系统中的应用&#xff0c;“信箱模型” 见下图。 客户端 A 将 “信件” 投入到客户端 B 的 “信箱” 中&#xff0c;然后客户端 B 去自己的 …...

编程日记 2024/11/12 3:08:08

Android Studio加载旧的安卓工程项目报错处理

文章目录 Invalid Gradle JDK configuration foundNDK not configuredCMake 3.10.2 was not found安装cmake适配cmake版本号 com.intellij.openapi.externalSystem.model.ExternalSystemExceptiongradle版本过低或下载不了下载gradle与依赖库超时替换gradle国内源替换Maven 仓库…...

编程日记 2024/11/12 3:05:06

阿里公告：停止 EasyExcel 更新与维护

最近&#xff0c;阿里发布公告通知&#xff0c;将停止对知名 Java Excel 工具库 EasyExcel 的更新和维护。EasyExcel 由阿里巴巴开源&#xff0c;作者是玉箫&#xff0c;在 GitHub 上拥有 30k stars、7.5k forks 的高人气。 据悉&#xff0c;EasyExcel 作者玉箫去年已从阿里离…...

编程日记 2024/11/12 3:04:05

Spring 中的 BeanWrapper

BeanWrapper 是 Spring 框架中的一个接口&#xff0c;它提供了一种方式来设置和获取 JavaBean 的属性。JavaBean 是一种特殊的 Java 类&#xff0c;遵循特定的编码约定&#xff08;例如&#xff0c;私有属性和公共的 getter/setter 方法&#xff09;&#xff0c;通常用于封装数…...

编程日记 2024/11/12 2:58:59

2024鹏城杯msic部分WP

MISC 网安第一课 查找字符key&#xff0c;发现key1&#xff0c;但是没看到key2 后缀改为zip&#xff0c;打开以后发现不一样的地方&#xff0c;三张图片和一个misc文件夹 图片放到010看一眼 编号为1的图片在文件尾发现key2 misc文件夹中是一个out.pcb&#xff0c;放到010发现…...

编程日记 2024/11/12 2:52:52

DAY23|回溯算法Part02|LeetCode: 39. 组合总和 、40.组合总和II 、131.分割回文串

目录 LeetCode: 39. 组合总和 基本思路 C代码 LeetCode: 40.组合总和II 基本思路 C代码 LeetCode: 131.分割回文串 基本思路 C代码 LeetCode: 39. 组合总和 力扣代码链接 文字讲解&#xff1a;LeetCode: 39. 组合总和 视频讲解&#xff1a;带你学透回溯算法-组合总和…...

编程日记 2024/11/12 2:51:51

go map

1、数据结构 // A header for a Go map. type hmap struct {// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.// Make sure this stays in sync with the compilers definition.count int // # live cells size of map.…...

编程日记 2024/11/12 2:50:50

三十七、Python基础语法（异常）

在 Python 中&#xff0c;异常是在程序执行过程中发生的错误情况。当出现异常时&#xff0c;程序的正常执行流程会被中断&#xff0c;并尝试寻找相应的异常处理机制来处理这个错误。 一、异常的类型 Python 中有很多内置的异常类型&#xff0c;例如&#xff1a; ZeroDivision…...

编程日记 2024/11/12 2:49:48

ThreadLocal的熟悉与使用

目录 1.ThreadLocal介绍2.ThreadLocal源码解析2.1 常用方法2.2 结构设计2.3 类图2.4 源码分析2.4.1 set方法分析2.4.2 get方法分析2.4.3 remove方法分析 3.ThreadLocal内存泄漏分析3.1 相关概念3.1.1 内存溢出3.1.2 内存泄漏3.1.3 强引用3.1.4 弱引用 3.2 内存泄漏是否和key使用…...

编程日记 2024/11/12 2:48:47

如何使用 Puppeteer 和 Browserless 抓取亚马逊产品数据？

您可以在亚马逊上找到所有有关产品、卖家、评论、评分、特价、新闻等的相关且有价值的信息。无论是卖家进行市场调研还是个人收集数据&#xff0c;使用高质量、便捷且快速的工具将极大地帮助您准确地抓取亚马逊上的各种信息。 为什么抓取亚马逊产品数据很重要&#xff1f; 亚…...

编程日记 2024/11/12 2:47:46

使用Python求解经典“三门问题”，揭示概率的奇妙之处

三门问题&#xff08;Monty Hall Problem&#xff09;是经典的概率问题&#xff0c;描述了一位游戏选手在三个门中选择一扇门&#xff0c;其中一扇门后有奖品&#xff0c;其余两扇门后是空的。选手做出选择后&#xff0c;主持人会打开另一扇空门&#xff0c;然后给选手一次更改…...

编程日记 2024/11/12 2:45:44

数据库基础(6) . DDL

3.2.DDL 数据定义语言 DDL : Data Definition Language 用于创建新的数据库、模式&#xff08;schema&#xff09;、表&#xff08;tables&#xff09;、视图&#xff08;views&#xff09;以及索引&#xff08;indexes&#xff09;等。 常见的DDL语句包括SHOW、CREATE、DRO…...

编程日记 2024/11/12 2:44:42

2024 年度分布式电力推进（DEP）系统发展探究

分布式电力推进 &#xff08;DEP&#xff09; 的发明是为了尝试和改进现代飞机&#xff1a;我们如何提高飞机的效率&#xff1f;提高它的机动性&#xff1f;缩短它的起飞和着陆距离&#xff1f; DEP 概念有望在提高性能的同时减少燃料消耗&#xff0c;在我们孜孜不倦地努力使航…...

编程日记 2024/11/12 2:42:40

vue通过iframe方式嵌套grafana图表

文章目录 前言一、iframe方式实现xxx.xxx.com拒绝连接登录不跳转Cookie 的SameSite问题解决不显示额外区域(kiosk1) 前言 我们的前端是vue实现的&#xff0c;监控图表是在grafana中的&#xff0c;需要在项目web页面直接显示grafana图表 一、iframe方式实现 xxx.xxx.com拒绝连…...

编程日记 2024/11/12 2:41:39

简单介绍下 Java 中的 @Validated 和 @Valid 注解的区别？

文章目录 Valid&#xff1a;专注单个对象的深度验证适用场景使用示例小结 Validated&#xff1a;聚焦接口分组的批量验证适用场景使用示例小结 主要区别总结如何选择&#xff1f;总结推荐阅读文章 在 Java 开发中&#xff0c;为了确保输入数据符合我们的要求&#xff0c;少不了…...

编程日记 2024/11/12 2:40:38

SpringBoot配置Rabbit中的MessageConverter对象

SpringAMQP默认使用SimpleMessageConverter组件对消息内容进行转换 SimpleMessageConverter&#xff1a; only supports String, byte[] and Serializable payloads仅仅支持String、Byte[]和Serializable对象Jackson2JsonMessageConverter&#xff1a;was expecting (JSON Str…...

编程日记 2024/11/12 2:37:35

C++ 错题本--duplicate symbol问题

顾名思义, duplicate symbol是重复符号的意思! 代码是用来做什么的(问题缘由 & 代码结构) 写排序算法, 提出了一个公共的头文件用来写一些工具方法, 比如打印数组内容. 以便于不同文件代码需要打印数组内容的时候,直接引入相关头文件即可, 但是编译时出现了 duplicate sym…...

编程日记 2024/11/12 2:33:30

Wan2.2-T2V-A5B提示词怎么写？新手快速出效果的实用指南

Wan2.2-T2V-A5B提示词怎么写&#xff1f;新手快速出效果的实用指南 1. 认识Wan2.2-T2V-A5B视频生成模型 Wan2.2-T2V-A5B是一款由通义万相开源的轻量级文本到视频生成模型&#xff0c;拥有50亿参数规模。虽然它生成的视频分辨率是480P&#xff0c;但在时序连贯性和运动推理能力…...

编程新知 2026/3/27 5:48:58

Pygame与MoviePy结合实战：打造动态视频游戏界面

1. 为什么需要Pygame与MoviePy结合&#xff1f; 很多游戏开发者在使用Pygame时都会遇到一个头疼的问题&#xff1a;视频播放功能。Pygame 2.0.0版本之后&#xff0c;官方移除了对视频模块的支持&#xff0c;这让很多想要在游戏中加入开场动画、过场CG或者动态背景的开发者感到束…...

编程新知 2026/3/27 3:17:02

程序员转行学习 AI 大模型： 提示词工程 ｜ 附精选学习资料

本文是程序员转行学习AI大模型的第12个核心知识点笔记&#xff0c;笔记后附精选的提示词工程学习资料。 当前阶段&#xff1a;还在学习知识点&#xff0c;由点及面&#xff0c;从 0 到 1 搭建 AI 大模型知识体系中。 系列更新&#xff0c;关注我&#xff0c;后续会持续记录分享…...

编程新知 2026/3/27 3:15:02

OpenClaw负载测试：GLM-4.7-Flash并发处理能力评估

OpenClaw负载测试&#xff1a;GLM-4.7-Flash并发处理能力评估 1. 测试背景与目标 上周在尝试用OpenClaw自动化处理一批市场调研报告时&#xff0c;遇到了一个典型问题&#xff1a;当我同时提交20份PDF文件让AI助手提取关键数据时&#xff0c;系统开始出现响应延迟和部分任务超…...

编程新知 2026/3/27 3:05:01

MATLAB Simulink代码生成全流程详解：涵盖环境配置、参数与信号配置、函数名配置、数...

matlab simulink代码生成 包括&#xff1a;环境配置&#xff0c;参数与信号配置&#xff0c;函数名配置&#xff0c;数据管理&#xff0c;代码生成&#xff0c;以及代码优化等 文档63页把Simulink模型变成可烧录的C代码&#xff0c;这事儿听起来挺玄乎&#xff0c;但只要你踩过…...

编程新知 2026/3/27 1:42:29

如何通过WechatRealFriends解决微信单向好友检测难题

如何通过WechatRealFriends解决微信单向好友检测难题 【免费下载链接】WechatRealFriends 微信好友关系一键检测&#xff0c;基于微信ipad协议&#xff0c;看看有没有朋友偷偷删掉或者拉黑你 项目地址: https://gitcode.com/gh_mirrors/we/WechatRealFriends 在数字化社…...

编程新知 2026/3/27 1:42:29

别再只盯着IoU了！用Python手把手教你计算语义分割的95% Hausdorff距离（附完整代码）

超越IoU&#xff1a;用Python实战95% Hausdorff距离的医学影像分割评估 当我们在医院看到CT扫描图像上肿瘤边缘被红色轮廓线精准勾勒时&#xff0c;很少有人会思考这背后的算法是如何评估自己分割结果的准确性的。传统指标如IoU&#xff08;交并比&#xff09;和Dice系数固然流…...

编程新知 2026/3/27 1:30:21

玩转AI！用FastAPI+RAG轻松构建智能文档问答系统，代码、文档全公开！

在企业数字化转型的浪潮中&#xff0c;我们常遇到这样一个痛点&#xff1a;海量的业务文档、研究报告、技术手册堆积如山&#xff0c;当需要从中寻找某个特定答案时&#xff0c;员工往往要花费数小时甚至数天进行翻阅。这不仅是效率的浪费&#xff0c;更是知识资产沉睡的体现**…...

编程新知 2026/3/27 1:13:53

Qt 5.12.8在Linux下编译qtvirtualkeyboard模块，我踩过的那些坑（附完整解决方案）

Qt 5.12.8在Linux下编译qtvirtualkeyboard模块的深度实践指南 当你在嵌入式或跨平台开发中突然发现系统自带的Qt缺少虚拟键盘模块时&#xff0c;那种感觉就像在沙漠里找到一瓶水却发现没带开瓶器。本文将带你深入探索在aarch64架构的Linux系统中&#xff0c;如何为预装的Qt 5.1…...

编程新知 2026/3/27 1:05:41

Windows右键菜单终极管理指南：3步告别臃肿，打造高效桌面体验

Windows右键菜单终极管理指南&#xff1a;3步告别臃肿&#xff0c;打造高效桌面体验 【免费下载链接】ContextMenuManager &#x1f5b1;️ 纯粹的Windows右键菜单管理程序 项目地址: https://gitcode.com/gh_mirrors/co/ContextMenuManager 你是否曾因Windows右键菜单过…...

编程新知 2026/3/27 0:25:29