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

Leecode刷题C语言之收集所有金币可获得的最大积分

news 来源：原创 2025/5/25 14:21:48

执行结果:通过

执行用时和内存消耗如下：

int dfs(int node, int parent, int f, int* coins, int k, int **children, int *childCount, int **memo) {if (memo[node][f] != -1) {return memo[node][f];}int res0 = (coins[node] >> f) - k;int res1 = coins[node] >> (f + 1);for (int i = 0; i < childCount[node]; ++i) {int child = children[node][i];if (child == parent) {continue;}res0 += dfs(child, node, f, coins, k, children, childCount, memo);if (f + 1 < 14) {res1 += dfs(child, node, f + 1, coins, k, children, childCount, memo);}}return memo[node][f] = fmax(res0, res1);
}int maximumPoints(int **edges, int edgesSize, int *edgesColSize, int *coins, int coinsSize, int k) {int* childCount = (int*)malloc(coinsSize * sizeof(int));memset(childCount, 0, coinsSize * sizeof(int));for (int i = 0; i < edgesSize; ++i) {int u = edges[i][0];int v = edges[i][1];childCount[u]++;childCount[v]++;}int** children = (int**)malloc(coinsSize * sizeof(int*));for (int i = 0; i < coinsSize; ++i) {children[i] = (int*)malloc(childCount[i] * sizeof(int));}memset(childCount, 0, coinsSize * sizeof(int));for (int i = 0; i < edgesSize; ++i) {int u = edges[i][0];int v = edges[i][1];children[u][childCount[u]++] = v;children[v][childCount[v]++] = u;}int **memo = (int **)malloc(coinsSize * sizeof(int *));for (int i = 0; i < coinsSize; i++) {memo[i] = (int *)malloc(14 * sizeof(int));memset(memo[i], -1, 14 * sizeof(int));}int result = dfs(0, -1, 0, coins, k, children, childCount, memo);for (int i = 0; i < coinsSize; ++i) {free(children[i]);free(memo[i]);}free(children);free(memo);free(childCount);return result;
}

解题思路：

这段代码实现了一个深度优先搜索（DFS）算法，用于解决一个特定的问题，该问题涉及到一个树状结构，每个节点都拥有一定数量的“硬币”（由coins数组表示），并且有一个特定的参数k。目标是在满足某些条件下，最大化能够收集到的硬币数量。以下是对代码思路的详细解释：

函数 `dfs`

参数解释：
- node：当前正在访问的节点。
- parent：当前节点的父节点，用于避免向上回溯时重复访问父节点，形成环路。
- f：当前考虑的位（bit），用于在coins数组中按位选择硬币数量。
- coins：一个整数数组，每个元素表示对应节点的硬币数量，通过位操作来访问不同范围内的硬币数量。
- k：一个阈值，用于与按位操作后的硬币数量进行比较。
- children：一个二维数组，存储每个节点的子节点列表。
- childCount：一个整数数组，存储每个节点的子节点数量。
- memo：一个二维数组，用于记忆化搜索，避免重复计算。
逻辑：
1. 记忆化检查：首先检查memo[node][f]是否已经被计算过，如果是，则直接返回结果。
2. 计算当前节点的贡献：
  - res0：当前节点在不考虑更高位的情况下，能够贡献的硬币数量（与k比较后）。
  - res1：当前节点在考虑更高位的情况下，能够贡献的硬币数量。
3. 递归遍历子节点：
  - 对于每个子节点，递归调用dfs函数，更新res0和res1。
  - 注意，当考虑更高位时（f + 1），只有f + 1 < 14时才进行递归，这可能是因为coins数组中的数值最多只有14位有效（或出于其他特定限制）。
4. 返回结果：返回fmax(res0, res1)，即两种情况下的最大值，并更新memo[node][f]。

函数 `maximumPoints`

参数解释：
- edges：一个二维数组，表示树的边，edges[i] = [u, v]表示节点u和节点v之间有一条边。
- edgesSize：edges数组的大小。
- edgesColSize：edges数组中每个子数组的大小（这里似乎未直接使用，但通常用于表示二维数组的第二维大小）。
- coins：一个整数数组，表示每个节点的硬币数量。
- coinsSize：coins数组的大小，也即节点的数量。
- k：与dfs函数中的k相同，用于比较硬币数量。
逻辑：
1. 初始化：为childCount、children和memo数组分配内存，并初始化。
2. 构建树的表示：通过遍历edges数组，构建每个节点的子节点列表和子节点数量。
3. 记忆化搜索：调用dfs函数，从根节点（假设为0）开始搜索，parent参数设为-1表示根节点没有父节点。
4. 释放内存：释放之前分配的内存，避免内存泄漏。
5. 返回结果：返回dfs函数的结果，即从根节点开始能够收集到的最大硬币数量。

