leetcode第254场周赛：全面且主流

字数统计: 3.3k字 | 阅读时长: 14分

2021-08-16

摘要: 本文是 leetcode 第 254 周赛的记录。主要涉及的算法包括贪心、快速幂、值域二分、搜索。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

总览

这是 leetcode 第 254 场周赛，本场比赛的赞助公司是恒生，前 400 名可获得校招免笔试机会：

恒生电子是一家以“让金融变简单”为使命的金融科技公司，总部位于中国杭州。1995年成立，2003年在上海证券交易所主板上市（600570.SH）。

恒生聚焦金融行业，致力于为证券、期货、基金、信托、保险、银行、交易所、私募等机构提供整体解决方案和服务。恒生已连续16年入选FinTech100全球金融科技百强榜单，2023 年排名第22位，位列中国上榜企业第一。目前公司拥有超过13000名员工，其中产品技术人员占比约73%。

更多信息可以看官网：

1	https://www.hundsun.com/

本场比赛主要涉及到的算法是暴力、贪心、快速幂、值域二分、搜索等，非常全面，知识点没有重合，并且都是主流算法。最终在几次出错罚时之后，全部通过，成绩如下：

各题的算法点以及参考文章如下：

A题: 暴力
- 参考：暴力思想的总结与分析
B题: 贪心
- 参考: 力扣324-摆动排序II
- 参考: TopK问题分类汇总
- 参考: 快速选择算法
C题: 快速幂
- 参考: 快速幂和矩阵快速幂
D题: 值域二分+搜索
- 参考: 二分
- 参考: 778. 水位上升的泳池中游泳
- 参考: 【搜索难题】力扣1439-有序矩阵中的第k个最小数组和

A 题

1967. 作为子字符串出现在单词中的字符串数目

给你一个字符串数组 patterns 和一个字符串 word ，统计 patterns 中有多少个字符串是 word 的子字符串。返回字符串数目。

子字符串是字符串中的一个连续字符序列。

提示：
1 <= patterns.length <= 100
1 <= patterns[i].length <= 100
1 <= word.length <= 100
patterns[i] 和 word 由小写英文字母组成

示例 1：
输入：patterns = [“a”,”abc”,”bc”,”d”], word = “abc”
输出：3
解释：

“a” 是 “abc” 的子字符串。

“abc” 是 “abc” 的子字符串。

“bc” 是 “abc” 的子字符串。

“d” 不是 “abc” 的子字符串。
patterns 中有 3 个字符串作为子字符串出现在 word 中。
示例 2：
输入：patterns = [“a”,”b”,”c”], word = “aaaaabbbbb”
输出：2
解释：

“a” 是 “aaaaabbbbb” 的子字符串。

“b” 是 “aaaaabbbbb” 的子字符串。

“c” 不是 “aaaaabbbbb” 的字符串。
patterns 中有 2 个字符串作为子字符串出现在 word 中。
示例 3：
输入：patterns = [“a”,”a”,”a”], word = “ab”
输出：3
解释：patterns 中的每个字符串都作为子字符串出现在 word “ab” 中。

算法: 暴力

枚举 patterns 里的词，在 str 里查找即可。

代码(Python)

class Solution:
    def numOfStrings(self, patterns: List[str], word: str) -> int:
        ans = 0
        for s in patterns:
            if s in word:
                ans += 1
        return ans

B 题

1968. 构造元素不等于两相邻元素平均值的数组

给你一个下标从 0 开始的数组 nums ，数组由若干互不相同的整数组成。你打算重新排列数组中的元素以满足：重排后，数组中的每个元素都不等于其两侧相邻元素的平均值。

更公式化的说法是，重新排列的数组应当满足这一属性：对于范围 1 <= i < nums.length - 1 中的每个 i ，(nums[i-1] + nums[i+1]) / 2 不等于 nums[i] 均成立。

返回满足题意的任一重排结果。

1
2
3

提示：
3 <= nums.length <= 1e5
0 <= nums[i] <= 1e5

示例 1：
输入：nums = [1,2,3,4,5]
输出：[1,2,4,5,3]
解释：
i=1, nums[i] = 2, 两相邻元素平均值为 (1+4) / 2 = 2.5
i=2, nums[i] = 4, 两相邻元素平均值为 (2+5) / 2 = 3.5
i=3, nums[i] = 5, 两相邻元素平均值为 (4+3) / 2 = 3.5

