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

Leetcode837.新21点

news 来源：原创 2025/6/8 5:49:07

题目

837. 新 21 点

算法标签: 数学, 概率, 动态规划

思路

定义状态表示为 $f [i]$ , 表示分数达到 $i$ 的时候的概率, 分析状态计算, 假设当前的分数是 $i$ , 抽取到的牌得分数是 $x$ , 那么当前状态就会转移到 $f [i + x]$ , 状态转移方程如下

$\frac{1}{\text{maxPts}} \left( dp[i+1] + dp[i+2] + \cdots + dp[i+\text{maxPts}] \right)$

计算时间复杂度, 外层枚举分数, 内层也需要枚举分数, 总的时间复杂度来到了 $O(n ^ 2)$ , 时间复杂度过高, 需要进行优化, 推 $i = i - 1$ 时的表达式

$\frac{1}{\text{maxPts}} \left( dp[i] + dp[i+1] + \cdots + dp[i+\text{maxPts - 1}] \right)$

设 $t = ma x Pt s$ , $\frac {f[i + 1] \times t + f[i + 1] - f[i + t + 1]}{t}$ , 整理后得到

$\frac {f[i + 1] - f[i + t + 1]} {t}$

这样就将时间复杂度降低到 $O (n)$

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>using namespace std;const int N = 2e4 + 10;class Solution {
public:double new21Game(int n, int k, int maxPts) {if (k == 0) return 1.0;//当前分数是i, 并且分数不超过n的概率double f[N] = {0};for (int i = k; i <= n && i < k + maxPts; ++i) f[i] = 1.0;//计算当前分数是i再抽一张牌, 得分不超过n的概率f[k - 1] = 1.0 * min(n - k + 1, maxPts) / maxPts;for (int i = k - 2; i >= 0; --i) {f[i] = f[i + 1] + (f[i + 1] - f[i + maxPts + 1]) / maxPts;}return f[0];}
};

Leetcode837.新21点

目录题目算法标签: 数学, 概率, 动态规划思路代码题目 837. 新 21 点算法标签: 数学, 概率, 动态规划思路定义状态表示为 f [ i ] f[i] f[i], 表示分数达到 i i i的时候的概率, 分析状态计算, 假设当前的分数是 i i i, 抽取到的牌得分数是 x x x, 那么当前状态就会转移…...

编程日记 2025/5/25 0:17:30

【C到Java的深度跃迁：从指针到对象，从过程到生态】第四模块·Java特性专精 —— 第十五章泛型：类型系统的元编程革命

一、从C的void*到Java类型安全 1.1 C泛型的原始实现 C语言通过void*和宏模拟泛型，存在严重安全隐患： 典型泛型栈实现： #define DECLARE_STACK(type) \ struct stack_##type { \ type* data; \ int top; \ int capacity; \ }; #de…...

编程日记 2025/5/27 6:43:04

纯净无噪，智见未来——MAGI-1本地部署教程，自回归重塑数据本质

一、MAGI-1简介 MAGI-1 是一种逐块生成视频的自回归去噪模型，而非一次性生成完整视频。每个视频块（含 24 帧）通过整体去噪处理，当前块达到特定去噪阈值后，立即启动下一块的生成。这种流水线设计支持最多 4 个块的并发…...

编程日记 2025/5/4 4:38:25

BG开发者日志0427：故事的起点

1、4月26日晚上，BG项目的gameplay部分开发完毕，后续是细节以及试玩版优化。开发重心转移到story部分，目前刚开始， 确切地说以前是长期搁置状态，因为过去的四个月中gameplay部分优先开发。 --- 2、BG这个项目的起点…...

编程日记 2025/5/27 7:04:29

直播预告|TinyVue 组件库高级用法：定制你的企业级UI体系

TinyVue 是一个跨端跨框架的企业级 UI 组件库，基于 renderless 无渲染组件设计架构，实现了一套代码同时支持 Vue2 和 Vue3，支持 PC 和移动端，包含 100 多个功能丰富的精美组件，可帮助开发者高效开发 Web 应用。 4 月 …...

编程日记 2025/5/12 14:47:09

基于Jamba模型的天气预测实战

深入探索Mamba模型架构与应用 - 商品搜索 - 京东 DeepSeek大模型高性能核心技术与多模态融合开发 - 商品搜索 - 京东由于大气运动极为复杂，影响天气的因素较多，而人们认识大气本身运动的能力极为有限，因此以前天气预报水平较低。预报员在预…...

编程日记 2025/4/28 13:20:28

Customizing Materials Management with SAP ERP Operations

Customizing Materials Management with SAP ERP Operations...

编程日记 2025/4/28 13:18:20

使用 NServiceBus 在 .NET 中构建分布式系统

在 .NET 中，NServiceBus 依然是构建可靠、可扩展、异步消息驱动架构的强大工具。本文将为你讲解如何在 .NET 环境下集成 NServiceBus，帮助你理解其核心概念及配置方法，并快速上手构建基于消息的系统。一、NServiceBus 简介 NServiceBus …...

编程日记 2025/4/28 13:18:18

【Linux网络与网络编程】13.五种 IO 模型

前言在前面的学习中，有一个问题一直没有展开来说，即 IO 问题。 IO 到底有多少种方式呢？什么是高效的 IO 呢？ IO 本质上就是 INPUT 和 OUTPUT 。在网络中 INPUT 就是从网卡中获取数据，而 OUTPUT 就是向网卡中发送数据…...

编程日记 2025/4/28 13:18:18

Java后端开发day37--源码解析：TreeMap可变参数--集合工具类：Collections

（以下内容全部来自上述课程） 1. TreeMap 1.1 须知 1.1.1 Entry 节点初始为黑色：提高代码阅读性 1.1.2 TreeMap中的成员变量 comparator：比较规则root：红黑树根节点的地址值size：集合的长度和红黑树…...

编程日记 2025/4/28 13:18:17

海关瑞数后缀分析 rs

声明本文章中所有内容仅供学习交流使用，不用于其他任何目的，抓包内容、敏感网址、数据接口等均已做脱敏处理，严禁用于商业用途和非法用途，否则由此产生的一切后果均与作者无关！ 逆向过程部分python代码 cp execj…...

编程日记 2025/4/28 13:17:13

【合新通信】---Mini单路光模块（Mini SFF/USOT)

