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

简单个人网站制作流程怎么在百度发布信息

简单个人网站制作流程,怎么在百度发布信息,如何在百度上添加店铺的位置,wordpress京豆插件力扣日记:【回溯算法篇】131. 分割回文串 日期:2023.1.27 参考:代码随想录、力扣 131. 分割回文串 题目描述 难度:中等 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可…

力扣日记:【回溯算法篇】131. 分割回文串

日期:2023.1.27
参考:代码随想录、力扣

131. 分割回文串

题目描述

难度:中等

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1:

输入:s = “aab”
输出:[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2:

输入:s = “a”
输出:[[“a”]]

提示:

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

题解

class Solution {
public:// 关键:将切割问题类比转换为组合问题(树状图)// 但切割与组合最大的不同在于横向遍历时,组合是从集合中取单个值,但切割是截取一个子串 -> for循环时,[startindex, i]表示当前截取的子串(左闭右闭)vector<vector<string>> results; // 组合的集合vector<string> path;    // 存储回文子串的组合vector<vector<string>> partition(string s) {backtracking(s, 0);return results;}// 如何判断回文串(双指针,一个从头往后,一个从尾往前,对应相等则为回文串)bool isPalindrome(string s, int startindex, int endindex) {// 左闭右闭while (startindex < endindex) {if (s[startindex] != s[endindex]) {return false;}startindex++;endindex--;}return true;}// 回溯三部曲:// 参数:字符串s以及记录当前截取子串的起始位置startindex(从同一个集合中连续截取,因此需要startindex用于递归纵向遍历)void backtracking(string s, int startindex) {// 终止条件,startindex超过s长度if (startindex == s.size()) { // 左闭,相等即超过// startindex能到最后,说明前面的子串都成功截取为回文串并保存了(否则在for循环将i遍历到最后return)results.push_back(path);return;}// for循环找到回文子串[startindex, i]for (int i = startindex; i < s.size(); i++) {// 是回文子串则截取并递归后面的子串,否则往后遍历找回文子串if (isPalindrome(s, startindex, i)) {// 截取子串并存储path.push_back(s.substr(startindex, i - startindex + 1)); // 注意substr的参数是起始位置以及截取长度backtracking(s, i + 1); // 从i之后的子串递归[i+1, s.size()-1]// 回溯,弹出path.pop_back(); // 之后for向右遍历,尝试截取[startindex, i+1]子串}}}};

复杂度

时间复杂度: O(n * 2^n)
空间复杂度: O(n^2)

思路总结

思路完全参考代码随想录

  • 本题实际上算是困难题目
  • 难点有以下:
    • 将切割问题抽象为组合问题,并转换为树状结构
    • 如何模拟那些切割线(如何记录截取子串的始末位置)
    • 切割问题中递归如何终止(终止条件)
    • 在递归循环中如何截取子串(什么时候该递归,什么时候跳过)
    • 如何判断回文
  • 将切割问题抽象为组合问题,并转换为树状结构:
    • 例如对于字符串abcdef:
      组合问题:选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个…。
      切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段…。

    • 但切割与组合最大的不同在于横向遍历时,组合是从集合中取单个值[i],但切割是截取一个子串(即[startindex, i]) 在这里插入图片描述
  • 如何模拟那些切割线(如何记录截取子串的始末位置)
    • for循环时,用[startindex, i]表示当前截取的子串(左闭右闭)
    • 递归时,startindex = i + 1表示对i之后的子串进行递归截取
  • 切割问题中递归如何终止(终止条件)
    • startindex超过s长度(由于左闭右闭,相等即超过)
    • 因为startindex能到最后,说明前面的子串都成功截取为回文串并保存了(否则在for循环将i遍历到最后return)
  • 在递归循环中如何截取子串(什么时候该递归,什么时候跳过)
    • 这里是本题“分割回文串”的特征所在,即处理节点(push_back)时要先确保当前for循环要截取的子串是回文串,才能对后面的子串进行递归;否则应该是循环遍历直到当前子串是回文串或结束for循环
    • 递归与回溯,发生的条件是 当前子串是回文子串(类似于40. 组合总和 II中只有满足“当前取的值不重复”的条件才能递归是一样的。所以也可以写成
      for(...) {// 不是回文串则跳过if (!isPalindrome(...)) {continue;}// 递归与回溯...
      }
      
  • 如何判断回文子串:
    • 双指针法, 一个从头往后,一个从尾往前,对应相等则为回文串
  • TODO:动态规划优化判断回文子串
http://www.ds6.com.cn/news/109780.html

相关文章:

  • 营销网站的建设与管理包括哪些事项重庆森林粤语
  • 网站系统维护一般多久品牌推广软文200字
  • 网站常用参数网络广告的形式
  • 重庆制作网站最牛餐饮营销手段
  • 河南省住房和城乡建设厅二维码网站深圳网站设计制作
  • 网站技术维护如何在百度提交自己的网站
  • 学做PPT报告的网站视频号广告推广
  • 静态网站漏洞婚恋网站排名前10
  • 打开百度竞价页面是网站是什么百度网址大全怎么设为主页
  • 天津外贸网站建设免费html网站模板
  • 在阿里巴巴上怎样做网站抖音黑科技引流推广神器
  • 服务器搭建网站数据库关键词林俊杰的寓意
  • 动态网站开发实训报告网络服务器地址怎么查
  • 北京西城区建设局网站百度指数专业版app
  • 网站建设服务联享科技网站买卖
  • 网站专题页面制作营销软件商城
  • 苏州做网站设计的公司有哪些百度上做广告怎么收费
  • 用flash做的ppt模板下载网站长春seo网站排名
  • macbook air网站开发搜索关键词排名一般按照什么收费
  • 网站开发需要java吗模板建站优点
  • 网站内容营销无锡seo培训
  • 如何用ps做网站首页图片网页设计收费标准
  • 网站手机页面如何做新闻头条最新消息10条
  • 如何评价一个企业的网站建设火星时代教育培训机构官网
  • 关于动漫制作专业宁波seo外包
  • 滨州网站建设公司电话自贡网站seo
  • 制作收款网站搜索引擎优化怎么做
  • 做网站用多大的服务器苏州网站开发公司
  • 网站为什么要备案品牌营销服务
  • 做网站的企业文化怎么写优化大师的三大功能