【LeetCode】 第 371 场周赛

2932. 找出强数对的最大异或值 I

给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件，则称其为 强数对 ：

|x - y| <= min(x, y)
你需要从 nums 中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（XOR）值是在该数组所有强数对中的 最大值 。

返回数组 nums 所有可能的强数对中的 最大 异或值。

注意，你可以选择同一个整数两次来形成一个强数对。

复杂度：O(N*N)
思路：暴力遍历

class Solution {
    public int maximumStrongPairXor(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        int n = nums.length;
        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                if(nums[j]-nums[i]<=nums[i]) {
                    ans = Math.max(ans, nums[i]^nums[j]);
                }
            }
        }
        return ans;

    }
}

2933. 高访问员工

给你一个长度为 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” 不属于同一小时内。

以列表形式，按任意顺序，返回所有 高访问 员工的姓名。

复杂度：O(NlogN)
思路：用List<String>[]存储每个人的时间节点，然后对其排序，对于第i个时间节点，看第i+2个与第i个时间节点的差值是否小于一小时。

class Solution {
    public List<String> findHighAccessEmployees(List<List<String>> access_times) {
        List<String> ans = new ArrayList();
        Map<String, Integer> map = new HashMap();
        int idx = 0;
        for(List<String> list:access_times) {
            String s = list.get(0);
            if(!map.containsKey(s)) {
                map.put(s, idx);
                idx ++;
            }
        List<String>[] strs = new ArrayList[map.size()];
        Arrays.setAll(strs, e->new ArrayList());
        for(List<String> list:access_times) {
strs[map.get(list.get(0))].add(list.get(1));
        }
        int cnt = 0;
        idx = -1;
        for(int i=0; i<map.size(); i++) {
            Collections.sort(strs[i]);
        }
        for(Map.Entry<String, Integer> entry:map.entrySet()) {
            List<String> list = strs[entry.getValue()];
            int n = list.size();
            for(int i=0; i<n; i++) {
                int j = i+2;
                if(j<n) {
                                    if(isHour(list.get(i),list.get(j))) {
                        ans.add(entry.getKey());
                        break;
                    }
                }                
            }
        }        
        return ans;
    }
    
    public boolean isHour(String a, String b) {
        int carry = 0;
        int res = 0;
        int num11 = 10*(a.charAt(0)-'0')+(a.charAt(1)-'0');
        int num12 = 10*(a.charAt(2)-'0')+(a.charAt(3)-'0');
        int num21 = 10*(b.charAt(0)-'0')+(b.charAt(1)-'0');
        int num22 = 10*(b.charAt(2)-'0')+(b.charAt(3)-'0');
        if(num22-num21<0) {
            carry = -1;
            res = 60 + num22-num12;
        } else {
            res = num22-num12;
        }
        res = (num21-num11+carry)*60 + res;
        return res<60;
    }
}

2934. 最大化数组末位元素的最少操作次数

给你两个下标从 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 。

复杂度：O(N)
思路：分类讨论。分为最后一个元素是否被交换的两类。然后，看每类各自需要多少次交换。

class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        int ans = opChange(nums1, nums2);
        int n = nums1.length;
        int t = nums1[n-1];
        nums1[n-1] = nums2[n-1];
        nums2[n-1] = t;
        int tmp = opChange(nums1, nums2);
        if(tmp>=0) {
           ans = Math.min(ans, 1+tmp); 
        }
        return ans;
    }

    // 查看需要修改多少次
    public int opChange(int[] nums1, int[] nums2) {
        int ans = 0;
        int n = nums1.length;
        for(int i=0; i<n-1; i++) {
            // 满足条件，向后遍历
            if(nums1[i] <=nums1[n-1] && nums2[i]<=nums2[n-1]) {

            } 
            // 不满足条件
            else {
                // 可以交换
                if(nums1[i]<=nums2[n-1] && nums2[i]<=nums1[n-1]) {
                    ans ++;
                } 
                // 无法交换
                else {
                    return -1;
                }
            }
        }
        return ans;
    }
}

2935. 找出强数对的最大异或值 II

给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件，则称其为 强数对 ：

|x - y| <= min(x, y)
你需要从 nums 中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（XOR）值是在该数组所有强数对中的 最大值 。

返回数组 nums 所有可能的强数对中的 最大 异或值。

注意，你可以选择同一个整数两次来形成一个强数对。

复杂度：O(N)
思路：因为求解的是两个数字异或的最大值，可以从掩码的角度考虑。因为a^b=c，可以得到c^b=a。求解数组中的两个数字异或值的最大值，可以最高位找起来，从高位到低位依次构造掩码，设前面得到的答案为ans，则本次最大值为2*ans+1，对于每个数字的掩码x，看看能不能找到x^ans，找不到，则ans-1，进入下一次循环。

class Solution {
    public int maximumStrongPairXor(int[] nums) {
        int maxBit = 30;
        // 由于小到大进行排序
        Arrays.sort(nums);
        int ans = 0;
        for(int k=maxBit; k>=0; k--) {
            Map<Integer, Integer> map = new HashMap();
            
            // 存储对应长度的掩码
            for(int num:nums) {
                map.put(num>>k, num);
            }

            // 前maxBit-k为理想最大值
            int nextX = 2*ans+1;
            boolean found = false;
            for(int x:nums) {
                // 另一个数字y的掩码，假设2*y>=x && y<=x
                int maskY = (x>>k)^nextX;                
                if(map.containsKey(maskY)&& map.get(maskY)*2>=x && map.get(maskY) <= x) {                    
                    found = true;
                }
            }

            if(found) {
                ans = nextX;
            } 
            // 没有找到相应的y，则ans为减一
            else {
                ans = nextX-1;
            }
        }
        return ans;
    }
}