产品特性 l 高可靠、全金属外壳、抗振动设计 l 紧凑的结构设计, 超小模块尺寸 l 可插拔标准LC单模光纤连接器接口，方便动态和灵活的配置数据连接 l 每通道工作速率可达1.25Gbps，速率可向下兼容 l 单路发射光纤通道，内置1310nm波长光发射…...

编程日记 2025/4/28 13:17:11

Java详解LeetCode 热题 100(02):LeetCode 49. 字母异位词分组（Group Anagrams）详解

文章目录 1. 题目描述2. 理解题目3. 解法一：排序法3.1 思路3.2 Java代码实现3.3 代码详解3.4 复杂度分析3.5 适用场景4. 解法二：计数法4.1 思路4.2 Java代码实现4.3 代码详解4.4 复杂度分析4.5 适用场景5. 解法三：字符串哈希法5.1 思路5.2 Java代码实现5.3 代码详解5.4 复杂…...

编程日记 2025/4/28 13:16:08

【每日随笔】文化属性 ① ( 天机 | 强势文化与弱势文化 | 文化属性的形成与改变 | 强势文化具备的特点 )

文章目录一、文化属性1、天机2、文化属性的强势文化与弱势文化强势文化弱势文化二、文化属性的形成与改变1、文化属性形成2、文化属性改变3、文化知识的阶层三、强势文化具备的特点一、文化属性 1、天机如果想要了解这个世界的底层架构 , 就需要掌握洞察事物本质的能…...

编程日记 2025/5/13 3:00:09

Java + Seleium4.X + TestNG自动化技术

系列文章目录文章目录系列文章目录前言一、 Java版Selenium自动化测试框架介绍和原理1.1 什么是Seleium1.2 特点1.3 注意点二、安装SeleiumChrome环境创建Maven项目2.1 安装Seleium Chrome环境2.2 Maven环境三、Selenium4.X UI元素定位实战3.1 ID选择器3.2 Name选择器3.…...

编程日记 2025/4/28 13:15:00

Spark SQL核心概念与编程实战：从DataFrame到DataSet的结构化数据处理

一、Spark-SQL是什么 Spark SQL 是 Spark 用于结构化数据(structured data)处理的 Spark 模块。二、Hive and SparkSQL SparkSQL 的前身是 Shark，Shark是给熟悉 RDBMS 但又不理解 MapReduce 的技术人员提供的快速上手的工具。 Hive 是早期唯一运行在 Hadoop 上的 S…...

编程日记 2025/4/28 13:15:00

electron-vite 应用打包自定义图标不显示问题

// 修改electron-builder.yml ... win:executableName: xxx //可执行文件名称icon: build/icon.ico //你的图标路径 ...打包后，自定义图标不显示原因: 1 cannot execute causeexit status 2，安装包无法生成用管理员身份运行，win11右击开始…...

