LeetCode-第253场周赛

Author： yfx
发布时间：August 8, 2021
646 views
No comments
6833 words
Categories：算法 C/C++ Python

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

# Problem A - [检查字符串是否为数组前缀](https://leetcode-cn.com/problems/check-if-string-is-a-prefix-of-array/)

## 方法一：模拟

> 题意理解：
>
> 字符串数组words的前k个连续的字符串能否合并获得字符串s
>
> 分析：
>
> 模拟操作并判断即可

### 比赛中代码：

```cpp
class Solution {
public:
    bool isPrefixString(string s, vector<string>& words) {
        string t = "";
        for (string str : words) {
            t += str;
            if (s == t) return true;
        }
        return false;
    }
};
```

### 赛后优化代码：

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

```cpp
class Solution {
public:
    bool isPrefixString(string s, vector<string>& words) {
        int n = s.size();
        int i = 0;
        for (string word : words) {
            int m = word.size();
            int j = 0;
            while (i < n && j < m && s[i] == word[j]) ++ i, ++ j;
            if (i == n && j == m) return true;
            if (j != m) return false;
        }
        return false;
    }
};
```

~~ps：利用双指针优化~~

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

```python
class Solution:
    def isPrefixString(self, s: str, words: List[str]) -> bool:
        t = ''
        for word in words:
            t += word
            if len(t) < len(s): continue
            if len(t) > len(s): return False
            return t == s
        return False
```

~~ps：从字符串长度来优化~~

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

## 复杂度分析

* 时间复杂度：$O(min(n, m))$，其中$n$为字符串$s$的长度，$m$为$words$所有字符串合并的长度。
* 空间复杂度：$O(min(n,m))$

# Problem B - [移除石子使总数最小](https://leetcode-cn.com/problems/remove-stones-to-minimize-the-total/)

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

> 题意理解：
>
> 给出一个数组，你可以对数组内的任意一个元素$x$进行一次$x-=floor(x/2)$的操作，且规定你需要操作k次，求操作k次后数组内元素总和的最小值
>
> 分析：
>
> 由题意不难看出若$x$越大则每次操作删去的值就越多，那么我们每次都操作数组中的最大元素操作$k$次则能得到最小的总和，这满足优先队列的属性，复杂度为$k\log n$满足要求

### 比赛中代码：

```cpp
class Solution {
public:
    int minStoneSum(vector<int>& p, int k) {
        int n = p.size();
        priority_queue<int> pq;
        int sum = 0;
        for (int x : p) {
            pq.push(x);
            sum += x;
        }
        while (k -- ) {
            int t = pq.top(); pq.pop();
            sum -= t / 2; t -= t / 2;
            pq.push(t);
        }
        return sum;
    }
};
```

### 赛后优化代码：

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

```cpp
class Solution {
public:
    int minStoneSum(vector<int>& piles, int k) {
        make_heap(piles.begin(), piles.end());
        while (k -- ) {
            pop_heap(piles.begin(), piles.end());
            piles.back() -= piles.back() >> 1;
            push_heap(piles.begin(), piles.end());
        }
        return accumulate(piles.begin(), piles.end(), 0);
    }
};
```

~~ps：又学到了新的C++语法~~

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

```python
from sortedcontainers import SortedList
class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        a = SortedList(piles)
        for _ in range(k):
            x = a.pop()
            x -= x >> 1
            a.add(x)
        return sum(a)
```

~~ps：与Python3的语法~~

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

### 复杂度分析

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

# Problem C - [使字符串平衡的最小交换次数](https://leetcode-cn.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/)

## 方法一：贪心

