LeetCode-第252场周赛

Author： yfx
发布时间：August 1, 2021
635 views
One comment
3189 words
Categories：算法 C/C++ Python

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

# Problem A - [三除数](https://leetcode-cn.com/problems/three-divisors/)

## 方法一：穷举

> 穷举因子即可

### 比赛中代码：

```cpp
class Solution {
public:
    bool isThree(int n) {
        int cnt = 2;
        for (int i = 2; i < n; ++ i)
            if (n % i == 0) ++ cnt;
        return cnt == 3;
    }
};
```

### 赛后优化代码：

<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-dcbecae654a7e0c041116712745141f610' role="tab" data-target='#tabs-dcbecae654a7e0c041116712745141f610'>**C++**</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-786bdf4e191a6f42d604cde93fc170e5711' role="tab" data-target='#tabs-786bdf4e191a6f42d604cde93fc170e5711'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-dcbecae654a7e0c041116712745141f610' class="tab-pane fade active in">

```cpp
class Solution {
public:
    bool isThree(int n) {
        int cnt = 2;
        for (int i = 2; i * i <= n; ++ i) {
            if (n % i == 0) {
                ++ cnt;
                if (i != n / i) ++ cnt;
            }
            if (cnt > 3) return false;
        }
        return cnt == 3;
    }
};
```

</div><div role="tabpanel" id='tabs-786bdf4e191a6f42d604cde93fc170e5711' class="tab-pane fade  ">

```python
class Solution:
    def isThree(self, n: int) -> bool:
        cnt = 2
        for i in range(2, n):
            if i * i > n: break
            if n % i == 0:
                cnt += 1
                if i != n / i: cnt += 1
        return cnt == 3
```

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

### 复杂度分析：

* 时间复杂度：$O(\sqrt{N})$
* 空间复杂度：$O(1)$

# Problem B - [你可以工作的最大周数](https://leetcode-cn.com/problems/maximum-number-of-weeks-for-which-you-can-work/)

## 方法一：贪心

> 贪心思路：每周选择剩余任务最多的项目，且与上周不同
>
> 分析可以发现：只要阶段最多的项目可以完成，那么其他项目都可以完成。若任务最多的项目超过其余项目的总和，那么该项目一定无法完成全部任务。

### 参考代码：

<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-4aab7134aef90476e1f2f09417449e02810' role="tab" data-target='#tabs-4aab7134aef90476e1f2f09417449e02810'>**C++**</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-a9f4f027120bb1ecbd8c1aa893079fc9551' role="tab" data-target='#tabs-a9f4f027120bb1ecbd8c1aa893079fc9551'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-4aab7134aef90476e1f2f09417449e02810' class="tab-pane fade active in">

```cpp
class Solution {
    using LL = long long;
public:
    long long numberOfWeeks(vector<int>& mi) {
        LL sum = 0, m = 0;
        for (LL x : mi) sum += x, m = max(m, x);
        return min(sum, (sum - m) * 2 + 1);
    }
};
```

</div><div role="tabpanel" id='tabs-a9f4f027120bb1ecbd8c1aa893079fc9551' class="tab-pane fade  ">

```python
class Solution:
    def numberOfWeeks(self, milestones: List[int]) -> int:
        s, m = sum(milestones), max(milestones)
        return min(s, (s - m) * 2 + 1)
```

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

### 复杂度分析：

* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$

# Problem C - [收集足够苹果的最小花园周长](https://leetcode-cn.com/problems/minimum-garden-perimeter-to-collect-enough-apples/)

## 方法一：二分+数学

