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

左神算法基础巩固--5

news 2025/11/12 19:26:22

文章目录

  • 前缀树
    • 生成前缀树
    • 查询前缀树
      • 查询字符串加入过几次
      • 查询所有加入的字符串中，有几个是以pre这个字符串作为前缀
    • 删除前缀树中的某个字符串
  • 贪心算法
    • 解题

前缀树

在这里插入图片描述

生成前缀树

要想生成一棵前缀树，需要先创建一个根节点，这个根节点有26条分支对应26个字母、pass代表有多少个字符串经过，end代码有多少个字符串以这个节点为终止节点。
在想往这棵前缀树中添加字符串的话，先是将字符串分割为一个又一个字符，之后从根节点出发先判断树中存不存在已经创建的节点，如果存在便直接pass++，如果不存在便需要创建出来，再往下走。当字符串的所有节点都正确的存在与树中时，便在最后指向的节点出end++
在这里插入图片描述

在这里插入图片描述
在构建完这棵树后，树上的每个节点都代表着一些前缀信息，如：上图中的根节点下a分支下的节点，该节点的pass代表着以a为前缀的字符串的个数，其end代表着字符a的个数；上图中根节点下a分支下b分支的节点，该节点的pass代表着以ab为前缀的字符串的个数，其end代表着字符串ab的个数。

查询前缀树

查询字符串加入过几次

由前缀树每个节点的信息得知，查询字符串加入过几次可以由树中字符串最后一个字符对应节点的end得知
我们先将字符串分割为一个又一个字符，之后从根节点出发根据那些字符找到该字符的最后一个节点，并直接返回最后一个节点的end信息。
在这里插入图片描述

查询所有加入的字符串中，有几个是以pre这个字符串作为前缀

由前缀树每个节点的信息得知，查询字符串加入过几次可以由树中字符串最后一个字符对应节点的pass得知
我们先将字符串分割为一个又一个字符，之后从根节点出发根据那些字符找到该字符的最后一个节点，并直接返回最后一个节点的pass信息。
在这里插入图片描述

删除前缀树中的某个字符串

在删除前缀树中的某个字符串中时，首先需要判断树中是否存在，在确定存在后将字符串分割为字符，后根据字符找到字符所对应的各个节点，将每个节点的pass值均减一并判断当存在某个节点的pass值为0时将其下一个节点设为null，如果没有便在最后的节点的位置将end–
在这里插入图片描述

贪心算法

在这里插入图片描述

解题

在这里插入图片描述

在这里插入图片描述
在此题中，我们需要知道以宣讲的结束时间按从小到大排序并进行选择所能选择的宣讲的场次是最多的。这个的证明需要耗费很多的篇幅，因此便不在这里证明，感兴趣的可以自行去搜索了解
在这里插入图片描述

在这里插入图片描述
这道题的解法需要我们知道要想求得拼接后字典序最小，我们可以将两两拼接后得到的结果进行比较，当a在前b在后得到的字典序大于b在前a在后，那么我们便得到我们需要将b在前a在后这个局部最优解，之后我们再根据局部最优解便能得到全局最优解
在这里插入图片描述

在这里插入图片描述
这道题是典型的哈夫曼编码问题，可以使用哈夫曼编码解决这个问题，问题的证明请大家自行去看证明。
哈夫曼编码问题可以用小根堆解决，我们先用给定数组创建一个小根堆，每次从小根堆中取出两个数，之后将两数相加的结果记录下来加入到最后的代价中并将其相加后的结果重新投入到小根堆中，不断循环直到小根堆为空。
在这里插入图片描述

在这里插入图片描述
求解这道问题是我们可以使用一个小根堆和一个大根堆，小根堆负责存储按项目的花费存储，大根堆可以将当前资金能够满足的项目按收益存储起来。在求解这道问题时，我们先将所有项目存储到小根堆中，再进行k轮判断，将小根堆中所有能够满足条件的项目加入到大根堆中，之后再弹出大根堆中的项目，并用所弹出的项目的利润更新当前所有的资金数。

在这里插入图片描述

在这里插入图片描述
这道题可以用加入一个皇后便进行检查的方法进行求解
在下面的代码中，我们采用遍历每一列的方式进行解决，record数组的每个元素存储着每个皇后存放在那一列，我们用递归的方法将进行尝试，如果该列能够能够放置皇后便找到加上在当前情况下再放皇后的可能性
在这里插入图片描述

相关文章：

左神算法基础巩固--5

文章目录 前缀树生成前缀树查询前缀树查询字符串加入过几次查询所有加入的字符串中，有几个是以pre这个字符串作为前缀 删除前缀树中的某个字符串 贪心算法解题 前缀树 生成前缀树 要想生成一棵前缀树，需要先创建一个根节点，这个根节点有26条…...

