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\ast d$，如果 $a<b$，那么就是 $b-a+2\ast d$，所以一合并变成了 $abs(a-b)+2\ast 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. 使数组包含目标值倍数的最少增量

题目链接

对于 $nums$ 数组中的任意一个元素来说，它可以成为 $target$ 数组中任意非空子集（从 $target$ 中任意选几个元素）的倍数，所以可以定义 $dfs(i,j)$：$[0,i]$ 满足集合 $j$ 中所有倍数条件的最小操作次数（用集合 j = { x , y , z , . . . } j=\{x,y,z,...\} j={x,y,z,...} 表示 $target$ 数组中还剩下几个元素没有满足倍数条件）

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

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

要计算 $operations$，需要先知道子集 $sub$ 中所有元素的最小公倍数，这里可以预处理出集合 $j$ 所有子集的最小公倍数 $lcm$。这里介绍一个简单做法，定义 $lcms[x]$：集合 $x$ 中所有元素的最小公倍数。从小到大枚举集合 $j$ 子集的大小，令 $bit=1<<i$，枚举所有大小小于 $i$ 的子集 $mask$，可以得到 $f[bit|mask]=lcm(f[mask],target[i])$

令 $l=lcms[sub]$，$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$ 的出现次数，然后相减。这个可以使用前缀和来进行计算：

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

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