编程日记 2025/4/28 13:14:59

AI中Token的理解与使用总结

AI中Token的理解与使用总结什么是Token 在AI领域，特别是自然语言处理(NLP)中，Token是指将文本分割成的最小处理单元。Tokenization(分词)是将原始文本分解为Token的过程。 Token的几种形式单词级Token：以单词为基本单位示例：“Hello world” → [“Hello”, “world”…...

编程日记 2025/4/28 13:13:54

C++/SDL 进阶游戏开发 —— 双人塔防（代号：村庄保卫战 14）

🎁个人主页：工藤新一 🔍系列专栏：C面向对象（类和对象篇） 🌟心中的天空之城，终会照亮我前方的路 🎉欢迎大家点赞👍评论📝收藏⭐文章文章目录二…...

编程日记 2025/4/28 13:13:53

全栈量子跃迁：当Shor算法破解RSA时，我们如何用晶格密码重构数字世界的信任基岩？

一、量子威胁的降维打击 1. Shor算法的毁灭性力量 # Shor算法量子电路简化示例（Qiskit实现） from qiskit import QuantumCircuit from qiskit.circuit.library import QFTdef shor_circuit(n: int, a: int) -> QuantumCircuit:qc QuantumCircuit(2…...

编程日记 2025/4/28 13:10:34

python实战项目65：drissionpage采集boss直聘数据

python实战项目65：drissionpage采集boss直聘数据一、需求简介二、流程分析三、完整代码一、需求简介 boss直聘网站近期改版，改版之后代码需要做相应的升级维护。drissionpage采集网页数据是一种不错的方式，笔者认为比Selenium好用，使用方法大家可以自行查阅资料。boss直聘…...

编程日记 2025/4/28 13:08:24

常用的性能提升手段--提纲

上一篇文章里，介绍了提升性能的一种优化手段：池化。这篇文章来归纳整理一下其他的常见的提升性能的手段 1. 缓存 (Caching) 缓存可以说是计算机领域的万金油了，它无处不在。举个最简单的例子，CPU -> L1,L2,L3 Cache -> 内存。 CPU的处理速度要比内存快几个数量…...

编程日记 2025/4/28 13:07:20

天梯——现代战争

第一次做的时候，直接暴力，显然最后超时。暴力代码如下： #include<bits/stdc.h> using namespace std; const int N10005; bool mark1[N]{0},mark2[N]{0}; int p[N][N]; int main(){int n,m,k,a,b;cin>>n>>m>>k;fo…...

编程日记 2025/4/28 13:06:14

Codeforces Round 1021 (Div. 2) D. Baggage Claim（建图）

每周五篇博客：（4/5） https://codeforces.com/contest/2098/problem/D 题意每个机场都有一个行李索赔区，巴尔贝索沃机场也不例外。在某个时候，Sheremetyevo的一位管理员提出了一个不寻常的想法：将行李索…...

编程日记 2025/4/28 13:06:13

常用第三方库：shared_preferences数据持久化

常用第三方库：shared_preferences数据持久化前言 shared_preferences是Flutter中最常用的轻量级数据持久化解决方案，它提供了一个简单的key-value存储机制，适合存储用户配置、应用设置等小型数据。本文将从实战角度深入讲解shared_prefere…...

编程日记 2025/4/28 13:04:03

项目驱动 CAN-bus现场总线基础教程》随笔

阅读：《项目驱动 CAN-bus现场总线基础教程》仲裁段的实现有感而发感觉出人意外之处感觉出人意外之处最近在阅读入门的CAN相关书籍时，在介绍仲裁段是如何实现各节点之间，通讯仲裁功能的章节中，有如下一段描述： …...

编程日记 2025/4/28 13:04:02

WPF之XAML基础

文章目录 XAML基础：深入理解WPF和UWP应用开发的核心语言1. XAML简介XAML与XML的关系 2. XAML语法基础元素语法属性语法集合语法附加属性 3. XAML命名空间命名空间映射关系 4. XAML标记扩展静态资源引用数据绑定相对资源引用常见标记扩展对比 5. XAML与代码的关系XAM…...

编程日记 2025/4/28 13:02:55

测试基础笔记第十四天

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录一、字符串1.字符串2.字符串切片3.查找find（）4.去除两端空白字符 strip5.字符串转换大小写 lower、upper5.拆分 split()6.字符串的其他常见方…...

编程日记 2025/4/28 13:02:54

Java详解LeetCode 热题 100(01):LeetCode 1. 两数之和（Two Sum）详解

文章目录 1. 题目描述2. 理解题目3. 解法一：暴力枚举法3.1 思路3.2 Java代码实现3.3 代码详解3.4 复杂度分析3.5 适用场景 4. 解法二：哈希表法4.1 思路4.2 Java代码实现4.3 代码详解4.4 复杂度分析4.5 适用场景 5. 解法三：两遍哈希表法5.1 思…...

编程日记 2025/4/28 13:01:50

机器学习之三：归纳学习

正如人们有各种各样的学习方法一样，机器学习也有多种学习方法。若按学习时所用的方法进行分类，则机器学习可分为机械式学习、指导式学习、示例学习、类比学习、解释学习等。这是温斯顿在1977年提出的一种分类方法。有关机器学习的基本概念，…...

编程日记 2025/4/28 12:57:33

AI声像融合守护幼儿安全——打骂/异常声音报警系统的智慧防护

幼儿园是孩子们快乐成长的摇篮，但打骂、哭闹或尖叫等异常事件可能打破这份宁静，威胁幼儿的身心安全。打骂/异常声音报警系统，依托尖端的AI声像融合技术，结合语音识别、情绪分析与视频行为检测，为幼儿园筑起一道智能安全…...

编程日记 2025/5/20 21:42:48

2024ICPC网络赛第二场题解

文章目录 F. Tourist(签到)I. Strange Binary(思维)J. Stacking of Goods(思维)A. Gambling on Choosing Regionals(签到)G. Game(数学)L. 502 Bad Gateway(数学)E. Escape(BFS)C. Prefix of Suffixes(kmp结论)K. match(01trie分治多项式乘法组合数) 题目链接 F. Tourist(签到…...

编程日记 2025/4/28 12:56:25

风控策略引擎架构设计全解析：构建智能实时决策系统

摘要本文深入探讨现代风控策略引擎的核心架构设计，结合金融反欺诈、电商交易风控等典型场景，详细解析实时决策、规则引擎、特征计算等关键技术模块的实现方案。通过分层架构设计、分布式计算优化、策略动态编排等创新方法，展示如何构建支撑每秒万级决策的高可用风控系统。…...

编程日记 2025/4/28 12:55:18

TensorFlow 安装全攻略

选择 TensorFlow 的原因： TensorFlow 是一个端到端平台，它提供多个抽象级别，因此您可以根据自己的需求选择合适的级别。您可以使用高阶 Keras API 构建和训练模型，该 API 让您能够轻松地开始使用 TensorFlow 和机器学习。如果您需…...

编程日记 2025/4/28 12:55:16

Dijkstra 算法代码步骤[leetcode.743网络延迟时间]

有 n 个网络节点，标记为 1 到 n。给你一个列表 times，表示信号经过有向边的传递时间。 times[i] (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。现在，…...

编程日记 2025/4/28 12:54:14

Ubuntu22.04/24.04 P104-100 安装驱动和 CUDA Toolkit

硬件环境使用一块技嘉 B85m-DS3H 安装 P104-100, CPU是带集成显卡的i5-4690. 先在BIOS中设置好显示设备优先使用集成显卡(IGX). 然后安装P104-100开机. 登入Ubuntu 后查看硬件信息, 检查P104-100是否已经被检测到 # PCI设备 lspci -v | grep -i nvidia lspci | grep NVIDIA …...

编程日记 2025/4/28 12:53:07

Golang 学习指南

目录变量与常量数据类型与控制结构常用数据结构函数与错误处理指针与并发Gin 框架与 go mod小结与参考资料 1. 变量与常量变量（var） 用于定义可变的值。可以指定类型，也可以自动推断类型。示例：var name string "Golang…...

编程日记 2025/4/28 12:53:02

Ubuntu 磁盘空间占用清理（宝塔）

目录前言1. 基本知识2. 实战前言 🤟 找工作，来万码优才：👉 #小程序://万码优才/r6rqmzDaXpYkJZF 爬虫神器，无代码爬取，就来：bright.cn 本身自搭建了一个宝塔，突然一下子多了好些空…...

编程日记 2025/4/28 12:51:59

AntBio: 2025 AACR Meeting - Charting New Oncology Frontiers Together

AntBio cordially invites you to attend the 2025 AACR Annual Meeting and jointly chart a new course in oncology research! The global benchmark for cancer research and therapeutics—the 2025 American Association for Cancer Research (AACR) Annual Meeting—wi…...

编程日记 2025/4/28 12:51:53

目录

题目

算法标签: 数学, 概率, 动态规划

思路

代码

相关文章：