Leetcode - 周赛435

一、3442. 奇偶频次间的最大差值 I

题目链接
在这里插入图片描述
本题使用数组统计字符串 $s$ 中每个字符的出现次数，然后求出现次数为奇数的最大值和出现次数为偶数的最小值，将它们相减得到答案。

代码如下：

class Solution {public int maxDifference(String s) {int[] cnt = new int[26];for(char c : s.toCharArray()){cnt[c-'a']++;}int mx = 0, mn = Integer.MAX_VALUE;for(int x : cnt){if(x % 2 == 1){mx = Math.max(mx, x);}else if(x > 0){mn = Math.min(mn, x);}}return mx - mn;}
}

二、3443. K 次修改后的最大曼哈顿距离

题目链接
在这里插入图片描述
曼哈顿距离求两个坐标点 $x_i,y_i)$ 和 $x_j,y_j)$ 的横坐标距离绝对值与纵坐标距离绝对值之和，即 $x_i-x_j|+|y_i-y_j|$ ，也就是说，可以将横纵坐标分开来计算：

对于 $x$ 轴来说（东西方向）：比如说，此时向东移动了 $a$ 步，向西移动了 $b$ 步， $a > b$ ，肯定是将向西移动转换成向东移动，才会使得它距离原点距离越远。假设转换了 $d$ 次，此时距离原点的距离就变成了 $a + d - (b - d) = a - b + 2 * d$ ，如果 $a < b$ ，那么就是 $b - a + 2 * d$ ，所以一合并变成了 $ab s (a - b) + 2 * d$ ，这里的 $d = min (a, b, k)$ ， $k = k - d$
对于 $y$ 轴来说（南北方向）也是同理.

代码如下：

class Solution {public int maxDistance(String s, int k) {String str = "NSWE";int[] f = new int[4];int ans = 0;for(char c : s.toCharArray()){f[str.indexOf(c)]++;int left = k - Math.min(Math.min(f[0], f[1]), k);int res = get(f[0], f[1], k) + get(f[2], f[3], left);ans = Math.max(ans, res);}return ans;}int get(int x, int y, int k){int a = Math.max(x, y);int b = Math.min(x, y);int d = Math.min(b, k);return a - b + 2 * d;}
}
//也可以换一个角度思考，设当前位置为(x,y):
//由上一种方法可知，每一次修改都会使得曼哈都距离增加 2,最多不会超过 i + 1
class Solution {public int maxDistance(String s, int k) {int ans = 0;int x = 0, y = 0;for(int i = 0; i < s.length(); i++){char c = s.charAt(i);if(c == 'N') y++;else if(c == 'S') y--;else if(c == 'W') x--;else x++;ans = Math.max(ans, Math.min(Math.abs(x) + Math.abs(y) + 2 * k, i + 1));}return ans;}
}

三、3444. 使数组包含目标值倍数的最少增量

题目链接
在这里插入图片描述
对于 $n u m s$ 数组中的任意一个元素来说，它可以成为 $t a r g e t$ 数组中任意非空子集（从 $t a r g e t$ 中任意选几个元素）的倍数，所以可以定义 $df s (i, j)$ ： $[0, i]$ 满足集合 $j$ 中所有倍数条件的最小操作次数（用集合 $j=\{x,y,z,...\}$ 表示 $t a r g e t$ 数组中还剩下几个元素没有满足倍数条件）

如果从后往前遍历 $n u m s$ 数组，对于 $x = n u m s [i]$ 来说，它有选或不选两种情况：

如果不选，即 $x$ 不会进行递增操作，就不会变成集合 $j$ 中任意元素的倍数，接下来问题变成前 $i$ 个数满足集合 $j$ 中所有元素倍数条件的最小操作次数，即 $df s (i - 1, j)$
如果选，即 $x$ 会进行递增操作，就一定要变成集合 $j$ 中任意非空子集的倍数，枚举集合 $j$ 的所有非空子集 $s u b$ ，接下来问题变成前 $i$ 个数满足集合 $j - s u b$ （即去除已选择的子集 $s u b$ ）中所有元素倍数条件的最小操作次数，即 $df s (i - 1, j - s u b)$
$df s (i, j) = min (df s (i - 1, j), df s (i - 1, j - s u b) + o p er a t i o n s)$ ， $sub\subseteq j$ ， $o p er a t i o n s$ 表示 $n u m s [i]$ 变成 $s u b$ 中所有元素的倍数的操作次数。

要计算 $o p er a t i o n s$ ，需要先知道子集 $s u b$ 中所有元素的最小公倍数，这里可以预处理出集合 $j$ 所有子集的最小公倍数 $l c m$ 。这里介绍一个简单做法，定义 $l c m s [x]$ ：集合 $x$ 中所有元素的最小公倍数。从小到大枚举集合 $j$ 子集的大小，令 $bi t = 1 << i$ ，枚举所有大小小于 $i$ 的子集 $ma s k$ ，可以得到 $f [bi t ∣ ma s k] = l c m (f [ma s k], t a r g e t [i])$

令 $l = l c m s [s u b]$ ， $operations=(l-nums[i]\%l)\%l$

代码如下：

