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

代码随想录算法训练营第三十八天-动态规划-完全背包-139.单词拆分

  • 类似于回溯算法中的拆分回文串
  • 题目是要求拆分字符串,问这些字符串是否出现在字典里。但这道题可以反着来考虑,从字典中的单词能不能组成所给定的字符串
    • 如果这样考虑, 这个字符串就背包,容器
    • 字典中的单词就是一个一个物品
    • 问题就转化成这些物品能不能正好装满这个背包,而且这些物品可以使用多次
    • 因此这是一个完全背包类问题
  • 动规五部曲
    • dp[j]数组含义:把题目给定的字符串能不能用字典字符串来添满。字符串长度为j时,能被字典字符串来组成,就返回true,否则为false
    • 递推公式:道德字符串中[i, j]内容正好字典中,而且dp[i]也为true的话,dp[j]也就是true
    • 初始化值:dp[0]必须为true,否则递推出来的内容都会是false
      • 非0下标都要初始化为false
    • 遍历顺序:给定字符串的内容是确定的,也就是说字典中内容是一种排列效果来生成字符串,而不是组合出多种效果来组成字符串(也根本组不成)
      • 所以要先遍历背包,再遍历物品
class Solution {
public:bool wordBreak(std::string s, std::vector<std::string>& wordDict) {std::unordered_set<std::string> wordSet(wordDict.begin(), wordDict.end());std::vector<bool> dp(s.size() + 1, false);dp[0] = true;for (int i = 1; i <= s.size(); ++i) {for (int j = 0; j < i; ++j) {std::string word = s.substr(j, i - j);if (wordSet.find(word) != wordSet.end() && dp[j])dp[i] = true;}}return dp.at(s.size());}
};
  • 汇总

相关文章:

代码随想录算法训练营第三十八天-动态规划-完全背包-139.单词拆分

类似于回溯算法中的拆分回文串题目是要求拆分字符串&#xff0c;问这些字符串是否出现在字典里。但这道题可以反着来考虑&#xff0c;从字典中的单词能不能组成所给定的字符串 如果这样考虑&#xff0c; 这个字符串就背包&#xff0c;容器字典中的单词就是一个一个物品问题就转…...

ML基础-Jupyter notebook中的魔法命令

在 Jupyter Notebook 或 IPython 环境中&#xff0c;“魔法命令”&#xff08;Magic Commands&#xff09;是一些以百分号&#xff08;%&#xff09;或惊叹号&#xff08;!)开头的特殊命令&#xff0c;用于执行一些与代码运行环境相关的操作&#xff0c;而不仅仅是执行普通的 P…...

Zookeeper入门部署(单点与集群)

本篇文章基于docker方式部署zookeeper集群&#xff0c;请先安装docker 目录 1. docker初期准备 2.启动zookeeper 2.1 单点部署 2.2 集群部署 3. Linux脚本实现快速切换启动关闭 1. docker初期准备 拉取zookeeper镜像 docker pull zookeeper:3.5.6 如果拉取时间过长&#xf…...

Kafa分区策略实现

引言 Kafka 的分区策略决定了生产者发送的消息会被分配到哪个分区中&#xff0c;合理的分区策略有助于实现负载均衡、提高消息处理效率以及满足特定的业务需求。 轮询策略&#xff08;默认&#xff09; 轮询策略是 Kafka 默认的分区策略&#xff08;当消息没有指定键时&…...

Pyside/Pyqt中QWebEngineView和QWebEnginePage的区别

在 PySide/Qt 的 WebEngine 模块中&#xff0c;QWebEngineView 和 QWebEnginePage 是两个紧密相关但职责不同的类。以下是它们的核心区别和关系&#xff1a; 1. 职责区分 类名核心职责模块归属QWebEngineView作为可视化的窗口部件&#xff08;Widget&#xff09;&#xff0c;负…...

Kafka的内部通信协议

引言 kafka内部用到的常见协议和优缺点可以看看原文 Kafka用到的协议 本文奖详细探究kafka核心通信协议和高性能的关键 网络层通信的实现 基于 Java NIO&#xff1a;Kafka 的网络通信层主要基于 Java NIO 来实现&#xff0c;这使得它能够高效地处理大量的连接和数据传输。…...

强大到工业层面的软件

电脑数据删不干净&#xff0c;简直是一种让人抓狂的折磨&#xff01;明明已经把文件扔进了回收站&#xff0c;清空了&#xff0c;可那些残留的数据就像牛皮癣一样&#xff0c;怎么也除不掉。这种烦恼简直无处不在&#xff0c;让人从头到脚都感到无比烦躁。 首先&#xff0c;心…...

数据分析和AI丨应对AI实施挑战,工程领域AI应用的五大方法

