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

哪个网站的域名到期直接注册表电商软文范例300字

哪个网站的域名到期直接注册表,电商软文范例300字,做网站三年3万块钱,广安网站设计公司131.分割回文串 给你一个字符串 s,请你将 s 分割成一些 子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。 示例 1: 输入:s "aab" 输出:[["a","a","b"],["a…

131.分割回文串

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

示例 1:

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

示例 2:

输入:s = "a"
输出:[["a"]]

提示:

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

在求具体的方案数时一般用深搜来解决,尤其是 n 最多只有 16 时,其实已经提醒了用 dfs 来写

通过枚举起点和终点来不断回溯搜索

代码

c++

class Solution {
public:vector<vector<string>> partition(string s) {int n = s.size();s = '|' + s;vector<string> path;vector<vector<string>> ans;auto check = [&](string s) -> bool{string s1 = s, s2 = s;reverse(s2.begin(), s2.end());return s1 == s2;};auto dfs = [&](auto &&self, int u) -> void{if(u > n){ans.push_back(path);return;}for(int i = u;i <= n;i ++){string ss = s.substr(u, i - u + 1);if(check(ss)){path.push_back(ss);self(self, i + 1);path.pop_back();}}};dfs(dfs, 1);return ans;}
};

py

class Solution:def partition(self, s: str) -> List[List[str]]:n = len(s)ans = []path = []def check(s) -> bool:return s == s[::-1]def dfs(x) -> None:if x == n:ans.append(path.copy())returnfor i in range(x, n):if check(s[x : i + 1]):path.append(s[x : i + 1])dfs(i + 1)path.pop()dfs(0)return ans

132.分割回文串 II

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文串。

返回符合要求的 最少分割次数 。

示例 1:

输入:s = "aab"
输出:1
解释:只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2:

输入:s = "a"
输出:0

示例 3:

输入:s = "ab"
输出:1

提示:

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

首先预处理一个 bool 数组出来使得能够快速判断字串 i-j 是否回文。定义 f 数组是前 i 个字符最少要分割几次才能全部回文,如果 g[1][i] 那么直接 f[i] = 0 就行了,否则可以枚举分割点,具体就是枚举 j ∈ [1, i) 作为分割点,如果 g[j + 1][i] == true 则 f[i] = min(f[i], f[j] + 1)

超时代码

class Solution {
public:int minCut(string s) {int n = s.size();s = '|' + s;vector<vector<bool>> g(n + 1, vector<bool>(n + 1, true));vector<int> f(n + 1, INT_MAX);for(int i = 1;i <= n;i ++){for(int j = i;j <= n;j ++){if(i == j) continue;string s1 = s.substr(i, j - i + 1), s2 = s1;reverse(s2.begin(), s2.end());if(s1 != s2) g[i][j] = false;}}for(int i = 1;i <= n;i ++){if(g[1][i]) f[i] = 0;else{for(int j = 1;j < i;j ++) if(g[j + 1][i]){f[i] = min(f[i], f[j] + 1);}}}return f[n];}
};

在预处理部分的 reverse 和 substr 部分会导致超时,那么这时候只需要换成 py 的代码,就可以水过这个数据

代码

from math import *class Solution:def minCut(self, s: str) -> int:n = len(s)s = '|' + sg = [[True] * (n + 1) for _ in range(n + 1)]f = [inf] * (n + 1) for i in range(1, n + 1):for j in range(i, n + 1):if i == j:continueif s[i:j+1] != s[i:j+1][::-1]:g[i][j] = False# print(f"{i}-{j}:{g[i][j]}")for i in range(1, n + 1):if g[1][i]:f[i] = 0else:for j in range(1, i):if g[j+1][i]:f[i] = min(f[i], f[j] + 1)return f[n]

1278.分割回文串 III 

给你一个由小写字母组成的字符串 s,和一个整数 k

请你按下面的要求分割字符串:

  • 首先,你可以将 s 中的部分字符修改为其他的小写英文字母。
  • 接着,你需要把 s 分割成 k 个非空且不相交的子串,并且每个子串都是回文串。

请返回以这种方式分割字符串所需修改的最少字符数。

示例 1:

输入:s = "abc", k = 2
输出:1
解释:你可以把字符串分割成 "ab" 和 "c",并修改 "ab" 中的 1 个字符,将它变成回文串。

示例 2:

输入:s = "aabbc", k = 3
输出:0
解释:你可以把字符串分割成 "aa"、"bb" 和 "c",它们都是回文串。

示例 3:

输入:s = "leetcode", k = 8
输出:0

提示:

  • 1 <= k <= s.length <= 100
  • s 中只含有小写英文字母。

递推,这个问题需要考虑一个二维 f 数组 :使前 i 项 分割成 k 个回文字符串需要修改的最小次数

用一个函数来调用:一个字符串需要修改多少字符变成回文串。初始状态 f[0][0] 就是 0 ,枚举递推即可

代码

c++

class Solution {
public:int palindromePartition(string s, int k) {int n = s.size();if(n == k) return 0;vector<vector<int>> f(n + 1, vector<int>(k + 1, 0x3f3f3f3f));f[0][0] = 0;auto get = [&](string s, int ist, int ed) -> int{int l = ist, r = ed, res = 0;for(;l < r;l ++, r --) if(s[l] != s[r]){res ++;}return res;};for(int i = 1;i <= n;i ++){for(int j = 1;j <= min(i, k);j ++){if(j == 1) f[i][j] = get(s, 0, i - 1);else{for(int z = j - 1;z < i;z ++){f[i][j] = min(f[i][j], f[z][j - 1] + get(s, z, i - 1));}}}}return f[n][k];}
};

py

class Solution:def palindromePartition(self, s: str, k: int) -> int:n = len(s)def get(s, l, r):res = 0while l < r:if s[l] != s[r]:res += 1l, r = l + 1, r - 1return resf = [[inf] * (k + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(1, min(i, k) + 1):if j == 1:f[i][j] = get(s, 0, i - 1)else:for z in range(j - 1, i):f[i][j] = min(f[i][j], f[z][j - 1] + get(s, z, i - 1))return f[n][k]

1745.分割回文串 IV

给你一个字符串 s ,如果可以将它分割成三个 非空 回文子字符串,那么返回 true ,否则返回 false 。

当一个字符串正着读和反着读是一模一样的,就称其为 回文字符串 。

示例 1:

输入:s = "abcbdd"
输出:true
解释:"abcbdd" = "a" + "bcb" + "dd",三个子字符串都是回文的。

示例 2:

输入:s = "bcbddxy"
输出:false
解释:s 没办法被分割成 3 个回文子字符串

提示:

  • 3 <= s.length <= 2000
  • s​​​​​​ 只包含小写英文字母。

这个问题跟 || 本质是一样的,只是有一个有一个类似三数之和的枚举技巧,先枚举第一段,然后枚举第二段,剩下的就是第三段,预处理之后 O(1)查询即可

代码

py

from math import *class Solution:def checkPartitioning(self, s: str) -> bool:n = len(s)s = '|' + sg = [[True] * (n + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(i + 1, n + 1):if s[i:j+1] != s[i:j+1][::-1]:g[i][j] = Falsefor i in range(1, n + 1):if g[1][i] == False:continuefor j in range(i + 1, n):if g[i + 1][j] == True and g[j + 1][n] == True:return Truereturn False

加油

http://www.zhongyajixie.com/news/16870.html

相关文章:

  • 深圳做外贸网站如何做一个网站的seo
  • wordpress改网站logo网上销售方法
  • 网站的内容更新重庆seo网络营销
  • 深圳市工商注册信息查询网站提高网站排名的软件
  • 故宫上海网络营销公司深圳seo优化外包公司
  • 建网站软件有哪些网络推广公司电话
  • 《小城镇建设》》杂志社网站网站加速
  • 旅游做哪个网站好昆明seo关键字推广
  • 做ppt用什么网站好长沙网站se0推广优化公司
  • 亚洲av成人影院手机版在线看志鸿优化网下载
  • 网站建设督查工作主持词西安seo服务外包
  • 精品课网站开发论文微信搜一搜seo
  • 宜春网站建设公司google推广公司哪家好
  • 中英文网站怎么做网络广告投放平台
  • 麒贺丝网做的网站优化武汉seo建站
  • web前端和网站开发百度应用平台
  • 素材图库嘉兴网站建设方案优化
  • 大门户wordpress主题破解seo日常工作
  • 北京哪里有做网站的产品软文范例500字
  • 网站做收录是什么意思免费找客源软件
  • 中国建设信息化期刊官网seo包年优化平台
  • 阿里巴巴网站建设方案书微信营销软件有哪些
  • 找人做任务网站有哪些杭州网站设计制作
  • 大庆+网站建设市场营销教材电子版
  • 松桃县住房和城乡建设局网站做网站推广需要多少钱
  • 合肥网站建设是什么意思湖南网站seo
  • wordpress媒体库插入图片不显示惠州seo外包费用
  • 四川省建筑人员证书查询无忧seo
  • 自己做网站难不难广州网站优化排名
  • 苹果浏览器怎么信任网站设置百度推广费用一天多少钱