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

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

news 2026/2/7 20:42:33

目录标题

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

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

动态规划

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

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

编程新知 2026/2/4 19:38:41

以下是对华为 HarmonyOS NETX 5属性动画（ArkTS）文档的结构化整理，通过层级标题、表格和代码块提升可读性：

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

编程新知 2026/1/28 21:15:38

【SQL学习笔记1】增删改查+多表连接全解析（内附SQL免费在线练习工具）

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

编程新知 2026/2/5 4:36:53

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现，论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

编程新知 2026/1/31 10:55:22

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

编程新知 2025/11/10 19:08:45

企业如何增强终端安全？

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

编程新知 2026/1/29 9:14:58

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

编程新知 2026/1/27 12:17:05

MySQL体系架构解析（三）：MySQL目录与启动配置全解析

MySQL中的目录和文件 bin目录 在 MySQL 的安装目录下有一个特别重要的 bin 目录&#xff0c;这个目录下存放着许多可执行文件。与其他系统的可执行文件类似&#xff0c;这些可执行文件都是与服务器和客户端程序相关的。 启动MySQL服务器程序 在 UNIX 系统中&#xff0c;用…...

编程新知 2026/1/23 12:07:06

工厂方法模式和抽象工厂方法模式的battle

1.案例直接上手 在这个案例里面&#xff0c;我们会实现这个普通的工厂方法&#xff0c;并且对比这个普通工厂方法和我们直接创建对象的差别在哪里&#xff0c;为什么需要一个工厂&#xff1a; 下面的这个是我们的这个案例里面涉及到的接口和对应的实现类&#xff1a; 两个发…...

编程新知 2026/2/6 1:00:34

十二、【ESP32全栈开发指南： IDF开发环境下cJSON使用】

一、JSON简介 JSON&#xff08;JavaScript Object Notation&#xff09;是一种轻量级的数据交换格式&#xff0c;具有以下核心特性&#xff1a; 完全独立于编程语言的文本格式易于人阅读和编写易于机器解析和生成基于ECMAScript标准子集 1.1 JSON语法规则 {"name"…...

编程新知 2025/12/30 15:37:52