示例 2：
输入：nums = [6,2,0,9,7]
输出：[9,7,6,2,0]
解释：
i=1, nums[i] = 7, 两相邻元素平均值为 (9+6) / 2 = 7.5
i=2, nums[i] = 6, 两相邻元素平均值为 (7+2) / 2 = 4.5
i=3, nums[i] = 2, 两相邻元素平均值为 (6+0) / 2 = 3

算法: 贪心

想要保证每个元素都不等于其两侧相邻元素的平均值，有很多种排列方式。

比较有规律的一种排列方式是元素是按照一大一小，一大一小这样的方式排的。那么对任意元素，相邻两个元素要么都比该元素大，平均值也就比该元素大，要么都比该元素小，平均值也就比该元素小，满足条件。

下面我们就要从原数组构造一个新数组，新数组元素是按照一大一小的方式排列。这种排序方式称为摆动排序，在 leetcode 上有题目，具体过程参考力扣324-摆动排序II。

这里直接给出思路:

首先将原数组分成 (小于中位数，中位数，大于中位数) 三部分，这在 leetcode 上也是有题目的，第 75 题三色排序。找中位数的过程用快速选择算法，快速选择算法是快速求 TopK 的一种算法，详细参考这篇文章快速选择算法。这里直接用 C++ STL 的 nth_element 即可。

分成 (小于中位数，中位数，大于中位数) 三部分之后构造新数组，前半部分 0 ~ n / 2 放在偶数下标位，后半部分 n / 2 + 1 ~ n - 1 放在奇数下标位。

代码(C++)

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        int n = nums.size();
        nth_element(nums.begin(), nums.begin() + n / 2, nums.end());
        vector<int> result(n);
        for(int i = 0; i < (n + 1) / 2; ++i)
        {
            result[i * 2] = nums[i];
        }
        for(int i = (n + 1) / 2, j = 0; i < n; ++i, ++j)
            result[j * 2 + 1] = nums[i];
        return result;
    }
};

C 题

1969. 数组元素的最小非零乘积

给你一个正整数 p 。你有一个下标从 1 开始的数组 nums ，这个数组包含范围 [1, 2p - 1] 内所有整数的二进制形式（两端都包含）。你可以进行以下操作任意次：

从 nums 中选择两个元素 x 和 y 。
选择 x 中的一位与 y 对应位置的位交换。对应位置指的是两个整数相同位置的二进制位。
比方说，如果 x = 1101 且 y = 0011 ，交换右边数起第 2 位后，我们得到 x = 1111 和 y = 0001 。

请你算出进行以上操作任意次以后，nums 能得到的最小非零乘积。将乘积对 1e9 + 7 取余后返回。

注意：答案应为取余之前的最小值。

1 2	提示： 1 <= p <= 60

示例 1：
输入：p = 1
输出：1
解释：nums = [1] 。
只有一个元素，所以乘积为该元素。

示例 2：
输入：p = 2
输出：6
解释：nums = [01, 10, 11] 。
所有交换要么使乘积变为 0 ，要么乘积与初始乘积相同。
所以，数组乘积 1 2 3 = 6 已经是最小值。

示例 3：
输入：p = 3
输出：1512
解释：nums = [001, 010, 011, 100, 101, 110, 111]

第一次操作中，我们交换第二个和第五个元素最左边的数位。

结果数组为 [001, 110, 011, 100, 001, 110, 111] 。

第二次操作中，我们交换第三个和第四个元素中间的数位。

结果数组为 [001, 110, 001, 110, 001, 110, 111] 。
数组乘积 1 6 1 6 1 6 7 = 1512 是最小乘积。

算法: 快速幂

给定 p 后，所有初始数字为 1,2,...,2^p-1。例如

p = 1，所有初始数字为 1,
p = 2，所有初始数字为 1, 2, 3
p = 3，所有初始数字为 1, 2, 3, 4, 5, 6, 7
p = 4，所有初始数字为 1, 2, 3, 4, …, 15

经过观察后，我们发现 2^p - 1 个数字可以分成两组:

第一组是单个数字 a = 2^p - 1，它就是二进制 p 个 1 组成
第二组是 (a - 1) // 2 对数字，每对数字都可以在交换若干次后，形成 1 和 2^p - 2

例如 p = 3 的情况，初始数字如下

分成的两组数如下：

第一组是单个数字 a = 2^p - 1 = 7
第二组是 (a - 1) // 2 = 3 对数字 (001, 110), (010, 101), (011, 100)

由数学上的结论: 和相等的两个数,两数差越大,他们的乘积越小,当两数相等时,乘积最大。

