leetcode 第 367 场算法比赛

零、背景

这次比赛题目不难，不过由于昨晚做视频做的比较晚，睡眠不足，今天比赛做得慢，昨晚四道题排名较后了。

leetcode 仓库地址：https://github.com/tiankonguse/leetcode-solutions

比赛代码：contest/3/367

一、找出满足差值条件的下标 I

题意：给一个数组，求找两个下标，满足下标距离不小于 v1，值距离不小于 v2。

思路：数据范围不大，两层循环比较即可。

二、最短且字典序最小的美丽子字符串

题意：给一个二进制字符串，求一个子串，使得子串中 1 的个数为 k。
求最短的子串，如果有多个，输出字典序最小的。

思路：滑动窗口维护一个 1 的个数为 k 的子串，求最优答案即可。

注意事项：由于求最短子串，显然不能有前缀 0，可以快速处理。

三、找出满足差值条件的下标 II

题意：给一个数组，求找两个下标，满足下标距离不小于 v1，值距离不小于 v2。

思路：与第一题一模一样，数据范围变大了。

解决方案与第二题一样，前缀值集合+滑动窗口解决。
滑动窗口保证下标的条件，前缀值即可二分查找是否有满足要求的答案。

对于 cpp 语言，前缀值集合可以使用 map 来代替。
对于其他语言，如果没有支持二分查找的有序集合，可以使用离散化线段树来做。

优化：集合里的下标都满足要求，对于值只需要保存一个最大值和最小值即可。

四、构造乘积矩阵

题意：给一个矩阵，求一个新的矩阵，新矩阵的元素值是旧矩阵中出了当前位置所有元素的乘积对 12345 取余。

思路：如果取余数是质数，可以使用逆元来做。
这里余数是非素数，所以只能对原矩阵划分求乘积了。

拆分1：矩阵拆分，上下左右是一维数组的乘积、四个角是矩阵的乘积。
拆分2：行划分，上半部所有行矩阵、下半部所有行矩阵、当前行前缀、当前行后缀。
拆分3：二维转一维拆分，前缀、后缀。

注意事项：值很大，相乘时需要转化为64位整数。

五、最后

这次比赛不难，最后一题是模拟题，其实没有第三题难。

《完》

-EOF-

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