牛客NC181 单词拆分(一)【中等 动态规划,前缀树 Java,Go,PHP】

题目

在这里插入图片描述
题目链接:
https://www.nowcoder.com/practice/c0d32c1ce5744472a01b2351a2c2767f

思路

前缀树+动态规划

参考答案Java

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param s string字符串* @param dic string字符串一维数组* @return bool布尔型*/public boolean wordDiv (String s, String[] dic) {//前缀树+动态规划PreTreeNode trie = new PreTreeNode();for (String s1 : dic) {add(trie, s1);}int n = s.length();boolean[] dp = new boolean[n + 1];dp[n] = true;for (int i = n - 1; i >= 0 ; i--) {PreTreeNode cur = trie;for (int j = i; j < n ; j++) {char c = s.charAt(j);cur = cur.nexts.get(c);if (cur == null) break;if (cur.end > 0) {dp[i] = dp[i] | dp[j + 1];}}}return dp[0];}static class PreTreeNode {int pass = 0;int end = 0;Map<Character, PreTreeNode> nexts = new HashMap<>();}public void add(PreTreeNode root, String word) {if (word == null || word.length() == 0) return;PreTreeNode cur = root;cur.pass++;for (int i = 0; i < word.length() ; i++) {char c = word.charAt(i);if (!cur.nexts.containsKey(c))cur.nexts.put(c, new PreTreeNode());cur = cur.nexts.get(c);cur.pass++;}cur.end++;}
}

参考答案Go

package main/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param s string字符串* @param dic string字符串一维数组* @return bool布尔型*/
func wordDiv(s string, dic []string) bool {//前缀树+动态规划trie := &PreTreeNode{0, 0, map[byte]*PreTreeNode{}}for i := 0; i < len(dic); i++ {trie.Add(dic[i])}n := len(s)dp := make([]bool, n+1)dp[n] = truefor i := n - 1; i >= 0; i-- {cur := triefor j := i; j < n; j++ {c := s[j]tmp, ok := cur.nexts[c]if !ok {break}cur = tmpif tmp.End > 0 {dp[i] = dp[i] || dp[j+1]}}}return dp[0]
}type PreTreeNode struct {Pass intEnd  intnexts map[byte]*PreTreeNode
}func (node *PreTreeNode) Add(word string) {if len(word) == 0 {return}cur := nodecur.Pass++for i := 0; i < len(word); i++ {c := word[i]_, ok := cur.nexts[c]if !ok {cur.nexts[c] = &PreTreeNode{0, 0, map[byte]*PreTreeNode{}}}cur = cur.nexts[c]cur.Pass++}cur.End++}

参考答案PHP

