当前位置: 首页 > 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…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...