算法周赛笔记（8月第1周）— LeetCode 第253场周赛

傷城~ 2022-09-04 11:49 202阅读 0赞

### 文章目录 ###

*   *  小结
     *  题目
     *   *  1961
         *  1962
         *  1963
         *  1964

## 小结 ##

本周只参加了一场LeetCode的周赛

还是先说战绩：2道题。/(ㄒoㄒ)/~~

这周情况比较特殊，周五下班的时候给了个紧急需求，周六带女票去弄牙齿，在医院门口坐着敲了一下午代码，周日又上线。

我在上线的间隙抽空参加了本周力扣周赛，这周的题目相对简单，一堆人ak，我也本来有机会过3道的。但由于需要配合上线，做题的时间不充足且总是被打断，唉（心里暗骂QAQ）

**本周题目考察的知识点**：

*  堆
 *  找规律/贪心
 *  动态规划/二分

## 题目 ##

### 1961 ###

[检查字符串是否为数组前缀][Link 1]

给你一个字符串 `s` 和一个字符串数组 `words` ，请你判断 `s` 是否为 `words` 的 **前缀字符串** 。

字符串 `s` 要成为 `words` 的 **前缀字符串** ，需要满足：`s` 可以由 `words` 中的前 `k`（`k` 为 正数 ）个字符串按顺序相连得到，且 `k` 不超过 `words.length` 。

如果 s 是 words 的 前缀字符串 ，返回 true ；否则，返回 false 。

**示例**

> 输入：s = “iloveleetcode”, words = \[“i”,“love”,“leetcode”,“apples”\]  
> 输出：true  
> 解释：  
> s 可以由 “i”、“love” 和 “leetcode” 相连得到。

**题解**

签到题，但要注意：字符串s需要**恰好**为words中的前k个字符串顺序拼接。

Java代码

class Solution { 
        public boolean isPrefixString(String s, String[] words) { 
    		int j = 0;
    		for (int i = 0; i < words.length; i++) { 
    			for (int k = 0; k < words[i].length(); k++) { 
    				if (words[i].charAt(k) != s.charAt(j)) return false;
    				j++;
    				if (j == s.length()) return k == words[i].length() - 1;
    			}
    		}
    		return false;
    	}
    }

### 1962 ###

[移除石子使总数最小][Link 2]

给你一个整数数组 `piles` ，数组 **下标从 0** 开始 ，其中 `piles[i]`表示第 `i` 堆石子中的石子数量。另给你一个整数 `k` ，请你执行下述操作 **恰好** `k` 次：

*  选出任一石子堆 `piles[i]` ，并从中 **移除** `floor(piles[i] / 2)` 颗石子。

**注意**：你可以对 **同一堆** 石子多次执行此操作。

返回执行 `k` 次操作后，剩下石子的 **最小** 总数。

`floor(x)` 为 **小于** 或 **等于** `x` 的 **最大** 整数。（即，对 `x` 向下取整）。

**示例**：

> 输入：piles = \[5,4,9\], k = 2  
> 输出：12  
> 解释：可能的执行情景如下：
> 
>  *  对第 2 堆石子执行移除操作，石子分布情况变成 \[5,4,5\] 。
>  *  对第 0 堆石子执行移除操作，石子分布情况变成 \[3,4,5\] 。  
>     剩下石子的总数为 12 。

**题解**

略加分析可知，每次移除时，都应当选择当前最大的石堆（有点贪心的意思）。很容易想到使用一个大根堆来维护当前的石子堆，每次选择堆顶元素，将其值变为原先的一半（上取整），然后调整堆，重复操作k次即可。

若是手动模拟的堆，可以按照上面的思路操作，如果使用内置的数据结构（Java中是`PriorityQueue`），则考虑将每次的操作变为两步

1.  弹出堆顶
2.  将堆顶元素变为原先的一半（上取整），再插入堆

Java代码如下（Java的`PriorityQueue`默认是小顶堆，我们初始化时需要自定义一个`Comparator`，将其变成大顶堆）

