给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，其中每个节点 至多 有一条出边。
图用一个大小为 n 下标从 0 开始的数组 edges 表示，节点 i 到节点 edges[i] 之间有一条有向边。如果节点 i 没有出边，那么 edges[i] == -1 。
请你返回图中的 最长 环，如果没有任何环，请返回 -1 。
一个环指的是起点和终点是 同一个 节点的路径。
示例 1：
输入：edges = [3,3,4,2,3]
输出去：3
解释：图中的最长环是：2 -> 4 -> 3 -> 2 。
这个环的长度为 3 ，所以返回 3 。示例 2：
输入：edges = [2,-1,3,1]
输出：-1
解释：图中没有任何环。说明：
//todo
给你一个整数 n 和一个在范围 [0, n - 1] 以内的整数 p ，它们表示一个长度为 n 且下标从 0 开始的数组 arr ，数组中除了下标为 p 处是 1 以外，其他所有数都是 0 。
同时给你一个整数数组 banned ，它包含数组中的一些位置。banned 中第 i 个位置表示 arr[banned[i]] = 0 ，题目保证 banned[i] != p 。
你可以对 arr 进行 若干次 操作。一次操作中，你选择大小为 k 的一个 子数组 ，并将它 翻转 。在任何一次翻转操作后，你都需要确保 arr 中唯一的 1 不会到达任何 banned 中的位置。换句话说，arr[banned[i]] 始终 保持 0 。
请你返回一个数组 ans ，对于 [0, n - 1] 之间的任意下标 i ，ans[i] 是将 1 放到位置 i 处的 最少 翻转操作次数，如果无法放到位置 i 处，此数为 -1 。
示例 1：
输入：n = 4, p = 0, banned = [1,2], k = 4
输出：[0,-1,-1,1]
解释：k = 4，所以只有一种可行的翻转操作，就是将整个数组翻转。一开始 1 在位置 0 处，所以将它翻转到位置 0 处需要的操作数为 0 。
我们不能将 1 翻转到 banned 中的位置，所以位置 1 和 2 处的答案都是 -1 。
通过一次翻转操作，可以将 1 放到位置 3 处，所以位置 3 的答案是 1 。示例 2：
输入：n = 5, p = 0, banned = [2,4], k = 3
输出：[0,-1,-1,-1,-1]
解释：这个例子中 1 一开始在位置 0 处，所以此下标的答案为 0 。
翻转的子数组长度为 k = 3 ，1 此时在位置 0 处，所以我们可以翻转子数组 [0, 2]，但翻转后的下标 2 在 banned 中，所以不能执行此操作。
由于 1 没法离开位置 0 ，所以其他位置的答案都是 -1 。示例 3：
输入：n = 4, p = 2, banned = [0,1,3], k = 1
输出：[-1,-1,0,-1]
解释：这个例子中，我们只能对长度为 1 的子数组执行翻转操作，所以 1 无法离开初始位置。说明：
// todo
字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。
给你一个字符串 s ，它只包含小写英文字母。请你返回 s 里所有 子字符串的 最大波动 值。
子字符串 是一个字符串的一段连续字符序列。
示例 1：
输入：s = "aababbb"
输出：3
解释：
所有可能的波动值和它们对应的子字符串如以下所示：
- 波动值为 0 的子字符串："a" ，"aa" ，"ab" ，"abab" ，"aababb" ，"ba" ，"b" ，"bb" 和 "bbb" 。
- 波动值为 1 的子字符串："aab" ，"aba" ，"abb" ，"aabab" ，"ababb" ，"aababbb" 和 "bab" 。
- 波动值为 2 的子字符串："aaba" ，"ababbb" ，"abbb" 和 "babb" 。
- 波动值为 3 的子字符串 "babbb" 。
所以，最大可能波动值为 3 。示例 2：
输入：s = "abcde"
输出：0
解释：
s 中没有字母出现超过 1 次，所以 s 中每个子字符串的波动值都是 0 。说明：
//todo
Alice 是 n 个花园的园丁，她想通过种花，最大化她所有花园的总美丽值。
给你一个下标从 0 开始大小为 n 的整数数组 flowers ，其中 flowers[i] 是第 i 个花园里已经种的花的数目。已经种了的花 不能 移走。同时给你 newFlowers ，表示 Alice 额外可以种花的 最大数目 。同时给你的还有整数 target ，full 和 partial 。
如果一个花园有 至少 target 朵花，那么这个花园称为 完善的 ，花园的 总美丽值 为以下分数之 和 ：
请你返回 Alice 种最多 newFlowers 朵花以后，能得到的 最大 总美丽值。
示例 1：
输入：flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1
输出：14
解释：Alice 可以按以下方案种花
- 在第 0 个花园种 2 朵花
- 在第 1 个花园种 3 朵花
- 在第 2 个花园种 1 朵花
- 在第 3 个花园种 1 朵花
花园里花的数目为 [3,6,2,2] 。总共种了 2 + 3 + 1 + 1 = 7 朵花。
只有 1 个花园是完善的。
不完善花园里花的最少数目是 2 。
所以总美丽值为 1 * 12 + 2 * 1 = 12 + 2 = 14 。
没有其他方案可以让花园总美丽值超过 14 。示例 2：
输入：flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6
输出：30
解释：Alice 可以按以下方案种花
- 在第 0 个花园种 3 朵花
- 在第 1 个花园种 0 朵花
- 在第 2 个花园种 0 朵花
- 在第 3 个花园种 2 朵花
花园里花的数目为 [5,4,5,5] 。总共种了 3 + 0 + 0 + 2 = 5 朵花。
有 3 个花园是完善的。
不完善花园里花的最少数目为 4 。
所以总美丽值为 3 * 2 + 4 * 6 = 6 + 24 = 30 。
没有其他方案可以让花园总美丽值超过 30 。
注意，Alice可以让所有花园都变成完善的，但这样她的总美丽值反而更小。说明：
有一个整数数组 flowers，flowers[i] 表示下标为 i 的花园种植的花的数目。花园的美丽值通过以下方式计算：
美丽值 = 所有完善花园的个数 * full美丽值 = 所有花园中花的最小数目 * partialAlice 可以向任意花园中种花，新种的花的数目不超过 newFlowers，求花园的最大美丽值。
// todo
给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
示例 1：
输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。示例 2：
输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。说明：
判断能否将给定字符串分割成三个非空回文子串。
核心逻辑：
i = 0 开始，枚举所有终点 j，如果是 s[i~j] 是回文，k-- 接着以 j + 1 为起点继续递归搜索。i == s.length() || k < 0，如果 k == 0 返回 true。
/**
* @date 2025-03-04 15:58
*/
public class CheckPartitioning1745 {
public boolean checkPartitioning(String s) {
int n = s.length();
boolean[][] isPalindrome = new boolean[n][n];
for (boolean[] row : isPalindrome) {
Arrays.fill(row, true);
}
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && isPalindrome[i + 1][j - 1];
}
}
char[][] mem = new char[n][4];
return dfs(0, 3, isPalindrome, s, mem);
}
public boolean dfs(int i, int k, boolean[][] isPalindrome, String s, char[][] mem) {
int n = s.length();
if (i == n || k < 0) {
return k == 0;
}
if (mem[i][k] != '\u0000') {
return mem[i][k] == 'T';
}
boolean res = false;
for (int j = i; j < n; j++) {
if (isPalindrome[i][j]) {
res = res || dfs(j + 1, k - 1, isPalindrome, s, mem);
}
}
mem[i][k] = res ? 'T' : 'F';
return res;
}
}
给你一个由小写字母组成的字符串 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说明：
将字符串 s 分割成 k 个非空回文子串，允许修改字符中的任意字符，求修改字符的最小次数。
需要将字符串分割成 k 份并且每一份都是回文。我们需要暴力枚举所有可能的分法，并求得每种分法的修改次数，取其最小值。
核心逻辑：
ops[i][j] = s.charAt(i) == s.charAt(j) ? ops[i + 1][j - 1] : ops[i + 1][j - 1] + 1;。由于需要从 i + 1 转移过来，所以外层倒序。初始化数组所有值为 0，外层从倒数第二个开始，内层从 i + 1 开始。i = 0 开始，枚举所有终点 j，无论 s[i~j] 是否是回文，我们直接加上 ops[i][j]，k-- 接着以 j + 1 为起点继续递归搜索。i 未到结尾 k 先减为 0，不符合要求，返回 INF，可以取 0x3f3f3f3fi == s.length()，如果 k == 0 返回 0，否则说明分割的子串没有 k 个，不符合题意返回 INF
/**
* @date 2025-03-03 8:52
*/
public class PalindromePartition1278 {
public int palindromePartition(String s, int k) {
int n = s.length();
int[][] ops = new int[n][n];
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
ops[i][j] = s.charAt(i) == s.charAt(j) ? ops[i + 1][j - 1] : ops[i + 1][j - 1] + 1;
}
}
int[][] mem = new int[n][k + 1];
for (int[] row : mem) {
Arrays.fill(row, -1);
}
return dfs(0, k, s, ops, mem);
}
public int dfs(int i, int k, String s, int[][] ops, int[][] mem) {
int n = s.length();
if (i == n) {
return k > 0 ? 0x3f3f3f3f : 0;
}
if (k == 0) {
return 0x3f3f3f3f;
}
if (mem[i][k] != -1) {
return mem[i][k];
}
int res = Integer.MAX_VALUE;
for (int j = i; j < n; j++) {
res = Math.min(res, ops[i][j] + dfs(j + 1, k - 1, s, ops, mem));
}
mem[i][k] = res;
return res;
}
}
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。示例 2：
输入：s = "a"
输出：0示例 3：
输入：s = "ab"
输出：1说明：
计算将字符串分割成回文子串的最小分割次数。
定义 dp[i] 表示前 i + 1 个字符的最小分割次数，如果 [0, i] 个字符已经是回文，无需切割，切割次数为 0。否则，需要枚举起点 j，如果 [j, i] 是回文，dp[i] = Math.min(dp[j - 1] + 1)。
预处理 [i, j] 是否是回文，isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && isPalindrome[i + 1][j - 1]，由于状态由 i + 1 转换而来，外层要倒序，内层正序或倒序都可以。
/**
* @date 2025-03-02 0:10
*/
public class MinCut132 {
public int minCut(String s) {
int n = s.length();
boolean[][] isPalindrome = new boolean[n][n];
for (boolean[] row : isPalindrome) {
Arrays.fill(row, true);
}
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && isPalindrome[i + 1][j - 1];
}
}
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
if (isPalindrome[0][i]) {
continue;
}
int res = Integer.MAX_VALUE;
for (int j = 1; j <= i; j++) {
if (isPalindrome[j][i]) {
res = Math.min(res, dp[j - 1] + 1);
}
}
dp[i] = res;
}
return dp[n - 1];
}
}
请你设计一个带光标的文本编辑器，它可以实现以下功能：
当删除文本时，只有光标左边的字符会被删除。光标会留在文本内，也就是说任意时候 0 <= cursor.position <= currentText.length 都成立。
请你实现 TextEditor 类：
示例 1：
输入：
["TextEditor", "addText", "deleteText", "addText", "cursorRight", "cursorLeft", "deleteText", "cursorLeft", "cursorRight"]
[[], ["leetcode"], [4], ["practice"], [3], [8], [10], [2], [6]]
输出：
[null, null, 4, null, "etpractice", "leet", 4, "", "practi"]
解释：
TextEditor textEditor = new TextEditor(); // 当前 text 为 "|" 。（'|' 字符表示光标）
textEditor.addText("leetcode"); // 当前文本为 "leetcode|" 。
textEditor.deleteText(4); // 返回 4
// 当前文本为 "leet|" 。
// 删除了 4 个字符。
textEditor.addText("practice"); // 当前文本为 "leetpractice|" 。
textEditor.cursorRight(3); // 返回 "etpractice"
// 当前文本为 "leetpractice|".
// 光标无法移动到文本以外，所以无法移动。
// "etpractice" 是光标左边的 10 个字符。
textEditor.cursorLeft(8); // 返回 "leet"
// 当前文本为 "leet|practice" 。
// "leet" 是光标左边的 min(10, 4) = 4 个字符。
textEditor.deleteText(10); // 返回 4
// 当前文本为 "|practice" 。
// 只有 4 个字符被删除了。
textEditor.cursorLeft(2); // 返回 ""
// 当前文本为 "|practice" 。
// 光标无法移动到文本以外，所以无法移动。
// "" 是光标左边的 min(10, 0) = 0 个字符。
textEditor.cursorRight(6); // 返回 "practi"
// 当前文本为 "practi|ce" 。
// "practi" 是光标左边的 min(10, 6) = 6 个字符。说明：
进阶：你能设计并实现一个每次调用时间复杂度为 O(k) 的解决方案吗？
提示：
设计一个文本编辑器，支持光标左右移动，在光标位置添加字符，删除光标左侧字符的功能。光标移动返回移动后，光标左侧的最多 10 个字符。删除字符返回实际删除的字符个数。
难点在于如何在 buffer 中间插入文本。
暴力解法就是将后面的字符平移，最坏的情况下，操作序列是add,左移,add,左移,……，那么总共移动的字符个数应该是 text.length * q * (q-1) / 2，q 是插入操作次数，插入最多 10^4，文本最大 40，大概 2 * 10^9，这样的复杂度竟然没有超时。
进阶的做法是使用对顶栈，使用两个栈，一个保存光标左侧字符，一个保存光标右侧字符。
prefix 0 ------> top | top <------ 0 suffix。光标左移就将左边的栈顶压到右边，右移反之。
StringBuilder 相关API：
/**
* @date 2025-02-27 8:41
*/
public class TextEditor {
StringBuilder prefix;
StringBuilder suffix;
public TextEditor() {
prefix = new StringBuilder();
suffix = new StringBuilder();
}
public void addText(String text) {
prefix.append(text);
}
public int deleteText(int k) {
int remainder = Math.max(0, prefix.length() - k);
int cnt = prefix.length() - remainder;
prefix.setLength(remainder);
return cnt;
}
public String cursorLeft(int k) {
while (k > 0 && prefix.length() > 0) {
suffix.append(prefix.charAt(prefix.length() - 1));
prefix.setLength(prefix.length() - 1);
k--;
}
return prefix.substring(Math.max(prefix.length() - 10, 0));
}
public String cursorRight(int k) {
while (k > 0 && suffix.length() > 0) {
prefix.append(suffix.charAt(suffix.length() - 1));
suffix.setLength(suffix.length() - 1);
k--;
}
return prefix.substring(Math.max(prefix.length() - 10, 0));
}
}
不使用任何库函数，设计一个 跳表 。
跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。
例如，一个跳表包含 [30, 40, 50, 60, 70, 90] ，然后增加 80、45 到跳表中，以下图的方式操作：
跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。
了解更多 : https://oi-wiki.org/ds/skiplist/
在本题中，你的设计应该要包含这些函数：
注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。
示例 1:
输入
["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
输出
[null, null, null, null, false, null, true, false, true, false]
解释
Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0); // 返回 false
skiplist.add(4);
skiplist.search(1); // 返回 true
skiplist.erase(0); // 返回 false，0 不在跳表中
skiplist.erase(1); // 返回 true
skiplist.search(1); // 返回 false，1 已被擦除说明:
// todo
给你一个下标从 0 开始的 二进制 字符串 floor ，它表示地板上砖块的颜色。
同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条 黑色 的地毯，每一条 黑色 的地毯长度都为 carpetLen 块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余 白色 砖块的数目 最小 。地毯相互之间可以覆盖。
请你返回没被覆盖的白色砖块的 最少 数目。
示例 1：
输入：floor = "10110101", numCarpets = 2, carpetLen = 2
输出：2
解释：
上图展示了剩余 2 块白色砖块的方案。
没有其他方案可以使未被覆盖的白色砖块少于 2 块。示例 2：
输入：floor = "11111", numCarpets = 2, carpetLen = 3
输出：0
解释：
上图展示了所有白色砖块都被覆盖的一种方案。
注意，地毯相互之间可以覆盖。说明：
有 floor.length 块一字排列的砖，floor[i] 的值表示砖的颜色，0 代表黑色，1 代表白色。另有 numCarpets 条长度为 carpetLen 的地毯。求使用地毯覆盖砖块剩余 白色 砖块的最小数目。
假设白色砖块有 k 个，那么可行的方案数有 C(k, numCarpets) 种，即选 k 块白砖为起点覆盖地毯。
//todo