leetCode !! word break
方法一:字典树+动态规划
首先,创建node类,每个对象应该包含:一个node array nexts(如果有通往’a’的路,那么对应的nexts[0]就不该为null); 一个boolean 变量(如果到达的这个字母恰好是字典中某个候选串的结尾,那么 标记end=true);
然后,根据 字典,建立字典树;
接着,使用动态规划的方式,检查目标字符串str是否可以用字典中的候选串拼出来。具体地,dp[i]表示 str[i…] 是否可以用字典中的候选串拼出来。对于str[i…],枚举第一子串该如何划分,str[i…end]中end可取值i,i+1,…。检查str[i…end]是否在字典中,对应地余下str[end+1,…]是否也可以 用字典中的候选串拼出来,即dp[end+1]==true么? 二者都成立说明 str[i…]可以用字典中的候选串拼出来, 即dp[i]==true.对于str[i…]来说,只要找到一种拼接方式即可,于是break,去枚举下一个str[i-1,…]是否可以用字典中的候选串拼出来。
public boolean wordBreak(String word, List<String> dict){// build a treeNode root = new Node();for(String s:dict){Node cur = root;int index=0;char[] str = s.toCharArray();for(char c:str){index = c-'a';if(cur.nexts[index]==null){cur.nexts[index]=new Node();}cur = cur.nexts[index];}cur.end=true;}// checkchar[] chs = word.toCharArray();// dp[i]int n= chs.length;boolean[] dp = new boolean[n+1];dp[n]=true;// !!// if str[i..n-1] can be done, //then obviously dp[i] = str[i...n-1]&&dp[n] = true; // so dp[n] should be true;for(int i=n-1;i>=0;i--){Node cur = root;for(int end=i;end<n;end++){int index = chs[end]-'a';if(cur.nexts[index]==null) {break;// 剪枝,避免了无效的枚举}cur = cur.nexts[index];if(cur.end&&dp[end+1]){dp[i]=true;break;}}}return dp[0];}
方法2: 递归函数+哈希表
写一个递归函数 str[index…] ,以字典为标本,有多少种分解方式.
注:在力扣上做测试,它超过了时间限制。
public static boolean wordBreak(String s, List<String> wordDict) {return process(s, 0, new HashSet<>(wordDict)) != 0;}// s[0......index-1]这一段,已经分解过了,不用在操心// s[index.....] 这一段字符串,能够被分解的方法数,返回public static int process(String s, int index, HashSet<String> wordDict) {if (index == s.length()) {// this cutting pattern is acceptedreturn 1;}// index没到最后// index...index// index...index+1// index....index+2// index....endint ways = 0;for (int end = index; end < s.length(); end++) {// s[index....end]String pre = s.substring(index, end + 1);if (wordDict.contains(pre)) {ways += process(s, end + 1, wordDict);}}return ways;}
方法三:动态规划+哈希表
在方法一的基础上,把字典树换成哈希表。
运行效率上,显然不如用字典树的方法一。这主要是因为方法一中间遇到不在Trie上的字符就break,进入下一个开头的尝试,这可以视为一种“剪枝”,避免不必要的操作。
而,这里使用哈希表,只要用substring函数切出来的,都检查他是否在哈希表中,所以费时。
public boolean wordBreak(String word,List<String> dict){int n = word.length();char[] str = word.toCharArray();boolean[] dp = new boolean[n+1];dp[n]=true;HashSet<String> set = new HashSet<>(dict);for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(set.contains(word.substring(i, j+1))&&dp[j+1]){dp[i] = true;}}}return dp[0];}
相关文章:
leetCode !! word break
方法一:字典树动态规划 首先,创建node类,每个对象应该包含:一个node array nexts(如果有通往’a’的路,那么对应的nexts[0]就不该为null); 一个boolean 变量(如果到达的这个字母恰好是字典中某个候选串的结尾,那么 标记…...

基础学习——关于list、numpy、torch在float和int等数据类型转换方面的总结
系列文章目录 Numpy学习——创建数组及常规操作(数组创建、切片、维度变换、索引、筛选、判断、广播) Tensor学习——创建张量及常规操作(创建、切片、索引、转换、维度变换、拼接) 基础学习——numpy与tensor张量的转换 基础学习…...
华纳云美国Linux服务器常用命令分享
美国Linux服务器系统目前也是跟Windows操作系统一样用户量非常多,其简单的纯命令操作模式可以节省很多系统空间,本文小编就来分享一些美国Linux服务器系统常用的命令,希望能够给刚入门的美国Linux服务器系统的用户提供一些操作参考。 1、系统…...
【minio】8.x版本与SpringBoot版本不兼容报错
错误异常: <minio.version>8.4.3</minio.version><spring-boot.version>2.6.13</spring-boot.version>Description:An attempt was made to call a method that does not exist. The attempt was made from the following location:io.min…...

如何用chatGPT赚钱?
赚钱思路 1)初级-账号 对于新事物的出现,很多人对此都是抱着一个看热闹的态度,大家对于这个东西的整体认知水平是很低的! 所以这个时候的思路就是快速去抢占市场,去各个平台发一些和ChatGPT相关的视频和文章去抢占市…...