总结

这段代码通过深度优先搜索（DFS）和记忆化搜索，在给定一个树状结构和每个节点的硬币数量的情况下，计算并返回在满足特定条件（与k比较）下能够收集到的最大硬币数量。通过位操作和递归，高效地遍历树并计算每个节点的贡献。

Leecode刷题C语言之收集所有金币可获得的最大积分

执行结果:通过执行用时和内存消耗如下： int dfs(int node, int parent, int f, int* coins, int k, int **children, int *childCount, int **memo) {if (memo[node][f] ! -1) {return memo[node][f];}int res0 (coins[node] >> f) - k;int res1 coins[no…...

编程日记 2025/5/25 14:21:48

STM32_SD卡的SDIO通信_基础读写

本篇将使用CubeMXKeil, 创建一个SD卡读写的工程。目录一、SD卡要点速读二、SDIO要点速读三、SD卡座接线原理图四、CubeMX新建工程五、CubeMX 生成 SD卡的SDIO通信部分六、Keil 编辑工程代码七、实验效果实现效果，如下图： 一、SD卡速读…...

编程日记 2025/5/24 2:43:11

新手理解：Android 中 Handler 和 Thread.sleep 的区别及应用场景

新手理解：Android 中 Handler 和 Thread.sleep 的区别及应用场景 Handler 是啥？Handler 的几个核心功能： Thread.sleep 是啥？Thread.sleep 的核心特点： 两者的区别它们的应用场景1. Handler 的应用场景2. Thread.sleep…...

编程日记 2025/5/23 10:36:13

C语言-----扫雷游戏

扫雷游戏的功能说明 ： • 使⽤控制台实现经典的扫雷游戏 • 游戏可以通过菜单实现继续玩或者退出游戏 • 扫雷的棋盘是9*9的格⼦ • 默认随机布置10个雷 • 可以排查雷： ◦ 如果位置不是雷，就显⽰周围有⼏个雷 ◦ 如果位置是雷，就…...

编程日记 2025/5/25 14:06:36

监控与调试：性能优化的利器 — ShardingSphere

在分布式数据库系统中，监控和调试是确保系统高效运行的关键。ShardingSphere 提供了多种监控和调试工具，帮助开发者实时跟踪和优化性能，识别瓶颈，进行故障排查，从而提升系统的稳定性和响应速度。本文将介绍如何使用 Sh…...

编程日记 2025/5/22 23:59:04

Kubernetes相关知识入门详解

一、Pod的滚动升级 1.服务升级的一般思路：停止与该服务相关的所有服务pod，重新拉去更新后的镜像并启动。这种方法存在一个比较现实的问题是逐步升级导致较长时间的服务不可用。 2.Kubernetes滚动升级的思路：通过滚动升级的命令创建新的rc&…...

编程日记 2025/5/25 14:01:52

多层 RNN原理以及实现

数学原理多层 RNN 的核心思想是堆叠多个 RNN 层，每一层的输出作为下一层的输入，从而逐层提取更高层次的抽象特征。 1. 单层 RNN 的数学表示首先，单层 RNN 的计算过程如下。对于一个时间步 t t t，单层 RNN 的隐藏状态 h t h_t…...

编程日记 2025/5/25 14:00:09

Unity阿里云OpenAPI 获取 Token的C#【记录】

获取Token using UnityEngine; using System; using System.Text; using System.Linq; using Newtonsoft.Json.Linq; using System.Security.Cryptography; using UnityEngine.Networking; using System.Collections.Generic; using System.Globalization; using Cysharp.Thr…...

编程日记 2025/5/25 10:13:01

java+vue项目部署记录

目录前言一、java和vue 二、部署记录 1.获取代码 2.运行前端 3.运行后端三、其他 1.nvm 总结前言近期工作需要部署一套javavue前后分离的项目，之前都略有接触，但属于不及皮毛的程度，好在对其他开发语言、html js这些还算熟&am…...

编程日记 2025/5/24 23:31:59

PID 控制算法（二）：C 语言实现与应用

在本文中，我们将用 C 语言实现一个简单的 PID 控制器，并通过一个示例来演示如何使用 PID 控制算法来调整系统的状态（如温度、速度等）。同时，我们也会解释每个控制参数如何影响系统的表现。什么是 PID 控制器&#xf…...

编程日记 2025/5/25 14:12:59

深入MapReduce——计算模型设计

引入通过引入篇，我们可以总结，MapReduce针对海量数据计算核心痛点的解法如下： 统一编程模型，降低用户使用门槛分而治之，利用了并行处理提高计算效率移动计算，减少硬件瓶颈的限制优秀的设计&#xff0c…...

编程日记 2025/5/19 19:08:57

在Spring Boot中使用SeeEmitter类实现EventStream流式编程将实时事件推送至客户端

😄 19年之后由于某些原因断更了三年，23年重新扬帆起航，推出更多优质博文，希望大家多多支持～ 🌷 古之立大事者，不惟有超世之才，亦必有坚忍不拔之志 🎐 个人CSND主页——Mi…...

编程日记 2025/5/25 3:05:36

Qt实践：一个简单的丝滑侧滑栏实现

Qt实践：一个简单的丝滑侧滑栏实现笔者前段时间突然看到了侧滑栏，觉得这个抽屉式的侧滑栏非常的有趣，打算这里首先尝试实现一个简单的丝滑侧滑栏。首先是上效果图 （C，GIF帧率砍到毛都不剩了） QProperty…...

编程日记 2025/5/25 14:08:00

基于ESP32-IDF驱动GPIO输出控制LED

基于ESP32-IDF驱动GPIO输出控制LED 文章目录基于ESP32-IDF驱动GPIO输出控制LED一、点亮LED3.1 LED电路3.2 配置GPIO函数gpio_config()原型和头文件3.3 设置GPIO引脚电平状态函数gpio_set_level()原型和头文件3.4 代码实现并编译烧录一、点亮LED 3.1 LED电路可以看到&#x…...

编程日记 2025/5/25 13:58:12

OpenCV文字绘制支持中文显示

OpenCV版本：4.4 IDE：VS2019 功能描述 OpenCV绘制文本的函数putText()不支持中文的显示，网上很多方法推荐的都是使用FreeType来支持，FreeType是什么呢？FreeType的官网上有介绍 FreeType官网 https://www.freetype.or…...

编程日记 2025/5/25 8:59:25

jenkins-k8s pod方式动态生成slave节点

一. 简述： 使用 Jenkins 和 Kubernetes (k8s) 动态生成 Slave 节点是一种高效且灵活的方式来管理 CI/CD 流水线。通过这种方式，Jenkins 可以根据需要在 Kubernetes 集群中创建和销毁 Pod 来执行任务，从而充分利用集群资源并实现更好的隔离性…...

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

消息队列篇--基础篇（消息队列特点，应用场景、点对点和发布订阅工作模式，RabbmitMQ和Kafka代码示例等）

1、消息队列的介绍消息（Message）是指在应用之间传送的数据，消息可以非常简单，比如只包含文本字符串，也可以更复杂，可能包含嵌入对象。消息队列（Message Queue，简称MQ&#xff09…...

编程日记 2025/5/16 11:40:12

Jetpack架构组件学习——使用Glance实现桌面小组件

基本使用 1.添加依赖添加Glance依赖: // For AppWidgets supportimplementation "androidx.glance:glance-appwidget:1.1.0"// For interop APIs with Material 3implementation "androidx.glance:glance-material3:1.1.0"// For interop APIs with Mater…...

编程日记 2025/5/19 19:24:15

go读取excel游戏配置

1.背景游戏服务器，配置数据一般采用csv/excel来作为载体，这种方式，策划同学配置方便，服务器解析也方便。在jforgame框架里，我们使用以下的excel配置格式。然后可以非常方便的进行数据检索，例如&#xff…...

编程日记 2025/5/22 5:47:20

Linux系统下速通stm32的clion开发环境配置

陆陆续续搞这个已经很久了。因为自己新电脑是linux系统无法使用keil，一开始想使用vscode里的eide但感觉不太好用；后面想直接使用cudeide但又不想妥协，想趁着这个机会把linux上的其他单片机开发配置也搞明白；而且非常想搞懂cmake…...

编程日记 2025/5/21 20:25:15

快慢指针及原理证明(swift实现)

目录链表快慢指针一、快慢指针基本介绍二、快慢指针之找特殊节点1.删除链表的倒数第k个结点题目描述解题思路 2.链表的中间节点题目描述解题思路三、快慢指针之环形问题1.判断环形链表题目描述解题思路 2.判断环形链表并返回入环节点题目描述解题思路 3.变种——判断快乐数题…...

编程日记 2025/5/21 11:30:34

web前端3--css

注意（本文一切代码一律是在vscode中书写） 1、书写位置 1、行内样式 //<标签名 style"样式声明"> <p style"color: red;">666</p> 2、内嵌样式 1、style标签里面写css代码 css与html之间分离 2、css属性:值…...

编程日记 2025/5/22 13:32:32

一文大白话讲清楚webpack基本使用——5——babel的配置和使用

文章目录一文大白话讲清楚webpack基本使用——5——babel的配置和使用1. 建议按文章顺序从头看，一看到底，豁然开朗2. babel-loader的配置和使用2.1 针对ES6的babel-loader2.2 针对typescript的babel-loader2.3 babel配置文件一文大白话讲清楚webpack基…...

编程日记 2025/5/20 11:08:22

Python自动化运维：一键掌控服务器的高效之道

《Python OpenCV从菜鸟到高手》带你进入图像处理与计算机视觉的大门！解锁Python编程的无限可能：《奇妙的Python》带你漫游代码世界在互联网和云计算高速发展的今天，服务器数量的指数增长使得手动运维和管理变得异常繁琐。Python凭借其强大的可读性和丰富的生态系统，成为…...

编程日记 2025/5/25 1:50:59

基于quartz，刷新定时器的cron表达式

文章目录前言基于quartz，刷新定时器的cron表达式1. 先看一下测试效果2. 实现代码前言如果您觉得有用的话，记得给博主点个赞，评论，收藏一键三连啊，写作不易啊^ _ ^。而且听说点赞的人每天的运气都不会太差&…...

编程日记 2025/5/22 16:37:09

HTML常用属性

HTML标签的常见属性包括许多不同的功能，可以为元素提供附加信息或控制元素的行为。以下是一些常见的属性及其解释： 1. src 描述：src（source）属性指定一个资源的路径，通常用于图像、音频、视频等标签。常见…...

编程日记 2025/5/17 23:27:50

在 Babylon.js 中使用 Gizmo：交互式 3D 操作工具

在 3D 应用程序中，交互式操作对象（如平移、旋转、缩放）是一个常见的需求。Babylon.js 提供了一个强大的工具——Gizmo，用于在 3D 场景中实现这些功能。本文将介绍如何在 Babylon.js 中使用 Gizmo，并展示如何通过代码实…...

编程日记 2025/5/25 14:05:00

蓝桥杯练习日常|递归-进制转换

蓝桥云课760数的计算一、递归题目： 我的解题代码： #include <iostream> using namespace std; int sum0; int main() {// 请在此输入您的代码int n;cin>>n;int fun(int n);fun(n); cout<<sum<<\n;return 0; } // void fu…...

编程日记 2025/5/22 10:15:26

LabVIEW滤波器选择与参数设置

在信号处理应用中，滤波器是去除噪声、提取目标信号的重要工具。LabVIEW 提供多种类型的滤波器（如低通、高通、带通、带阻），用户需要根据采样频率、信号特性和应用需求合理选择滤波器类型及参数设置。本文以采样率 100kHz&#xf…...

编程日记 2025/5/22 2:40:40

【c语言日寄】Vs调试——新手向

【作者主页】siy2333 【专栏介绍】⌈c语言日寄⌋：这是一个专注于C语言刷题的专栏，精选题目，搭配详细题解、拓展算法。从基础语法到复杂算法，题目涉及的知识点全面覆盖，助力你系统提升。无论你是初学者，还是…...

编程日记 2025/5/24 9:18:25

C#中的Timers.Timer使用用法及常见报错

System.Timers.Timer 是一个基于服务器的计时器，它可以在应用程序中定期触发事件。这个计时器特别适合用于多线程环境，并且不应该与用户界面(UI)直接交互。在 ASP.NET 中，通常使用 System.Timers.Timer 来处理周期性的任务。主要使用步骤&am…...

编程日记 2025/5/25 14:12:59

chrome小插件：长图片等分切割

前置条件： 安装有chrome谷歌浏览器的电脑使用步骤： 1.打开chrome扩展插件 2.点击管理扩展程序 3.加载已解压的扩展程序 4.选择对应文件夹 5.成功后会出现一个扩展小程序 6.点击对应小程序 7.选择图片进行切割，切割完成后会自动保存代码…...

编程日记 2025/5/25 14:09:52

mysql数据被误删的恢复方案

文章目录一、使用备份恢复二、使用二进制日志（Binary Log）三、使用InnoDB表空间恢复四、使用第三方工具预防措施数据误删是一个严重的数据库管理问题，但通过合理的备份策略和使用适当的恢复工具，可以有效地减少数据丢失的风险…...

编程日记 2025/5/25 3:27:03

K8S-Pod资源清单的编写，资源的增删改查，镜像的下载策略

1. Pod资源清单的编写 1.1 Pod运行单个容器的资源清单 ##创建工作目录 mkdir -p /root/manifests/pods && cd /root/manifests/pods vim 01-nginx.yaml ##指定api版本 apiVersion: v1 ##指定资源类型 kind: Pod ##指定元数据 metadata:##指定名称name: myweb ##用户…...

编程日记 2025/5/21 8:19:31

Unity Line Renderer Component入门

Overview Line Renderer 组件是 Unity 中用于绘制连续线段的工具。它通过在三维空间中的两个或两个以上的点的数组，并在每个点之间绘制一条直线。可以绘制从简单的直线到复杂的螺旋线等各种图形。 1. 连续性和独立线条连续性：Line Renderer 绘制的线条…...

编程日记 2025/5/23 10:36:07

计算机工程：解锁未来科技之门！

计算机工程与应用是一个充满无限可能性的领域。随着科技的迅猛发展，计算机技术已经深深渗透到我们生活的方方面面，从医疗、金融到教育，无一不在彰显着计算机工程的巨大魅力和潜力。在医疗行业，计算机技术的应用尤为突出。比如&a…...

编程日记 2025/5/20 8:18:44

翻译：How do I reset my FPGA?

文章目录背景翻译：How do I reset my FPGA?1、Understanding the flip-flop reset behavior2、Reset methodology3、Use appropriate resets to maximize utilization4、Many options5、About the author 背景在写博客《复位信号的同步与释放（同步复…...

编程日记 2025/5/18 2:10:35

在Unity中使用大模型进行离线语音识别

文章目录 1、Vosk下载下载vosk-untiy-asr下载模型在项目中使用语音转文字音频转文字2、whisper下载下载unity项目下载模型在unity中使用1、Vosk 下载下载vosk-untiy-asr Github链接：https://github.com/alphacep/vosk-unity-asr 进不去Github的可以用网盘夸克网盘链接：h…...

编程日记 2025/5/20 14:39:45

SpringBoot+Vue使用Echarts

前言在vue项目中使用echarts，本次演示是使用vue2 1 前端准备 echarts官网： https://echarts.apache.org/zh/index.html 官网提供了基本的使用说明和大量的图表 1.1 下载echarts 执行命令 npm install echarts 直接这样执行很可能会失败，…...

编程日记 2025/5/25 2:21:33

【QT】-explicit关键字

explicit explicit 是一个 C 关键字，用于修饰构造函数。它的作用是防止构造函数进行隐式转换。为什么需要 explicit？ 在没有 explicit 的情况下，构造函数可以用于隐式类型转换。这意味着，如果你有一个接受某种类型的参数的构造…...

编程日记 2025/5/24 23:59:23

docker: Device or resource busy

(base) [rootbddx-vr-gpu-bcc2 /]#rm -rf /ssd1/docker/overlay2/8d96a51e3fb78e434fcf2b085e952adcc82bfe37485d427e1e017361a277326d/ rm: cannot remove ‘/ssd1/docker/overlay2/8d96a51e3fb78e434fcf2b085e952adcc82bfe37485d427e1e017361a277326d/merged’: Device or re…...

编程日记 2025/5/25 2:18:24

函数 dfs

函数 maximumPoints

总结

相关文章：

函数 `dfs`

函数 `maximumPoints`