LeetCode-第371场周赛

Author： yfx
发布时间：November 19, 2023
521 views
No comments
5987 words
Categories：算法 Python

<div class="tip share">请注意，本文编写于 553 天前，最后修改于 553 天前，其中某些信息可能已经过时。</div>

# Problem A - [找出强数对的最大异或值 I](https://leetcode.cn/problems/maximum-strong-pair-xor-i/)

## 方法一：暴力

> 题意理解：$nums$中$x$和$y$满足$|x-y|\leq min(x,y)$，求所以满足条件的$x$和$y$的最大$x$^$y$。
>
> 分析：数据量小直接暴力枚举即可。

### 比赛中代码：

<div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-54a64fc8a099274b911658a113706a5793" aria-expanded="true"><div class="accordion-toggle"><span style="">**Python3**</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-54a64fc8a099274b911658a113706a5793" class="collapse collapse-content"><p></p>

```python
class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        ans = 0
        n = len(nums)
        for i in range(n):
            for j in range(n):
                if abs(nums[i] - nums[j]) <= min(nums[i], nums[j]):
                    ans = max(ans, nums[i] ^ nums[j])
        return ans
```

### 赛后优化代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-f6dd05b8155547a11627877fe9a9edb2850' role="tab" data-target='#tabs-f6dd05b8155547a11627877fe9a9edb2850'>**Python3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-f6dd05b8155547a11627877fe9a9edb2850' class="tab-pane fade active in">

```python
class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        ans = 0
        for i, num in enumerate(nums):
            for j in range(i, len(nums)):
                if abs(num - nums[j]) <= min(num, nums[j]):
                    ans = max(ans, num ^ nums[j])
        return ans
```

</div>
</div>
</div>

## 复杂度分析

* 时间复杂度：$O(n^2)$，其中$n$为$nums$数字的长度。
* 空间复杂度：$O(1)$。

# Problem B - [高访问员工](https://leetcode.cn/problems/high-access-employees/)

## 方法一：排序+模拟

> 题意理解：找出所有有在1小时内访问不少于3次的员工姓名
>
> 分析：哈希表记录每个用户的所有访问时间，为了方便对比可将时间转为分钟，最后排序判断相邻$3$次访问是不是在一个小时内即可。数据量不大。

### 比赛中代码：

<div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-fc09c939af663a0966cd9d9f3b4ce68c77" aria-expanded="true"><div class="accordion-toggle"><span style="">**Python3**</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-fc09c939af663a0966cd9d9f3b4ce68c77" class="collapse collapse-content"><p></p>

```python
class Solution:
    def findHighAccessEmployees(self, access_times: List[List[str]]) -> List[str]:
        def change(t):
            h = int(t[:2])
            m = int(t[2:])
            return h * 60 + m
        ans = []
        dic = defaultdict(list)
        for name, t in access_times:
            dic[name].append(change(t))
  
        def check(v):
            n = len(v)
            i = 2
            while i < n:
                if v[i] - v[i - 2] < 60:
                    return True
                i += 1
            return False
  
        for k, v in dic.items():
            v.sort()
            if check(v):
                ans.append(k)
        return ans
```

### 赛后优化代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-de2e008948fa2c659db1b5ac6f035755970' role="tab" data-target='#tabs-de2e008948fa2c659db1b5ac6f035755970'>**Python3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-de2e008948fa2c659db1b5ac6f035755970' class="tab-pane fade active in">

```python
class Solution:
    def findHighAccessEmployees(self, access_times: List[List[str]]) -> List[str]:
        name2times = defaultdict(list)
        for name, s in access_times:
            t = int(s[:2]) * 60 + int(s[2:])
            name2times[name].append(t)
  
        ans = []
        for name, a in name2times.items():
            a.sort()
            if any(a[i] - a[i - 2] < 60 for i in range(2, len(a))):
                ans.append(name)
        return ans
```

</div>
</div>
</div>

## 复杂度分析

* 时间复杂度：$O(Ln+n\log{n})$，其中$n$为$access_times$的长度，$L$为员工姓名的长度，本题不超过$10$。
* 空间复杂度：$O(Ln)$。

# Problem C - [最大化数组末位元素的最少操作次数](https://leetcode.cn/problems/minimum-operations-to-maximize-last-elements-in-arrays/)

## 方法一：思维

> 题意理解：两个数组求使数组满足最后一个元素是最大值的最小操作次数，如果不能返回-1。每次可以交换两个数组相同下标的元素。
>
> 分析：两种情况：是否交换最后一个元素。然后挨个判断，如果当前位置不叫换或交换都存在不满足条件的情况，则返回-1。