<?php/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param s string字符串 * @param dic string字符串一维数组 * @return bool布尔型*/
function wordDiv( $s ,  $dic )
{// 前缀树+动态规划$trie = new Node();foreach ($dic as $word){add($trie,$word);}$n = strlen($s);$dp= array();$dp[$n] = true;for($i=$n-1;$i>=0;$i--){$cur = $trie;for($j=$i;$j<$n;$j++){$c = $s[$j];$cur =$cur->nexts[$c];if($cur==null ||empty($cur))break;if($cur->end >0){$dp[$i]=$dp[$i] ||$dp[$j+1];}}}return $dp[0];
}class Node{public $pass = 0;public $end =0;public $nexts = array();
}//添加到单词到前缀树
function add(&$root,$word){$cur =$root;$cur->pass++;for($i=0;$i<strlen($word);$i++){$c = $word[$i];if(!isset($cur->nexts[$c])){$cur->nexts[$c] = new Node();}$cur = $cur->nexts[$c];$cur->pass++;}$cur->end++;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/299068.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Docker、Kubernetes之间的区别

比较容器化工具&#xff1a;了解 Docker、Kubernetes 在应用程序部署和管理方面的差异。 基本概述 Docker 是一个流行的容器化平台&#xff0c;允许开发人员在容器中创建、部署和运行应用程序。 Docker 提供了一组工具和 API&#xff0c;使开发人员能够构建和管理容器化应用程…

C++输出格式控制

setprecision(n)可控制输出流显示浮点数的数字个数。C默认的流输出数值有效位是6&#xff0c;所以不管数据是多少&#xff0c;都只输出六位。如果setprecision(n)与setiosflags(ios::fixed)或者setiosflags(ios_base::fixed)合用&#xff0c;可以控制小数点右边的数字个数。set…

数据结构面试题报错调试方法记录

栈和队列报错调试 1.用栈实现队列 232. 用栈实现队列 - 力扣&#xff08;LeetCode&#xff09; 此题解题思路如下&#xff1a; 先将数据放在pushst栈里面&#xff0c;popst栈为空再把pushst栈里面的数据放进popst栈里面去&#xff0c;不为空则不执行。不为空时候直接拿取栈…

机器学习模型——关联规则

目录 关联规则 - 基本概念 关联规则的挖掘步骤: Apriori算法 Apriori算法简介&#xff1a; Apriori算法举例&#xff1a; Apriori算法优缺点&#xff1a; Apriori算法应用 FP-growth算法&#xff1a; FP-growth算法简介&#xff1a; FP-growth的数据结构&#xff1a; …

Mysql的基本命令

1 服务相关命令 命令描述systemctl status mysql查看MySQL服务的状态systemctl stop mysql停止MySQL服务systemctl start mysql启动MySQL服务systemctl restart mysql重启MySQL服务ps -ef | grep mysql查看mysql的进程mysql -uroot -hlocalhost -p123456登录MySQLhelp显示MySQ…

OLAP 和 OLTP

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 OLTP与OLAP的介绍OLTP&#xff08;on-line transaction processing&#xff09;&#xff1a;联机事务处理OLAP&#xff08;On-Line Analytical Processing&#xff…

Dockerd的使用

端口映射 存储卷 类似于mount&#xff0c;把真机的某个目录映射都容器里面 -v 选项可以有多个 利用存储卷修改配置文件 容器间网络模式 共享网络为 --networkcontainer&#xff1a;容器名 微服务架构 一种由容器为载体&#xff0c;使用多个小型服务组合来构建复杂的架构为…

【可靠性】陷阱电荷对TDDB影响的多尺度模拟

【From Accelerated to Operating Conditions: How Trapped Charge Impacts on TDDB in SiO2 and HfO2 Stacks】 文章总结&#xff1a; 本研究深入探讨了在SiO2和HfO2介质堆叠中&#xff0c;陷阱电荷对时间依赖介电击穿&#xff08;TDDB&#xff09;现象的影响。通过引入载流子…

ElementUI 表格横向滚动条时滚动到指定位置

ElementUI 表格横向滚动条时滚动到指定位置 getColumnOffset(columnProp) {this.$nextTick(() > {const table this.$refs.tableRef.$refs.multipleTable;const columns table.columns;const column columns.find((col) > col.property columnProp);if (column) {// …

Kafka基础 (上)

前言 各位清明 快乐呀,近期博主也是学习了一下kafka,以下是博主的一些学习笔记,希望对你有所帮助 前置知识 线程中的数据交互以及进程中的数据交互 我们知道线程之间可以使用堆空间进行数据交互的 但是如果发送方和接收方处理数据的效率差距过大,这里就会造成消息积压的问题,怎…

UE小:UE5.3无法创建C++工程

当您在使用Unreal Engine (UE) 构建项目时&#xff0c;如果遇到以下问题&#xff1a; Running C:/Program Files/Epic Games/UE\_5.3/Engine/Build/BatchFiles/Build.bat -projectfiles -project"C:/UEProject/Shp\_1/Shp\_1.uproject" -game -rocket -progress Usi…

Hippo4j线程池实现技术

文章目录 &#x1f50a;博主介绍&#x1f964;本文内容部署运行模式集成线程池监控配置参数默认配置 &#x1f4e2;文章总结&#x1f4e5;博主目标 &#x1f50a;博主介绍 &#x1f31f;我是廖志伟&#xff0c;一名Java开发工程师、Java领域优质创作者、CSDN博客专家、51CTO专家…

了解 Solidity 语言:构建智能合约的首选编程语言

了解 Solidity 语言&#xff1a;构建智能合约的首选编程语言 Solidity 是一种用于编写智能合约的高级编程语言&#xff0c;广泛应用于以太坊和其他以太坊虚拟机&#xff08;EVM&#xff09;兼容的区块链平台。它是以太坊智能合约的首选语言之一&#xff0c;具有丰富的功能和灵活…

【HTML】CSS样式(二)

上一篇我们学习了CSS基本样式和选择器&#xff0c;相信大家对于样式的使用有了初步认知。 本篇我们继续来学习CSS中的扩展选择器及CSS继承性&#xff0c;如何使用这些扩展选择器更好的帮助我们美化页面。 下一篇我们将会学习CSS中常用的属性。 喜欢的 【点赞】【关注】【收藏】…

最新在线工具箱网站系统源码

内容目录 一、详细介绍二、效果展示1.部分代码2.效果图展示 三、学习资料下载 一、详细介绍 系统内置高达72种站长工具、开发工具、娱乐工具等功能。此系统支持本地调用API&#xff0c;同时还自带免费API接口&#xff0c; 是一个多功能性工具程序&#xff0c;支持后台管理、上…

FPGA常用IP核之FIFO学习

IP核是FPGA芯片公司提供的逻辑功能块&#xff0c;在FPGA芯片中可以进行优化和预先配置&#xff0c;可以直接在用户设计的程序中使用&#xff0c;应用范围很广。在FPGA设计开发过程中使用IP核&#xff0c;可以大大的缩短开发周期&#xff0c;高度优化的IP核可以使FPG开发工程师专…

CANoe自带的TCP/IP协议栈中TCP的keep alive机制是如何工作的

TCP keep alive机制我们已经讲过太多次,车内很多控制器的TCP keep alive机制相信很多开发和测试的人也配置或者测试过。我们今天想知道CANoe软件自带的TCP/IP协议栈中TCP keep alive机制是如何工作的。 首先大家需要知道TCP keep alive的参数有哪些?其实就三个参数:CP_KEEP…

腾讯云容器与Serverless的融合:探索《2023技术实践精选集》中的创新实践

腾讯云容器与Serverless的融合&#xff1a;探索《2023技术实践精选集》中的创新实践 文章目录 腾讯云容器与Serverless的融合&#xff1a;探索《2023技术实践精选集》中的创新实践引言《2023腾讯云容器和函数计算技术实践精选集》整体评价特色亮点分析Serverless与Kubernetes的…

【C++航海王:追寻罗杰的编程之路】C++的类型转换

目录 1 -> C语言中的类型转换 2 -> 为什么C需要四种类型转换 3 -> C强制类型转换 3.1 -> static_cast 3.2 -> reinterpret_cast 3.3 -> const_cast 3.4 -> dynamic_cast 4 -> RTTI 1 -> C语言中的类型转换 在C语言中&#xff0c;如果赋值运…

PyQt ui2py 使用PowerShell将ui文件转为py文件并且将导入模块PyQt或PySide转换为qtpy模块开箱即用

前言 由于需要使用不同的qt环境&#xff08;PySide&#xff0c;PyQt&#xff09;所以写了这个脚本&#xff0c;使用找到的随便一个uic命令去转换ui文件&#xff0c;然后将导入模块换成qtpy这个通用库(支持pyside2-6&#xff0c;pyqt5-6)&#xff0c;老版本的是Qt.py(支持pysid…