Krahets88道 双指针
判断子序列
Problem: 392. 判断子序列
思路
单词循环逐个对比各个字符串
解题方法
比较基础的双指针应用
复杂度
时间复杂度:
添加时间复杂度, 示例： O(n)
空间复杂度:
添加空间复杂度, 示例： O(1)
Code
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
"""判断子序列"""
i = j = 0
if not s:
return True
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
if i == len(s):
return True
j += 1
return False
链表的中间节点
Problem: 876. 链表的中间结点
思路
没思路，看了提示用快慢指针，也没做出来
解题方法
对于链表了解的不多，一直以为双指针指的是两个索引，但不清楚的是，对于链表而言，应将指针理解为引用
复杂度
时间复杂度:
添加时间复杂度, 示例： O(n)
空间复杂度:
添加空间复杂度, 示例： O(n)
Code
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
"""
链表的中间节点
对于链表了解的不多，一直以为双指针指的是两个索引，但不清楚的是，对于链表而言，应将指针理解为引用
"""
fast = slow = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
相交链表
Problem: 160. 相交链表
思路
没做出来，以下为Krahests的思路：
设HeadA到公共节点之前的长度为a，设HeadB到公共节点之前的长度为b，公共长度为c。
已知：a + c + b = b + c + a
即 HeadA到公共节点之前的长度 加上 公共长度 加上 HeadB到公共节点之前的长度 等于 HeadB到公共节点之前的长度 加上 HeadA到公共节点之前的长度
解题方法
通过同时从headA、headB开始循环，直至找到公共节点为止，如遍历完链表后仍未找到则返回空。
复杂度
时间复杂度:
添加时间复杂度, 示例： O(n)
空间复杂度:
添加空间复杂度, 示例： O(1)
Code
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
A, B = headA, headB
while a != b:
A = A.next if A else headB
B = B.next if B else headA
# 很神奇，一时竟未理解这种写法为何不会导致死循环，看了评论区找到了答案：即使A和B无相交节点也会再遍历到最后时结束，因为两链表末尾都有Null节点
两数之和 II - 输入有序数组
Problem: 167. 两数之和 II - 输入有序数组
思路、解题方法
已知数组按正序排列，使用双指针指向数组首尾。如果和大于目标值则将头指针向后移动来使和更大；如果和小于目标值则将尾指针向前移动来使和更小（俗称对撞双指针）。
复杂度
时间复杂度:
添加时间复杂度, 示例： O(n)
空间复杂度:
添加空间复杂度, 示例： O(1)
Code
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
i, j = 0, len(numbers) -1
if len(numbers) <= 1:
return None
while i < j:
if numbers[j] + numbers[i] > target:
j -= 1
elif numbers[j] + numbers[i] < target:
i += 1
else:
return [i + 1, j + 1]
环形链表 II
Problem: 142. 环形链表 II
思路
啊！用了笨办法哈希表做出来了，看了K神的双指针讲解，又学到了。
解题方法
Krahets
设快慢指针（似乎对于链表则都是快慢指针，跟链表的特性有关），令fast每轮走2步，slow每轮走1步，会出现两种结果：
1.fast指针走过链表末端，说明链表无环，此时直接返回null，如果链表存在环，则双指针一定会相遇，因为每走1轮，fast与slow的间距 +1，fast一定会追上slow。
2.当fast = slow时，两针再环中第一次相遇，设链表共 a + b个节点，其中链表头部到链表入口有a个节点，链表环有b个节点，设两指针各走了f、s步，则有：
1
2
3
1.fast走的步数是slow步数的两倍，即f = 2s
2.fast比slow夺走了n个环的长度，即f = s + nb（双指针都走过a步，然后再环内绕圈直到重合，重合时fast比slow多走环的长度整数倍）
以上两式可得 f = 2nb , s = nb , 即fast和slow指针分别走了2n，n个环的周长。
如果让指针从链表头走k步，那么所有走到链表入口节点时的部署就是k = a + nb。而目前slow已经走了nb步，那么再走a步，就可以到达环的入口，而这时可以用一个新指针，从头列表与slow一起走，当他们相遇的时候，则说明已经找到环入口。
双指针第二次相遇
- 令fast重新指向链表头部节点，此时f = 0 , s = nb。
- 令slow和fast每轮只走一步。
- 当fast指针走到f = a时，slow指针走到s = a + nb步。此时双指针重合，并同时指向链表环入口，返回slow指向的节点即可。
答案出处: 环形链表 II（双指针，清晰图解）-Krahets
感觉这个题的双指针解法好难啊，看了三四遍才看懂。
复杂度
时间复杂度:
添加时间复杂度, 示例： O(n)
空间复杂度:
添加空间复杂度, 示例： O(1)
Code
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
dic = dict()
while head:
dic[head.val] = head
head = head.next
if head.val in dic.keys():
return dic[head.val]
return None
# Krahets双指针解法
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast, slow = head, head
while True:
if not (fast and fast.next): return
fast, slow = fast.next.next, slow.next
if fast == slow: break
fast = head
while fast != slow:
fast, slow = fast.next, slow.next
return fast
反转字符串中的单词
Problem: [409. 最长回文串]
思路
解题方法
复杂度
时间复杂度:
添加时间复杂度, 示例： O()
空间复杂度:
添加空间复杂度, 示例： O()
Code
无重复字符的最长字串
Problem: [409. 最长回文串]
思路
解题方法
复杂度
时间复杂度:
添加时间复杂度, 示例： O()
空间复杂度:
添加空间复杂度, 示例： O()
Code
三数之和
Problem: [409. 最长回文串]
思路
解题方法
复杂度
时间复杂度:
添加时间复杂度, 示例： O()
空间复杂度:
添加空间复杂度, 示例： O()
Code