记 a = 2^p - 1，最后的答案就是一个 a 和 (a-1)//2 个 a - 1 相乘。

其中 (a-1)//2 个 a - 1 相乘必须用快速幂，否则超时。并且用 Python 实现比较好，可以不用考虑溢出的问题了。

代码(Python)

MOD = int(1e9 + 7)

def quickpower2(a, n, p):
    ans = 1
    while n > 0:
        if n % 2 == 1:
            ans = (ans * a) % p
        a = a * a % p
        n = n // 2
    return ans % p;

class Solution:
    def minNonZeroProduct(self, p: int) -> int:
        a = 2 ** p - 1
        b = a - 1
        n = (a - 1) // 2
        ans = (a * quickpower2(b, n, MOD)) % MOD
        return ans

D 题

1970. 你能穿过矩阵的最后一天

给你一个下标从 1 开始的二进制矩阵，其中 0 表示陆地，1 表示水域。同时给你 row 和 col 分别表示矩阵中行和列的数目。

一开始在第 0 天，整个矩阵都是陆地。但每一天都会有一块新陆地被水淹没变成水域。给你一个下标从 1 开始的二维数组 cells ，其中 cells[i] = [ri, ci] 表示在第 i 天，第 ri 行 ci 列（下标都是从 1 开始）的陆地会变成水域（也就是 0 变成 1 ）。

你想知道从矩阵最上面一行走到最下面一行，且只经过陆地格子的最后一天是哪一天。你可以从最上面一行的任意格子出发，到达最下面一行的任意格子。你只能沿着四个基本方向移动（也就是上下左右）。

请返回只经过陆地格子能从最上面一行走到最下面一行的最后一天。

示例 1：
输入：row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
输出：2
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 2 天。

示例 2：
输入：row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
输出：1
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 1 天。

示例 3：
输入：row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
输出：3
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 3 天。

提示：
2 <= row, col <= 2 * 1e4
4 <= row * col <= 2 * 1e4
cells.length == row * col
1 <= ri <= row
1 <= ci <= col
cells 中的所有格子坐标都是 唯一 的。

算法: 值域二分 + DFS

首先由于水域是一天一天地加的，最多可以加 row * col 天。

对于第 i 天:

如果第一行和最后一行可以连通，那么第 0,1,…i-1 这些天也一定可以连通。答案在 i, i+1, …, row col 之中。
如果第一行和最后一行不能连通，那么第 i+1, i+2, …, row col 这些天也一定不能连通。答案在 0,1,…i-1 之中。

因此我们可以用值域二分。现在的问题是给定第 i 天，如何判断第一行和最后一行是否可以连通。这个连通性的判断有各种算法可以选择，一般 BFS, DFS, 并查集都可以。这里我们用 DFS。

代码

class Solution {
public:
    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
        int n = row * col;
        int left = 1, right = n;
        while(left < right)
        {
            int mid = (left + right + 1) / 2;
            if(check(row, col, cells, mid))
                left = mid;
            else
                right = mid - 1;
        }
        return left;
    }

private:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    bool check(const int row, const int col, const vector<vector<int>>& cells, int mid)
    {
        vector<vector<int>> matrix(row, vector<int>(col, 0));
        for(int i = 0; i < mid; ++i)
        {
            matrix[cells[i][0] - 1][cells[i][1] - 1] = 1;
        }
        vector<vector<bool>> visited(row, vector<bool>(col, false));
        for(int j = 0; j < col; ++j)
        {
            if(visited[0][j])
                continue;
            if(matrix[0][j] == 1)
                continue;
            visited[0][j] = true;
            if(dfs(matrix, visited, 0, j, row, col))
                return true;
        }
        return false;
    }

    bool dfs(const vector<vector<int>>& matrix, vector<vector<bool>>& visited, int i, int j, const int row, const int col)
    {
        if(i == row - 1)
            return true;
        for(int d = 0; d < 4; ++d)
        {
            int x = i + dx[d];
            int y = j + dy[d];
            if(x < 0 || x >= row || y < 0 || y >= col)
                continue;
            if(visited[x][y])
                continue;
            visited[x][y] = true;
            if(matrix[x][y] == 1)
                continue;
            if(dfs(matrix, visited, x, y, row, col))
                return true;
        }
        return false;
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法leetcode

leetcode第254场周赛：全面且主流

总览

A 题

算法: 暴力

代码(Python)

B 题

算法: 贪心

代码(C++)

C 题

算法: 快速幂

代码(Python)

D 题

算法: 值域二分 + DFS

代码