第一题直接暴力就行了，题目和最后一题一样，我就偷懒只放最后一题的题解了。
100128. High-Access Employees
给你一个长度为 n 、下标从 0 开始的二维字符串数组 access_times 。对于每个 i（0 <= i <= n - 1 ），access_times[i][0] 表示某位员工的姓名，access_times[i][1] 表示该员工的访问时间。access_times 中的所有条目都发生在同一天内。
访问时间用 四位 数字表示， 符合 24 小时制 ，例如 "0800" 或 "2250" 。
如果员工在 同一小时内 访问系统 三次或更多 ，则称其为 高访问 员工。
时间间隔正好相差一小时的时间 不 被视为同一小时内。例如，"0815" 和 "0915" 不属于同一小时内。
一天开始和结束时的访问时间不被计算为同一小时内。例如，"0005" 和 "2350" 不属于同一小时内。
以列表形式，按任意顺序，返回所有 高访问 员工的姓名。
测试样例：
输入：access_times = [["a","0549"],["b","0457"],["a","0532"],["a","0621"],["b","0540"]]
输出：["a"]
解释：
"a" 在时间段 [05:32, 06:31] 内有三条访问记录，时间分别为 05:32 、05:49 和 06:21 。
但是 "b" 的访问记录只有两条。
因此，答案是 ["a"] 。
解答：这道题目范围很小，其实暴力也行。我是先用HashMap，把同一个员工的打卡记录保存起来。然后按照每个员工的访问时间排序，用双指针判断他/她是高访问员工。
class Solution {
public List<String> findHighAccessEmployees(List<List<String>> access_times) {
HashMap<String, List<Integer>> accessTimeMap = new HashMap<>();
for (List<String> access : access_times) {
String name = access.get(0);
int time = turnTime(access.get(1));
if (!accessTimeMap.containsKey(name)) {
accessTimeMap.put(name, new ArrayList<>());
}
accessTimeMap.get(name).add(time);
}
List<String> res = new ArrayList<>();
for (Map.Entry<String, List<Integer>> kv : accessTimeMap.entrySet()) {
List<Integer> times = kv.getValue();
Collections.sort(times);
int st = 0, ed = 0;
while (ed < times.size()) {
while (times.get(ed) - times.get(st) >= 60) {
++st;
}
if (ed - st >= 2) {
res.add(kv.getKey());
break;
}
++ed;
}
}
return res;
}
private int turnTime(String access) {
return Integer.parseInt(access.substring(0, 2)) * 60 + Integer.parseInt(access.substring(2));
}
}100117. Minimum Operations to Maximize Last Elements in Arrays
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，这两个数组的长度都是 n 。
你可以执行一系列 操作（可能不执行）。
在每次操作中，你可以选择一个在范围 [0, n - 1] 内的下标 i ，并交换 nums1[i] 和 nums2[i] 的值。
你的任务是找到满足以下条件所需的 最小 操作次数：
- nums1[n - 1] 等于 nums1 中所有元素的 最大值 ，即 nums1[n - 1] = max(nums1[0], nums1[1], ..., nums1[n - 1]) 。
- nums2[n - 1] 等于 nums2 中所有元素的 最大值 ，即 nums2[n - 1] = max(nums2[0], nums2[1], ..., nums2[n - 1]) 。
以整数形式，表示并返回满足上述 全部 条件所需的 最小 操作次数，如果无法同时满足两个条件，则返回 -1 。
测试样例：
输入：nums1 = [1,2,7]，nums2 = [4,5,3]
输出：1
解释：
在这个示例中，可以选择下标 i = 2 执行一次操作。
交换 nums1[2] 和 nums2[2] 的值，nums1 变为 [1,2,3] ，nums2 变为 [4,5,7] 。
同时满足两个条件。
可以证明，需要执行的最小操作次数为 1 。
因此，答案是 1 。
解答：这道题目只需要枚举2种情况：
- nums1和nums2最后元素执行操作
- nums1和nums2最后元素不执行操作
对于这两种情况，分别遍历数组，查看最小操作数。
class Solution {
public int minOperations(int[] nums1, int[] nums2) {
int len = nums1.length;
int l1 = nums1[len - 1], l2 = nums2[len - 1];
int res = Integer.MAX_VALUE;
{
int cur = 0;
boolean isValid = true;
for (int i = 0; i < len - 1; ++i) {
if (nums1[i] > l1 || nums2[i] > l2) {
if (nums2[i] > l1 || nums1[i] > l2) {
isValid = false;
break;
} else {
++cur;
}
}
}
if (isValid) {
res = Math.min(res, cur);
}
}
{
int cur = 1;
boolean isValid = true;
for (int i = 0; i < len - 1; ++i) {
if (nums1[i] > l2 || nums2[i] > l1) {
if (nums2[i] > l2 || nums1[i] > l1) {
isValid = false;
break;
} else {
++cur;
}
}
}
if (isValid) {
res = Math.min(res, cur);
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}
}100124. Maximum Strong Pair XOR II
给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件，则称其为 强数对 ：
- |x - y| <= min(x, y)
你需要从 nums 中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（XOR）值是在该数组所有强数对中的 最大值 。
返回数组 nums 所有可能的强数对中的 最大 异或值。
注意，你可以选择同一个整数两次来形成一个强数对。
测试样例
输入：nums = [1,2,3,4,5]
输出：7
解释：
数组 nums 中有 11 个强数对：(1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) 和 (5, 5) 。
这些强数对中的最大异或值是 3 XOR 4 = 7 。
解答：本来以为这道题目会很难，好久不见的8分题目。其实是一道模版题。利用Trie数可以快速搜索最大XOR值。然后把数组排序，利用双指针就能知道结果了。
class Solution {
private class TrieNode {
TrieNode[] next;
int count;
public TrieNode() {
next = new TrieNode[2];
count = 0;
}
}
private void addNum(int n, TrieNode root) {
TrieNode tmp = root;
for (int i = 20; i >= 0; --i) {
int curByte = (n >> i) & 1;
if (tmp.next[curByte] == null) {
tmp.next[curByte] = new TrieNode();
}
tmp = tmp.next[curByte];
++tmp.count;
}
}
private void removeNum(int n, TrieNode root) {
TrieNode tmp = root;
for (int i = 20; i >= 0; --i) {
int curByte = (n >> i) & 1;
TrieNode last = tmp;
tmp = tmp.next[curByte];
tmp.count -= 1;
if (tmp.count == 0) {
last.next[curByte] = null;
}
}
}
private int searchMax(int n, TrieNode root) {
TrieNode tmp = root;
int res = 0;
for (int i = 20; i >= 0; --i) {
int curByte = (n >> i) & 1;
if (curByte == 0) {
if (tmp.next[1] != null) {
tmp = tmp.next[1];
res += (1 << i);
} else {
tmp = tmp.next[0];
}
} else {
if (tmp.next[0] != null) {
tmp = tmp.next[0];
} else {
res += (1 << i);
tmp = tmp.next[1];
}
}
}
return res;
}
public int maximumStrongPairXor(int[] nums) {
Arrays.sort(nums);
TrieNode root = new TrieNode();
int res = 0;
int st = 0, ed = 0;
while (st < nums.length) {
while (ed < nums.length && nums[ed] - nums[st] <= nums[st]) {
addNum(nums[ed], root);
++ed;
}
int findMax = searchMax(nums[st], root);
res = Math.max(findMax ^ nums[st], res);
removeNum(nums[st], root);
++st;
}
return res;
}
}