LeetCode题解1147. 段式回文

段式回文 其实与 一般回文 类似,只不过是最小的单位是 一段字符 而不是 单个字母。

举个例子,对于一般回文 "abcba" 是回文,而 "volvo" 不是,但如果我们把 "volvo" 分为 "vo"、"l"、"vo" 三段,则可以认为 “(vo)(l)(vo)” 是段式回文(分为 3 段)。

 

给你一个字符串 text,在确保它满足段式回文的前提下,请你返回 段 的 最大数量 k。

如果段的最大数量为 k,那么存在满足以下条件的 a_1, a_2, ..., a_k:

每个 a_i 都是一个非空字符串;

将这些字符串首位相连的结果 a_1 + a_2 + ... + a_k 和原始字符串 text 相同;

对于所有1 <= i <= k,都有 a_i = a_{k+1 - i}。

 

示例 1:

输入:text = "ghiabcdefhelloadamhelloabcdefghi"

输出:7

解释:我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。

示例 2:

输入:text = "merchant"

输出:1

解释:我们可以把字符串拆分成 "(merchant)"。

示例 3:

输入:text = "antaprezatepzapreanta"

输出:11

解释:我们可以把字符串拆分成 "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)"。

示例 4:

输入:text = "aaa"

输出:3

解释:我们可以把字符串拆分成 "(a)(a)(a)"。

 

提示:

text 仅由小写英文字符组成。

1 <= text.length <= 1000

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/longest-chunked-palindrome-decomposition

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解:```javascript
/**
* 贪心解法
* @param {string} text
* @return {number}
*/
var longestDecomposition = function(text) {
if (text === '') {
return 0
}
for(let i = 1; i <= text.length / 2; i++) {
if (text.substring(0, i) === text.substring(text.length - i)) {
return 2 + longestDecomposition(text.substring(i, text.length - i))
}
}
return 1
};
```

LeetCode题解深度优先遍历和回溯的关系?

深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。

LeetCode题解10个小球,随机分到12个盒子里,求恰好10个盒子都为空的概率。

10个小球,随机分到12个盒子里,求恰好10个盒子都为空的概率。要求用程序模拟十万次,暴力求出该概率来自:字节跳动 算法工程师一面的第一题 (3月30日,60分钟,牛客网视频面)https://www.nowcoder.com/discuss/395924

LeetCode题解烧绳子

烧一根不均匀的绳要用一个小时,如果要准确判断一个小时十五分钟,至少需要几根绳子?注意:- 每一根绳子虽然都可以烧一个小时,但均匀程度都不一样题解:三根1. 第一根点燃一头的同时,第二根两头同时点燃。2. 点燃两头的绳子燃尽时,同时点燃第一根绳子的另一头 并开始计时3. 等第一根绳子燃尽 再点燃第三根绳子的一头4. 燃尽 一小时十五分钟

LeetCode题解堆排序和快速排序

堆排序和快速排序都是时间复杂度$O(nlogn)$ 的算法,其中 n 为数据规模。 那么两者谁更快呢? 为什么?题解:快排最坏情况下是O(n^2),平均和最好是O(nlogn) ,堆排序始终为O(nlogn),还是堆排序快吧

LeetCode题解足球排球和篮球

一个班级60%喜欢足球,70%喜欢篮球,80%喜欢排球,问:三种球都喜欢占比最大可能有多少,最小可能有多少?即求三种球都喜欢的比例范围题解:(1)首先确定最多的一种情况,就是 60% 喜欢足球的人同时也喜欢篮球和排球,此时为三种球都喜欢的人的最大比例。 (2)然后确定最小的一种情况,根据题目可以知道有 40%的人不喜欢足球,30%的人不喜欢篮球,20%的人不…