27 移除元素

理清楚，在本题中，快慢指针代表的意义是什么。

我的代码

class Solution:def removeElement(self, nums: List[int], val: int) -> int:slow = 0n = len(nums)for fast in range(n):if nums[fast] != val:nums[slow] = nums[fast]slow += 1return slow

26 删除有序数组中的重复项

我的代码

弄清楚slow和fast指针的含义，最后别忘记给slow加一。

class Solution:def removeDuplicates(self, nums: List[int]) -> int:slow = 0 n = len(nums)if n == 1 :return 1for fast in range(1,n):if nums[fast] != nums[slow] :slow += 1nums[slow] = nums[fast]return slow+1

283 移动0

想太多，已知移动0，那就是把0剔除+末尾赋值。

我的代码

class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""slow = 0n = len(nums)for fast in range(n):if nums[fast] != 0 :nums[slow] =  nums[fast]slow = slow + 1if slow < n :for i in range(slow,n):nums[i] = 0return nums

844 比较含退格的字符串

我的代码

加一个多重退格判断。

class Solution:def backspaceCompare(self, s: str, t: str) -> bool:s = list(s)t = list(t)s_slow = 0n = len(s)for fast in range(n):if s[fast] != '#' :s[s_slow] = s[fast]s_slow = s_slow + 1else:if s_slow > 0 :s_slow = s_slow - 1t_slow = 0n = len(t)for fast in range(n):if t[fast] != '#' :t[t_slow] =  t[fast]t_slow = t_slow + 1else:if t_slow > 0 :t_slow = t_slow - 1if s[0:s_slow] == t[0:t_slow]:return Trueelse:return False

977 有序数组的平方

已经掌握了，两个指针加和判断绝对值大小，申请新数组作为返回值。

我的代码

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:first = 0end = len(nums)-1res = nums.copy()index = endwhile first <= end :if nums[first] + nums[end] < 0 :res[index] = nums[first] * nums[first]first += 1else :res[index] = nums[end] * nums[end]end -= 1index -= 1return res

344 反转字符串

小意思，双指针，以后如果再需要反转，直接调内置函数吧。

我的代码

class Solution:def reverseString(self, s: List[str]) -> None:"""Do not return anything, modify s in-place instead."""start = 0end = len(s)-1while start < end:s[end] , s[start] = s[start] , s[end]  start += 1end -= 1

剑指offer 05–替换空格

思路1：申请额外空间+遍历
思路2：代码随想录的思路，只申请一块需要替换的额外空间，在原数组上操作。

这里试一下思路2。

我的代码

在编写过程中，已经可以完全理清思路2的做法，但由于Python编程语言的特性：str为不可更改类型，所以强硬写出来并不美观，不如直接替换。

class Solution:def replaceSpace(self, s: str) -> str:s = list(s)n = len(s)for i in range(n-1,-1,-1):if s[i]==' ':s[i] = '%20'return ''.join(s)

class Solution:def replaceSpace(self, s: str) -> str:res = ''for i in s:if i != ' ':res += ielse :res += '%20'return res

151 反转字符串里的单词

这题较难，此次复习并未做出此题。整体思路不难：即先反转整个字符串，再反转每个单词。

没想到的是如何处理空格，只能想到了很复杂的方法，先处理前后，再处理中间，实则运用双指针法就可以去除所有空格。

移除空格的思想，运用前面编写的过的移除元素的思想。

我的代码

看了代码随想录的解答之后，自己试图进行独立的代码编写。

失败，去除空格的逻辑理不清。

代码随想录的代码

class Solution:def reverseWords(self, s: str) -> str:# 将字符串拆分为单词，即转换成列表类型words = s.split()# 反转单词left, right = 0, len(words) - 1while left < right:words[left], words[right] = words[right], words[left]left += 1right -= 1# 将列表转换成字符串return " ".join(words)

重写代码随想录的代码

我觉得给出的代码不好，怪不得第一遍写完后，印象非常浅薄，原因就是Python的内置函数太方便了，一个split就把空格全部去掉，并且完成了单词的切割，这不好。

下面的代码是，完全按照代码随想录给出的思路进行的复现。