### 比赛中代码：

<div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-20f610ae12c808409df9fb54dd63e14739" aria-expanded="true"><div class="accordion-toggle"><span style="">**Python3**</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-20f610ae12c808409df9fb54dd63e14739" class="collapse collapse-content"><p></p>

```python
class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        4449
        for i in range(n - 1):
            temp = [(nums1[i], i), (nums2[i], i), (nums1[-1], n - 1), (nums2[-1], n - 1)]
            temp.sort()
            if temp[-1][1] != n - 1:
                return -1
            if temp[0][1] == n - 1:
                return -1
        mx1, mx2 = max(nums1), max(nums2)
        if (mx1 != nums1[-1] and nums1[-1] >= max(nums2[:n-1])) or (mx2 != nums2[-1] and nums2[-1] >= max(nums1[:n-1])):
            return 1
        # ans = cnt = 0
        # for i in range(n):
        #     if nums1[i] > nums1[-1] or nums2[i] > nums2[-1]:
        #         ans += 1
        #     if nums1[i] == nums2[i]:
        #         cnt += 1
        # return min(ans, n - cnt - ans)
        ans = 0
        if nums1[-1] < nums2[-1]:
            cnt1 = cnt2 = 0
            for i in range(n - 1):
                if nums1[i] > nums1[-1]:
                    cnt1 += 1
                if nums2[i] > nums1[-1]:
                    cnt2 += 1
            cnt2 += 1
            ans = min(cnt1, cnt2)
        else:
            cnt1 = cnt2 = 0
            for i in range(n - 1):
                if nums1[i] > nums2[-1]:
                    cnt1 += 1
                if nums2[i] > nums2[-1]:
                    cnt2 += 1
            cnt1 += 1
            ans = max(ans, min(cnt1, cnt2))
        return ans
```

### 赛后优化代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-3255a0fa143fd3efbdb495955c9062aa360' role="tab" data-target='#tabs-3255a0fa143fd3efbdb495955c9062aa360'>**Python3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-3255a0fa143fd3efbdb495955c9062aa360' class="tab-pane fade active in">

```python
class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        def f(last1: int, last2: int) -> int:
            ans = 0
            for x, y in zip(nums1, nums2):
                if x > last1 or y > last2:
                    if y > last1 or x > last2:
                        return inf
                    ans += 1
            return ans
        ans = min(f(nums1[-1], nums2[-1]), f(nums2[-1], nums1[-1]))
        return ans if ans != inf else -1
```

</div>
</div>
</div>

## 复杂度分析

* 时间复杂度：$O(n)$，其中$n$为$nums_1$的长度。
* 空间复杂度：$O(1)$。

# Problem D - [找出强数对的最大异或值 II](https://leetcode.cn/problems/maximum-strong-pair-xor-ii/)

## 方法一：排序+双指针+Trie树

> 题意理解：同第1题，但数据量更大。
>
> 分析：假设$x<y$，则条件转为$y\leq 2*x$，求满足这个条件的最大$x$^$y$。使用双指针加Trie树，先将数组排序，枚举$y$并放入Trie树中，将所有不满足$y\leq 2*x$的$x$从Trie树中移除（$j$枚举$x$，因为数组有序只增不减），查询$y$能得到的最大异或值，同时维护$ans$。

### 赛后代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-06d545901b0961ce87eb6d80c144c1cb440' role="tab" data-target='#tabs-06d545901b0961ce87eb6d80c144c1cb440'>**Python3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-06d545901b0961ce87eb6d80c144c1cb440' class="tab-pane fade active in">

```python
class Trie:
    HIGH_BIT = 19
    __slots__ = 'son', 'cnt'

def __init__(self):
        self.son: List[Trie | None] = [None, None]
        self.cnt = 0

def insert(self, num: int) -> None:
        node = self
        for i in range(Trie.HIGH_BIT, -1, -1):
            j = num >> i & 1
            if node.son[j] is None:
                node.son[j] = Trie()
            node = node.son[j]
            node.cnt += 1

def query(self, num: int) -> int:
        node, ans = self, 0
        for i in range(Trie.HIGH_BIT, -1, -1):
            j = num >> i & 1
            if node.son[1 - j]:
                ans |= 1 << i
                node = node.son[1 - j]
            else:
                node = node.son[j]
        return ans
  
    def remove(self, num: int) -> None:
        node = self
        for i in range(Trie.HIGH_BIT, -1, -1):
            j = num >> i & 1
            node.son[j].cnt -= 1
            if node.son[j].cnt <= 0:
                node.son[j] = None
                break
            node = node.son[j]
  
class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        trie = Trie()
        nums.sort()
        n = len(nums)
        ans = j = 0
        for num in nums:
            trie.insert(num)
            while j < n and nums[j] * 2 < num:
                trie.remove(nums[j])
                j += 1
            ans = max(ans, trie.query(num))
        return ans
```