> 题意理解：
>
> 给出一个括号字符串，每次可以交换两个括号的位置，求最小的操作次数，使给出的字符串平衡。
>
> 分析：
>
> 因为字符串当中左右括号的数量一定是相等的，所以前$k$个字符串中左括号的数量不少于右括号的数量时我们必定可以找到一种分配方式使其是平衡的，该猜想对任意$k$成立。故我们遍历每个字符，统计当前左右括号的数量，若当前右括号数量大于左括号数量，则进行一次操作。
>
> 类似题目：[TMT Document](https://codeforces.com/contest/1509/problem/B)

### 比赛中代码：

```cpp
class Solution {
public:
    int minSwaps(string s) {
        int n = s.size();
        int sum = 0, ans = 0;
        for (int i = 0; i < n; ++ i) {
            if (s[i] == '[') ++ sum;
            else -- sum;
            if (sum < 0) {
                sum += 2;
                ++ ans;
            }
        }
        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-c84fe878a25e1423c14b0ff4ef9946ea810' role="tab" data-target='#tabs-c84fe878a25e1423c14b0ff4ef9946ea810'>**C++**</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-a4d943362cf994ce738fc65c79d9c75b661' role="tab" data-target='#tabs-a4d943362cf994ce738fc65c79d9c75b661'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-c84fe878a25e1423c14b0ff4ef9946ea810' class="tab-pane fade active in">

```cpp
class Solution {
public:
    int minSwaps(string s) {
        int n = s.size();
        int sum = 0, ans = 0;
        for (int i = 0; i < n; ++ i) {
            if (s[i] == '[') ++ sum;
            else if (sum > 0) -- sum;
            else ++ sum, ++ ans;
        }
        return ans;
    }
};
```

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

```python
class Solution:
    def minSwaps(self, s: str) -> int:
        su, ans = 0, 0
        for i, c in enumerate(s):
            if c == '[': su += 1
            elif su > 0: su -= 1
            else: 
                su += 1; ans += 1
        return ans
```

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

### 复杂度分析

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

# Problem D - [找出到每个位置为止最长的有效障碍赛跑路线](https://leetcode-cn.com/problems/find-the-longest-valid-obstacle-course-at-each-position/)

## 方法一：DP+二分

> 题意理解：
>
> 给出一个数组a，返回求每一个元素为结尾的最长不下降子序列。
>
> 分析：
>
> 首先想到的思路就是$dp$，可以设$dp(i)$表示前$0-i$可以得到的最长不下降子序列的长度，最朴素的做法就是两重循环更新则$dp(n-1)$则为答案。但n为$10^5$该时间复杂度无法接受，需要优化。
>
> 那么优化的切入点就是降低第二重循环的时间复杂度即：能否快速找到满足条件的$dp(k)$，考虑到不同长度的不降子序列都有多可能，为了让最终的子序列达到最长，那么我们的每种长度的序列的最后一个元素的值要保持最小，故我们定义一个数组$d$其中，$d(i)$表示长度为$i$的不降子序列的末尾元素的最小值。即我们将每种长度的最优序列存储到了数组$d$当中。
>
> 我们变可以用二分到数组$d$更快的找到以$a[i]$为结尾能得到的最大长度，二分查找该数组中第一个大于当前元素的位置$i$：
>
> * 若$i=len(d)$那么直接把$a[i]$添加到数组$d$
> * 否则更新$d[i]$即$d[i-1]\leqslant a[i]$且$a[i]<d[i]$
>
> 相关题目：[最长递增子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/) [最长上升子序列 II](https://www.acwing.com/problem/content/898/)

### 参考代码：

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

```cpp
class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        int n = obstacles.size();
        vector<int> ans, q;
        for (int obstacle : obstacles) {
            auto it = upper_bound(q.begin(), q.end(), obstacle);
            if (it == q.end()) {
                q.push_back(obstacle);
                ans.push_back(q.size());
            } else {
                ans.push_back(it - q.begin() + 1);
                *it = obstacle;
            }
        }
        return ans;
    }
};
```

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

```python
class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        n = len(obstacles)
        ans, q = [1] * n, list()
        for i, x in enumerate(obstacles):
            it = bisect_right(q, x)
            if it == len(q): q.append(x)
            else: q[it] = x
            ans[i] = it + 1
        return ans
```

~~ps：[bisect](https://www.cnblogs.com/skydesign/archive/2011/09/02/2163592.html)解释~~

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

### 复杂度分析

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

Last modification：August 18, 2021

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

LeetCode-第253场周赛

yfx • 2021 年 08 月 08 日

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

# Problem A - [检查字符串是否为数组前缀](https://leetcode-cn.com/problems/check-if-string-is-a-prefix-of-array/)

## 方法一：模拟

> 题意理解：
>
> 字符串数组words的前k个连续的字符串能否合并获得字符串s
>
> 分析：
>
> 模拟操作并判断即可

### 比赛中代码：

### 赛后优化代码：

~~ps：利用双指针优化~~

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

~~ps：从字符串长度来优化~~

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

## 复杂度分析

* 时间复杂度：$O(min(n, m))$，其中$n$为字符串$s$的长度，$m$为$words$所有字符串合并的长度。
* 空间复杂度：$O(min(n,m))$

# Problem B - [移除石子使总数最小](https://leetcode-cn.com/problems/remove-stones-to-minimize-the-total/)

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

### 比赛中代码：

### 赛后优化代码：

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

~~ps：又学到了新的C++语法~~

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

~~ps：与Python3的语法~~

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

### 复杂度分析

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

# Problem C - [使字符串平衡的最小交换次数](https://leetcode-cn.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/)

## 方法一：贪心

### 比赛中代码：

### 赛后优化代码：

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

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

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

### 复杂度分析

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

# Problem D - [找出到每个位置为止最长的有效障碍赛跑路线](https://leetcode-cn.com/problems/find-the-longest-valid-obstacle-course-at-each-position/)

## 方法一：DP+二分

### 参考代码：

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

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

~~ps：[bisect](https://www.cnblogs.com/skydesign/archive/2011/09/02/2163592.html)解释~~

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

### 复杂度分析

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

LeetCode-第253场周赛

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

本站Handsoem主题的美化教程

宝塔网站nginx反向代理避坑

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

LeetCode-高效制胜-两数之和

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

去除桌面快捷方式图标箭头脚本

LeetCode-第252场周赛

本站Handsoem主题的美化教程

Codeforces-Round #731 (Div. 3)

Windows上值得一用的软件

LeetCode-第253场周赛

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

LeetCode-第253场周赛

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