巨硬8.27最后一次笔试
巨硬=微 软， 为防止被和谐！
巨硬公司的梗来自于网友为了调侃微软，因为微软叫微软，微”对应“巨”，“软”对“硬”，这就是巨硬公司的由来。
1. 求字符串S中所有字母均为偶数个的最长子字符串长度。字符串范围1-1E5，全为小写字母。
输入：一个字符串
输出：所有字母均为偶数个的最长子字符串长
例子1："bdaaadadb"，返回6
例子2："abacb"，返回0
例子3："zthzth"，返回6
————————————————————————————————————————————
（LC1371变种）
思路：由于题目的字符串范围较大，我们必须想出O(N)的解法，暴力法不可取。
可以采用掩码的方式，用掩码的每一位记录：
- 位为0，表明该字母出现的次数是偶数
- 位为1，表明该字母出现的次数是奇数
用哈希表记录每个掩码对应的位置。
我们依次遍历字符串S，设当前位置为i，字符为c，我们在掩码mask中对应c的位置异或1. 然后看哈希表有没有当前的掩码：
- 有，说明hashmap[mask]对应的位置idx，对应所有字符均为偶数个的子字符串长度为(i + 1 - idx)，同时更新result
- 否， 则将（mask, i + 1）加入哈希表。
返回result即为所有字母均为偶数个的最长子字符串长度。
class Solution {
public int solution1(String s) {
Map<Integer, Integer> maskHashMap = new HashMap<>();
maskHashMap.put(0, 0);
int mask = 0;
int result = 0;
for (int i = 0, len = s.length(); i < len; ++i) {
mask ^= 1 << (s.charAt(i) - 'a');
int idx = maskHashMap.getOrDefault(mask, -1);
if (idx != -1) {
result = Math.max(result, i + 1 - idx);
}
else {
maskHashMap.put(i + 1, mask);
}
}
return result;
}
} 2. 找数轴上一个最大的点的集合，该集合任意两个点距离都被M的整除。
输入：一个点的坐标数组和M
输出：最大的集合大小
例子1：{-3,-2,1,0,8,7,1 }，M = 4，输出4
例子2：{7,1,11,8,4,10}，M = 8，输出1
————————————————————————————————————————————
基本思路是，先将数组排序，然后遍历数组每个元素x，我们用一个哈希表保存每个数的mod( = ((x%M)+M)%M)值，对于同一个集合的元素，它们的mod一定是相同的。
我们查找哈希表，如果没有对应的mod，则将(mod, 1)加入到哈希表；否则将(mod, v + 1)加入到哈希表。
最后返回的是哈希表最大的值，如果哈希表为空，则返回1.
另外我们需要分析M的取值范围，负数，正数和0.
M为正数和负数的情况相同，对M取绝对值即可。当M为0的时候，就不能对x取模，直接将x作为mod加入到哈希表，进行上述类似的判断。
public int Solution2(int[] A, int M) {
Map<Integer, Integer> freq = new HashMap<>();
if (M == 0) {
for (int x : A) {
freq.compute(x, (k, v) -> {
if (v == null) {
return 1;
}
else {
return v + 1;
}
});
}
}
else {
M = Math.abs(M);
for (int x : A) {
int mod = ((x % M) + M) % M;
freq.compute(mod, (k, v) -> {
if (v == null) {
return 1;
}
else {
return v + 1;
}
});
}
}
return freq.isEmpty() ? 0 : freq.values().stream().max(Comparator.naturalOrder()).get();
} 3. 给定两个相同大小的数组A,B,从每个下标在A，B对应元素选一个合并为新数组C，要求C中的最小不存在正整数最小。N∈[1,1E5]；
输入：数组A，B
输出：C的最小不存在整数
例子1：A=[1,2,4,3], B=[1,3,2,3]，返回2
例子2：A=[3,2,1,6,5]，B=[4,2,1,3,3]，返回3
例子3：A=[1,2]，B=[1,2]，返回3
———————————————————————————————————————————
LC41 贪心算法，每次选择A，B对应元素较大的那个，然后加入到集合set中，找到set中最小不存在整数即可。
public int Solution3(int[] A, int[] B) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < A.length; ++i) {
set.add(Math.max(A[i], B[i]));
}
for (int i = 1; i <= A.length; ++i) {
if (!set.contains(i)) {
return i;
}
}
return A.length + 1;
} 总之，题目基本是LC中等难度题，如果想进微软，LC必须好好刷一下才行。