编程日记 2025/1/9 10:21:28

Python的Matplotlib库应用（超详细教程）

目录 一、环境搭建 1.1 配置matplotlib库 1.2 配置seaborn库 1.3 配置Skimage库 二、二维图像 2.1 曲线（直线）可视化 2.2 曲线（虚线）可视化 2.3 直方图 2.4 阶梯图 三、三维图像 3.1 3D曲面图 3.2 3D散点图 3.3 3D散…...

编程日记 2025/1/9 10:20:26

负载均衡服务器要怎么配置？

目录 一、概述： 二、硬件配置： 三、操作系统配置： 四、负载均衡软件： 五、网络配置： 六、软件安装步骤： 6.1 安装 Nginx 6.2 安装 LVS 6.3 安装 HAProxy 6.4 安装 Keepalived 一、概述&#xff1…...

编程日记 2025/1/9 10:19:25

CANopen转EtherCAT网关连接伺服驱动

在现代工业自动化领域，CANopen和EtherCAT是两种常见的通信协议，各自在不同的应用场景中发挥着重要作用。然而，随着工业自动化系统的日益复杂化，不同设备间的通信需求也变得多样化。因此，如何实现不同协议设备之间的无缝…...

编程日记 2025/1/9 10:16:23

自动化测试脚本实践：基于 Bash 的模块化测试框架

前言 在现代软件开发中，测试自动化是确保软件质量和稳定性的核心手段之一。随着开发周期的缩短和功能模块的增多，手动测试逐渐无法满足高效性和准确性的需求。因此，测试人员需要依赖自动化工具来提升测试效率，减少人为干预和错误。…...

编程日记 2025/1/9 10:14:20

WebSocket 测试入门篇

Websocket 是一种用于 H5 浏览器的实时通讯协议，可以做到数据的实时推送，可适用于广泛的工作环境，例如客服系统、物联网数据传输系统， 基础介绍 我们平常接触最多的是 http 协议的接口，http 协议是请求与响应的模式&…...

编程日记 2025/1/9 10:12:17

Apache Traffic存在SQL注入漏洞(CVE-2024-45387)

免责声明: 本文旨在提供有关特定漏洞的深入信息，帮助用户充分了解潜在的安全风险。发布此信息的目的在于提升网络安全意识和推动技术进步，未经授权访问系统、网络或应用程序，可能会导致法律责任或严重后果。因此，作者不对读者基于本文内容所采取的任何行为承担责任。读者在…...

编程日记 2025/1/9 10:11:15

Centos7使用yum工具出现 Could not resolve host: mirrorlist.centos.org

在 CentOS 7 中使用 yum 工具时，出现 "Could not resolve host: mirrorlist.centos.org" 的错误，一般情况是因为默认的镜像源无法访问。 以下是一些常用的解决方法： 检查网络连接：首先使用 ping 命令测试网络连接是否…...

编程日记 2025/1/9 10:10:14

zookeeper shell操作和zookeeper 典型应用（配置中心、集群选举服务、分布式锁）

文章目录 引言I zookeeper客户端命令查看子节点 ls创建子节点 create获取节点信息 get更新节点数据 set删除节点 delete\ rmrII 监听机制node1：设置监听node3：修改监听节点node1:得到监听反馈III zookeeper 典型应用分布式锁集群选举服务数据发布/订阅（配置中心）引言 zk 的…...

编程日记 2025/1/9 10:08:11

Vue中Watch使用监听修改变动

使用注意 监听一个值时 多个值时...

编程日记 2025/1/9 10:06:04

Lua语言的文件IO

1、我们都知道，在任何语言当中都有输入输出，比如c语言当中就有很多printf,scanf,get ,put,gets,puts,文件io:open,read,write,close,标准io:fopen,fread,fwrite,fclose.在lua语言当中，也有相同的一些输入输出特性，叫io.open,io.re…...

编程日记 2025/1/9 10:05:02

C语言基本知识复习浓缩版：输出函数printf

输出函数printf学习 printf()的作用是将文本输出到屏幕上使用之前需要先引入stdio.h头文件printf函数在使用的时候，至少需要一个参数 printf() 是 C 语言标准库中的一个函数，用于将格式化的文本输出到标准输出设备（通常是屏幕）。…...

编程日记 2025/1/9 10:02:58

Ubuntu中使用miniconda安装R和R包devtools

安装devtools环境包 sudo apt-get install gfortran -y sudo apt-get install build-essential -y sudo apt-get install libxt-dev -y sudo apt-get install libcurl4-openssl-dev -y sudo apt-get install libxml2.6-dev -y sudo apt-get install libssl-dev -y sudo apt-g…...