![image.png](https://cdn.xuyifan.top/handsome-static/images/blog-image/996740772.png)

> 观察上图可以发现如下规律：
>
> 以$(n, n)$为顶点的一圈其边的规律为$2n,2n-1,\cdots,n,\cdots,2n-1,2n$，所以我们以$(n,n)$顶点到下一个顶点有$2\cdot\frac{(n + 2n)\cdot(n + 1)}{2} - n - 2n = 3n^2$，故一圈有$4\cdot3n^2 = 12n^2$个苹果则从$(1,1)$到$(n,n)$共$12\sum_{i = 1}^n{i^2}=2n(n+1)(2n+1)$，其对应周长为$8n$
>
> 故可使用二分来枚举其顶点即可

### 参考代码：

<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-f09282b8639617c6b8260d6f2881bba7990' role="tab" data-target='#tabs-f09282b8639617c6b8260d6f2881bba7990'>**C++**</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-cee1e0620c6560d0f17132015235ea55981' role="tab" data-target='#tabs-cee1e0620c6560d0f17132015235ea55981'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-f09282b8639617c6b8260d6f2881bba7990' class="tab-pane fade active in">

```cpp
class Solution {
    using LL = long long;
public:
    long long minimumPerimeter(long long neededApples) {
        LL l = 1, r = 1e5;
        while (l < r) {
            LL mid = (l + r) >> 1;
            if (2 * mid * (mid + 1) * (2 * mid + 1) >= neededApples) r = mid;
            else l = mid + 1;
        }
        return 8 * l;
    }
};
```

</div><div role="tabpanel" id='tabs-cee1e0620c6560d0f17132015235ea55981' class="tab-pane fade  ">

```python
class Solution:
    def minimumPerimeter(self, neededApples: int) -> int:
        lo, hi = 1, int(1e5)
        while lo < hi:
            mid = (lo + hi) >> 1
            if 2 * mid * (mid + 1) * (2 * mid + 1) >= neededApples: hi = mid
            else: lo = mid + 1
        return 8 * lo
```

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

### 复杂度分析：

* 时间复杂度：$O(\log C)$，其中$C=10^5$
* 空间复杂度：$O(1)$

Last modification：August 18, 2021

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

One comment

kqzvdzpyty
March 4th, 2025 at 06:58 pm

作者的布局谋篇匠心独运，让读者在阅读中享受到了思维的乐趣。

Reply

LeetCode-第252场周赛

yfx • 2021 年 08 月 01 日

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

# Problem A - [三除数](https://leetcode-cn.com/problems/three-divisors/)

## 方法一：穷举

> 穷举因子即可

### 比赛中代码：

```cpp
class Solution {
public:
    bool isThree(int n) {
        int cnt = 2;
        for (int i = 2; i < n; ++ i)
            if (n % i == 0) ++ cnt;
        return cnt == 3;
    }
};
```

### 赛后优化代码：

</div><div role="tabpanel" id='tabs-786bdf4e191a6f42d604cde93fc170e5711' class="tab-pane fade  ">

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

### 复杂度分析：

* 时间复杂度：$O(\sqrt{N})$
* 空间复杂度：$O(1)$

# Problem B - [你可以工作的最大周数](https://leetcode-cn.com/problems/maximum-number-of-weeks-for-which-you-can-work/)

## 方法一：贪心

### 参考代码：

<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-4aab7134aef90476e1f2f09417449e02810' role="tab" data-target='#tabs-4aab7134aef90476e1f2f09417449e02810'>**C++**</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-a9f4f027120bb1ecbd8c1aa893079fc9551' role="tab" data-target='#tabs-a9f4f027120bb1ecbd8c1aa893079fc9551'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-4aab7134aef90476e1f2f09417449e02810' class="tab-pane fade active in">

</div><div role="tabpanel" id='tabs-a9f4f027120bb1ecbd8c1aa893079fc9551' class="tab-pane fade  ">

```python
class Solution:
    def numberOfWeeks(self, milestones: List[int]) -> int:
        s, m = sum(milestones), max(milestones)
        return min(s, (s - m) * 2 + 1)
```

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

### 复杂度分析：

* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$

# Problem C - [收集足够苹果的最小花园周长](https://leetcode-cn.com/problems/minimum-garden-perimeter-to-collect-enough-apples/)

## 方法一：二分+数学

![image.png](https://cdn.xuyifan.top/handsome-static/images/blog-image/996740772.png)

### 参考代码：

<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-f09282b8639617c6b8260d6f2881bba7990' role="tab" data-target='#tabs-f09282b8639617c6b8260d6f2881bba7990'>**C++**</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-cee1e0620c6560d0f17132015235ea55981' role="tab" data-target='#tabs-cee1e0620c6560d0f17132015235ea55981'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-f09282b8639617c6b8260d6f2881bba7990' class="tab-pane fade active in">

</div><div role="tabpanel" id='tabs-cee1e0620c6560d0f17132015235ea55981' class="tab-pane fade  ">

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

### 复杂度分析：

* 时间复杂度：$O(\log C)$，其中$C=10^5$
* 空间复杂度：$O(1)$

LeetCode-第252场周赛

One comment

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

本站Handsoem主题的美化教程

宝塔网站nginx反向代理避坑

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

LeetCode-高效制胜-两数之和

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

Codeforces-Round #731 (Div. 3)

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

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

LeetCode-二叉树中所有距离为 K 的结点

LeetCode-第251场周赛

LeetCode-第252场周赛

One comment

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

LeetCode-第252场周赛

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