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

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

目录标题

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

抽牌概率问题 (动态规划)

动态规划

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

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

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

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...

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

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

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 仓库…...

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

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

Spring 中的 BeanWrapper

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

2024鹏城杯msic部分WP

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

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

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

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.…...

三十七、Python基础语法(异常)

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

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使用…...

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

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

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

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

数据库基础(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 年度分布式电力推进(DEP)系统发展探究

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

vue通过iframe方式嵌套grafana图表

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

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

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

SpringBoot配置Rabbit中的MessageConverter对象

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

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

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

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...