编程日记 2025/1/9 10:00:55

Jmeter-压测时接口如何按照顺序执行

Jmeter-压测时接口如何按照顺序执行-临界部分控制器 在进行压力测试时，需要按照顺序进行压测，比如按照接口1、接口2、接口3、接口4 进行执行 查询结果是很混乱的，如果请求次数少，可能会按照顺序执行，但是随着次数增加…...

编程日记 2025/1/9 9:57:51

Ungoogled Chromium127 编译指南 MacOS篇（七）- 安装依赖包

1. 引言 在获取了 Ungoogled Chromium 的源代码之后，我们需要安装所有必要的依赖包。这些依赖包对于成功编译 Chromium 至关重要。本文将指导您完成所有必需软件包的安装。 2. 依赖包安装 2.1 使用 Homebrew 安装基础依赖 # 安装 Ninja 构建系统 brew install n…...

编程日记 2025/1/9 9:56:50

批量写入数据到数据库，卡顿怎么解决

在批量写入数据到数据库时，遇到卡顿或性能瓶颈是比较常见的问题。以下是一些可能的解决方案和优化策略，帮助你提高批量写入的性能： ### 1. **批量大小优化** - **调整批量大小**：尝试调整批量写入的数据量，找到一个平衡点。过大或过小的批量大小都可能影响性能。通常，批…...

编程日记 2025/1/9 9:55:49

Python爬虫 - 豆瓣图书数据爬取、处理与存储

文章目录 前言一、使用版本二、需求分析1. 分析要爬取的内容1.1 分析要爬取的单个图书信息1.2 爬取步骤1.2.1 爬取豆瓣图书标签分类页面1.2.2 爬取分类页面1.2.3 爬取单个图书页面 1.3 内容所在的标签定位 2. 数据用途2.1 基础分析2.2 高级分析 3. 应对反爬机制的策略3.1 使用 …...

编程日记 2025/1/9 9:52:46

Qt 5.14.2 学习记录 —— 칠 QWidget 常用控件（2）

文章目录 1、Window Frame2、windowTitle3、windowIcon4、qrc机制5、windowOpacity 1、Window Frame 在运行Qt程序后，除了用户做的界面，最上面还有一个框，这就是window frame框。对于界面的元素，它们的原点是Qt界面的左上角或win…...

编程日记 2025/1/9 9:50:39

在vue3项目中利用自定义ref实现防抖

一&#xff0c;效果展示 自定义ref实现防抖效果 二&#xff0c;代码部分 1在app.vue中 <template><input v-model"text"/><p class"result">{{text}}</p> </template><script setup> import {debounceRef} from ./u…...

编程日记 2025/1/9 9:49:37

服务器及MySQL安全设置指南

文章目录 Linux安全配置1、密码复杂度策略2、登陆失败策略3、登录超时策略4、安全日志记录5、账户策略5.1 创建系统管理员&#xff08;应该对/var进行授权&#xff0c;修改可能会影响到ssh登录&#xff09;5.2 创建安全管理员&#xff08;应该对/etc进行授权&#xff09;5.3 创…...

编程日记 2025/1/9 9:48:36

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

编程新知 2025/9/11 12:54:42

【Zephyr 系列 10】实战项目：打造一个蓝牙传感器终端 + 网关系统（完整架构与全栈实现）

🧠关键词：Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者：希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数：约 5200 字 ✨ 项目总览 在物联网实际项目中，**“终端 + 网关”**是…...

编程新知 2025/11/8 8:46:12

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作（核心）三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结，涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

编程新知 2025/8/11 1:05:59

C++ 求圆面积的程序（Program to find area of a circle）

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

编程新知 2025/11/9 15:32:13

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

编程新知 2025/11/12 6:42:27

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

编程新知 2025/11/12 8:16:24

Webpack性能优化：构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

编程新知 2025/10/14 13:57:17

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...

编程新知 2025/10/17 2:32:49

Java 与 MySQL 性能优化：MySQL 慢 SQL 诊断与分析方法详解

文章目录 一、开启慢查询日志&#xff0c;定位耗时SQL1.1 查看慢查询日志是否开启1.2 临时开启慢查询日志1.3 永久开启慢查询日志1.4 分析慢查询日志 二、使用EXPLAIN分析SQL执行计划2.1 EXPLAIN的基本使用2.2 EXPLAIN分析案例2.3 根据EXPLAIN结果优化SQL 三、使用SHOW PROFILE…...

编程新知 2025/7/24 5:10:25

数据结构第5章：树和二叉树完全指南（自整理详细图文笔记）

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...

编程新知 2025/11/9 17:11:00