【C++ 算法进阶】算法提升二十四
目录标题
- 数组对排序 （数学问题）
- 题目
- 题目分析
- 分割数组问题 （前缀和）
- 题目
- 题目分析
- 字符串包含另一个字符串 （滑动窗口）
- 题目
- 题目分析
数组对排序 （数学问题）
题目
给定一个数组arr 数组是无序的 数组中每两个数字都可以两两组成一个数据对
现在要求你将组成的所有数据对排序 求出其中第K小的某个数据对
题目分析
这道题目实际上是个数学问题
我们可以先将整个数组排序 然后求出前面每个数字能组成的数据对是多少 （其实就是数组的长度）
然后我们就能求出这个数据对第一个数是多少
之后我们按照类似的方法求出第二个数即可
时间复杂度为N * LogN
分割数组问题 （前缀和）
题目
给定一个数组arr 数组的长度一定大于6 现在要求你讲整个数组分成四段 也就是切三刀
每一刀都必须在数组的一个元素上 且这个元素不属于任意一段
现在请问 给你一个数组 该数组是否能分成四段一样的数值
题目分析
首先我们建立一个前缀和数组
第一刀的位置我们是无法确定的 只能一个个尝试 但是确定了第一刀的位置之后 后续的位置就相对确定下来了
- 第一刀的尝试 从0位置开始到终止位置 -5结束都可以尝试
- 确定了第一刀的位置之后 我们就可以求出第一区间的前缀和 （当前位置的前缀和 - 切刀位置的元素）
之后我们想确定第二刀的位置就简单很多了 假设第一刀位置的元素是9 第一区间的值为100 那么我们就要找到前缀和为209的位置 在它的下一位置切一刀 （找不到或者末尾位置是都直接pass ）
字符串包含另一个字符串 （滑动窗口）
题目
现在给定你一个字符串s2 现在请问字符串s1中是否有一个子串包含s2 如果有 返回其中最小的一个子串
题目分析
字符包含问题我们都可以使用滑动窗口 + map来解决
我们可以使用一个map来记录s2中字符出现的次数 使用一个变量all来记录滑动窗口区间的欠账
当all大于0的时候 R不断右扩
当all等于0的时候 L不断右缩
每次当all等于0的时候 我们看看区间是否更小了 不断循环即可