100104. Minimum Number of Changes to Make Binary String Beautiful
给你一个长度为偶数下标从 0 开始的二进制字符串 s 。
如果可以将一个字符串分割成一个或者更多满足以下条件的子字符串，那么我们称这个字符串是 美丽的 ：
- 每个子字符串的长度都是 偶数 。
- 每个子字符串都 只 包含 1 或 只 包含 0 。
你可以将 s 中任一字符改成 0 或者 1 。
请你返回让字符串 s 美丽的 最少 字符修改次数。
测试样例：
输入：s = "1001"
输出：2
解释：
我们将 s[1] 改为 1 ，且将 s[3] 改为 0 ，得到字符串 "1100" 。字符串 "1100" 是美丽的，因为我们可以将它分割成 "11|00" 。将字符串变美丽最少需要 2 次修改。
解答：有一点脑筋急转弯，因为分组要求字符串长度是偶数，且每个字符串只包含1或者0。那当然是字符串长度越短（都是2），改的越少。
class Solution {
public int minChanges(String s) {
int res = 0;
for (int i = 1; i < s.length(); i = i + 2) {
if (s.charAt(i) != s.charAt(i - 1)) {
++res;
}
}
return res;
}
}100042. Length of the Longest Subsequence That Sums to Target
给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。
返回和为 target 的 nums 子序列中，子序列 长度的最大值 。如果不存在和为 target 的子序列，返回 -1 。
子序列 指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组。
请你返回一个整数，表示得到一个合法分组方案的 最少 组数。
测试样例：
输入：nums = [1,2,3,4,5], target = 9
输出：3
解释：
总共有 3 个子序列的和为 9 ：[4,5] ，[1,3,5] 和 [2,3,4] 。最长的子序列是 [1,3,5] 和 [2,3,4] 。所以答案为 3 。
解答：比较标准的动态规划。
class Solution {
public int lengthOfLongestSubsequence(List<Integer> nums, int target) {
Integer[] mem = new Integer[target + 1];
mem[0] = 0;
for (int n : nums) {
for (int i = target; i - n >= 0; --i) {
if (mem[i - n] != null) {
if (mem[i] == null) {
mem[i] = mem[i - n] + 1;
} else {
mem[i] = Math.max(mem[i], mem[i - n] + 1);
}
}
}
}
return mem[target] == null ? -1 : mem[target];
}
}100074. Subarrays Distinct Element Sum of Squares II
给你一个下标从 0 开始的整数数组 nums 。
定义 nums 一个子数组的 不同计数 值如下：
- 令 nums[i..j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组（满足 0 <= i <= j < nums.length ），那么我们称子数组 nums[i..j] 中不同值的数目为 nums[i..j] 的不同计数。
请你返回 nums 中所有子数组的 不同计数 的 平方 和。
由于答案可能会很大，请你将它对 10^9 + 7 取余 后返回。
子数组指的是一个数组里面一段连续 非空 的元素序列。
测试样例
输入：nums = [1,2,1]
输出：15
解答：这道题目，竞赛的时候我没想到什么好的办法。平方和有公式(x + 1) (x + 1) = x x + 2 x + 1。所以我们遍历数组，记录当前数字影响的平方和范围。因为2 x需要累和，没想到啥好的办法，就用了lazy segment tree。
class Solution {
class LazySegmentTree {
int MAX; // Max tree size
int tree[]; // To store segment tree
int lazy[]; // To store pending updates
private void updateRangeUtil(int si, int ss, int se, int us,
int ue, int diff) {
if (lazy[si] != 0) {
tree[si] += (se - ss + 1) * lazy[si];
if (ss != se) {
lazy[si * 2 + 1] += lazy[si];
lazy[si * 2 + 2] += lazy[si];
}
lazy[si] = 0;
}
if (ss > se || ss > ue || se < us)
return;
if (ss >= us && se <= ue) {
tree[si] += (se - ss + 1) * diff;
if (ss != se)
{
lazy[si * 2 + 1] += diff;
lazy[si * 2 + 2] += diff;
}
return;
}
int mid = (ss + se) / 2;
updateRangeUtil(si * 2 + 1, ss, mid, us, ue, diff);
updateRangeUtil(si * 2 + 2, mid + 1, se, us, ue, diff);
tree[si] = tree[si * 2 + 1] + tree[si * 2 + 2];
}
public void updateRange(int n, int us, int ue, int diff) {
updateRangeUtil(0, 0, n - 1, us, ue, diff);
}
private int getSumUtil(int ss, int se, int qs, int qe, int si) {
if (lazy[si] != 0) {
tree[si] += (se - ss + 1) * lazy[si];
if (ss != se) {
lazy[si * 2 + 1] += lazy[si];
lazy[si * 2 + 2] += lazy[si];
}
lazy[si] = 0;
}
// Out of range
if (ss > se || ss > qe || se < qs)
return 0;
if (ss >= qs && se <= qe)
return tree[si];
int mid = (ss + se) / 2;
return getSumUtil(ss, mid, qs, qe, 2 * si + 1) +
getSumUtil(mid + 1, se, qs, qe, 2 * si + 2);
}
public int getSum(int n, int qs, int qe) {
if (qs < 0 || qe > n - 1 || qs > qe) {
System.out.println("Invalid Input");
return -1;
}
return getSumUtil(0, n - 1, qs, qe, 0);
}
private void constructSTUtil(int arr[], int ss, int se, int si) {
if (ss > se)
return;
if (ss == se)
{
tree[si] = arr[ss];
return;
}
int mid = (ss + se) / 2;
constructSTUtil(arr, ss, mid, si * 2 + 1);
constructSTUtil(arr, mid + 1, se, si * 2 + 2);
tree[si] = tree[si * 2 + 1] + tree[si * 2 + 2];
}
public void constructST(int[] arr) {
MAX = findMax(0, arr.length) + 1;
tree = new int[MAX];
lazy = new int[MAX];
constructSTUtil(arr, 0, arr.length - 1, 0);
}
private int findMax(int si, int remain) {
if (remain == 1) {
return si;
} else {
return Math.max(findMax(si * 2 + 1, remain - remain / 2), findMax(si * 2 + 2, remain / 2));
}
}
}
private static final int mod = 1_000_000_007;
public int sumCounts(int[] nums) {
HashMap<Integer, Integer> lastObserve = new HashMap<>();
int len = nums.length;
long[] squareResult = new long[len + 1], addResult = new long[len + 1];
long res = 0;
LazySegmentTree tree = new LazySegmentTree();
tree.constructST(new int[len]);
for (int i = 0; i < len; ++i) {
if (!lastObserve.containsKey(nums[i])) {
long prevSquare = squareResult[i], prevAdd = addResult[i];
squareResult[i + 1] = 1 + prevSquare + 2 * prevAdd + i;
addResult[i + 1] = prevAdd + i + 1;
tree.updateRange(len, 0, i, 1);
} else {
long prevSquare = squareResult[i], prevAdd = addResult[i];
int prevPos = lastObserve.get(nums[i]) + 1;
long prevPosAddTune = tree.getSum(len, 0, prevPos - 1);
long remainAdd = prevAdd - prevPosAddTune;
squareResult[i + 1] = 1 + prevSquare + 2 * remainAdd + i - prevPos;
addResult[i + 1] = (i + 1) - prevPos + addResult[i];
tree.updateRange(len, prevPos, i, 1);
}
lastObserve.put(nums[i], i);
res += squareResult[i + 1];
}
return (int) (res % mod);
}
}