</div>
</div>
</div>

## 复杂度分析

* 时间复杂度：$O(n\log{n}+n\log{U})$，其中$n$为$nums$的长度，$U=max(nums)$本题$U=2^{20}-1$，即$nums$的二进制长度不会超过20。
* 空间复杂度：$O(n\log{U})$。

Last modification：November 19, 2023

看着给点？(●'◡'●)？

LeetCode-第371场周赛

yfx • 2023 年 11 月 19 日

<div class="tip share">请注意，本文编写于 553 天前，最后修改于 553 天前，其中某些信息可能已经过时。</div>

# Problem A - [找出强数对的最大异或值 I](https://leetcode.cn/problems/maximum-strong-pair-xor-i/)

## 方法一：暴力

> 题意理解：$nums$中$x$和$y$满足$|x-y|\leq min(x,y)$，求所以满足条件的$x$和$y$的最大$x$^$y$。
>
> 分析：数据量小直接暴力枚举即可。

### 比赛中代码：

### 赛后优化代码：

</div>
</div>
</div>

## 复杂度分析

* 时间复杂度：$O(n^2)$，其中$n$为$nums$数字的长度。
* 空间复杂度：$O(1)$。

# Problem B - [高访问员工](https://leetcode.cn/problems/high-access-employees/)

## 方法一：排序+模拟

### 比赛中代码：

### 赛后优化代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-de2e008948fa2c659db1b5ac6f035755970' role="tab" data-target='#tabs-de2e008948fa2c659db1b5ac6f035755970'>**Python3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-de2e008948fa2c659db1b5ac6f035755970' class="tab-pane fade active in">

</div>
</div>
</div>

## 复杂度分析

* 时间复杂度：$O(Ln+n\log{n})$，其中$n$为$access_times$的长度，$L$为员工姓名的长度，本题不超过$10$。
* 空间复杂度：$O(Ln)$。

# Problem C - [最大化数组末位元素的最少操作次数](https://leetcode.cn/problems/minimum-operations-to-maximize-last-elements-in-arrays/)

## 方法一：思维

### 比赛中代码：

### 赛后优化代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-3255a0fa143fd3efbdb495955c9062aa360' role="tab" data-target='#tabs-3255a0fa143fd3efbdb495955c9062aa360'>**Python3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-3255a0fa143fd3efbdb495955c9062aa360' class="tab-pane fade active in">

</div>
</div>
</div>

## 复杂度分析

* 时间复杂度：$O(n)$，其中$n$为$nums_1$的长度。
* 空间复杂度：$O(1)$。

# Problem D - [找出强数对的最大异或值 II](https://leetcode.cn/problems/maximum-strong-pair-xor-ii/)

## 方法一：排序+双指针+Trie树

### 赛后代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-06d545901b0961ce87eb6d80c144c1cb440' role="tab" data-target='#tabs-06d545901b0961ce87eb6d80c144c1cb440'>**Python3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-06d545901b0961ce87eb6d80c144c1cb440' class="tab-pane fade active in">

```python
class Trie:
    HIGH_BIT = 19
    __slots__ = 'son', 'cnt'

def __init__(self):
        self.son: List[Trie | None] = [None, None]
        self.cnt = 0

</div>
</div>
</div>

## 复杂度分析

* 时间复杂度：$O(n\log{n}+n\log{U})$，其中$n$为$nums$的长度，$U=max(nums)$本题$U=2^{20}-1$，即$nums$的二进制长度不会超过20。
* 空间复杂度：$O(n\log{U})$。

LeetCode-第371场周赛

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

本站Handsoem主题的美化教程

宝塔网站nginx反向代理避坑

纪元1800.DLC完全解锁补丁【正版适用】-2023.11.14

LeetCode-高效制胜-两数之和

LeetCode-高效制胜-两数之和 II - 输入有序数组

考研 · 励志手杖——音乐，温柔的陪伴

LeetCode-第252场周赛

PyCharm设置Python文件头部模板信息

LeetCode-第372场周赛

LeetCode-找到最终的安全状态

LeetCode-第371场周赛

Leave a Comment Cancel reply 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

LeetCode-第371场周赛

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款