day39|139.单词拆分 背包问题ending
139.单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例 1:
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2:
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释:返回 true
因为 "applepenapple"可以由 "apple" "pen" "apple" 拼接成。注意,你可以重复使用字典中的单词。
示例 3:
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
问题分析:
1、确定dp数组以及下标的含义
dp[j]:拆分字符串的长度为j,dp[j]=true表示可以拆分为一个或多个字典中出现的单词。
2、确定递推公式
完全背包,重复利用物品,且为排列数
字符串为背包,单词为物品,截字符串(j-len,j)看是否是一个单词,并且他的前序子串也是一个或多个单词,也就是判断是否为true
所以递推公式为:
if(j>=len&&dp[j-len]&&word.equals(s.substring(j-len,j)))就为true
3、dp数组初始化
初始化dp[0]=true,否则所有都为false
4、确定遍历顺序
本题要求是排列数,有顺序要求
5、打印dp数组
class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp=new boolean[s.length()+1];//有空字符串dp[0]=true;for (int j=1;j<=s.length();j++){for (String word:wordDict){int len=word.length();if (j>=len&&dp[j-len]&&word.equals(s.substring(j-len,j))){dp[j]=true;break;}}}/* for (int j=1;j<=s.length();j++){System.out.print(dp[j]+" ");}*/return dp[s.length()];}
}
相关文章:
day39|139.单词拆分 背包问题ending
139.单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 示例 1: 输入: s "leetcode",…...
Shell脚本编程
Shell编程 视频地址https://www.bilibili.com/video/BV1hW41167NW/?p1&vd_source977d52a6b92ce8b6ae67c16fc61f0428 第一章 Shell概述 大数据程序员为什么要学习Shell呢? 需要看懂运维人员编写的Shell程序偶尔会编写一些简单的Shell程序来管理集群…...
ChatGPT解答:JavaScript保存当前网页页面图片为pdf文件或者word文件,前端用vue2,给出详细的方案和代码
ChatGPT解答:JavaScript保存当前网页页面图片为pdf文件或者word文件,前端用vue2,给出详细的方案和代码 ChatGPTDemo Based on OpenAI API (gpt-3.5-turbo). JavaScript保存当前网页页面图片为pdf文件或者word文件,前端用vue2&am…...
Python基础学习11——文件
我们可以利用python对本电脑文件夹里的文件进行处理,python中提供了一系列相关的方法和函数供我们使用。 读取文件 我们现在在本python文件中有一个txt文件名为Lego,那么我们就可以利用python打开该文件 with open(Lego.txt) as file_text:contents …...
外网用户打不开公司的网站?web服务器端口映射到公网
我们经常会遇到这样的情景,在公司内部可以打开公司的网站,在家里或者外网却打不开,按照网上的做法,重新启动了服务器和iis,还是不行。许多用户设置了路由器端口映射功能,但是端口映射不成功怎么办ÿ…...
【CS224W】(task9)图神经网络的表示能力(更新中!!)
note 基于图同构网络(GIN)的图表征网络。为了得到图表征首先需要做节点表征,然后做图读出。GIN中节点表征的计算遵循WL Test算法中节点标签的更新方法,因此它的上界是WL Test算法。 在图读出中,我们对所有的节点表征&…...
binlog找回误删数据
1、检查当前是否开启binlog存储 输入命令show variables like %log_bin%;,结果如下 可以看到log_bin的值是ON,说明binlog开启了。 2、查找binlog的存储位置 这个去到数据库的my.cnf配置文件中寻找,有一个log_bin的配置 切换到log_bin的目…...
《程序员面试金典(第6版)》面试题 02.03. 删除中间节点
题目描述 若链表中的某个节点,既不是链表头节点,也不是链表尾节点,则称其为该链表的「中间节点」。 假定已知链表的某一个中间节点,请实现一种算法,将该节点从链表中删除。 例如: 传入节点 c(…...
Spring Boot
目录 SpringBoot SpringBoot创建和使用 什么是Spring Boot Spring Boot优点 Spring Boot项目的创建 项目目录介绍和运行 目录介绍 项目运行 SpringBoot核心设计思想 SpringBoot的配置文件 配置文件的作用 配置文件的格式 注意事项 properties配置文件 propertie…...
图论初入门
目录 一、前言 二、图的概念 三、例题及相关概念 1、全球变暖(2018年省赛,lanqiao0J题号178) 2、欧拉路径 3、小例题 4、例题(洛谷P7771) 一、前言 本文主要讲了树与图的基本概念,图的存储、DFS遍历…...
02-Oracle数据库的启动与关闭
本文章主要讲解Oracle数据库的启动与关闭方法,详细讲解启动Oracle的命令,三种启动数据库的方法及区别;关闭数据库的4种方法及他们的区别。 启动和关闭数据库 •数据库没启动前,只有拥有DBA权限或者以sysoper或sysdba身份才能连接到…...
网络营销培训完能达到什么水平?学完能创业吗?
网络营销本身就是一门创业的技术,很多人学习网络营销,往往担心学完以后技术达不到,再工作几年才可以创业,实际这是错误的理解,那么,网络营销培训完能达到什么水平?新手学员参加网络营销培训&…...
大数据技术之——zeppelin数据清洗
一、zeppelin的安装zeppelin解压后进入到conf配置文件界面。修改zeppelin-site.xml[roothadoop02 conf]# cp zeppelin-site.xml.template zeppelin-site.xml[roothadoop02 conf]# vim zeppelin-site.xml将IP地址和端口号设置成自己的修改 zeppelin-env.shexport JAVA HOME/opt/…...
Barra模型因子的构建及应用系列五之NonLinear Size因子
一、摘要 在前期的Barra模型系列文章中,我们构建了Size因子、Beta因子、Momentum因子和Residual Volatility因子,并分别创建了对应的单因子策略,本节文章在该系列下进一步构建NonLinear Size因子。从回测结果看,自2022年以来&…...
C++ 常用命令行开发工具(Linux)
文章目录1、简介2、gcc / g2.1 system(执行shell 命令)2.2 popen(建立管道I/O)2.3 vforkexec(新建子进程)3、clang3.1 下载和安装clang3.2 clang和gcc比较3.2.1 gcc3.2.2 clang3.2.3 LLVM4、make4.1 例子14…...
java基础学习 day47(抽象类,抽象方法)
1. 抽象方法 将共性的行为(方法)抽取到父类之后,由于每一个子类执行的内容是不一样的,所以,在父类中不能确定具体的方法体,该方法就可以定义为抽象方法。抽象方法定义格式: public abstract 返…...
Java代码弱点与修复之——Open redirect(开放重定向)
弱点描述 Open redirect , 开放重定向,是一种常见的安全漏洞,也被称为“重定向漏洞”。该漏洞通常出现在 Web 应用程序中,攻击者可以利用它将用户重定向到恶意站点,从而进行钓鱼攻击、恶意软件传播、诱骗等活动。 在 Java 中,通过重定向 HTTP 请求来实现应用程序中的跳转…...
Go 指针
指针在编程中,一个内存地址用来定位一段内存。通常地,一个内存地址用一个操作系统原生字(native word)来存储。 一个原生字在32位操作系统上占4个字节,在64位操作系统上占8个字节。 所以,32位操作系统上的理…...
shardingsphere5.1.1分表分库yaml配置 自定义策略
前言通过阅读官方稳定给出示例 https://shardingsphere.apache.org/document一、基本配置示例spring:sharding:datasource:names: ds0, ds1ds0:driver-class-name: com.mysql.jdbc.Driverurl: jdbc:mysql://localhost:3306/db0username: rootpassword: rootds1:driver-class-na…...
“探索未来:VR全景直播技术引领新媒体时代”
随着虚拟现实技术的不断发展,VR全景直播已经成为了越来越受欢迎的直播形式。VR全景直播可以让观众通过虚拟现实设备亲临直播现场,享受身临其境的观看体验。VR全景直播是什么? VR全景直播是虚拟现实技术和直播的结合。相对于传统直播ÿ…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
ui框架-文件列表展示
ui框架-文件列表展示 介绍 UI框架的文件列表展示组件,可以展示文件夹,支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项,适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...
写一个shell脚本,把局域网内,把能ping通的IP和不能ping通的IP分类,并保存到两个文本文件里
写一个shell脚本,把局域网内,把能ping通的IP和不能ping通的IP分类,并保存到两个文本文件里 脚本1 #!/bin/bash #定义变量 ip10.1.1 #循环去ping主机的IP for ((i1;i<10;i)) doping -c1 $ip.$i &>/dev/null[ $? -eq 0 ] &&am…...
LangChain【6】之输出解析器:结构化LLM响应的关键工具
文章目录 一 LangChain输出解析器概述1.1 什么是输出解析器?1.2 主要功能与工作原理1.3 常用解析器类型 二 主要输出解析器类型2.1 Pydantic/Json输出解析器2.2 结构化输出解析器2.3 列表解析器2.4 日期解析器2.5 Json输出解析器2.6 xml输出解析器 三 高级使用技巧3…...
SOC-ESP32S3部分:30-I2S音频-麦克风扬声器驱动
飞书文档https://x509p6c8to.feishu.cn/wiki/SKZzwIRH3i7lsckUOlzcuJsdnVf I2S简介 I2S(Inter-Integrated Circuit Sound)是一种用于传输数字音频数据的通信协议,广泛应用于音频设备中。 ESP32-S3 包含 2 个 I2S 外设,通过配置…...
持续交付的进化:从DevOps到AI驱动的IT新动能
文章目录 一、持续交付的本质:从手动到自动的交付飞跃关键特性案例:电商平台的高效部署 二、持续交付的演进:从CI到AI驱动的未来发展历程 中国…...