class Solution { 
        public int minStoneSum(int[] piles, int k) { 
    		// 大顶堆
    		PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);
    		// 全部元素插入堆
            for (int i : piles) heap.offer(i);
    		// 执行k次操作
            while (k-- > 0) { 
    			int max = heap.poll(); // 弹出堆顶
    			max -= max / 2; // 减
    			heap.offer(max); // 插入堆
    		}
    		int sum = 0;
    		Iterator<Integer> it = heap.iterator();
    		while (it.hasNext()) sum += it.next();
    		return sum;
    	}
    }

### 1963 ###

[使字符串平衡的最小交换次数][Link 3]

给你一个字符串 `s` ，**下标从 0 开始** ，且长度为偶数 `n` 。字符串 **恰好** 由 `n / 2` 个开括号 `[` 和 `n / 2` 个闭括号 `]` 组成。

只有能满足下述所有条件的字符串才能称为 **平衡字符串** ：

*  字符串是一个空字符串，或者
 *  字符串可以记作 `AB` ，其中 `A` 和 `B` 都是 **平衡字符串** ，或者
 *  字符串可以写成 `[C]` ，其中 `C` 是一个 **平衡字符串** 。

你可以交换 **任意** 两个下标所对应的括号 **任意** 次数。

返回使 `s` 变成 **平衡字符串** 所需要的 **最小** 交换次数。

**示例1**：

>     输入：s = "][]["
>     输出：1
>     解释：交换下标 0 和下标 3 对应的括号，可以使字符串变成平衡字符串。
>     最终字符串变成 "[[]]" 。

**示例2**：

>     输入：s = "]]][[["
>     输出：2
>     解释：执行下述操作可以使字符串变成平衡字符串：
>     
>     - 交换下标 0 和下标 4 对应的括号，s = "[]][[]" 。
>     - 交换下标 1 和下标 5 对应的括号，s = "[[][]]" 。
>       最终字符串变成 "[[][]]" 。

**题解**：

**思路一**（力扣题解）：

看到这道题，第一想到的就是很像**括号匹配**。由于`]`的数量和`[`的数量相同，则`s`一定能变成平衡字符串。

我们先来分析**平衡字符串**的定义，容易发现，这个定义是一种**递归式**的描述。就像`GNU is not Unix`。

我们先来看看**平衡字符串**都长什么样。首先找到递归的退出条件，即空字符串，这是**最短的平衡字符串**。然后根据平衡字符串的定义，我们依次构造更长的平衡字符串。根据第三个条件，则比空字符串稍长的平衡字符串，即`[]`。

根据第二个条件，能够构造`[][]`；根据第三个条件，能够构造`[[]]`。

我们发现，有长度的，最短的平衡字符串，就是`[]`。这是构成其他所有平衡字符串的最小单位。接下来，我们构造平衡字符串，无外乎下面几种情况

*  只套用第二个条件
 *  只套用第三个条件
 *  混合套用第二和第三个条件

其中，只用第二个条件，构造的平衡字符串，都长这样：

`[][][]`，`[][][][]`，`[][][][][][][]`，…

只用第三个条件，构造的平衡字符串，都长这样：

`[[]]`，`[[[]]]`，`[[[[[]]]]]`，…

混合套用第二，第三个条件，构造的平衡字符串，都长这样：

`[[][]]`，`[][][[[]]]`，`[[[]]][][][[][]]`，…

我们观察可以发现，对于一个平衡字符串，左右括号都是两两匹配的。并且，在我们从左往右，遍历一个平衡字符串时，我们左括号`[`的数量，始终是**大于等于**右括号`]`的数量的。也就是说，我们开一个变量`ctn`来记录左括号`[`的数量，然后从左往右遍历，当遇到左括号`[`时，将`ctn`加一，遇到右括号`]`时，将`ctn`减一（表示这个右括号消耗了其左侧一个一个左括号，完成匹配）。则，只要遍历的过程中，一直保持`ctn`大于等于`0`，即说明字符串是平衡字符串了。

也就是说，在从左往右遍历的过程中，只要遇到一个右括号`]`，就总能在这个位置之前找到一个**未被使用**的左括号`[`与之匹配。