class Solution:def reverseWords(self, s: str) -> str:s = list(s)s = self.remove_space(s)s = s[::-1] # 反转函数，直接调内部，前面写过了n = len(s)slow = 0for i in range(n):if s[i] == ' ':temp = s[slow:i]temp = temp[::-1]s[slow:i] = tempslow = i+1if i == n-1 :temp = s[slow:i+1]temp = temp[::-1]s[slow:i+1] = tempreturn ''.join(s)def remove_space(self,s):slow = 0n = len(s)i = 0while i < n:if s[i]!=' ':if slow != 0:s[slow] = ' 'slow += 1while i < n and s[i]!=' ':s[slow] = s[i]i += 1slow += 1i+=1return s[:slow]

206 反转链表

学习递归写法，一直没去看这方面！！！

我的代码

写复杂了。

class ListNode:def __init__(self,val=0,next=None):self.val = valself.next = nextclass Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:if head == None or head.next==None:return headslow = headfast = head.nexthead.next = Nonewhile fast != None :temp = fast.nextfast.next = slowslow = fastfast = tempreturn slow

代码随想录的代码

class Solution:def reverseList(self, head: ListNode) -> ListNode:cur = head   pre = Nonewhile cur:temp = cur.next # 保存一下 cur的下一个节点，因为接下来要改变cur->nextcur.next = pre #反 转#更新pre、cur指针pre = curcur = tempreturn pre

递归写法

class Solution:def reverseList(self, head: ListNode) -> ListNode:return self.reverse(head, None)def reverse(self, cur: ListNode, pre: ListNode) -> ListNode:if cur == None:return pretemp = cur.nextcur.next = prereturn self.reverse(temp, cur)

19 删除链表的倒数第 N 个结点

双指针，让fast先走N步。

我的代码

class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:virtual = ListNode(0,head)slow = virtualfast = virtualfor i in range(n):fast = fast.nextwhile fast.next :slow = slow.nextfast = fast.nextslow.next = slow.next.nextreturn virtual.next

面试题0207–链表相交

没啥好说的，先求两个长度，然后让长的先走n1-n2步。

我的代码

class ListNode:def __init__(self,val=0,next=None):self.val = valself.next = nextclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:virtualA = ListNode(0,headA)virtualB = ListNode(0,headB)curA = virtualAcurB = virtualBcountA = countB = 0while virtualA.next:countA = countA + 1virtualA = virtualA.nextwhile virtualB.next:countB = countB + 1virtualB = virtualB.nextif countA >= countB:diff = countA - countBfor i in range(diff):curA = curA.nextwhile curA:if curB==curA:return curAelse:curB = curB.nextcurA = curA.nextelse:return Noneelse:diff = countB - countAfor i in range(diff):curB = curB.nextwhile curA:if curB==curA:return curAelse:curB = curB.nextcurA = curA.nextelse:return None

142 环形链表II

分两步：判断是否有环，fast若和slow相遇，即为有环。判断相遇结点。

我的代码

class Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[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

15 三数之和

重点在去重逻辑的思考，并未掌握。

代码随想录的代码

看了视频后，自己写出来的，注意：最后的else的最后，要移动left和right，不然就会陷入循环。

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums = sorted(nums)res = []n = len(nums)for i in range(n):if nums[i] > 0 :breakif i > 0 and nums[i]==nums[i-1]:  # a去重continueleft = i+1right = n-1while left < right:if nums[i]+nums[left]+nums[right] < 0:left+=1elif nums[i]+nums[left]+nums[right] > 0:right -= 1else :res.append([nums[i],nums[left],nums[right]])while left < right and nums[right] == nums[right-1]:right -= 1while left < right and nums[left] == nums[left+1]:left += 1left+=1right -= 1return res

18 四数之和

重点在去重逻辑的思考，并未掌握。

代码随想录的代码

看了视频后，自己写出来的，掌握了三数之和后，四数之和就比较直观了。

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:nums = sorted(nums)n = len(nums)res = []for k in range(n):if nums[k] > 0 and target > 0 and nums[k] > target :breakif k > 0 and nums[k]==nums[k-1]:continuefor i in range(k+1,n):if nums[k]+nums[i] > 0 and target > 0 and nums[k]+nums[i] > target :breakif i > k+1 and nums[i]==nums[i-1]:continueleft = i+1right = n-1while left < right :if nums[k]+nums[i]+nums[left]+nums[right] < target:left += 1elif nums[k]+nums[i]+nums[left]+nums[right] > target:right -= 1else:res.append([nums[k],nums[i],nums[left],nums[right]])while left < right and nums[left] == nums[left+1]:left += 1while left < right and nums[right] == nums[right-1]:right -= 1left += 1right -=1return res