【Go编程语言】流程控制
流程控制 文章目录 流程控制一、if 语句1.if 嵌套语句 二、switch 语句三、for 循环四、string 程序的流程控制结构一具有三种:顺序结构,选择结构,循环结构 顺序结构:从上到下,逐行执行。默认的逻辑 选择结构…...

Sql Server 自动备份
Sql Server 自动备份 文章目录 Sql Server 自动备份1. 打开SQL Server,在管理下找到”维护计划”,右键点击”维护计划向导”,如图;2. 再次点击维护计划向导3. 在选择维护任务下勾选”备份数据库”、”清楚维护任务”4.选择需要备份…...

ThreadLocal的应用
1. ThreadLocal 是什么 JDK 对ThreadLocal的描述为: 此类提供线程局部变量。这些变量与普通变量的不同之处在于,每个访问一个变量的线程(通过其get或set方法)都有自己的、独立初始化的变量副本。ThreadLocal 实例通常是类中的私有…...
中值滤波_中值滤波原理
均值滤波是典型的线性滤波算法,它是指在图像上对目标像素给一个模板,该模板包括了其周围的临近像素(以目标象素为中心的周围8个象素,构成一个滤波模板,即去掉目标象素本身).再用模板中的全体像素的平均值来代替原来像素值.均值滤波也称为线性滤波,其采用的主要方法为领域平均法…...

day15 - 使用图像金字塔进行图像拼接
在我们之前的学习过程中,使用的都是恒定大小的图像,但是在某些情况下,我们需要使用不同分辨率的(相同)图像。例如,当在图像中搜索某些东西(例如人脸)时,我们不确定对象将…...

算法修炼之筑基篇——筑基一层初期(解决01背包问题)
✨博主:命运之光 ✨专栏:算法修炼之练气篇 ✨博主的其他文章:点击进入博主的主页 前言:学习了算法修炼之练气篇想必各位蒟蒻们的基础已经非常的扎实了,下来我们进阶到算法修炼之筑基篇的学习。筑基期和练气期…...
JVM的空间结构
目录 一、概述 二、分类 1.程序计数器区域(Program Counter Register): 2.Java虚拟机栈(Stack): 3.堆区(Heap): 4.方法区(Method Area): 5.本地方法栈(Native Method Stack): 一、概述 JVM分为5个主要区域&…...
图像分割的常用算法
图像分割是指将一幅图像划分成多个子区域或像素集合的过程,其中每个子区域或像素集合具有一定的统计特征或语义信息。图像分割是图像处理中的基础任务,其应用涵盖了医学影像、计算机视觉、机器人技术等多个领域。常用的图像分割算法包括: 1.…...
AI歌手真的可以吗
你听过AI歌手吗?近日,“AI孙燕姿”火遍全网,AI孙燕姿翻唱林俊杰的《她说》、周董的《爱在西元前》、赵雷的《成都》等等歌曲让网友听了直呼:“听了一晚上,出不去了。”你认为AI歌手会取代流行歌手成为主流吗࿱…...

Kubernetes高级存储
Kubernetes高级存储 PV PVC k8s支持的存储系统很多,全部掌握不现实。为了屏蔽底层存储实现的细节,方便用户使用,k8s引入PV和PVC两种资源对象。 PV(Persistent Volume)持久化卷,对底层共享存储的抽象,一般由k8s管理员进…...

云原生之使用Docker部署docker-compose-ui工具
云原生之使用Docker部署docker-compose-ui工具 一、Docker Compose UI介绍二、检查本地docker环境1.检查系统版本2.检查docker状态 三、下载Docker Compose UI镜像四、部署Docker Compose UI服务1.新建安装目录2.创建Docker Compose UI容器3.检查Docker Compose UI容器状态4.查…...

文心一言 vs GPT4
本周真是科技爱好者的狂欢节。GPT4和文心一言接连发布,AI工具已经开始走进千家万户。 拿文心一言发布会上的几个问题调戏了 GPT4 一下,看看表现如何。 第一个为文心的回答,第二个为GPT4 的回答。 1. 可以总结一下三体的核心内容吗…...
Tcl-5. format 命令
format 命令和 C 语言中的 printf 和 sprintf 命令类似。它根据一组格式说明来格式化字符 串。此命令不会改变被操作字符串的内容。 [语法]:format spec value1 value2 ... spec 变元包含了格式说明关键词和附加文字。使用%来引入一个关键词,后跟 0 个…...

BloombergGPT: 首个金融垂直领域大语言模型
BloombergGPT: 首个金融垂直领域大语言模型 Bloomberg 刚刚发布了一篇研究论文,详细介绍了他们最新的突破性技术 BloombergGPT。BloombergGPT是一个大型生成式人工智能模型,专门使用大量金融数据进行了训练,以支持金融行业自然语言处理 (NLP…...

CMake深度解析:掌握add_custom_command,精通Makefile生成规则
CMake深度解析:掌握add_custom_command,精通Makefile生成规则 1. CMake简介与基础知识1.1 CMake的基本概念(CMake Basic Concepts)1.1.1 项目(Project)1.1.2 目标(Target)1.1.3 命令…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...

JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...