若遍历过程中，遇到一个右括号`]`，但在其前面的位置，已经没有可以与之匹配的左括号`[`时，说明这个字符串就不是平衡字符串。此时我们需要将这个右括号`]`，与其右侧的某个左括号`[`交换。（由于左括号和右括号数量相等，则每个右括号一定能找到属于自己的那个左括号）。那么交换时，**我们采用贪心的策略，试图将这个右括号，尽可能地交换到靠右边。以使得后续交换的次数最少。**

为什么这样做就能使得交换次数最少呢？

我们考虑上面使用`ctn`变量在遍历过程中对左括号进行计数的场景。只要把右括号尽可能地往右边放，就能让`ctn`减的最慢。而要字符串是平衡字符串，就需要保证`ctn`一直保持大于等于`0`，则尽可能地推后对`ctn`做减法的情况，就能达到这种效果。

此时，我们可能需要一个双指针，右边指针指向从右往左第一个左括号的位置。然后遍历进行交换并统计，直到两个指针相遇。

然而，我们观察可以发现，从左往右遍历的过程中，只有当遇到右括号`]`且此时`ctn`小于等于`0`了，才需要进行一次交换。而这个交换可以不用实际进行。只要遇到`]`并且此时`ctn`小于等于`0`了，就将交换次数加一，并将`ctn`加一（因为此时已经相当于把该位置变成了左括号`[`），继续遍历下去即可。因为没有实际进行交换，则后面遍历到原本已经交换了的位置时，那个位置还是左括号`[`（如果执行了实际交换，那个位置应该是被交换过来的右括号`]`），而左括号并不会导致交换次数加一，所以不影响最终结果。

Java代码

class Solution { 
        public int minSwaps(String s) { 
            int ctn = 0, ans = 0;
            for (int i = 0; i < s.length(); i++) { 
                if (s.charAt(i) == '[') ctn++;
                else if (ctn > 0) ctn--;
                else { 
                    ctn++;
                    ans++;
                }
            }
            return ans;
        }
    }

**思路二**（我的思路）：

思路一采用的是贪心的策略，下面我们换一种思路。我们需要交换的，只是形如`][`这样的括号组。对于那些已经匹配上的括号组`[]`，我们完全可以把它们从字符串中剔除掉，只要所有的括号组都是形如`[]`的形式，则字符串就是个平衡字符串了。

我们的任务就是从整个字符串中，找出形如`][`这样的括号组的个数，即我们只需要排除已经能够匹配的，形如`[]`这样的括号组。

比如我们将字符串中已经匹配的括号组全部删除，最后得到的一定是形如`]]]][[[[`这样的，左侧全是`]`，右侧全是`[`的字符串。

我们仍然从左到右遍历字符串，用`ctn`来计数左括号的数量，用`num`来计数找到的形如`][`的括号组的个数

*  遇到`[`时，对`ctn`加一
 *  遇到`]`时，
    
     *  当`ctn > 0` 时，对`ctn`减一
     *  当`ctn <= 0`时，对`num`加一

最后，对于形如`]]]][[[[`这样的字符串，我们可以这样考虑：每次交换，最好是能够消除尽可能多的括号（已经完成匹配的括号就可以被消除了），这样，总的交换次数就能达到最少。我们每次交换，最多消掉2组括号，即4个括号。

每次交换，是将一个`]`与一个`[`交换，最好的情况是，交换后，原先右括号能带走一个左括号，原先的左括号能带走一个右括号，一共消掉2组，共4个括号。

假设最后剩余的是`]]][[[`，我们可以看到其长度为6，共有3对括号没有匹配好，则我们每交换一次，就能消掉2对，共4个括号。

假设最后剩余共`n`对括号（长度为`2n`），则最少的交换次数则为 `(n + 1) / 2`

Java代码

