Python教程网
--左手Python,右手AI!

数据结构 | 最常见的双指针问题 。

关于 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 题 :

Leetcode打卡 | No.26 删除排序数组中的重复项
Leetcode打卡 | No.27 移除元素

⒋奇偶排序

一个公司的面试题 ,给定一个数组 ,有奇数也有偶数 ,要通过处理将奇数放在左边 ,偶数在右边 。这个也可以通过双指针思路进行解决 。
– 定义两个指针 ,分别指向首尾 。
– 左边指针元素若为奇数(取模得 1)指针右移 ,直到指向第一个偶数元素 。
– 右边指针元素若为偶数 (取模得 0)指针左移 ,直到指向第一个奇数元素 。
– 将上述两个指针指向元素互换 。
– 重复上述步骤 ,直到指针指向同一个元素 。

参考代码如下 :


(如果看不清,请点击此处跳转原文阅读)

⒌待你补充!

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

最后,本文首发于公众号:小詹学Python,欢迎扫码关注!

赞(3)
未经允许不得转载:Python教程网 » 数据结构 | 最常见的双指针问题 。
分享到: 更多 (0)

评论 128

  1. #1

    数据结构之最常见的双指针问题 。
    omxongqtw http://www.gk25q05snm6fllk77w82du4w65d79q28s.org/
    [url=http://www.gk25q05snm6fllk77w82du4w65d79q28s.org/]uomxongqtw[/url]
    aomxongqtw

    匿名5个月前 (09-28)回复
  2. #2

    3 Wheel Street Bike

    匿名5个月前 (10-09)回复
  3. #3

    Alcohol Free Wipes

    匿名5个月前 (10-12)回复
  4. #4

    7ml glass vial

    匿名5个月前 (10-13)回复
  5. #5

    Active Dry Shirt

    匿名5个月前 (10-13)回复
  6. #6

    Curved Treadmill

    匿名5个月前 (10-14)回复
  7. #7
  8. #8
  9. #9
  10. #10
  11. #11
  12. #12

    Best mask factory

    匿名5个月前 (10-19)回复
  13. #13

    Church Podium

    匿名4个月前 (10-20)回复
  14. #14

    Designer Coat Hooks

    匿名4个月前 (10-20)回复
  15. #15

    License Frame Price

    匿名4个月前 (10-22)回复
  16. #16

    Metal Shelf

    匿名4个月前 (10-22)回复
  17. #17

    File Tray Price

    匿名4个月前 (10-23)回复
  18. #18

    Mini Electric Grinder Factory

    匿名4个月前 (10-23)回复
  19. #19

    Aluminium Extrusion Dies

    匿名4个月前 (10-26)回复
  20. #20

    Grinding Media Ball Price

    匿名4个月前 (10-27)回复
  21. #21
  22. #22

    40G/100G Modules

    匿名4个月前 (10-29)回复
  23. #23

    Lock Device Factory

    匿名4个月前 (10-30)回复
  24. #24
  25. #25

    school+counselors+need+to+know-a0157032924 buy viagra online
    viagra vs cialis vs levitra

    匿名4个月前 (10-30)回复
  26. #26

    Fitting For Gas

    匿名4个月前 (11-02)回复
  27. #27

    Asphalt Road Cutter Machine

    匿名4个月前 (11-03)回复
  28. #28

    Hand Glove

    匿名4个月前 (11-04)回复
  29. #29

    I’ll let you know how I made out. http://genqpviag.com generic viagra 100

    匿名4个月前 (11-05)回复
  30. #30

    If urinary pain or vaginal burning and redness occur in a young girl, she may
    have an allergy to bubble bath or soap. buy viagra online canada viagra online?trackid=sp-006

    匿名4个月前 (11-05)回复
  31. #31

    Hardware Cable

    匿名4个月前 (11-07)回复
  32. #32

    Vertical Submersible Water Pump

    匿名4个月前 (11-09)回复
  33. #33

    日本性爱直播

    匿名4个月前 (11-12)回复
  34. #34
  35. #35

    Air Filter For Sales

    匿名4个月前 (11-15)回复
  36. #36

    buying viagra in cuba how much is viagra per pill at cvs medicare pays viagra

    匿名4个月前 (11-15)回复
  37. #37

    cost of viagra https://paradiseviagira.com/ online viagra, no prescription

    匿名4个月前 (11-16)回复
  38. #38

    Blank Tracksuits

    匿名4个月前 (11-16)回复
  39. #39

    viagra online buy paypal viagracialisevit viagra online stores

    匿名4个月前 (11-16)回复
  40. #40

    limbaugh smuggles viagra https://purevigra.com/ viagra newsletter anmelden

    匿名4个月前 (11-17)回复
  41. #41

    cuanto tiempo antes debo tomar viagra https://buybuyviamen.com/ estudio de mercado viagra

    匿名4个月前 (11-18)回复
  42. #42

    viagra no presciption herbal viagra gnc where to buy no prescription viagra with discover card

    匿名4个月前 (11-18)回复
  43. #43

    Colorful Plastic Shell Skate

    匿名4个月前 (11-18)回复
  44. #44

    viagra super force https://wowviaprice.com/ where to buy cheap viagra from an american company

    匿名3个月前 (11-19)回复
  45. #45

    viagra 10mg price india viagra cheapest price for sildenafil 100 mg

    匿名3个月前 (11-20)回复
  46. #46

    real viagra for sale canada viagra price viagra 1 tablet

    匿名3个月前 (11-21)回复
  47. #47

    Cheap prices for viagra lightvigra.com
    cost of generic viagra in india

    匿名3个月前 (11-21)回复
  48. #48

    Viagra rx cost https://miraclevigra.com/ sildenafil 1000 mg

    匿名3个月前 (11-21)回复
  49. #49

    viagra interaction with amlodipine viagra reação el viagra caduca

    匿名3个月前 (11-21)回复
  50. #50

    generic viagra online free shipping viagra gel pills viagra 200mg tablets

    匿名3个月前 (11-21)回复
  51. #51

    White paper foil pouch

    匿名3个月前 (11-21)回复
  52. #52

    Bulk Feed Bin

    匿名3个月前 (11-22)回复
  53. #53
  54. #54

    Polyester Fabric

    匿名3个月前 (11-24)回复
  55. #55

    Free Perfume Sample Vial

    匿名3个月前 (11-24)回复
  56. #56
  57. #57

    Pvc Wall Panel China Ceiling

    匿名3个月前 (11-25)回复
  58. #58

    no prescription viagra canada buy cheap viagra generic online generic viagra us

    匿名3个月前 (11-25)回复
  59. #59

    free trial of viagra in canada acquistare viagra in svizzera alternative viagra uk

    匿名3个月前 (11-26)回复
  60. #60

    priligy and viagra jeneric viagra for sale generic viagra low cost

    匿名3个月前 (11-27)回复
  61. #61
  62. #62

    writing dissertation service conclusion research paper essays education

    匿名3个月前 (11-29)回复
  63. #63

    best resume writing services homework help online apologia chemistry homework help

    匿名3个月前 (11-29)回复
  64. #64

    essay writing books help with college help me with my geometry homework

    匿名3个月前 (11-29)回复
  65. #65

    essay writing methods buy essay online write an assignment

    匿名3个月前 (11-30)回复
  66. #66

    best homework help sites college essay 3 college admission essay

    匿名3个月前 (11-30)回复
  67. #67

    Plastic Extruder Shaft

    匿名3个月前 (11-30)回复
  68. #68

    study help research paper zombie apocalypse college essay art

    匿名3个月前 (11-30)回复
  69. #69

    Stump Crushing Machine

    匿名3个月前 (11-30)回复
  70. #70

    Buy essay cheap https://buyessayhelpbtg.com
    where can i buy an essay

    匿名3个月前 (12-02)回复
  71. #71

    Hand Power Tool

    匿名3个月前 (12-03)回复
  72. #72

    write a speech on global warming benefits of essay writing writing essay exams

    匿名3个月前 (12-03)回复
  73. #73

    Law thesis https://thesiswritinghelpsjj.com/ help writing thesis statement

    匿名3个月前 (12-03)回复
  74. #74

    Electrical Distribution Box

    匿名3个月前 (12-04)回复
  75. #75

    Stainless Steel Swaging Fitting

    匿名3个月前 (12-04)回复
  76. #76

    Waterproof Materials

    匿名3个月前 (12-05)回复
  77. #77

    High Torque Motor Price

    匿名3个月前 (12-06)回复
  78. #78

    Anti-Microbial gloves

    匿名3个月前 (12-08)回复
  79. #79

    geneneric cialis aus free cialis medication cialis no prescrip

    匿名3个月前 (12-09)回复
  80. #80

    cialis daily use canadianmed cialis cialis no prescription

    匿名3个月前 (12-10)回复
  81. #81

    genetic viagra il viagra in uk buy viagra without

    匿名3个月前 (12-10)回复
  82. #82

    viagra clinic does alcohol inhibit viagra cheap viagra

    匿名3个月前 (12-11)回复
  83. #83

    viagra 50 mg canada drugs what is more effective,cialis or viagra? cheap viagra australia

    匿名3个月前 (12-12)回复
  84. #84

    viagra paypal payment professional viagra cialis taking cialis and viagra together

    匿名3个月前 (12-12)回复
  85. #85

    What is cialis gocialirx.com generic cialis online

    匿名3个月前 (12-13)回复
  86. #86

    100mg Generic Viagra Online LiseMirl cialis prices cackVial Propecia Grageas

    匿名3个月前 (12-13)回复
  87. #87

    cialis buy cialis and viagra taken together cialis dosage strengths

    匿名3个月前 (12-13)回复
  88. #88

    viagra patent date viagra cialis levitra viagra patent date

    匿名3个月前 (12-14)回复
  89. #89

    viagra cialis on line parmacy viagra montreal online buy viagra

    匿名3个月前 (12-14)回复
  90. #90

    Вот привожу пруфы: hydraruzxpnew4af

    匿名3个月前 (12-17)回复
  91. #91

    It’s fantastic that you are getting ideas from this article as well as from
    our discussion made here.

    My webpage xxx videos (europepmc.org)

    匿名2个月前 (12-22)回复
  92. #92

    canadian pharmacies online online drugstore pharmacy pharmacy online drugstore

    匿名2个月前 (01-11)回复
  93. #93

    pharmacy rx one reviews online canadian pharmacy specialty pharmacy

    匿名2个月前 (01-11)回复
  94. #94

    drugstore cowboy online pharmacy canada pharmacy express

    匿名2个月前 (01-12)回复
  95. #95

    Do you have a spam issue on this website; I also am a blogger,
    and I was wondering your situation; we have created some nice practices and we are looking to trade techniques
    with others, why not shoot me an email if interested.

    Also visit my page … cheap flights

    匿名1个月前 (01-31)回复
  96. #96

    Hello There. I found your blog using msn. This
    is a really well written article. I will be sure to bookmark it and come back to
    read more of your useful information. Thanks for the post.
    I will definitely return.

    Also visit my web-site – cheap flights

    匿名4周前 (02-02)回复
  97. #97

    Hello! I simply would like to offer you a big thumbs up for your great info you have
    got right here on this post. I’ll be returning to your blog for more soon.

    Also visit my web-site cheap flights (http://tinyurl.com/y2rzk76k)

    匿名4周前 (02-02)回复
  98. #98

    Excellent beat ! I wish to apprentice whilst you amend your website, how can i subscribe for
    a blog site? The account aided me a acceptable deal. I were tiny bit acquainted of this your broadcast offered bright clear idea

    Feel free to surf to my web site – cheap flights

    匿名4周前 (02-02)回复
  99. #99

    We stumbled over here coming from a different page and
    thought I may as well check things out. I like
    what I see so now i am following you. Look forward to
    going over your web page yet again.

    Feel free to visit my site: cheap flights (tinyurl.com)

    匿名4周前 (02-03)回复
  100. #100

    pharmacies prescription online cialis super active

    匿名4周前 (02-04)回复
  101. #101

    can buy viagra over counter australia walmart viagra price viagra loest prise

    匿名4周前 (02-05)回复
  102. #102

    Viagra Soft Tabs northwest pharmacy canada anti-depressants

    匿名4周前 (02-06)回复
  103. #103

    cialis online pharmacy Cialis Super Active prescription cost comparison

    匿名4周前 (02-07)回复
  104. #104

    best canadian pharmacies prescription pricing pharmacy

    匿名3周前 (02-08)回复
  105. #105

    walmartviagra viagra tijuana mx viagra without prescription in australia

    匿名3周前 (02-08)回复
  106. #106

    ge money personal loans interest rates advance loan letter format cash advance lumberton nc

    匿名3周前 (02-11)回复
  107. #107

    viagra cana viagra online melbourne canadian pharmacy viagra generic

    匿名3周前 (02-11)回复
  108. #108

    I’m gone to convey my little brother, that he should also go to see
    this web site on regular basis to get updated
    from newest news update.

    my page :: cheap flights [http://tinyurl.com/]

    匿名3周前 (02-12)回复
  109. #109

    viagra sale online near south bend viagra professional generic viagra online us pharmacys

    匿名3周前 (02-12)回复
  110. #110

    payday loan in an hour no credit check payday loans problems payday loans in vista ca

    匿名3周前 (02-13)回复
  111. #111

    can i take cialis with aleve cialis fluoxetin todo sobre el cialis

    匿名3周前 (02-14)回复
  112. #112

    cialis and urine flow cialis coupon canada cialis ambalaj

    匿名3周前 (02-14)回复
  113. #113

    payday loans riverside california cash converters loans darwin payday loan lenders in nc

    匿名2周前 (02-17)回复
  114. #114

    快车足彩

    匿名2周前 (02-17)回复
  115. #115

    Chain Degreaser

    匿名2周前 (02-18)回复
  116. #116

    Cast Nylon Price Supplier

    匿名2周前 (02-20)回复
  117. #117

    Bamboo Car Seat Cushion

    匿名1周前 (02-21)回复
  118. #118

    Fire retardant cloth

    匿名1周前 (02-22)回复
  119. #119

    Black Tungsten Supplier

    匿名1周前 (02-23)回复
  120. #120

    Car Parts

    匿名5天前回复
  121. #121
  122. #122

    buy cialis from cananda cialis 20 what color is cialis pill

    匿名3天前回复
  123. #123
  124. #124
  125. #125

    viagra uses viagra online prescription viagra prescription online

    匿名2天前回复
  126. #126

    Bubble Envelope

    匿名2天前回复
  127. #127
  128. #128