专栏首页小诚信驿站算法攻关-双指针笔记
原创

算法攻关-双指针笔记

一、题目分类

双指针目前LC上涉及83道题,属于面试的一个高频范围区。我们根据标签分类是可以获取到一部分信息笔试考察范围点的。目前LC上一共是1989道题。概率为83/1989= 4.17%.

公众号-小诚信驿站,算法攻关

二、题目举例

  • 链表中是否有环
  • 查找、删除链表倒数第K个节点
  • 最小覆盖子串
  • 两数之和-有序数组
  • 三数之和
  • 最接近的三数之和
  • ....等

三、双指针的思想

双指针的思想可以归纳为:

双指针很奇妙,一快一慢走。

相距K位,可解链表倒数K节点。

相距K位,可解链表是否有环。

相距K位,滑动窗口思想题目跑不了。

持续更新....

四、解题表达式

双指针公式->固定一方,变动另一方,或者双方一起同步

right = left + K;
//链表倒数第K个节点类问题
while(right.next != null){
  left= left.next;
  }
  return left;
//链表循环检测问题 right比left快一步
right = left + K ; K =1;
while(left != right){
   if(left ==null || right.next == null){
     return false;
   }
   left = left.next;
   right = right.next.next;
}

滑动窗口公式->固定一方,变动另一方:

when(right - left + 1 > minWindow){
    //固定左指针,移动右指针
    if(condition1){
        //处理使其满足condition2条件,并不符合condition1条件
        right++;
    }
    //固定右指针,移动左指针
    if(condition2){
        //处理使其满足condition1条件,并不符合condition2条件
        left++;
    }
}

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Mac下golang实现Java加密方式调用

    安装完毕会在home目录下usr/local/go默认的安装目录。然后这个时候可以配置下环境变量

    小诚信驿站
  • 系统设计面试:保姆指南

    像编码面试一样,那些没有有意识地为SDI做准备的应聘者,大多是表现不佳,尤其是在谷歌、Facebook、亚马逊、微软等顶级公司公司,即表现不高于平均水平的候选人...

    小诚信驿站
  • go的代码写作规范

    gopath环境变量指定了你工作区间的位置,默认是home目录下的go目录,eg:/home/go。

    小诚信驿站
  • leecode刷题(21)-- 删除链表的倒数第N个节点

    这道题我们可以采用双指针法来解答。定义两个指针 left 和 right, 都让其指向链表的头节点。先让 right 指针向后移动 n 步,然后 left 指针...

    希希里之海
  • 【一天一大 lee】填充每个节点的下一个右侧节点指针 (难度:中等) - Day20201015

    给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

    前端小书童
  • 机器学习中的常见问题——K-Means算法与矩阵分解的等价

    K-Means算法是较为经典的聚类算法,假设训练数据集XXX为:{x1,x2,⋯,xn}{x1,x2,⋯,xn}\left \{ \mathbf{x}_1,\m...

    zhaozhiyong
  • 一天一大 leet(从先序遍历还原二叉树)难度:困难 DAY-18

    在遍历中的每个节点处,我们输出 D 条短划线(其中 D 是该节点的深度),然后输出该节点的值。(如果节点的深度为 D,则其直接子节点的深度为 D + 1...

    前端小书童
  • LinkedList源码详解

    秋白
  • 用 python 操作 elasticsearch

    用 python 操作 elasticsearch 使用的第三方库是 elasticsearch 。

    用户4945346
  • Linkled List链表

    链表通过指针将一组零散的内存块串联在一起。其中,我们把内存块称为链表的“结点”。为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结...

    羊羽shine

扫码关注云+社区

领取腾讯云代金券