53场双周赛成绩~

T1 5754. 长度为三且各字符不同的子字符串

题目

如果一个字符串不含有任何重复字符,我们称这个字符串为字符串。
给你一个字符串 s ,请你返回 s 中长度为 3 的好子字符串的数量。
注意,如果相同的好子字符串出现多次,每一次都应该被记入答案之中。
子字符串是一个字符串中连续的字符序列。

示例 1:
输入:s = “xyzzaz”
输出:1
解释:总共有 4 个长度为 3 的子字符串:“xyz”,“yzz”,“zza” 和 “zaz” 。
唯一的长度为 3 的好子字符串是 “xyz” 。

示例 2:
输入:s = “aababcabc”
输出:4
解释:总共有 7 个长度为 3 的子字符串:“aab”,“aba”,“bab”,“abc”,“bca”,“cab” 和 “abc” 。
好子字符串包括 “abc”,“bca”,“cab” 和 “abc” 。

提示:

  • 1 <= s.length <= 100
  • s​​​​​​ 只包含小写英文字母。

题解

长度为3,互不相同可以直接拿不等于进行两两判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int countGoodSubstrings(String s) {
if (s.length() < 3) return 0;
char[] str;
int n = 0;
for (int i = 0; (i + 3) <= s.length(); i++) {
str = s.substring(i, i + 3).toCharArray();
if (str[0] != str[1] && str[0] != str[2] && str[1] != str[2]) {
n++;
}
}
return n;
}
}

大聪明做法:如果子字符串的长度继续增加,可以考虑滑动窗口,当然每次遍历cnt数组还是有开销的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int countGoodSubstrings(String s) {
int len = s.length();
if(len < 3) return 0;
int res = 0;
int[] cnt = new int[26];
for(int i = 0; i < 3; i++){
cnt[(int)(s.charAt(i) - 'a')]++;
}
for(int i = 0; i < len - 3; i++){
if(isValid(cnt)) res++;
cnt[(int)(s.charAt(i) - 'a')]--;
cnt[(int)(s.charAt(i + 3) - 'a')]++;
}
if(isValid(cnt)) res++;
return res;
}
public boolean isValid(int[] cnt){
for(int x: cnt){
if(x > 1) return false;
}
return true;
}
}

T2 5755. 数组中最大数对和的最小值

题目

一个数对 (a,b) 的数对和等于 a + b 。最大数对和是一个数对数组中最大的 数对和 。
比方说,如果我们有数对 (1,5) ,(2,3) 和 (4,4),最大数对和 为 max(1+5,2+3,4+4)=max(6,5,8)=8max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8 。
给你一个长度为 偶数 n 的数组 nums ,请你将 nums 中的元素分成 n / 2 个数对,使得:
nums 中每个元素 恰好一个 数对中,且

  • 最大数对和 的值 最小 。
  • 请你在最优数对划分的方案下,返回最小的 最大数对和 。

示例 1:
输入:nums = [3,5,2,3][3,5,2,3]
输出:7
解释:数组中的元素可以分为数对 (3,3) 和 (5,2) 。
最大数对和为 max(3+3,5+2)=max(6,7)=7max(3+3, 5+2) = max(6, 7) = 7

示例 2:
输入:nums = [3,5,4,2,4,6][3,5,4,2,4,6]
输出:8
解释:数组中的元素可以分为数对 (3,5),(4,4) 和 (6,2) 。
最大数对和为 max(3+5,4+4,6+2)=max(8,8,8)=8max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8

提示:
n == nums.length
2 <= n <= 10^5
n 是 偶数
1 <= nums[i] <= 10^5

题解

排序 + 贪心
猜测:将数组排序,前后组合即可

关键在于证明:
令当前数组有序,即x1...xnx_1 \leq ... \leq x_n
考虑上述命题的充分条件:假设给定拆分方法中的数对和xk+xn+1kx_k + x_{n+1-k}k=kk = k'时最大,那么对于任意的拆分方法,都存在一组 u,vu, v,使得 xu+xvxk+xx+1kx_u + x_v \geq x_{k'} + x_{x+1-k'}
反证法:
假设u<vu < v,那么使得xvxn+1kx_v \geq x_{n+1-k'}vv值为闭区间
内部[n+1k,n][n + 1 - k', n]的所有整数,有kk'种,如果想使xu+xv<xk+xx+1kx_u + x_v < x_{k'} + x_{x+1-k'}恒成立,必有xu<xkx_u < x_{k'},但是uu的取值只有[1,k1][1, k' - 1],共k1k' - 1种,两者数量不匹配,无法对于全部数对满足,故不成立,反证法得证

代码很简单如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int minPairSum(int[] nums) {
int max = 0;
int len = nums.length;
Arrays.sort(nums);
int lo = 0, hi = len - 1;
while(lo < hi){
max = Math.max(nums[lo] + nums[hi], max);
lo++;
hi--;
}
return max;
}
}

类似题目: AcCoder Regular Contest 121

T3 5757. 矩阵中最大的三个菱形和

题目

给你一个 m x n 的整数矩阵 grid 。
菱形和 指的是 grid 中一个正菱形 边界 上的元素之和。本题中的菱形必须为正方形旋转45度,且四个角都在一个格子当中。下图是四个可行的菱形,每个菱形和应该包含的格子都用了相应颜色标注在图中。

注意,菱形可以是一个面积为 0 的区域,如上图中右下角的紫色菱形所示。

请你按照 降序 返回 grid 中三个最大的 互不相同的菱形和 。如果不同的和少于三个,则将它们全部返回。

示例 1:

输入:
grid=[[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]]grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]]
输出:[228,216,211][228,216,211]
解释:最大的三个菱形和如上图所示。
蓝色:20 + 3 + 200 + 5 = 228
红色:200 + 2 + 10 + 4 = 216
绿色:5 + 200 + 4 + 2 = 211