class Solution { 
        public int minSwaps(String s) { 
            int leftBraceNums = 0;
            int matchNums = 0; // 匹配上的括号对的个数
            for (int i = 0; i < s.length(); i++) { 
                if (s.charAt(i) == '[') leftBraceNums++;
                else if (leftBraceNums > 0) { 
                    leftBraceNums--;
                    matchNums++;
                }
            }
            return (s.length() - matchNums * 2 + 2) / 4;
        }
    }

### 1964 ###

[找出到每个位置为止最长的有效障碍赛跑路线][Link 4]

你打算构建一些障碍赛跑路线。给你一个 **下标从 0 开始** 的整数数组 `obstacles` ，数组长度为 `n` ，其中 `obstacles[i]` 表示第 `i` 个障碍的高度。

对于每个介于 `0` 和 `n - 1` 之间（包含 `0` 和 `n - 1`）的下标 `i` ，在满足下述条件的前提下，请你找出 `obstacles` 能构成的最长障碍路线的长度：

*  你可以选择下标介于 `0` 到 `i` 之间（包含 `0` 和 `i`）的任意个障碍。
 *  在这条路线中，必须包含第 `i` 个障碍。
 *  你必须按障碍在 `obstacles` 中的 **出现顺序** 布置这些障碍。
 *  除第一个障碍外，路线中每个障碍的高度都必须和前一个障碍 **相同** 或者 **更高** 。

返回长度为 `n` 的答案数组 `ans` ，其中 `ans[i]` 是上面所述的下标 `i` 对应的最长障碍赛跑路线的长度。

**示例1**：

>     输入：obstacles = [1,2,3,2]
>     输出：[1,2,3,3]
>     解释：每个位置的最长有效障碍路线是：
>     
>     - i = 0: [1], [1] 长度为 1
>     - i = 1: [1,2], [1,2] 长度为 2
>     - i = 2: [1,2,3], [1,2,3] 长度为 3
>     - i = 3: [1,2,3,2], [1,2,2] 长度为 3

**示例2**：

>     输入：obstacles = [3,1,5,6,4,2]
>     输出：[1,1,2,3,2,2]
>     解释：每个位置的最长有效障碍路线是：
>     
>     - i = 0: [3], [3] 长度为 1
>     - i = 1: [3,1], [1] 长度为 1
>     - i = 2: [3,1,5], [3,5] 长度为 2, [1,5] 也是有效的障碍赛跑路线
>     - i = 3: [3,1,5,6], [3,5,6] 长度为 3, [1,5,6] 也是有效的障碍赛跑路线
>     - i = 4: [3,1,5,6,4], [3,4] 长度为 2, [1,4] 也是有效的障碍赛跑路线
>     - i = 5: [3,1,5,6,4,2], [1,2] 长度为 2

**题解**：

稍微分析一下，就能知道这道题，等价于求解一个数组在每个位置的，单调递增（不是严格递增）子序列的最大长度（单调递增子序列必须包含当前位置）。

**解法一**：动态规划

对于位置`i`，我们考虑用`d[i]`来表示：以当前位置结尾的最长单调递增子序列的长度。对于`i`  ∈ \\in ∈ `[1, n]`，我们从左到右依次求解各个`d[i]`。

当我们求解到某个位置`d[i]`时，一定已经求解出了`d[0]`，`d[1]`，…，`d[i-1]`

而在求解`d[i]`时，子序列的最后一个位置一定是`i`，我们考虑最长的子序列的倒数第二个位置。倒数第二个位置，要么是在`0`到`i-1`中选择一个，要么最长子序列只包含`i`这一个位置。

我们只需要遍历`j`  ∈ \\in ∈ `[0, i-1]`，当`obstacle[i] >= obstacle[j]` 时，可以将`i`接到`j`后面，此时更新`d[i] = max(d[i], d[j] + 1)`

求出所有的`d[i]`之后，从中找出最大值即可。

Java代码如下

class Solution { 
        public int[] longestObstacleCourseAtEachPosition(int[] obstacles) { 
            int[] d = new int[obstacles.length];
            int ans = 1;
            Arrays.fill(d, 1); // 每个位置的最长子序列的最小可能长度都至少是1 (其本身)
            for (int i = 1; i < obstacles.length; i++) { 
                for (int j = 0; j < i; j++) { 
                    if (obstacles[i] >= obstacles[j]) d[i] = Math.max(d[i], d[j] + 1);
                }
                ans = Math.max(ans, d[i]);
            }
            return d;
        }
    }

