题目
如果一个字符串不含有任何重复字符，我们称这个字符串为好字符串。
给你一个字符串 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;
}
}
|
题目
一个数对 (a,b) 的数对和等于 a + b 。最大数对和是一个数对数组中最大的 数对和 。
比方说，如果我们有数对 (1,5) ，(2,3) 和 (4,4)，最大数对和 为 max(1+5,2+3,4+4)=max(6,5,8)=8 。
给你一个长度为 偶数 n 的数组 nums ，请你将 nums 中的元素分成 n / 2 个数对，使得：
nums 中每个元素 恰好 在 一个 数对中，且
- 最大数对和 的值 最小 。
- 请你在最优数对划分的方案下，返回最小的 最大数对和 。
示例 1：
输入：nums = [3,5,2,3]
输出：7
解释：数组中的元素可以分为数对 (3,3) 和 (5,2) 。
最大数对和为 max(3+3,5+2)=max(6,7)=7 。
示例 2：
输入：nums = [3,5,4,2,4,6]
输出：8
解释：数组中的元素可以分为数对 (3,5)，(4,4) 和 (6,2) 。
最大数对和为 max(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≤...≤xn
考虑上述命题的充分条件：假设给定拆分方法中的数对和xk+xn+1−k 在 k=k′时最大，那么对于任意的拆分方法，都存在一组 u,v，使得 xu+xv≥xk′+xx+1−k′
反证法：
假设u<v，那么使得xv≥xn+1−k′的v值为闭区间
内部[n+1−k′,n]的所有整数，有k′种，如果想使xu+xv<xk′+xx+1−k′恒成立，必有xu<xk′，但是u的取值只有[1,k′−1]，共k′−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
题目
给你一个 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]]
输出：[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]]
输出：[20,9,8]
解释：最大的三个菱形和如上图所示。
蓝色：4 + 2 + 6 + 8 = 20
红色：9 （右下角红色的面积为 0 的菱形）
绿色：8 （下方中央面积为 0 的菱形)
示例 3：
输入：grid=[[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;
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;
}
}
|
题目
给你两个整数数组 nums1 和 nums2 ，它们长度都为 n 。
两个数组的 异或值之和 为 (nums1[0]XORnums2[0])+(nums1[1]XORnums2[1])+...+(nums1[n−1]XORnums2[n−1]) （下标从 0 开始）。
比方说，[1,2,3] 和 [3,2,1] 的 异或值之和 等于 (1XOR3)+(2XOR2)+(3XOR1)=2+0+2=4 。
请你将 nums2 中的元素重新排列，使得 异或值之和 最小 。
请你返回重新排列之后的 异或值之和 。
示例 1：
输入：nums1=[1,2],nums2=[2,3]
输出：2
解释：将 nums2 重新排列得到 [3,2] 。
异或值之和为 (1XOR3)+(2XOR2)=2+0=2 。
示例 2：
输入：nums1=[1,0,3],nums2=[5,3,4]
输出：8
解释：将 nums2 重新排列得到 [5,4,3] 。
异或值之和为 (1XOR5)+(0XOR4)+(3XOR3)=4+4+0=8 。
提示：
n == nums1.length
n == nums2.length
1 <= n <= 14
0 <= nums1[i], nums2[i] <= 10^7
题解
这题看到n≤14问题就很简单了，套用一个状压dp，创建数组dp[len+1][1<<len]
dp[i][j]表示nums1数组前i−1个元素与nums2对应二进制j状态量之间的最优解
为了规范边界条件，我们设定dp[0]该行表示nums1数组前0个元素的对应取值，即全为0
我们得到转移方程
dp[i][j]=Math.min(dp[i−1][j−(1<<k)]+(nums1[i−1]⨁nums2[k]),dp[i][j])
其中k为状态量j的1所在的位数， 则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];
}
}
|
