Fork me on GitHub

尺取法

字数统计: 506字   |   阅读时长≈ 1分

对于尺取法，一般用于线性表的处理。

我们有两个指针一样的东西，l和r分别指向两个元素，l于r之间的东西就是我们尝试维护的东西。

例题1

询问序列中和大于s的子串的最小长度。

题解

初始左端点为0，右端点为n-1, 长度为n-1

如果当前区间不满足，同时右移左右端点

如果当前区间满足，最小长度自减

例题2

询问序列中以第k个元素为起点的长度为n的子串的前缀和的最小值大于s的最小i

题解

设立一个前缀和最小值，以及区间和，让尺子长度逐渐增大，增大到N时结束

如果当前区间最小值满足，右移右端点，更新区间和，如果区间和小于于最小值，那么当我们右移左端点时当前最小前缀和在右端点不动时永远都是整个区间和，右移左端点直到区间和大于s，迭代

例题3

询问序列中与值t相差最小的子串和

题解

​ 对前缀和排序，再尺取

​ 如果右端点减去左端点大于t，尝试用此时的端点来更新答案，然后右移左端点，如果右端点减去左端点依旧大于t，迭代，反之先尝试更新答案，然后右移右端点直到右端点减去左端点大于t(最后一次移动前尝试更新答案)，迭代

例题4

询问序列中包含所有值的最短子串

题解

​ 建立map记录有没有，cnt记录种类，以加快判断，

​ 如果当前区间不满足，右移右端点，如果此时长度大于或等于已经找到的最小长度(初始化为无穷大)，右移左端点，迭代

​ 如果当前区间满足，更新最小长度，右移右端点，迭代

赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

主要涉及技术：
Java后端开发、聚合支付、
公众号开发、开源爱好者、Linux

联系QQ:2434387555

很惭愧

只做了一点微小的工作
谢谢大家