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

开鲁企业网站建设企业网络搭建方案

开鲁企业网站建设,企业网络搭建方案,wordpress响应式模板工业用,东莞做网站企业铭代码随想录算法训练营第五十七天| 647. 回文子串 516.最长回文子序列 一、力扣647. 回文子串 题目链接 思路:对于字符串cabac,其中a,b,c,aba,cabac,都是回文子串,如果当前的字串是回文字串,那么它的字串中也会有回文…

代码随想录算法训练营第五十七天| 647. 回文子串 516.最长回文子序列

一、力扣647. 回文子串

题目链接
思路:对于字符串cabac,其中a,b,c,aba,cabac,都是回文子串,如果当前的字串是回文字串,那么它的字串中也会有回文字串,所以状态是有区间的,确定dp数组,dp[i][j]表示,区间[i,j]左闭右闭,表示该区间内的子串是否是回文子串。
当i=j时,一定是回文子串。
当s[i]=s[j],且i+1=j时,是回文子串,类似aa。
当s[i]=s[j],且i+2=j时,也就是类似于aba,i=0,j=2,只要中间的子串是回文子串,那么它也是,故只要dp[i+1][j-1]=true,即为回文子串。
遍历时要注意区间[i,j](i<j),且从下向上,从左向右。

class Solution {public int countSubstrings(String s) {int len = s.length(), result = 0;boolean[][] dp = new boolean[len][len];for (int i = len-1; i >= 0; i--) {for (int j = i; j < len; j++) {if (s.charAt(i) == s.charAt(j)) {if (j - i <= 1) {result++;dp[i][j] = true;}else if (dp[i+1][j-1]) {result++;dp[i][j] = true;}}}}return result;}
}

二、力扣 516.最长回文子序列

题目链接
思路:上面求回文子串数量,是连续的,这里求最长回文子串,是非连续的,依然是dp[i][j]区间[i,j]。
如果s[i]=s[j]那么,状态转移公式就出来了dp[i][j] = dp[i+1][j-1] + 2。
如果s[i]!=s[j]那么,就各取一个留最长的, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])。

class Solution {public int longestPalindromeSubseq(String s) {int len = s.length();int[][] dp = new int[len][len];for (int i = 0; i < len; i++) {dp[i][i] = 1;}for (int i = len-1; i >= 0; i--) {for (int j = i+1; j < len; j++) {if (s.charAt(i) == s.charAt(j)) {dp[i][j] = dp[i+1][j-1] + 2;}else {dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);}}}return dp[0][len-1];}
}
http://www.yidumall.com/news/73938.html

相关文章:

  • 申请域名后可以做自己的网站吗最新做做网站
  • 买外贸衣服的网站2022新闻热点10条
  • 天河区网站建设关于市场营销的100个问题
  • 网站建好了怎么做才赚钱危机公关
  • 今日头条做网站百度推广一年要多少钱
  • 小户型室内装修设计公司网站今日热点新闻事件摘抄2022
  • 北京做网站的外包公司泉州百度推广咨询
  • 什么软件做网站比较好云计算培训费用多少钱
  • 专业网站建设公司网络推广有哪些渠道
  • dw做网站教程吉林网络seo
  • 北京市建设教育协会网站查询石家庄seo排名公司
  • 响应式网页模版重庆seo网站推广费用
  • 天津建设人才网官网seo标签优化
  • 渭南网站建设与维护windows优化大师是什么
  • php网站怎么做post订单营销网站建设方案
  • 公关策划网站建设企业推广宣传方案
  • 百度seo最新算法郑州网站seo推广
  • 网上做一道题2元的网站深圳网络营销推广服务
  • 关于网站平台建设调研的函nba最新新闻
  • 广州做动态网站的公司新网站如何快速收录
  • 武汉做网站哪家公司好广告软文范例大全100
  • 天骏手表网站产品关键词大全
  • 佛山专业网站建设团队长沙网站定制
  • 高端文化网站模板爱链工具
  • 做自己网站做站长网站推广内容
  • b2c电商企业有哪些营销网站优化推广
  • 做网站多少费用陕西seo排名
  • 佛山营销型网站大数据精准获客软件
  • 为赌博网站做网络维护网络营销推广的方法有哪些
  • 路由器统一登录网站关于搜索引擎的搜索技巧