海外营销网站设计,wordpress老文章,网站过度优化,wordpress重定向过多双指针法-栈与队列 双指针法章节移除元素删除有序数组中的重复项移动零比较含退格的字符串有序数组的平方反转字符串反转字符串II替换空格反转字符串中的单词纯手撕版#xff0c;需要注意的地方还蛮多的反转链表删除链表的倒数第 N 个结点这道题之前做的时候没有注意#xff… 双指针法-栈与队列 双指针法章节移除元素删除有序数组中的重复项移动零比较含退格的字符串有序数组的平方反转字符串反转字符串II替换空格反转字符串中的单词纯手撕版需要注意的地方还蛮多的反转链表删除链表的倒数第 N 个结点这道题之前做的时候没有注意边界处理是需要着重考虑的就是删除节点是链表尾结点的情况。为什么会有上述问题要从本质上去分析我们要删除倒数第N个节点那么slow指针最后就应该停在倒数第N1个节点假设我们最后fast指针指向None(这个可由while循环的判断条件来控制)那么在结果处fast和slow指针之间相隔N个节点注意是“相隔”所以在一开始移动时要让fast移动N1步才能达到目标。而移动N1步可能造成链表越界所以要加入虚拟头。不加入虚拟头会面临当N等于链表长度时按照我的错误做法fast会走到尾结点后的None那么fast.next就会报错目前我没想到好的解决方案同样当链表只有一个节点时不加入虚拟头slow.nextslow.next.next也会报错。本题告诉我虚拟头节点多么重要但是我还没有理解到必须加入虚拟头的原因不加的话有很多边界情况难以处理但这似乎不是必须加入的理由单独处理边界情况N等于链表长度(换句话说就是删除头结点) 链表相交环形链表 II我上一次写这道题的代码这一次学习了卡哥的写法后的代码可以看出选择 while 循环的判断条件也非常有讲究 三数之和四数之和用栈实现队列用队列实现栈有效的括号删除字符串中的所有相邻重复项滑动窗口最大值自己写的代码直接就AC了证明单调队列这里我还是有点印象的。卡哥的代码可以做对比我觉得最主要的区别就在于一些极端错误情况的处理上在实际工程中可能出现类似问题但是在力扣的示例中肯定不会有这种情况的。 前K个高频元素不会是涉及大顶堆小顶堆的内容。 双指针法章节
移除元素
class Solution:def removeElement(self, nums: List[int], val: int) - int:n len(nums)slow 0fast 0while fast n :if nums[fast]!val :nums[slow] nums[fast]slow 1fast 1else :fast 1return slow删除有序数组中的重复项
注意本题的判断条件是 slow-1 , 所以需要先判定 slow 0
class Solution:def removeDuplicates(self, nums: List[int]) - int:n len(nums)slow 0fast 0while fast n :# 注意这个判断条件是 slow-1 , 所以需要先判定 slow 0if slow 0 and nums[fast] nums[slow-1] :fast 1else :nums[slow] nums[fast]fast 1slow 1return slow移动零
注意本题要最后进行一步赋值0的操作
class Solution:def moveZeroes(self, nums: List[int]) - None:Do not return anything, modify nums in-place instead.n len(nums)slow 0fast 0while fast n :if nums[fast] ! 0 :nums[slow] nums[fast]slow 1fast 1else :fast 1while slow n :nums[slow] 0slow 1比较含退格的字符串
class Solution:def backspaceCompare(self, s: str, t: str) - bool:slow 0fast 0s list(s)t list(t)ns len(s)nt len(t)# 先做swhile fast ns :if s[fast] ! #:s[slow] s[fast]slow 1fast 1else :if slow 0 :slow - 1fast 1slen slowslow 0fast 0# 再做twhile fast nt :if t[fast] ! #:t[slow] t[fast]slow 1fast 1else :if slow 0 :slow - 1fast 1tlen slowif slen ! tlen :return Falseelse :for i in range(slen):if s[i]!t[i]:return Falsereturn True有序数组的平方
class Solution:def sortedSquares(self, nums: List[int]) - List[int]:n len(nums)res [0]*nstart 0end n-1# 倒序给结果数组赋值这样才能保证是非递减顺序index n-1while start end :if nums[start]nums[end] 0 :res[index] nums[end]**2end - 1index - 1elif nums[start]nums[end] 0 :res[index] nums[start]**2index - 1start 1else :res[index] nums[start]**2index - 1start 1return res反转字符串
class Solution:def reverseString(self, s: List[str]) - None:Do not return anything, modify s in-place instead.n len(s)slow 0fast n-1while slow fast :s[slow],s[fast] s[fast],s[slow]slow 1fast - 1反转字符串II
class Solution:def reverseStr(self, s: str, k: int) - str:n len(s)for i in range(0,n,2*k):temp s[i:ik]s s[:i] temp[::-1] s[ik:]return s
替换空格
class Solution:def replaceSpace(self, s: str) - str:s list(s)n len(s)count 0for i in s :if i :count 1extend [0]*count*2s s extendnewn n count*2slow n-1fast newn-1while slow -1 :if s[slow]! :s[fast] s[slow]slow - 1fast - 1else :s[fast-2:fast1] %20fast - 3slow - 1return .join(s)反转字符串中的单词
使用 split() 函数版
class Solution:def reverseWords(self, s: str) - str:# 甚至可以不用这个strip# 直接split也会把首尾的空格去掉s s.strip()s s[::-1]s s.split()n len(s)for i in range(n) :temp s[i]s[i] temp[::-1]return .join(s)纯手撕版需要注意的地方还蛮多的
class Solution:def reverseWords(self, s: str) - str:s list(s)n len(s)slow 0fast 0while fast n :if slow 0 and s[fast] :fast 1elif slow 0 and s[fast] and s[slow-1] ! :s[slow] s[fast]slow 1fast 1elif slow 0 and s[fast] and s[slow-1] :fast 1# 上面对 fast 做了加一操作下面这里的 if 是和上面独立的# 所以在进行一切操作之前一定要加上最外层while循环的判断条件 fast nif fast n and s[fast] ! :s[slow] s[fast]slow 1fast 1# 最后一个字符是否是空格是的话就去掉# 我上面的逻辑就会导致最后一位可能是空格if s[slow-1] :s s[:slow-1]length slow-1else :s s[:slow]lenght slows s[::-1] left 0right 0while right slow :if s[right] ! :right 1else :temp s[left:right]s[left:right] temp[::-1]right 1left right# 这里也要注意要单独处理 right 走到最后一个位置的情况由于前面已经去掉了空格# 所以要单独处理if right slow-1 :temp s[left:]s[left:] temp[::-1]right 1left rightreturn .join(s)
反转链表
class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:pre Nonecur headwhile cur :temp cur.nextcur.next prepre curcur tempreturn pre删除链表的倒数第 N 个结点
这道题之前做的时候没有注意边界处理是需要着重考虑的就是删除节点是链表尾结点的情况。
边界错误情况
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:slow headfast head while n 0:fast fast.nextn - 1while fast and fast.next :fast fast.nextslow slow.nextslow.next slow.next.nextreturn head歪打正着虚拟头节点
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:virtual ListNode(0,head)slow virtualfast virtualwhile n 0 :fast fast.nextn - 1while fast.next :fast fast.nextslow slow.nextslow.next slow.next.nextreturn virtual.next
卡哥的代码
class Solution:def removeNthFromEnd(self, head: ListNode, n: int) - ListNode:# 创建一个虚拟节点并将其下一个指针设置为链表的头部dummy_head ListNode(0, head)# 创建两个指针慢指针和快指针并将它们初始化为虚拟节点slow fast dummy_head# 快指针比慢指针快 n1 步for i in range(n1):fast fast.next# 移动两个指针直到快速指针到达链表的末尾while fast:slow slow.nextfast fast.next# 通过更新第 (n-1) 个节点的 next 指针删除第 n 个节点slow.next slow.next.nextreturn dummy_head.next为什么会有上述问题要从本质上去分析我们要删除倒数第N个节点那么slow指针最后就应该停在倒数第N1个节点假设我们最后fast指针指向None(这个可由while循环的判断条件来控制)那么在结果处fast和slow指针之间相隔N个节点注意是“相隔”所以在一开始移动时要让fast移动N1步才能达到目标。而移动N1步可能造成链表越界所以要加入虚拟头。
不加入虚拟头会面临当N等于链表长度时按照我的错误做法fast会走到尾结点后的None那么fast.next就会报错目前我没想到好的解决方案同样当链表只有一个节点时不加入虚拟头slow.nextslow.next.next也会报错。
本题告诉我虚拟头节点多么重要但是我还没有理解到必须加入虚拟头的原因不加的话有很多边界情况难以处理但这似乎不是必须加入的理由
单独处理边界情况N等于链表长度(换句话说就是删除头结点)
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:slow headfast head while n 0 :fast fast.nextn - 1# 单独处理当链表长度等于N的情况即删除头结点if fast None :head head.nextelse :while fast.next :fast fast.nextslow slow.nextslow.next slow.next.nextreturn head链表相交
class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode:curA headAcurB headBcountA 0countB 0while curA :curA curA.nextcountA 1while curB :curB curB.nextcountB 1# 在下面这个判断之后只需要考虑 countA countB 的情况了if countA countB :headA,headB headB,headAcountA,countB countB,countAdiff countA - countBwhile diff 0 :headA headA.nextdiff - 1while headA :if headA headB :return headAheadA headA.nextheadB headB.nextreturn None环形链表 II
这里列出一个代码对比
我上一次写这道题的代码
class Solution:def detectCycle(self, head: ListNode) - ListNode:slow headfast headwhile fast and fast.next:slow slow.nextfast fast.next.next# If there is a cycle, the slow and fast pointers will eventually meetif slow fast:# Move one of the pointers back to the start of the listslow headwhile slow ! fast:slow slow.nextfast fast.nextreturn slow# If there is no cycle, return Nonereturn None
这一次学习了卡哥的写法后的代码
class Solution:def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]:slow headfast headwhile fast and fast.next :slow slow.nextfast fast.next.nextif slow fast :fast headwhile fast ! slow :slow slow.nextfast fast.nextreturn slowreturn None可以看出选择 while 循环的判断条件也非常有讲究
三数之和
class Solution:def threeSum(self, nums: List[int]) - List[List[int]]:nums.sort()n len(nums)res []for i in range(0,n-2):if nums[i] 0 :breakif i 0 and nums[i] nums[i-1] :continueleft i1right n-1while left right :if nums[i] nums[left] nums[right] 0 :right - 1elif nums[i] nums[left] nums[right] 0 :left 1else :path [nums[i] , nums[left] , nums[right]] res.append(path)while left right and nums[right] nums[right-1]:right - 1while left right and nums[left] nums[left1]:left 1left 1right - 1return res四数之和
class Solution:def fourSum(self, nums: List[int], target: int) - List[List[int]]:nums sorted(nums)n len(nums)res []for i in range(0,n-3):if i 0 and nums[i]nums[i-1]:continue# 剪枝细节一定注意要考虑target是负数的情况if nums[i] 0 and nums[i] target:# 这里因为是最外层循环所以break还是return 无所谓breakfor j in range(i1,n-2):if j i1 and nums[j]nums[j-1]:continue# 剪枝细节一定注意要考虑target是负数的情况同时要留意到# 多个负数相加是更小的负数所以(nums[i]nums[j]) 0是必须的# 比如 target-8,解是[-1,-2,-2,-3]前两个的加和是大于target的if (nums[i]nums[j]) 0 and (nums[i]nums[j]) target:# 注意这里不能是return 而是breakbreakleft j1right n-1temp target - (nums[i]nums[j])while left right :if nums[left]nums[right] temp :right - 1elif nums[left]nums[right] temp :left 1else :path [nums[i],nums[j],nums[left],nums[right]]res.append(path)while left right and nums[left]nums[left1]:left 1while left right and nums[right]nums[right-1]:right - 1left 1right - 1return res用栈实现队列
class MyQueue:def __init__(self):self.pushin []self.pushout []def push(self, x: int) - None:self.pushin.append(x)def pop(self) - int:if self.pushout ! [] :return self.pushout.pop()else :self.pushout self.pushin[::-1]self.pushin []return self.pushout.pop()def peek(self) - int:# 我觉得这里是唯一的难点搞清楚代码复用的逻辑# pop出来后在对pushoutappend进去就好了# 这样下次再pop还是这个值是正确的# 因为pushout已经可以看做是一个队列了num self.pop()self.pushout.append(num)return numdef empty(self) - bool:if self.pushin [] and self.pushout []:return Trueelse :return False用队列实现栈
两个队列实现
from collections import deque
class MyStack:def __init__(self):self.dq1 deque()self.dq2 deque()self.number 0def push(self, x: int) - None:self.dq1.append(x)self.number 1def pop(self) - int:if self.empty():return Nonefor i in range(0,self.number-1):self.dq2.append(self.dq1.popleft())num self.dq1.popleft()self.dq1 , self.dq2 self.dq2 , self.dq1self.number - 1return numdef top(self) - int:return self.dq1[-1]def empty(self) - bool:if len(self.dq1) 0:return Trueelse :return False
一个队列实现
from collections import deque
class MyStack:def __init__(self):self.dq1 deque()self.number 0def push(self, x: int) - None:self.dq1.append(x)self.number 1def pop(self) - int:if self.empty():return Nonefor i in range(0,self.number-1):self.dq1.append(self.dq1.popleft())num self.dq1.popleft() self.number - 1return numdef top(self) - int:return self.dq1[-1]def empty(self) - bool:if len(self.dq1) 0:return Trueelse :return False有效的括号
class Solution:def isValid(self, s: str) - bool:stack []n len(s)i 0while i n :if s[i]( :stack.append())elif s[i][ :stack.append(])elif s[i]{ :stack.append(})else :if stack [] or stack.pop() ! s[i]:return Falsei 1if len(stack)!0 :return Falseelse :return True删除字符串中的所有相邻重复项
class Solution:def removeDuplicates(self, s: str) - str:stack []n len(s)i 0while i n :if stack [] :stack.append(s[i])else :if s[i] stack[-1]:stack.pop()else :stack.append(s[i])i 1return .join(stack)滑动窗口最大值
自己写的代码直接就AC了证明单调队列这里我还是有点印象的。
from collections import deque
class DQ:def __init__(self):self.dq deque()def push(self,val):if len(self.dq) 0 :self.dq.append(val)else :while len(self.dq) ! 0 and val self.dq[-1] :self.dq.pop()self.dq.append(val)def top(self):return self.dq[0]def popleft(self):self.dq.popleft()class Solution:def maxSlidingWindow(self, nums: List[int], k: int) - List[int]:res []dq DQ()n len(nums)for i in range(k):dq.push(nums[i])res.append(dq.top())for i in range(k,n):if nums[i-k] dq.top() :dq.popleft()dq.push(nums[i])res.append(dq.top())return res
卡哥的代码可以做对比
from collections import dequeclass MyQueue: #单调队列从大到小def __init__(self):self.queue deque() #这里需要使用deque实现单调队列直接使用list会超时#每次弹出的时候比较当前要弹出的数值是否等于队列出口元素的数值如果相等则弹出。#同时pop之前判断队列当前是否为空。def pop(self, value):if self.queue and value self.queue[0]:self.queue.popleft()#list.pop()时间复杂度为O(n),这里需要使用collections.deque()#如果push的数值大于入口元素的数值那么就将队列后端的数值弹出直到push的数值小于等于队列入口元素的数值为止。#这样就保持了队列里的数值是单调从大到小的了。def push(self, value):while self.queue and value self.queue[-1]:self.queue.pop()self.queue.append(value)#查询当前队列里的最大值 直接返回队列前端也就是front就可以了。def front(self):return self.queue[0]class Solution:def maxSlidingWindow(self, nums: List[int], k: int) - List[int]:que MyQueue()result []for i in range(k): #先将前k的元素放进队列que.push(nums[i])result.append(que.front()) #result 记录前k的元素的最大值for i in range(k, len(nums)):que.pop(nums[i - k]) #滑动窗口移除最前面元素que.push(nums[i]) #滑动窗口前加入最后面的元素result.append(que.front()) #记录对应的最大值return result我觉得最主要的区别就在于一些极端错误情况的处理上在实际工程中可能出现类似问题但是在力扣的示例中肯定不会有这种情况的。
前K个高频元素
不会是涉及大顶堆小顶堆的内容。
卡哥的代码
#时间复杂度O(nlogk)
#空间复杂度O(n)
import heapq
class Solution:def topKFrequent(self, nums: List[int], k: int) - List[int]:#要统计元素出现频率map_ {} #nums[i]:对应出现的次数for i in range(len(nums)):map_[nums[i]] map_.get(nums[i], 0) 1#对频率排序#定义一个小顶堆大小为kpri_que [] #小顶堆#用固定大小为k的小顶堆扫描所有频率的数值for key, freq in map_.items():heapq.heappush(pri_que, (freq, key))if len(pri_que) k: #如果堆的大小大于了K则队列弹出保证堆的大小一直为kheapq.heappop(pri_que)#找出前K个高频元素因为小顶堆先弹出的是最小的所以倒序来输出到数组result [0] * kfor i in range(k-1, -1, -1):result[i] heapq.heappop(pri_que)[1]return result前K个高频元素–大顶堆小顶堆
