LeetCode 系列——双指针问题 。

关于 LeetCode 系列有段时间没有逐题更新了 ,还是想到一题一题的刷有些凌乱 。如前段时间的推文所说 ,准备系统的讲讲数据结构相关知识点 。

刷 LeetCode 那点事 !

今天想要分享的是在刷题中频繁遇到的一个知识点——双指针问题 。杠精读者有没有 ?

指针 ?博主你又在扯蛋 ,Python 没有指针好的伐 !

的确是 ,Python 中没有指针的概念 。刷前几题的时候遇到过链表问题 ,有读者就对链表问题表示困惑 ,其实根本原因就在这 。Python 中用的就是模拟指针 ,所以链表也是模拟链表哟 。

双指针说白了就是两个指针指向两个地址 ,可能是移动速度不同 ,可能是指向不同的节点(元素)。用这种方式去解决一些实际问题 。

合并问题 。比如给定两个有序数组 ,要求将两个有序数组进行合并 ,合并成一个有序数组 。其实有点类似之前刷过的第 4 题 :

LeetCode | 两个有序数组的中位数

当时写的代码不够优化美观 ,但是这类合并问题都可以用到双指针思路解决噢 。

  • 分别定义两个 “指针” ,指向两个数组(list_1;list_2)的首位 。再定义一个新数组(列表list_3)用于存储最终结果 。
  • 将指针指向的两个元素进行比较 ,将较小的元素 copy 到 list_3 中 。
  • 将元素较小的数组指针右移一位 ,继续比较 。直到 list_1 或者list_2 中某一个所有元素都遍历完 ,将另一个剩下的所有元素 copy 到 list_3 即可 。

链表是否有环问题 。链表也是我们所常见的一个数据结构了 ,判断一个链表是否有环就可以用双指针思路解决 。这个在 LeetCode 的第 141 题 。

  • 定义两个指针 ,一快一慢 。比如慢指针一次移动 1 个位置 ,快指针移动 2 个 。
  • 初始快慢指针放在一个位置 ,并开始循环移动 。
  • 如果有环 ,那么随着移动的进行 ,终有快指针经过环遇到并超过慢指针的时候 ,那么这就可以用来判断是否存在环的依据啦 。

原地移除重复元素 。这也是 LeetCode 上比较经典也比较容易的问题 。给定一个排序数组 ,要求删除其中的重复项 。同类型的还有删除给定值 。这两题在 LeetCode 的第 26 和第 27 题 :

No.26 删除排序数组中的重复项

No.27 移除元素

奇偶排序 。一个公司的面试题 ,给定一个数组 ,有奇数也有偶数 ,要通过处理将奇数放在左边 ,偶数在右边 。这个也可以通过双指针思路进行解决 。

  • 定义两个指针 ,分别指向首尾 。
  • 左边指针元素若为奇数(取模得 1)指针右移 ,直到指向第一个偶数元素 。
  • 右边指针元素若为偶数 (取模得 0)指针左移 ,直到指向第一个奇数元素 。
  • 将上述两个指针指向元素互换 。
  • 重复上述步骤 ,直到指针指向同一个元素 。

参考代码如下 :

关于双指针的应用还有很多呀 ,欢迎读者小伙伴们一起留言区补充交流 。

本文分享自微信公众号 - 小詹学Python(xiaoxiaozhantongxue)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据之美

浅谈 Scala 中下划线的用途

Scala 作为一门函数式编程语言,对习惯了指令式编程语言的同学来说,会不大习惯,这里除了思维方式之外,还有语法层面的,比如 underscore(下划线)就会...

207100
来自专栏JetpropelledSnake

Python入门之面向对象编程(一)面向对象概念及优点

本文分为如下几个部分 首先说明面向对象是什么,然后结合实际例子说明面向对象的如下几个优点 方便函数管理 数据封装 对象操作 最后总结一下面向对象的好处 概念...

40670
来自专栏小古哥的博客园

秒懂JS对象、构造器函数和原型对象之间的关系

学习JS的过程中,想要掌握面向对象的程序设计风格,对象模型(原型和继承)是其中的重点和难点,拜读了各类经典书籍和各位前辈的技术文章,感觉都太过高深,花费了不少时...

34470
来自专栏恰童鞋骚年

剑指Offer面试题:16.合并两个排序的链表

PS:这也是一道出镜率极高的面试题,我相信很多童鞋都会很眼熟,就像于千万人之中遇见不期而遇的人,没有别的话可说,唯有轻轻地问一声:“哦,原来你也在这里? ”

7010
来自专栏诸葛青云的专栏

C语言入门基础学习函数?来看我就告诉你!

在前面我们已经讲过了一些简单的函数,如程序的主函数main()、标准输出函数printf()。在C语言中,大多数功能都是依靠函数来实现的。But,你知道什么是函...

15130
来自专栏程序猿DD

第五章 正则表达式的拆分【修订】

本篇文章本不该存在,因小编的失误出现了一些错误,应作者要求,修正昨天同名文章的两处错误。 第五章 正则表达式的拆分 对于一门语言的掌握程度怎么样,可以有两个角度...

21460
来自专栏较真的前端

前端面试题“七连击”(一)

22370
来自专栏GreenLeaves

JavaScript之apply()和call()的区别

我 在一开始看到javascript的函数apply和call时,非常的模糊,看也看不懂,最近在网上看到一些文章对apply方法和call的一些示 例,总算是看...

23470
来自专栏轮子工厂

6. 简单又复杂的“运算符”,建议你看一哈

昨天的《5. 很“迷”的字符与字符串》初稿本来很短的,但是我觉得内容太少了,就加了一些,结果好像就变得特别多〒▽〒。

11030
来自专栏我和PYTHON有个约会

26. 企业级开发基础7:面向对象特征(多态)

多态是让我们的程序在运行的过程中,在不同的状态下进行动态的切换,实现复杂的功能为目的的一种程序开发手段

7610

扫码关注云+社区

领取腾讯云代金券