LeetCode-第275场周赛(纪念首次AK)

Author： yfx
发布时间：January 15, 2022
583 views
No comments
4468 words
Categories：算法 C/C++ Python

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

# Problem A - [检查是否每一行每一列都包含全部整数](https://leetcode-cn.com/problems/check-if-every-row-and-column-contains-all-numbers/)

## 方法一：数组

> 题意理解：
>
> 每行每列都是1-n这n个数每个数都有且唯一
>
> 分析：
>
> 按题目要求模拟即可

### 比赛中代码：

```cpp
class Solution {
public:
    bool checkValid(vector<vector<int>>& ma) {
        int n = ma.size();
        for (int i = 0; i < n; ++ i) {
            vector<bool> v(n + 1, false);
            for (int j = 0; j < n; ++ j) {
                if (v[ma[i][j]]) return false;
                v[ma[i][j]] = true;
            }
        }
        for (int i = 0; i < n; ++ i) {
            vector<bool> v(n + 1, false);
            for (int j = 0; j < n; ++ j) {
                if (v[ma[j][i]]) return false;
                v[ma[j][i]] = true;
            }
        }
        return true;
    }
};
```

## 复杂度分析

* 时间复杂度：$O(n^2)$
* 空间复杂度：$O(n)$

# Problem B - [最少交换次数来组合所有的](https://leetcode-cn.com/problems/minimum-swaps-to-group-all-1s-together-ii/)

## 方法一：前缀和

> 题意理解：
>
> 我们需要把所有的1放在一起，首尾也算相邻，求最少需要操作几次
>
> 分析：
>
> 由于每个$1$可以和任意$0$交换位置，假设有$n$个$1$那么最多移动$n$次。现在需要把所有的1放在一起，即最后的$1$在$[i, i + n - 1]$范围内为了移动最少个数的$1$只需要统计哪个区间内$0$最少，则可得到最少的交换次数。由于首位规定相邻，我们可以将数组接长方便操作，则该题转化成求区间和的问题，可以用用前缀和快速得到区间和。

### 比赛中代码：

<div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-4ff9ef0913e12df0f40098497da7febf66" 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-4ff9ef0913e12df0f40098497da7febf66" class="collapse collapse-content"><p></p>

```python
class Solution:
    def minSwaps(self, _nums: List[int]) -> int:
        nums = _nums + _nums
        cnt, ans, n, m = _nums.count(1), 1000000, len(_nums), len(nums)
        psum = [0 for _ in range(m + 1)]
        for i in range(m):
            psum[i + 1] = psum[i] + 1 - nums[i]
        l, r = 0, cnt - 1
        while l < n:
            cur = psum[r + 1] - psum[l]
            ans = min(ans, cur)
            l += 1; r += 1
        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-a337530cabcb29f0cc6eeb3498ac5a63890' role="tab" data-target='#tabs-a337530cabcb29f0cc6eeb3498ac5a63890'>**Python3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-a337530cabcb29f0cc6eeb3498ac5a63890' class="tab-pane fade active in">

```python
class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        n, cnt = len(nums), sum(nums)
        if cnt == 0:
            return 0
  
        cur = 0
        for i in range(cnt):
            cur += (1 - nums[i])
  
        ans = cur
        for i in range(1, n):
            if nums[i - 1] == 0:
                cur -= 1
            if nums[(i + cnt - 1) % n] == 0:
                cur += 1
            ans = min(ans, cur)
        return ans
