欢迎大家加QQ群：623375442，可以方便群里面交流。
100402. Count Substrings That Satisfy K-Constraint I
给你一个 二进制 字符串 s 和一个整数 k。
如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：
- 字符串中 0 的数量最多为 k。
- 字符串中 1 的数量最多为 k。
- 返回一个整数，表示 s 的所有满足 k 约束 的子字符串的数量。
测试样例：
输入：s = "10101", k = 1
输出：12
解释：
s 的所有子字符串中，除了 "1010"、"10101" 和 "0101" 外，其余子字符串都满足 k 约束。
解答：计算符合要求前缀，前缀和。
class Solution {
public int countKConstraintSubstrings(String s, int k) {
int[] count = {0,0};
int len = s.length(), st = 0;
int res = 0;
for (int i = 0; i < s.length(); ++i) {
count[s.charAt(i) - '0'] += 1;
while (count[0] > k && count[1] > k) {
count[s.charAt(st++) - '0'] -= 1;
}
res += (i - st + 1);
}
return res;
}
}100386. Maximum Energy Boost From Two Drinks
来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB，数组长度都等于 n。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。
你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而，如果从一种能量饮料切换到另一种，你需要等待一小时来梳理身体的能量体系（在那个小时里你将不会获得任何强化能量）。
返回在接下来的 n 小时内你能获得的 最大 总强化能量。
注意 你可以选择从饮用任意一种能量饮料开始。
测试样例：
输入：energyDrinkA = [1,3,1], energyDrinkB = [3,1,1]
输出：5
解释：要想获得 5 点强化能量，需要选择只饮用能量饮料 A（或者只饮用 B）。
解答：经典动态规划。
class Solution {
public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {
int len = energyDrinkA.length;
long[][] res = new long[len + 1][2];
for (int i = 0; i < len; ++i) {
res[i + 1][0] = res[i][0] + energyDrinkA[i];
res[i + 1][1] = res[i][1] + energyDrinkB[i];
if (i - 1 >= 1) {
res[i + 1][0] = Math.max(res[i + 1][0], res[i - 1][1] + energyDrinkA[i]);
res[i + 1][1] = Math.max(res[i + 1][1], res[i - 1][0] + energyDrinkB[i]);
}
}
return Math.max(res[len][0], res[len][1]);
}
}100409. Find the Largest Palindrome Divisible by K
给你两个 正整数 n 和 k。
如果整数 x 满足以下全部条件，则该整数是一个 k 回文数：
- x 是一个 回文数。
- x 可以被 k 整除。
以字符串形式返回 最大的 n 位 k 回文数。
注意，该整数 不 含前导零。
测试样例：
输入：n = 3, k = 5
输出："595"
解释：595 是最大的 3 位 k 回文数。
解答：7真的太恶心了，不知道怎么处理7.先抄一个别人的吧。
class Solution {
public String largestPalindrome(int n, int k) {
if (n == 1) {
return largestOneDigit(k);
}
char[] arr = new char[n];
Arrays.fill(arr, '9');
if (k == 2) {
arr[0] = '8';
arr[n - 1] = '8';
} else if (k == 4) {
arr[0] = '8';
arr[1] = '8';
arr[n - 2] = '8';
arr[n - 1] = '8';
} else if (k == 5) {
arr[0] = '5';
arr[n - 1] = '5';
} else if (k == 6) {
if (n == 2) {
return "66";
}
if (n == 3) {
return "888";
}
if (n == 4) {
return "8778";
}
arr[0] = '8';
arr[n - 1] = '8';
if (n % 2 != 0) {
arr[n / 2] = '8';
} else {
arr[n / 2 - 1] = '7';
arr[n / 2] = '7';
}
} else if (k == 7) {
if (n == 2) {
return "77";
}
if (n == 3) {
return "959";
}
if (n % 2 != 0) {
int midIndex = n / 2;
int originalRemainder = 0;
for (int i = 0; i < n; i++) {
originalRemainder = (originalRemainder * 10 + 9) % 7;
}
if (originalRemainder == 0) {
return new String(arr);
}
int midRemainder = 1;
for (int i = n / 2; i > 0; i--) {
midRemainder = midRemainder * 10 % 7;
}
for (int digit = 8; digit >= 0; digit--) {
originalRemainder = (originalRemainder - midRemainder) % 7;
if (originalRemainder < 0) {
originalRemainder += 7;
}
if (originalRemainder == 0) {
arr[midIndex] = (char) ('0' + digit);
break;
}
}
} else {
int midIndex1 = n / 2 - 1, midIndex2 = n / 2;
int originalRemainder = 0;
for (int i = 0; i < n; i++) {
originalRemainder = (originalRemainder * 10 + 9) % 7;
}
if (originalRemainder == 0) {
return new String(arr);
}
int midRemainder = 11;
for (int i = n / 2 - 1; i > 0; i--) {
midRemainder = midRemainder * 10 % 7;
}
for (int digit = 8; digit >= 0; digit--) {
originalRemainder = (originalRemainder - midRemainder) % 7;
if (originalRemainder < 0) {
originalRemainder += 7;
}
if (originalRemainder == 0) {
arr[midIndex1] = (char) ('0' + digit);
arr[midIndex2] = (char) ('0' + digit);
break;
}
}
}
} else if (k == 8) {
if (n <= 2) {
Arrays.fill(arr, '8');
} else {
arr[0] = '8';
arr[1] = '8';
arr[2] = '8';
arr[n - 3] = '8';
arr[n - 2] = '8';
arr[n - 1] = '8';
}
}
return new String(arr);
}
public String largestOneDigit(int k) {
if (k == 1 || k == 3 || k == 9) {
return "9";
}
if (k == 2 || k == 4 || k == 8) {
return "8";
}
return String.valueOf(k);
}
}100404. Count Substrings That Satisfy K-Constraint II
给你一个 二进制 字符串 s 和一个整数 k。
另给你一个二维整数数组 queries ，其中 queries[i] = [li, ri] 。
如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：
- 字符串中 0 的数量最多为 k。
- 字符串中 1 的数量最多为 k。
返回一个整数数组 answer ，其中 answer[i] 表示 s[li..ri] 中满足 k 约束 的 子字符串 的数量。
测试样例：
输入：s = "0001111", k = 2, queries = [[0,6]]
输出：[26]
解释：对于查询 [0, 6]， s[0..6] = "0001111" 的所有子字符串中，除 s[0..5] = "000111" 和 s[0..6] = "0001111" 外，其余子字符串都满足 k 约束。
解答：和第一题一样，利用前缀发现当位置i位结束时，它最大的前缀区域。因为有一个复杂的query，我们利用线段树配合折半搜索来计算。
class Solution {
class SegmentTree {
long[] tree;
int n;
public SegmentTree(int[] nums) {
if (nums.length > 0) {
n = nums.length;
tree = new long[n * 2];
buildTree(nums);
}
}
private void buildTree(int[] nums) {
for (int i = n, j = 0; i < 2 * n; i++, j++)
tree[i] = nums[j];
for (int i = n - 1; i > 0; --i)
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
public long sumRange(int l, int r) {
l += n;
r += n;
long sum = 0;
while (l <= r) {
if ((l % 2) == 1) {
sum += tree[l];
l++;
}
if ((r % 2) == 0) {
sum += tree[r];
r--;
}
l /= 2;
r /= 2;
}
return sum;
}
}
public long[] countKConstraintSubstrings(String s, int k, int[][] queries) {
int[] count = {0,0};
int len = s.length(), st = 0;
int[] mem = new int[len];
for (int i = 0; i < s.length(); ++i) {
// 计算前缀区域
count[s.charAt(i) - '0'] += 1;
while (count[0] > k && count[1] > k) {
count[s.charAt(st++) - '0'] -= 1;
}
mem[i] = st;
}
SegmentTree tree = new SegmentTree(mem);
long[] res = new long[queries.length];
for (int i = 0; i < queries.length; ++i) {
long q0 = queries[i][0], q1 = queries[i][1];
// 利用等差数列，但是有些地方会因为queriers[i][0]较大的原因被截断
int firstBig = binarySearch(mem, queries[i][0]);
if (firstBig <= q1) {
long right = firstBig - 1;
// 截断
if (right >= q0) res[i] = (right - q0 + 1 + 1) * (right - q0 + 1) / 2;
res[i] += (firstBig + q1 + 2) * (q1 - firstBig + 1) / 2 - tree.sumRange(firstBig, (int) q1);
} else {
res[i] = (q1 - q0 + 1 + 1) * (q1 - q0 + 1) / 2;
}
}
return res;
}
private int binarySearch(int[] mem, int st) {
int p0 = 0, p1 = mem.length;
while (p0 < p1) {
int mid = (p0 + p1) / 2;
if (mem[mid] <= st) {
p0 = mid + 1;
} else {
p1 = mid;
}
}
return p0;
}
}