示例 2:

输入:grid=[[1,2,3],[4,5,6],[7,8,9]]grid = [[1,2,3],[4,5,6],[7,8,9]]
输出:[20,9,8][20,9,8]
解释:最大的三个菱形和如上图所示。
蓝色:4 + 2 + 6 + 8 = 20
红色:9 (右下角红色的面积为 0 的菱形)
绿色:8 (下方中央面积为 0 的菱形)

示例 3:
输入:grid=[[7,7,7]]grid = [[7,7,7]]
输出:[7][7]
解释:所有三个可能的菱形和都相同,所以返回 [7][7]

提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 100
1 <= grid[i][j] <= 10^5

题解

这道题目挺恶心,当场没做出来,暴力模拟即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public int[] getBiggestThree(int[][] grid) {
int mm = grid.length;
int nn = grid[0].length;
List<Integer> list = new ArrayList();
int cur = 0;
//1 3 5 7 9
//i表示第几层菱形,100*100的矩形最大可以包含50层菱形
//xx yy表示第i层菱形的中间那个位置
for (int i = 1; i <= 50; i++) {
for (int x = i - 1; x < mm - i + 1; x++) {
for (int y = i - 1; y < nn - i + 1; y++) {
cur = 0;
for (int xx = x - i + 1; xx <= x + i - 1; xx++) {
cur += grid[xx][y - ((i - 1) - Math.abs(xx - x))];
if ((i - 1) - Math.abs(xx - x) != 0) {
cur += grid[xx][y + ((i - 1) - Math.abs(xx - x))];
}
}
list.add(cur);
}
}
}
//去重
HashSet set = new HashSet(list);
list.clear();
list.addAll(set);
Collections.sort(list);

int ans[];
if (list.size() >= 3) {
ans = new int[3];
ans[0] = list.get(list.size() - 1);
ans[1] = list.get(list.size() - 2);
ans[2] = list.get(list.size() - 3);
} else {
ans = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
ans[i] = list.get(list.size() - i - 1);
}
}
return ans;
}
}

T4 5756. 两个数组最小的异或值之和

题目

给你两个整数数组 nums1 和 nums2 ,它们长度都为 n 。
两个数组的 异或值之和 为 (nums1[0]XORnums2[0])+(nums1[1]XORnums2[1])+...+(nums1[n1]XORnums2[n1])(nums_1[0] XOR nums_2[0]) + (nums_1[1] XOR nums_2[1]) + ... + (nums_1[n - 1] XOR nums_2[n - 1]) (下标从 0 开始)
比方说,[1,2,3][1,2,3] 和 [3,2,1][3,2,1] 的 异或值之和 等于 (1XOR3)+(2XOR2)+(3XOR1)=2+0+2=4(1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4 。
请你将 nums2 中的元素重新排列,使得 异或值之和 最小 。
请你返回重新排列之后的 异或值之和 。

示例 1:
输入:nums1=[1,2],nums2=[2,3]nums1 = [1,2], nums2 = [2,3]
输出:2
解释:将 nums2 重新排列得到 [3,2][3,2]
异或值之和为 (1XOR3)+(2XOR2)=2+0=2(1 XOR 3) + (2 XOR 2) = 2 + 0 = 2

示例 2:
输入:nums1=[1,0,3],nums2=[5,3,4]nums1 = [1,0,3], nums2 = [5,3,4]
输出:8
解释:将 nums2 重新排列得到 [5,4,3][5,4,3]
异或值之和为 (1XOR5)+(0XOR4)+(3XOR3)=4+4+0=8(1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8

提示:
n == nums1.length
n == nums2.length
1 <= n <= 14
0 <= nums1[i], nums2[i] <= 10^7

题解

这题看到n14n \leq 14问题就很简单了,套用一个状压dp,创建数组dp[len+1][1<<len]dp[len + 1][1 << len]
dp[i][j]dp[i][j]表示nums1nums_1数组前i1i - 1个元素与nums2nums_2对应二进制jj状态量之间的最优解
为了规范边界条件,我们设定dp[0]该行表示nums1nums_1数组前0个元素的对应取值,即全为0
我们得到转移方程
dp[i][j]=Math.min(dp[i1][j(1<<k)]+(nums1[i1]nums2[k]),dp[i][j])dp[i][j] = \\ Math.min(dp[i - 1][j - (1 << k)] + (nums_1[i - 1] \bigoplus nums_2[k]), dp[i][j])
其中k为状态量j的1所在的位数, 则j(1<<k)j - (1 << k)表示为j状态去除一个元素后的状态
注意加法和异或的优先级问题

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public int minimumXORSum(int[] nums1, int[] nums2) {
int len = nums1.length;
int[][] dp = new int[len + 1][1 << len];
for(int[] x: dp) Arrays.fill(x, Integer.MAX_VALUE / 2);
Arrays.fill(dp[0], 0);
for(int i = 1; i <= len; i++){
for(int j = 0; j < (1 << len); j++){
int tmp = j;
int cnt = 0;
while(tmp != 0){
tmp &= tmp - 1;
cnt++;
}
if(cnt != i) continue;
for(int t = 0; t < len; t++){
if((j & (1 << t)) != 0){
dp[i][j] = Math.min(dp[i - 1][j - (1 << t)] + (nums1[i - 1] ^ nums2[t]), dp[i][j]);
}
}
}
}
return dp[len][(1 << len) - 1];
}
}