如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。
给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。
示例 1：
输入：n = 20
输出：19
解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。示例 2：
输入：n = 5
输出：5
解释：1 到 5 所有整数都是特殊整数。示例 3：
输入：n = 135
输出：110
解释：从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为：22 ，114 和 131 。说明：
求 1 ~ n 之间的特殊整数，所谓特殊整数指 十进制 下的每一位都不相同的整数。
// todo
在 X轴 上有一些奖品。给你一个整数数组 prizePositions ，它按照 非递减 顺序排列，其中 prizePositions[i] 是第 i 件奖品的位置。数轴上一个位置可能会有多件奖品。再给你一个整数 k 。
你可以选择两个端点为整数的线段。每个线段的长度都必须是 k 。你可以获得位置在任一线段上的所有奖品（包括线段的两个端点）。注意，两个线段可能会有相交。
请你返回在选择两个最优线段的前提下，可以获得的 最多 奖品数目。
示例 1：
输入：prizePositions = [1,1,2,2,3,3,5], k = 2
输出：7
解释：这个例子中，你可以选择线段 [1, 3] 和 [3, 5] ，获得 7 个奖品。示例 2：
输入：prizePositions = [1,2,3,4], k = 0
输出：2
解释：这个例子中，一个选择是选择线段 [3, 3] 和 [4, 4] ，获得 2 个奖品。说明：
x轴的一些整数坐标上放有奖品，相同坐标点上可能有多个奖品。已知所有奖品所在坐标从小到大排序后的数组 prizePositions，问使用两个长度为k的线段最多能覆盖多少个奖品。线段可以相交，但相交区间内的奖品仅计数一次，线段端点处的奖品也计入总数。
最直观的想法是使用滑动窗口，固定区间长度，然后求能够覆盖的最多奖品数。但我们需要的是两个线段所能覆盖的最多奖品，能否记录下第一次求得的区间范围，然后在范围之外（两个线段尽量不相交才能覆盖更多奖品）在用相同的方法求次最多的奖品数。这看上去似乎可行，但具体写完之后会发现一些问题。
如果存在多个最大区间如何处理？可以参考下图，k取3的情况，不同的选择直接影响另一线段的取值。可以用一个列表记录区间范围，然后分别对这些区间范围之外的区间执行同样的算法？时间复杂度为 O(m * l)，m 为最大线段个数，l 为区间长度。
就算上面的复杂度可以接受，两个线段获得最多奖品，一定要其中一个线段覆盖最多的奖品吗？这个是不必要的。参考下图，k取2的情况：
针对这道题，这种贪心策略是不行的，局部最优解并不一定是全局最优解。现在我们没有一个明确的目标，最优的线段该如何取？如果我们同时滑动两个窗口呢？暴力写法是先固定一个，然后滑动另一个。时间复杂度为 O(n^2)，肯定超时。我们发现这里面有重复的子问题，定义 num[i] 表示以 prizePositions[i] 为起点长度为 k 的线段所能覆盖的奖品数。然后再用一个 max[i] 表示起点大于等于 prizePositions[i] 长度为 k 的线段所能覆盖的最大奖品数。这样我们就能以 O(1) 的复杂度取到固定一个窗口之后，另一个窗口的最大值。枚举固定窗口求出最大值即可。
写完之后发现，保存 num[i] 是不必要的，它只用来更新当前的 max[i]。
滑动窗口有两种写法，枚举左边界，循环内部直接到达可能的最右边界。另一种写法是枚举右边界，如果条件不满足，更新左边界直到满足条件。注意确保不要越界。
官网题解提供了二分法的解法，确实遇到有序数组就要想到二分法，但是这里二分找什么呢？大概是二分找所能覆盖的左边界，然后还是动态规划求不超过左边界的另一线段所能覆盖的最大值。官方题解这个解法的java版本好像是其它题目的，给错答案了。
/**
* @date 2024-09-11 8:57
*/
public class MaximizeWin2555 {
public int maximizeWin_v1(int[] prizePositions, int k) {
int n = prizePositions.length;
if (k * 2 + 1 >= prizePositions[n - 1] - prizePositions[0]) {
return n;
}
int res = 1;
int[] max = new int[n + 1];
int l = n - 1;
for (int r = n - 1; r >= 0; r--) {
while (l >= 0 && prizePositions[r] - prizePositions[l] <= k) {
max[l] = Math.max(r - l + 1, max[l + 1]);
res = Math.max(res, r - l + 1 + max[r + 1]);
l--;
}
}
return res;
}
}
给你一个长度为 n 下标从 0 开始的整数数组 nums ，它包含 1 到 n 的所有数字，请你返回上升四元组的数目。
如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：
示例 1：
输入：nums = [1,3,2,4,5]
输出：2
解释：
- 当 i = 0 ，j = 1 ，k = 2 且 l = 3 时，有 nums[i] < nums[k] < nums[j] < nums[l] 。
- 当 i = 0 ，j = 1 ，k = 2 且 l = 4 时，有 nums[i] < nums[k] < nums[j] < nums[l] 。
没有其他的四元组，所以我们返回 2 。示例 2：
输入：nums = [1,2,3,4]
输出：0
解释：只存在一个四元组 i = 0 ，j = 1 ，k = 2 ，l = 3 ，但是 nums[j] < nums[k] ，所以我们返回 0 。说明：
题目看错了，并非是严格递增子序列，而是要求小1 大1 小2 大2，并且 小2 大于 小1， 大2 大于 大1。
// todo
给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。
请你返回 nums 中 好 子序列 的最长长度
示例 1：
输入：nums = [1,2,1,1,3], k = 2
输出：4
解释：
最长好子序列为 [1,2,1,1,3] 。示例 2：
输入：nums = [1,2,3,4,5,1], k = 0
输出：2
解释：
最长好子序列为 [1,2,3,4,5,1] 。说明：
这个和昨天的题类似，只不过数据范围变了。
// todo
给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。
请你返回 nums 中 好 子序列 的最长长度
示例 1：
输入：nums = [1,2,1,1,3], k = 2
输出：4
解释：
最长好子序列为 [1,2,1,1] 。示例 2：
输入：nums = [1,2,3,4,5,1], k = 0
输出：2
解释：
最长好子序列为 [1,1] 。说明：
提示：
dp[i][j] be the length of the longest subsequence till index j with at most i positions such that seq[i] != seq[i + 1].dp[i][x] = max(dp[i][x] + 1, dp[i - 1][y] + 1), where y != x.求整数数组 nums 的子序列，要求子序列中最多存在 k 个下标 i 满足 seq[i] != seq[i + 1]，即至多 k 对相邻元素 不同。
只要选出了子序列，那么相邻元素 不同 的对数就已经确定。
记忆化搜索超时了 // todo
给你一个下标从 0 开始的整数数组 nums ，它表示一个班级中所有学生在一次考试中的成绩。老师想选出一部分同学组成一个 非空 小组，且这个小组的 实力值 最大，如果这个小组里的学生下标为 i0, i1, i2, ... , ik ，那么这个小组的实力值定义为 nums[i0] * nums[i1] * nums[i2] * ... * nums[ik] 。
请你返回老师创建的小组能得到的最大实力值为多少。
示例 1：
输入：nums = [3,-1,-5,2,5,-9]
输出：1350
解释：一种构成最大实力值小组的方案是选择下标为 [0,2,3,4,5] 的学生。实力值为 3 * (-5) * 2 * 5 * (-9) = 1350 ，这是可以得到的最大实力值。示例 2：
输入：nums = [-4,-5,-4]
输出：20
解释：选择下标为 [0, 1] 的学生。得到的实力值为 20 。我们没法得到更大的实力值。说明：
有一个存在负数的数组，求它的非空子序列使得子序列的乘积最大。
首先，要选择所有正数，不能选零（除非全是零），负数必须成对的选（可以使用栈来保存）。可以将数组从小到大排序，从后向前取所有大于零的值，然后再从前向后取，判断栈是否为空，为空入栈，非空出栈，直到零。特别需要注意的是初值的设置需要分情况讨论，如果全是零或者至多一个负数，直接返回零。如果至少有一个正数，则初值设为1。如果全是负数，初值设为第一个元素，之所以不设为1是因为如果只有一个负数，那么就应该取这个值，如果设为1后面再配对的话就不对了，所以需要特殊处理成对匹配的情况。
/**
* @date 2024-09-03 8:57
*/
public class MaxStrength2708 {
public long maxStrength(int[] nums) {
long res = 1L;
Arrays.sort(nums);
int n = nums.length;
int i = n - 1;
for (; i >= 0; i--) {
if (nums[i] > 0) {
res *= nums[i];
} else if (nums[i] < 0) {
// 跳过0，使i指向最后一个负数
break;
}
}
int j = 0;
boolean flag = true;
// 至多一个负数，其余全是0，返回0。
if (i <= 0 && nums[n - 1] == 0) {
return 0L;
} else if (i == n - 1) {
// 如果全是负数
res = nums[0];
flag = false;
j = 1;
}
ArrayDeque<Integer> stack = new ArrayDeque<>();
for (; j <= i; j++) {
if (nums[j] < 0) {
if (stack.isEmpty() && flag) {
stack.push(nums[j]);
} else {
if (!flag) {
res *= nums[j];
} else {
res *= stack.pop() * nums[j];
}
flag = true;
}
}
}
return res;
}
}
一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。（也就是连续出现 true 或者连续出现 false）。
给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：
请你返回在不超过 k 次操作的情况下，最大 连续 'T' 或者 'F' 的数目。
示例 1：
输入：answerKey = "TTFF", k = 2
输出：4
解释：我们可以将两个 'F' 都变为 'T' ，得到 answerKey = "TTTT" 。
总共有四个连续的 'T' 。示例 2：
输入：answerKey = "TFFT", k = 1
输出：3
解释：我们可以将最前面的 'T' 换成 'F' ，得到 answerKey = "FFFT" 。
或者，我们可以将第二个 'T' 换成 'F' ，得到 answerKey = "TFFF" 。
两种情况下，都有三个连续的 'F' 。示例 3：
输入：answerKey = "TTFTTFTT", k = 1
输出：5
解释：我们可以将第一个 'F' 换成 'T' ，得到 answerKey = "TTTTTFTT" 。
或者我们可以将第二个 'F' 换成 'T' ，得到 answerKey = "TTFTTTTT" 。
两种情况下，都有五个连续的 'T' 。说明：
有一个字符串 answerKey 由 T 或 F 组成, 允许我们执行 k 次操作，每次操作可以将字符串中的 T 改为 F 或者 F 改为 T。问 T 或 F 可能的最大连续个数。
这道题没有做出来，想着使用动态规划去做，但是没有找到合适的状态定义。比如 dp[i][j][k] 表示 [0,i] 以 T 或 F 结尾剩余操作次数 k 时的最大连续个数。2 x 10^8 的存储空间肯定不行。
题解说是滑动窗口、或者 前缀和 + 二分查找，也有使用动态规划的。
这道题的难点在于想明白这 k 次操作必须统一，要么全部从 T 改为 F，要么全部从 F 改为 T，才能使连续个数最大。因为如果 T 的连续个数最多，并且存在将 T 改为 F 的操作，那么我们总可以撤回该操作，并将一个 F 改为 T（如果存在的话，如果不存在说明全是T，撤销操作也会加一） 使得连续个数至少加一。
网友题解中的动态规划是这样定义的 dp[i] 表示 [0,i] 中以 answerKey[i] 结尾的连续后缀个数。这里的前提就是遇到不连续的统一从 T 改为 F 或者 从 F 改为 T 使之连续，如果超过了可操作的次数，需要撤回最早的操作，使得当前后缀连续。后缀连续个数可以用当前下标减去最早进行操作的下标计算得到（使用链表保存操作的下标，获取链表head记录的下标后将其删，再将当前下标加入链表末尾）。在计算dp过程中记录其最大值即为最大连续个数。如果对这个动态规划进行存储优化，那就是滑动窗口。
寻找一个窗口，使得窗口内的 T 或者 F 个数小于等于 k，并且使 F 或者 T 的个数最大。滑动窗口的套路一般是枚举右边界，如果条件不满足，更新左边界直到条件满足。
二分的做法本质也是滑动窗口，枚举左边界，二分查找能够到达的最远右边界。
/**
* @date 2024-09-02 16:55
*/
public class MaxConsecutiveAnswers2024 {
/**
* 前缀和 + 二分查找
* 其实本质也是滑动窗口，枚举左边界，二分查找最远的右边界
* O(nlogn) 62ms
*/
public int maxConsecutiveAnswers_v1(String answerKey, int k) {
int n = answerKey.length();
int[] prefix = new int[n + 1];
for (int i = 1; i <= n; i++) {
if (answerKey.charAt(i - 1) == 'T') {
prefix[i] = prefix[i - 1] + 1;
} else {
prefix[i] = prefix[i - 1];
}
}
int res = 0;
for (int i = 1; i <= n; i++) {
int l = i, r = n;
int mid = l + (r - l) / 2;
while (l <= r) {
int num = mid - i + 1;
int cnt = prefix[mid] - prefix[i - 1];
if (num - cnt <= k || cnt <= k) {
l = mid + 1;
} else {
r = mid - 1;
}
mid = l + (r - l) / 2;
}
res = Math.max(res, r - i + 1);
}
return res;
}
/**
* 滑动窗口 O(n)
* 21ms
*/
public int maxConsecutiveAnswers(String answerKey, int k) {
return Math.max(process(answerKey, k, 'T'), process(answerKey, k, 'F'));
}
public int process(String answerKey, int k, char turnTo) {
int n = answerKey.length();
int res = 0;
List<Integer> optsIndex = new LinkedList<>();
int cnt = 0;
for (int i = 0; i < n; i++) {
if (answerKey.charAt(i) != turnTo) {
if (k > 0) {
k--;
optsIndex.add(i);
cnt++;
} else {
cnt = i - optsIndex.remove(0);
optsIndex.add(i);
}
} else {
cnt++;
}
res = Math.max(res, cnt);
}
return res;
}
}
给你一个字符串 s ，你需要将它分割成一个或者更多的 平衡 子字符串。比方说，s == "ababcc" 那么 ("abab", "c", "c") ，("ab", "abc", "c") 和 ("ababcc") 都是合法分割，但是 ("a", "bab", "cc") ，("aba", "bc", "c") 和 ("ab", "abcc") 不是，不平衡的子字符串用粗体表示。
请你返回 s 最少 能分割成多少个平衡子字符串。
注意：一个 平衡 字符串指的是字符串中所有字符出现的次数都相同。
示例 1：
输入：s = "fabccddg"
输出：3
解释：
我们可以将 s 分割成 3 个子字符串：("fab, "ccdd", "g") 或者 ("fabc", "cd", "dg") 。示例 2：
输入：s = "abababaccddb"
输出：2
解释：
我们可以将 s 分割成 2 个子字符串：("abab", "abaccddb") 。说明：
提示：
将字符串划分成子字符串，要求子字符串中每个字符的出现次数相同，求划分后子字符串的最少个数。
想了一会没有头绪，暴力求解该如何做？枚举所有可能的划分？分情况讨论，如果划分为两部分有n-1种分发，如果是三部分有C(n-1,2)种，以此类推。这种枚举显然是不可能的。
考虑贪心算法尽可能多的合并？对应示例2，如果前面尽可能多的合并了 ababab 后面的 ac cd db 就要拆开了，并不是最小的。
如何判断给定区间上字符串是平衡的？还是要遍历计数，然后再来一次循环判断个数是否相同。
先将字符串划分为出现次数都是1的子串，然后再进行合并？如何合并？记录 dp[start][end] ？状态如何转移？
看了题解需要使用动态规划，dp[i] 表示 子串 [0 ~ i) 的最小平衡子串的个数。状态转移方程为 for (int j = i; j >= 0; j--) { if (isBlance(word[j, i])) { dp[i+1] = Math.min(dp[j] + 1, dp[i+1])} }
关键点是使用不同字符的种类乘以最大个数直接判断给定区间是否是平衡的，使用循环会超时。
/**
* @date 2024-08-28 10:29
*/
public class MinimumSubstringsInPartition3144 {
public int minimumSubstringsInPartition_v1(String s) {
int n = s.length();
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
int[] cnt = new int[26];
for (int i = 0; i < n; i++) {
Arrays.fill(cnt, 0);
int k = 0, max = 0;
for (int j = i; j >= 0; j--) {
int index = s.charAt(j) - 'a';
k += ++cnt[index] == 1 ? 1 : 0;
max = Math.max(cnt[index], max);
if (k * max == i - j + 1) {
dp[i + 1] = Math.min(dp[j] + 1, dp[i + 1]);
}
}
}
return dp[n];
}
}
给你一个整数 k 和一个整数 x 。整数 num 的价值是它的二进制表示中在 x，2x，3x …… 等位置处 set bit(指在某数的二进制表示中值为 1 的二进制位) 的数目（从最低有效位开始）。下面的表格包含了如何计算价值的例子。
| x | num | Binary Representation | Price |
|---|---|---|---|
| 1 | 13 | 000001101 | 3 |
| 2 | 13 | 000001101 | 1 |
| 2 | 233 | 011101001 | 3 |
| 3 | 13 | 000001101 | 1 |
| 3 | 362 | 101101010 | 2 |
num 的 累加价值 是从 1 到 num 的数字的 总 价值。如果 num 的累加价值小于或等于 k 则被认为是 廉价 的。
请你返回 最大 的廉价数字。
示例 1：
输入：k = 9, x = 1
输出：6
解释：由下表所示，6 是最大的廉价数字。| x | num | Binary Representation | Price | Accumulated Price |
|---|---|---|---|---|
| 1 | 1 | 001 | 1 | 1 |
| 1 | 2 | 010 | 1 | 2 |
| 1 | 3 | 011 | 2 | 4 |
| 1 | 4 | 100 | 1 | 5 |
| 1 | 5 | 101 | 2 | 7 |
| 1 | 6 | 110 | 2 | 9 |
| 1 | 7 | 111 | 3 | 12 |
示例 2：
输入：k = 7, x = 2
输出：9
解释：由下表所示，9 是最大的廉价数字。| x | num | Binary Representation | Price | Accumulated Price |
|---|---|---|---|---|
| 2 | 1 | 0001 | 0 | 0 |
| 2 | 2 | 0010 | 1 | 1 |
| 2 | 3 | 0011 | 1 | 2 |
| 2 | 4 | 0100 | 0 | 2 |
| 2 | 5 | 0101 | 0 | 2 |
| 2 | 6 | 0110 | 1 | 3 |
| 2 | 7 | 0111 | 1 | 4 |
| 2 | 8 | 1000 | 1 | 5 |
| 2 | 9 | 1001 | 1 | 6 |
| 2 | 10 | 1010 | 2 | 8 |
说明：
1 <= k <= 10^151 <= x <= 8提示：
给定步长x，数字的价值定义为从最低有效位开始，以步长x遍历数字的二进制表示，并记录bit为1的个数。数字n的累加价值定义为 1 ~ n 的价值之和。给定数字k，求累加价值不超过k的最大数字。
先尝试模拟暴力求解。注意到返回值是 long 类型，说明n的规模超过了10^9，即便是 O(n) 的解法也会超时，并且每个数字都要循环bit位计数，肯定超时。我们需要要找一种 O(logn) 的解法。
提示说使用二分查找，问题的关键是如何直接计算出给定数字的累加价值。
// todo
可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：
如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况 数量 。答案可能很大，所以返回对 10^9 + 7 取余 的结果。
示例 1：
输入：n = 2
输出：8
解释：
有 8 种长度为 2 的记录将被视为可奖励：
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
只有"AA"不会被视为可奖励，因为缺勤次数为 2 次（需要少于 2 次）。示例 2：
输入：n = 1
输出：3示例 3：
输入：n = 10101
输出：183236316说明：
使用 A L P 三种字符组成长度为 n 的字符串，要求字符串中最多包含一个 'A'，并且不能连续出现三个及以上的 'L'，问满足条件的字符串有多少个。
很明显需要使用动态规划求解。定义状态 dp[i][hadAbsent][ithState] 表示长度为i，以ithState（0：L; 1:P; 2:A）结尾，hadAbsent（0 ~ i-1，包含1/不包含0）'A'的字符串的个数。
状态转移方程为
dp[i][0][0] = dp[i-2][0][0] + 2*dp[i-2][0][1] LPL PPL PLLdp[i][0][1] = dp[i-1][0][0] + dp[i-1][0][1] LP PPdp[i][0][2] = dp[i-1][0][0] + dp[i-1][0][1] LA PAdp[i][1][0] = dp[i-2][1][0] + 2*dp[i-2][1][1] + 2*dp[i-2][0][2] + dp[i-1][0][2] (A)LPL (A)PPL (A)PLL ALL APL ALdp[i][1][1] = dp[i-1][1][0] + dp[i-1][1][1] + dp[i-1][0][2] (A)LP (A)PP AP初始条件需要提前计算：
dp[0][0][0] = 1; Ldp[0][0][1] = 1; Pdp[0][0][2] = 1; Adp[1][0][0] = 2; LL PLdp[1][0][1] = 2; LP PPdp[1][0][2] = 2; LA PAdp[1][1][0] = 1; ALdp[1][1][1] = 1; AP模运算（取余）满足以下规律：
(a + b + c) % mod = ((a % mod) + (b % mod) + (c % mod)) % mod(a * b * c) % mod = ((a % mod) * (b % mod) * (c % mod)) % mod/**
* @date 2024-08-19 9:53
*/
public class CheckRecord552 {
private static final int MOD = 1000000007;
public int checkRecord(int n) {
if (n == 1) {
return 3;
}
long[][][] dp = new long[n][2][3];
dp[0][0][0] = 1;
dp[0][0][1] = 1;
dp[0][0][2] = 1;
dp[1][0][0] = 2;
dp[1][0][1] = 2;
dp[1][0][2] = 2;
dp[1][1][0] = 1;
dp[1][1][1] = 1;
for (int i = 2; i < n; i++) {
int pre = i - 1;
int prepre = i - 2;
dp[i][0][0] = (dp[prepre][0][0] + 2 * dp[prepre][0][1]) % MOD;
dp[i][0][1] = (dp[pre][0][0] + dp[pre][0][1]) % MOD;
dp[i][0][2] = (dp[pre][0][0] + dp[pre][0][1]) % MOD;
dp[i][1][0] = (dp[prepre][1][0] + 2 * dp[prepre][1][1] + 2 * dp[prepre][0][2] + dp[pre][0][2]) % MOD;
dp[i][1][1] = (dp[pre][1][0] + dp[pre][1][1] + dp[pre][0][2]) % MOD;
}
return (int) ((dp[n - 1][0][0] + dp[n - 1][0][1] + dp[n - 1][0][2] + dp[n - 1][1][0] + dp[n - 1][1][1]) % MOD);
}
}