朴素动态规划，时间复杂度较高，达到了  O ( n 2 ) O(n^2) O(n2)，提交会报`TLE`，下面我们考虑一下如何优化

**解法二**：贪心+二分

由于我们需要求解以某个位置为终点，**最长**的单调递增子序列。如何让单调递增的子序列达到最长呢？用贪心的思想，很容易想到，只要子序列单调递增的更慢（子序列的每个位置，都尽可能取满足单调性的更小的值），那么得到的子序列长度就会更长。

我们考虑用`d[i]`来表示，长度为`i`的单调递增子序列的末尾元素的最小值。容易发现，`d[i]`是与`i`呈正相关的，即`d[i]`是与`i`单调递增的。假设对于长度为`k`的单调子序列，我们有`d[k]=a`，即长度为`k`的单调子序列的末尾元素的最小值为`a`，那么对于长度为`k+1`的子序列，其一定是在长度为`k`的子序列后面追加一个值，即在`k+1`的位置追加一个值。由于子序列是递增的，那么第`k+1`个位置的数，一定要大于等于第`k`个位置的数，而第`k`个位置的数最小为`d[k]`，那么`K+1`这个位置的数，一定是大于等于`d[k]`的，那么第`k+1`这个位置能够放上去的最小的值`d[k+1]`，也一定是大于等于`d[k]`的。所以`d[i]`是关于`i`单调递增的。

我们从左往右处理，用`len`来表示当前能够得到的最大长度的单调递增子序列，则我们已经知道了 `i`  ∈ \\in ∈ `[1, len]`范围内的全部 `d[i]`，对于当前位置（设为`j`），我们只需要将其追加到前面某个子序列的后面，就能构成一个更长的子序列。我们尽可能的在`i`  ∈ \\in ∈ `[1, len]`中选取长度更长的子序列，并获取到其末尾元素的最小值`d[i]`，把当前元素追加到其后面。

我们可以从右往左遍历`i`，遍历`[len,1]`，找到第一个满足`d[i] <= obstacles[j]`，则这是当前位置能够追加的最长的子序列了。直接追加。而由于`d[i]`是具有单调性的，所以这个查找的过程可以通过二分来做。

Java代码如下

class Solution { 
        public int[] longestObstacleCourseAtEachPosition(int[] obstacles) { 
            int[] d = new int[obstacles.length + 1]; // 存储长度为len的, 末尾最小的元素
            int[] ans = new int[obstacles.length]; // 答案
            d[1] = obstacles[0]; //
            int len = ans[0] = 1;
            for (int i = 1; i < obstacles.length; i++) { 
                // 当当前位置大于最大长度len的最小末尾元素时, 可以直接追加
                if (obstacles[i] >= d[len]) d[ans[i] = ++len] = obstacles[i];
                else { 
                    // 否则, 通过二分找到一个合适的插入位置, 即得到以当前位置结尾的最长递增字串
                    int l = 1, r = len;
                    while (l < r) { 
                        int mid = l + r >> 1;
                        if (d[mid] <= obstacles[i]) l = mid + 1;
                        else r = mid;
                    }
                    // l 的位置满足 d[l-1] <= obstacle[i] < d[l]
                    // 即长度为l的递增子串, 末尾的最小元素由原先的 d[l] 更新为 obstacle[i]
                    d[l] = obstacles[i];
                    ans[i] = l;
                }
            }
            return ans;
        }
    }

（完）

[Link 1]: https://leetcode-cn.com/problems/check-if-string-is-a-prefix-of-array/
[Link 2]: https://leetcode-cn.com/problems/remove-stones-to-minimize-the-total/
[Link 3]: https://leetcode-cn.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/
[Link 4]: https://leetcode-cn.com/problems/find-the-longest-valid-obstacle-course-at-each-position/