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

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

news 2026/5/12 4:05:26

目录标题

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

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

动态规划

假设现在有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

利用大语言模型实现数据自动标注：Autolabel 实战指南

1. 项目概述&#xff1a;用大模型自动标注数据&#xff0c;告别人工标注的苦差事 如果你做过机器学习项目&#xff0c;尤其是监督学习&#xff0c;那你一定对数据标注这个环节又爱又恨。爱的是&#xff0c;有了高质量标注数据&#xff0c;模型性能才有保障&#xff1b;恨的是&a…...

编程新知 2026/5/12 3:43:39

VS Code图表神器：零配置用代码画UML、流程图与架构图

1. 项目概述&#xff1a;在VS Code里优雅地“画”图作为一名长期在技术文档、架构设计和日常笔记中与图表打交道的老兵&#xff0c;我深知一个痛点&#xff1a;从想法到一张清晰可用的图表&#xff0c;中间往往隔着“安装Java环境”、“配置GraphViz路径”、“折腾渲染引擎”等…...

编程新知 2026/5/12 3:07:35

VRM-VRChat双向转换引擎：打破虚拟角色平台壁垒的技术解决方案

VRM-VRChat双向转换引擎&#xff1a;打破虚拟角色平台壁垒的技术解决方案 【免费下载链接】VRMConverterForVRChat 项目地址: https://gitcode.com/gh_mirrors/vr/VRMConverterForVRChat VRM格式转换、VRChat SDK3兼容、Unity编辑器扩展、虚拟角色迁移、跨平台角色转换…...

编程新知 2026/5/12 2:28:10

AI技能（SKILL）中文翻译项目：打破语言壁垒，赋能中文AI社区

1. 项目概述&#xff1a;一个为中文AI社区“破壁”的翻译工程如果你和我一样&#xff0c;在过去一年里深度使用过Claude、ChatGPT或者各类AI Agent平台&#xff0c;那你一定对“SKILL”这个概念不陌生。简单来说&#xff0c;SKILL就是AI的“技能包”&#xff0c;它把特定领域的…...

编程新知 2026/5/12 2:07:05

光纤偏振测量：从琼斯矢量到庞加莱球，六种工具深度解析与工程实践

1. 从一道周五小测题说起&#xff1a;光纤测量中的偏振态表征上周五&#xff0c;我在整理旧资料时&#xff0c;翻到了EE Times在2015年发布的一篇“周五小测”文章&#xff0c;主题是光纤光学测量。其中第一道题就很有意思&#xff0c;它问的是&#xff1a;“以下哪种工具不能用…...

编程新知 2026/5/12 2:03:03

ARM Firmware Suite与Integrator开发板嵌入式开发指南

1. ARM Firmware Suite与Integrator开发板概述ARM Firmware Suite&#xff08;AFS&#xff09;是ARM架构下专为嵌入式系统开发设计的固件套件&#xff0c;在Integrator系列开发板上发挥着核心作用。这套工具链最初由ARM Limited在1999-2002年间开发&#xff0c;至今仍在许多传统…...

编程新知 2026/5/12 1:44:19

java+uniapp集成unipush2实现消息推送

一、开通uniPush2.0 1.实名认证 登录DCloud开发者中心&#xff0c;通过实名认证 2.进入UniPush控制台 HBuilderX中打开项目的manifest.json文件 导航在“App模块配置” → 项的“Push(消息推送)” → “UniPush”下点击配置 或者申请开通。 3.配置应用信息 在UniPush开通界面…...

编程新知 2026/5/12 1:37:54

TINA-TI仿真实战：从运放振铃到电源设计的电路调试指南

1. 为什么我们需要TINA-TI仿真软件 作为一个在硬件设计领域摸爬滚打多年的工程师&#xff0c;我见过太多因为电路设计问题导致的返工案例。记得有一次&#xff0c;我们团队花了两周时间手工焊接的样机&#xff0c;上电后运放输出端出现了严重的振铃现象&#xff0c;不得不全部拆…...

编程新知 2026/5/11 23:13:49

C++ 知识点22 函数模板

C 函数模板一、为什么要有函数模板&#xff1f;先看痛点&#xff1a;你要写两个交换函数&#xff0c;int 版、double 版&#xff1a;// int 交换 void swapInt(int &a, int &b) {int t a; a b; b t; } // double 交换 void swapDouble(double &a, double &b…...

编程新知 2026/5/11 21:14:51

从Kaggle竞赛到实战：基于XGBoost的Otto多分类产品识别系统构建

1. 从Kaggle竞赛到真实业务场景的跨越 第一次接触Otto数据集是在2015年的Kaggle竞赛上&#xff0c;当时只觉得这是个典型的多分类问题。直到去年为某跨境电商平台搭建商品自动分类系统时&#xff0c;我才真正理解这个案例的实战价值——90%的参赛者只关注模型精度&#xff0c;而…...

编程新知 2026/5/11 20:31:17