```

~~ps：由于是定区间所以可以优化掉前缀和数组~~

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

### 复杂度分析

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

# Problem C - [统计追加字母可以获得的单词数](https://leetcode-cn.com/problems/count-words-obtained-after-adding-a-letter/)

## 方法一：暴力

> 题意理解：
>
> 统计targetWords当中有多少个字符串可以从startWords当中选取一个字符串通过给定的转换方式得到。
>
> 分析：
>
> 因为每次可添加一个不存在的字母，并且每个字符串最长为26。我们可以逆向思维，targetWords当中遍历每一个字符串并排序后依次删去某个字符判断其是否存在于startWords当中即可。为了提高查找效率，我们可以把startWords当中的字符串排序后加入到哈希表当中。

### 比赛中代码：

```cpp
class Solution {
public:
    int wordCount(vector<string>& st, vector<string>& ta) {
        int ans = 0;
        set<string> S;
        for (string s : st) {
            sort(s.begin(), s.end());
            S.insert(s);
        }
        for (string s : ta) {
            sort(s.begin(), s.end());
            string tmp;
            for (int i = 0; i < s.size(); ++ i) {
                tmp = s.substr(0, i) + s.substr(i + 1);
                if (S.count(tmp)) {
                    ++ ans;
                    break;
                }
            }
        }
        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-02bc97ac085a5ba6dfc7af7549432088580' role="tab" data-target='#tabs-02bc97ac085a5ba6dfc7af7549432088580'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-02bc97ac085a5ba6dfc7af7549432088580' class="tab-pane fade active in">

```python
class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
        s = set()
        for word in startWords:
            mask = 0
            for ch in word:
                mask |= 1 << (ord(ch) - ord('a'))
            s.add(mask)
        ans = 0
        for word in targetWords:
            mask = 0
            for ch in word:
                mask |= 1 << (ord(ch) - ord('a'))
            for ch in word:
                if mask ^ (1 << (ord(ch) - ord('a'))) in s:
                    ans += 1
                    break
        return ans
```

~~ps：优化掉排序，直接进行状态统计即可~~

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

# Problem D - [全部开花的最早一天](https://leetcode-cn.com/problems/earliest-possible-day-of-full-bloom/)

## 方法一：贪心+优先队列

> 题意理解：
>
> 有个$n$个种子，每个种子有一定的成长时间以及开花时间。种子生时需要一直劳作，即种子不可并行照顾，但进入开花期便可任其自己生长即开花与培养种子可并行。
>
> 分析：
>
> 注意，每天只能为一颗种子劳动，但开始开花时便无需打理，故我们可以先播种种子生最需要时间最长的，其次若时间一样那么为了最大化利用时间，先播种开花期最长的。这样便可以最大化利用时间。

### 参考代码：

```cpp
class Solution {
    using PII = pair<int, int>;
public:
    int earliestFullBloom(vector<int>& plant, vector<int>& grow) {
        int n = plant.size();
        priority_queue<PII> pq;
        for (int i = 0; i < n; ++ i) {
            pq.push({grow[i], plant[i]});
        }
        int cur = 0, f = 0;
        while(!pq.empty()) {
            auto [g, p] = pq.top(); pq.pop();
            cout << p << ' ' << g << endl;
            f = max(f, cur + p + g);
            cur += p;
        }
        return f;
    }
};
```

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

### 复杂度分析

* 时间复杂度：$O(n\log n)$
* 空间复杂度：$O(n)$

Last modification：April 18, 2023

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

LeetCode-第275场周赛(纪念首次AK)

yfx • 2022 年 01 月 15 日

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

# Problem A - [检查是否每一行每一列都包含全部整数](https://leetcode-cn.com/problems/check-if-every-row-and-column-contains-all-numbers/)

## 方法一：数组

> 题意理解：
>
> 每行每列都是1-n这n个数每个数都有且唯一
>
> 分析：
>
> 按题目要求模拟即可

### 比赛中代码：

## 复杂度分析

* 时间复杂度：$O(n^2)$
* 空间复杂度：$O(n)$

# Problem B - [最少交换次数来组合所有的](https://leetcode-cn.com/problems/minimum-swaps-to-group-all-1s-together-ii/)

## 方法一：前缀和

### 比赛中代码：

### 赛后优化代码：

~~ps：由于是定区间所以可以优化掉前缀和数组~~

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

### 复杂度分析

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

# Problem C - [统计追加字母可以获得的单词数](https://leetcode-cn.com/problems/count-words-obtained-after-adding-a-letter/)

## 方法一：暴力

### 比赛中代码：

### 赛后优化代码：

<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-02bc97ac085a5ba6dfc7af7549432088580' role="tab" data-target='#tabs-02bc97ac085a5ba6dfc7af7549432088580'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-02bc97ac085a5ba6dfc7af7549432088580' class="tab-pane fade active in">

~~ps：优化掉排序，直接进行状态统计即可~~

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

# Problem D - [全部开花的最早一天](https://leetcode-cn.com/problems/earliest-possible-day-of-full-bloom/)

## 方法一：贪心+优先队列

### 参考代码：

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

### 复杂度分析

* 时间复杂度：$O(n\log n)$
* 空间复杂度：$O(n)$

LeetCode-第275场周赛(纪念首次AK)

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

本站Handsoem主题的美化教程

宝塔网站nginx反向代理避坑

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

LeetCode-高效制胜-两数之和

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

算法题模板

好用的网站

LeetCode-第371场周赛

LeetCode-高效制胜-两数之和

书生·浦语大模型实战

LeetCode-第275场周赛(纪念首次AK)

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

LeetCode-第275场周赛(纪念首次AK)

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