工程领域的人工智能 &#xff08;AI&#xff09; 已经开始发挥价值&#xff0c;低代码和无代码工具正在使曾经仅属于专业数据科学家的 AI 能力变得大众化。 然而&#xff0c;并非工程领域的每个人都能从中受益&#xff0c;使用新的便捷的 AI 工具提高工作效率并不难&#xff0c…...

54. UDP协议

UDP协议 UDP&#xff08;User Datagram Protocol&#xff0c;用户数据报协议&#xff09;是一个无连接的传输层协议&#xff0c;它提供简单的、不可靠的信息传送服务。与TCP&#xff08;传输控制协议&#xff09;不同&#xff0c;UDP不提供数据包的排序、错误检查&#xff08;仅…...

AJAX笔记入门篇

黑马程序员视频地址&#xff1a; 黑马程序员前端AJAX入门到实战全套教程https://www.bilibili.com/video/BV1MN411y7pw?vd_source0a2d366696f87e241adc64419bf12cab&spm_id_from333.788.videopod.episodes&p2https://www.bilibili.com/video/BV1MN411y7pw?vd_source…...

深入解析Java集合框架:春招面试要点

在上一篇文章中&#xff0c;我们深入探讨了Java核心基础&#xff0c;这是学习Java的基石。而在实际的Java开发中&#xff0c;集合框架的使用频率极高&#xff0c;它为我们提供了丰富的数据结构和算法实现&#xff0c;极大地提高了开发效率。对于春招面试来说&#xff0c;集合框…...

【Elasticsearch】Elasticsearch的查询

Elasticsearch的查询 DSL查询基础语句叶子查询全文检索查询matchmulti_match 精确查询termrange 复合查询算分函数查询bool查询 排序分页基础分页深度分页 高亮高亮原理实现高亮 RestClient查询基础查询叶子查询复合查询排序和分页高亮 数据聚合DSL实现聚合Bucket聚合带条件聚合…...

STM32 PWM驱动直流电机

接线图&#xff1a; 代码配置&#xff1a; 根据驱动舵机的代码来写&#xff0c;与舵机不同的是&#xff0c;这次的引脚接到了PA2上&#xff0c;所以需要改一下引脚以及改为OC3通道。 另外还需在配置两个GPIO引脚&#xff0c;来控制电机的旋转方向&#xff0c;这里连接到了PA4与…...

系统思考—心智模式

“我们的大脑对连贯性的渴望远胜于对准确性的追求。”—诺贝尔经济学得主丹尼尔卡尼曼 在面对复杂的决策时&#xff0c;我们往往更倾向于寻找那些能够迅速串联起来的信息&#xff0c;而非深入挖掘每一个细节的真实性。这种倾向在日常生活中或许能帮助我们迅速作出决策&#xf…...

JavaScript_02 表单

表单常用演示: 1.图片 结果失真了... 2.切换图片 切换结果 3.表单:...

【Qt】06-对话框

对话框 前言一、模态和非模态对话框1.1 概念1.2 模态对话框1.2.1 代码QAction类 1.2.2 模态对话框运行分析 1.3 非模态对话框1.3.1 代码局部变量和成员变量setAttribute 类 1.3.2 现象解释 二、标准对话框2.1 提示对话框 QMessageBox2.1.1 现象及解释 2.2 问题对话框2.2.1 现象…...

AI学习指南Ollama篇-使用Ollama构建自己的私有化知识库

一、引言 (一)背景介绍 随着企业对数据隐私和效率的重视,私有化知识库的需求日益增长。私有化知识库不仅可以保护企业数据的安全性,还能提供高效的知识管理和问答系统,提升企业内部的工作效率和创新能力。 (二)Ollama和AnythingLLM的结合 Ollama和AnythingLLM的结合…...

2.策略模式(Strategy)

定义 定义一系列算法&#xff0c;把它们一个个封装起来&#xff0c;并且使他们可互相替换&#xff08;变化&#xff09;。该模式使算法可独立于使用它的客户程序&#xff08;稳定&#xff09;而变化&#xff08;拓展&#xff0c;子类化&#xff09;。 动机&#xff08;Motiva…...

Python里的小整数问题挺有意思的

简单来说&#xff0c;Python为了优化性能&#xff0c;会把一些常用的整数&#xff08;通常是-5到256&#xff09;提前创建好&#xff0c;放到一个“缓存池”里。这样&#xff0c;当你用到这些小整数时&#xff0c;Python就不用每次都重新创建对象了&#xff0c;直接从缓存池里拿…...

开源智慧园区管理系统对比五款主流产品探索智能运营新模式

内容概要 在这个数字化迅速发展的时代&#xff0c;园区管理也迎来了全新的机遇和挑战。众所周知&#xff0c;开源智慧园区管理系统作为一种创新解决方案&#xff0c;正逐步打破传统管理的局限性。它的开放性不仅使得系统可以根据具体需求进行灵活调整&#xff0c;也为用户提供…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

ubuntu22.04 安装docker 和docker-compose

首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...