leetcode 第 254 场算法比赛

零、背景

这次题目比较简单，但是昨晚腿疼没睡好，发呆了好久，用了一个小时才做完所有题，排名100之外了。

一、作为子字符串出现在单词中的字符串数目

题意：给一个字符串数组( k 个，平均长度为 n)和一个原始字符串（长度为 m），问数组中有多少字符串是原始字符串的子串。

思路：数据量不大，直接子串查找即可。
复杂度：O(k*n*m)

优化：标准的做法预处理出 KMP 的 next 函数，然后快速查找。
复杂度：O(k*(n + m))

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

题意：给 n 个互不相同的数字，问如何排列数字，才能使得每个位置的数字不等于左右数字的平均数。

思路：构造题。

我的方法：让中间的数字都小于或都大于两边的数字即可。

实现方法：先排序，然后奇数位置放一半小的数字，偶数位置放一半大的数字。

三、数组元素的最小非零乘积

题意：给一个数字 p，可以得到 [1, 2^p - 1] 范围的整数，即2^p-1个数字。 现在可以任意选择两个数字，对任意一位进行交换（交换后不允许出现数字 0）。
现在可以交换无数次，问怎么交换，才能使得所有数字的乘积最小。

思路：首先需要找到最优答案的状态。

我纸上推导了一番，发现好复杂，首先需要确定需要交换的两个数字，但是数字这么多。

突然我想到，这个是第三题，不可能那么难，于是猜想肯定存在规律。
根据第三组数据样例，发现这个样例存在一个规律：将所有的数字交换为1 和 2^p-2。

按照这个规律来看，最终有一个数字是a=2^p-1，有b=(2^p-2)/2个 1 和 c=2^p-2。
则最终乘积是a * c ^ b。

c^b需要使用快速幂来做，使用模板即可。

int minNonZeroProduct(int p) {
    if(p == 1) return 1;
    ull one = 1;
    ull a = ((one<<p) - 1) %  mod;
    ull b = ((one<<p) - 2) % mod;
    ull c = (one<<(p - 1)) - 1;
    // a * (b ^c)
    return (powMod(b, c, mod) * a) % mod;
}

四、你能穿过矩阵的最后一天

题意：给一个冰山地图，每天地图有一个陆地会变成水，问能坚持到哪天，地图依旧可以从第一行走到最后一行。

思路：这道题我读了好久（可以看我B站的录播视频，我甚至切换到英文反复读题）。
读到题意后，发现直接二分天数，得到当前地图，DFS 判断即可。

五、最后

这次题除了第三题是找规律，其他题都不难。

这次题你都做出来了吗，第三题你证明出规律的正确性了吗？

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code