class Solution {long gcd(long x , long y){return y == 0 ? x : gcd(y, x % y); }long lcm(long x, long y){return x * y / gcd(x, y);}public int minimumIncrements(int[] nums, int[] target) {int n = target.length;//预处理 lcmslong[] lcms = new long[1<<n];lcms[0] = 1;for(int i=0; i<n; i++){int bit = 1 << i;for(int j=0; j<bit; j++){lcms[bit|j] = lcm(target[i], lcms[j]);}}int m = nums.length;memo = new long[m][1<<n];for(long[] r : memo) Arrays.fill(r, -1);return (int)dfs(m-1, (1<<n)-1, nums, lcms);}long[][] memo;long dfs(int i, int j, int[] nums, long[] lcms){if(j == 0) return 0;if(i < 0) return Long.MAX_VALUE/2;if(memo[i][j] != -1) return memo[i][j];long res = dfs(i-1, j, nums, lcms);int sub = j;//枚举 j 的子集while(sub > 0){long l = lcms[sub];res = Math.min(res, dfs(i-1, j^sub, nums, lcms) + (l - nums[i] % l) % l);sub = (sub - 1) & j;}return memo[i][j] = res;}
}//递推写法
class Solution {long gcd(long x , long y){return y == 0 ? x : gcd(y, x % y); }long lcm(long x, long y){return x * y / gcd(x, y);}public int minimumIncrements(int[] nums, int[] target) {int n = nums.length;int m = target.length;long[] lcms = new long[1<<m];lcms[0] = 1;for(int i = 0; i < m; i++){int bit = 1 << i;for(int mask = 0; mask < bit; mask++){lcms[bit | mask] = lcm(target[i], lcms[mask]);}}long[][] f = new long[n+1][1<<m];Arrays.fill(f[0], Long.MAX_VALUE/2);for(int i = 0; i < n; i++){f[i][0] = 0;for(int j = 0; j < 1 << m; j++){f[i+1][j] = f[i][j];for(int sub = j; sub != 0; sub = (sub - 1) & j){long l = lcms[sub];f[i+1][j] = Math.min(f[i+1][j], f[i][j^sub] + (l - nums[i] % l) % l);}}}return (int)f[n][(1<<m)-1];}
}

四、3445. 奇偶频次间的最大差值 II

题目链接
在这里插入图片描述
题目中字符串 $s$ 仅由数字 $0, 1, 2, 3, 4$ 构成，所以可以枚举出现奇数次的字符 $x$ 和出现偶数次的字符 $y$ （ $x! = y$ ），求子串中两个字符出现的频次之差，就是求区间中字符 $x$ 、 $y$ 的出现次数，然后相减。这个可以使用前缀和来进行计算：

假设数组 $pre_x[i+1]$ 表示前 $i$ 个元素中字符 $x$ 的出现次数， $pre_y[i+1]$ 表示前 $i$ 个元素中字符 $y$ 的出现次数，求区间 $[l, r]$ 中 $x$ 、 $y$ 出现频次之差为 $pre_x[r+1]-pre_x[l]-(pre_y[r+1]-pre_y[l])$ ，把式子中 $r + 1$ 放到一边， $l$ 放到一边，得到 $pre_x[r+1]-pre_y[r+1]-(pre_x[l]-pre_y[l])$ ，此时发现，本题可以使用滑动窗口中的枚举右，维护左来做：

本题要求子字符串的长度至少为 $k$ ，且子字符串中 $x, y$ 的出现次数大于 $0$ ，即 $\geqslant k$ ， $pre_x[r+1]>pre_y[r+1]$ ， $pre_x[l]>pre_y[l]$
本题求最大差值，在右端点固定的情况下，要想使得 $pre_x[r+1]-pre_y[r+1]-(pre_x[l]-pre_y[l])$ 越大，就是要 $pre_x[l]-pre_y[l]$ 的值越小，所以需要维护 $pre_x[l]-pre_y[l]$ 的最小值。又因为本题要求子字符串中 $x$ 的出现次数必须为奇数， $y$ 的出现次数必须为偶数（ $> 0$ ），这里可以使用数组 $m e m o [p] [q]$ 来记录 $x$ 、 $y$ 的出现次数是为 $p$ 、 $q$ 时， $pre_x[l]-pre_y[l]$ 的最小值（ $p, q$ 只表示奇偶性）
更新答案 $ans = max(ans,pre_x[r+1]-pre_y[r+1]-memo[p][q])$ ，这里的 $p$ 的奇偶性与 $pre_x[r+1]$ 相反， $q$ 的奇偶性与 $pre_y[r+1]$ 相同。

代码如下：

class Solution {public int maxDifference(String s, int k) {final int inf = Integer.MAX_VALUE/2;int n = s.length();int ans = -inf;for(int x = 0; x < 5; x++){for(int y = 0; y < 5; y++){if(x == y) continue;int[] pre_x = new int[n+1];int[] pre_y = new int[n+1];int[][] memo = {{inf, inf}, {inf, inf}};for(int l = 0, r = 0; r < n; r++){int a = s.charAt(r) - '0';pre_x[r+1] = pre_x[r] + (a == x ? 1 : 0);pre_y[r+1] = pre_y[r] + (a == y ? 1 : 0);// r - l + 1 >= k// pre_x[r+1] > pre_x[l]// pre_y[r+1] > pre_y[l]while(r - l + 1 >= k && pre_x[r+1] > pre_x[l] && pre_y[r+1] > pre_y[l]){int p = pre_x[l] & 1;int q = pre_y[l] & 1; memo[p][q] = Math.min(memo[p][q], pre_x[l] - pre_y[l]);l++;}//子字符串长度大于等于 k，才能更新答案if(r + 1 >= k)ans = Math.max(ans, pre_x[r+1] - pre_y[r+1] - memo[pre_x[r+1] & 1 ^ 1][pre_y[r+1] & 1]);}}}return ans;}
}