python代码随想录 冲刺训练营
每天保证至少两小时
day1--9.17
704. 二分查找
解析：
题解：
总结： xxx
27. 移除元素
题解：
class Solution: def removeElement(self, nums: List[int], val: int) -> int: # 移除元素 快慢指针法 slowIndex = 0 for fastIndex in range(0, len(nums)): if nums[fastIndex] != val: nums[slowIndex] = nums[fastIndex] slowIndex += 1 return slowIndex总结：
本题，想到用双指针处理问题，但是所用的指针是头尾指针，相对来说时间复杂度比暴力低一些，而且各项特殊情况不好进行处理。
使用快慢指针，则不会存在特殊数组处理的问题。
此类问题核心在于是数组移动，将需要的值移动，不需要的丢弃。此时通过控制双指针的移动，来剔除特定值。碰到无用的值，slow指针不动，通过后移fast指针，剔除该值。遇到有用的值，再将fast所指向的值赋值给slow指针所指向的位置，此时slow、fast同步后移。以此类推。
"双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法。"
977. 有序数组的平方
解析：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
题解：
class Solution: def sortedSquares(self, nums: List[int]) -> None: for i in range(0, len(nums)): nums[i] *= nums[i] nums.sort() print(nums) # 方法二 双指针 + 反转列表 def sortedSquares(self, nums: List[int]) -> List[int]: res = [] first = 0 last = len(nums) - 1 for i in range(0, len(nums)): if nums[first] * nums[first] >= nums[last] * nums[last]: res.append(nums[first] * nums[first]) first += 1 else: res.append(nums[last] * nums[last]) last -= 1 res.reverse() return res总结：
本题相对好过，进一步优化主要在于时间复杂度上，这里要记住常用算法的时间复杂度：快排是
O(nlgn)双指针的用法：由于nums是有序的，而且nums中存在负数，那么平方后最大的数，应该在nums的两端，而非中间。因此每次取最大的数存入res中，最后将res进行反转即可。
day2---9.18
209. 长度最小的子数组
解析：
题解：
#解法一：暴力双循环，会超时 #解法二：快慢指针，卡哥这边叫做滑动窗口，更形象 class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: sum = 0 res = len(nums) + 1 fastIndex = 0 slowIndes = 0 while fastIndex < len(nums): # 借助连续条件，找到第一个target后，记录res，后移slow，sum减去slow的值，fast继续前移，直到末尾 sum += nums[fastIndex] while sum >= target and slowIndes <= fastIndex: res = min(res, fastIndex - slowIndes + 1) sum -= nums[slowIndes] slowIndes += 1 fastIndex += 1 if res > len(nums): return 0 return res总结
题目阅读：leetcode题干对于子数组的说明进行了隐藏，鼠标移动至标蓝子数组，既有相关说明。本题重要条件即连续。
利用连续条件，不断调整窗口，找到最小的窗口，使其满足窗口内所有元素之和大于或等于target即可。
59. 螺旋矩阵 II
解析
题解：
class Solution: def generateMatrix(self, n: int) -> List[List[int]]: res = [[0] * n for _ in range(n)] count = 1 startRow, startClow = 0, 0 # 控制每一圈起始位置 loop = n // 2 while loop > 0: row = startRow clow = startClow while clow < (n - 1 - startClow): # 左 -> 右 res[row][clow] = count count += 1 clow += 1 while row < (n - 1 - startRow): # 上 -> 下 res[row][clow] = count count += 1 row += 1 while clow > startClow: # 右 -> 左 res[row][clow] = count count += 1 clow -= 1 while row > startRow: res[row][clow] = count count += 1 row -= 1 startRow += 1 startClow += 1 loop -= 1 if (n % 2) != 0: # 奇数，处理中心点 res[startRow][startClow] = count return res总结：
本题考验边界处理能力、中心点处理能力，主要考察模拟解决现实问题的能力。
本题两次碰壁，其一在于每次循环起点的处理上，仅想通过一个变量n来控制，显然是不现实的，的。包括现在用变量n和starRow、starClow控制边界，对于代码可读性，还存在可以改进的空间。这里可以再多设置几个变量，如left、right、top、bottom，使边界更加明确，且代码更容易读懂；其二在于对奇数中心点问题的处理上，特殊问题特殊处理，总想着在while循环中直接完成，这总导致索引超限。
收获：其一，适当的增加变量，替换判断条件的每一次运算，可以增强代码可读性；其二，特殊问题，特殊处理，剥离特殊与一般；其三，写代码之前，务必提前理清思路，针对题解等现实问题，先行根据样例进行模拟，确保代码在编写之前，思路不存在问题。
本题模拟过程如下图
day3---9.24
203. 移除链表元素
题解：
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: """'移除链表中，list.val=val的值，利用虚拟头节点进行处理""" dummyHead = ListNode() dummyHead.next = head prev = dummyHead cur = prev.next while cur is not None: """进行删除""" if cur.val == val: prev.next = cur.next cur = prev.next continue prev = prev.next cur = prev.next return dummyHead.next 总结：
对于链表问题，需要善用虚拟头节点
707. 设计链表
题解：
class LinkNodes: def __init__(self, val=-1, next=None): self.val = val self.next = next class MyLinkedList: def __init__(self): self.dummyHead = LinkNodes() self.size = 0 def get(self, index: int) -> int: """获取链表中下标为index的节点的值""" if index >= self.size: return -1 cur = self.dummyHead.next while index > 0 and cur is not None: cur = cur.next index -= 1 return cur.val def addAtHead(self, val: int) -> None: """插入头节点""" cur = LinkNodes(val, self.dummyHead.next) self.dummyHead.next = cur self.size += 1 def addAtTail(self, val: int) -> None: """尾部插入节点""" cur = self.dummyHead while cur.next is not None: cur = cur.next cur.next = LinkNodes(val, cur.next) self.size += 1 def addAtIndex(self, index: int, val: int) -> None: """插入某个节点之前""" if index > self.size: return if index == self.size: self.addAtTail(val) return cur = self.dummyHead while index > 0 and cur is not None: cur = cur.next index -= 1 new_node = LinkNodes(val, cur.next) cur.next = new_node self.size += 1 def deleteAtIndex(self, index: int) -> None: """删除链表中的某一个节点""" if index >= self.size: return cur = self.dummyHead while index > 0 and cur is not None: cur = cur.next index -= 1 cur.next = cur.next.next self.size -= 1 # Your MyLinkedList object will be instantiated and called as such: # obj = MyLinkedList() # param_1 = obj.get(index) # obj.addAtHead(val) # obj.addAtTail(val) # obj.addAtIndex(index,val) # obj.deleteAtIndex(index)总结：
处理链表题时，一定要想清楚到底是带虚拟头节点，还不不带虚拟头节点，对链表的所有操作要保持一致性，否则会导致编写代码后一团乱麻。
编写测试样例时，若涉及到多功能的函数（如本题），一定要尽量依据题目中函数，这样做一是减少编写代码工作量和重复性工作；二是本身函数中存在联调，单个函数满足要求，不一定能确保多个函数联调时功能执行正常。
206. 反转链表
题解：
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: if head is None: return None res = ListNode() cur = head while cur is not None: tmp = cur cur = cur.next tmp.next = res.next res.next = tmp return res.next 总结：
没什么难度~
反转链表问题转换为头插法，每次遍历一个节点，将该节点插入res的头节点即可完成反转
卡哥使用的双指针法也非常有意思，使用prev和cur两个指针，每次遍历将cur.next指向prev，然后cur借用temp移动至原链表下一个节点，如此往复循环。此方法相较本文更加节省空间。
day4---10.02
24. 两两交换链表中的节点
解析：
题解：
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: """使用递归完成链表节点两两交换""" if head is None or head.next is None: return head prev = head cur = head.next next = head.next.next head = cur cur.next = prev prev.next = self.swapPairs(next) return head class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: """使用迭代法完成链表节点两两交换""" if head is None or head.next is None: return head prev = head cur = prev.next next = cur.next head = cur while prev is not None and cur is not None: cur.next = prev if next is None or next.next is None: prev.next = next return head else: prev.next = next.next prev = next cur = prev.next next = cur.next return head总结：
本题处理起来还不熟练，主要在两点，其一是递归处理，特别返回值这块儿存在问题；其二是问题思考方式，交换prev和cur还是交换cur和next，两种不同的思考方式，代码编写逻辑也不一样，故代码编写前一定要思量好。
除了递归外，迭代也可以做，练习一下。
19. 删除链表的倒数第 N 个结点
解析：
题解：
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: """ 本题我想到两种方法，其一，新建一个链表，正数第len(head) - N 个不接入新链表（递归？）；其二，利用栈，删除倒数第N个 1.链表全部入栈 2.节点弹出，同时n--，当n==1时，不进行记录 3.弹出节点通过头插法建立新链表 4.返回新链表 """ if head is None: return None dummy_head = ListNode() stack = [] while head is not None: stack.append(head) head = head.next cur = dummy_head while len(stack) != 0: if n != 1: """如果n != 1 则直接出栈，并通过头插法构建新链表""" stack[-1].next = cur.next cur.next = stack[-1] stack.pop() else: stack.pop() n -= 1 return dummy_head.next class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: """ 1.fast前进n+1 2.fast、slow一起前进，直至fast=None 3.删除slow.next指向的节点 """ if head is None or n <= 0: return None dummy_head = ListNode(-1, head) slow = dummy_head fast = dummy_head while n >= 0 and fast is not None: fast = fast.next n = n - 1 if n >= 0 and fast is None: # 处理超越链表长度情况 return None while fast is not None: slow = slow.next fast = fast.next slow.next = slow.next.next # 要删除的节点在fast和slow之间 return dummy_head.next总结：
一次AC~
此类题，看到就想到对栈的用法，编写过程中存在问题，
stack=[]这里和C/C++不一样，要记得python中列表是动态类型的，可以存储任何值，如果要注解其类型（类似C/C++中声明变量可以参考如下方式：stack: List[ListNode] = []卡哥这里采用的双指针，较本文更加节省空间和时间，思路同数组中的移除元素，采用快慢指针进行处理。
面试题 02.07. 链表相交
题解：
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def getLinkListLen(self, head: ListNode) -> int: """求链表长度""" if head is None: return 0 cur = head res = 0 while cur is not None: res += 1 cur = cur.next return res def movePoint(self, head:ListNode, count) -> ListNode: if head is None or count == 0: return head cur = head while count > 0 and cur is not None: count -= 1 cur = cur.next return cur def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: """ 思路：先对齐，AB长短不一样，若相交，则AB长度之差则为需要对齐而移动的距离 1.求AB长度，及长度差值d，假设B比A长 2.长的链表（B)，其指针先走d步，对齐AB指针位置 3.AB指针同步移动，若AB指针指向地址一致，即为交点 4.若AB遍历完了，还没有相交，则返回null """ if headA is None or headB is None: return None len_A = self.getLinkListLen(headA) len_B = self.getLinkListLen(headB) curA, curB = headA, headB if len_A > len_B: # 使AB指针离交点距离一样 curA = self.movePoint(curA, len_A - len_B) else: curB = self.movePoint(curB, len_B - len_A) while curA is not None or curB is not None: if curA == curB: return curA curA = curA.next curB = curB.next return None总结：
读题，leetcode输入和给出的函数样式并不完全一致，如本题，leetcode输入有skipA和skipB，但是给出的函数，却无法获取到skipA和skipB，因此读题要仔细，明确题目要求。
此外，本题许多提示都在题目中，仔细阅读也会发现。
142. 环形链表 II
解析：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E6%80%9D%E8%B7%AF
题解：
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: """ 思路1：使用map，但是空间复杂度为O(N) 思路2：双指针，当slow移动一步，fast移动两步，slow和fast一定会在环内相遇 """ if head is None: return None node_map = {} cur = head while cur is not None and cur not in node_map: node_map[cur] = 1 cur = cur.next return cur class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: """ 思路：使用set，但是空间复杂度为O(N) """ if head is None: return None visit = set() cur = head while cur is not None and cur not in visit: visit.add(cur) cur = cur.next return cur总结：
本题最容易想到的就是利用map，一旦发现指针已存入到map中，则找到环入口
难以处理的是双指针，主要是数学推导、理解比较困难，其中最难的点还是fast一定会在环入口处追上slow不好理解。
另外，这里使用set更加贴合实际，且相较于map多开辟一个空间存放没用的value，set则不存在这样的问题
学习set的用法
day5---10.03
242. 有效的字母异位词
解析：
题解
class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) == 0 or len(t) == 0: return False countA = Counter(s) countB = Counter(t) if countA == countB: return True return False总结：
本题考哈希基础，统计每个字母出现的次数，若次数一样，则满足提议。
这里重点学习一下
Counter()
349. 两个数组的交集
解析：
题解：
class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: """ 思路： 1.Counter，记录每个数字出现次数， 2.找出相同的数字 3.返回最终结果 """ if len(nums1) == 0 or len(nums2) == 0: return None count1 = Counter(nums1) count2 = Counter(nums2) res = [] for num,_ in count1.items(): if num in count2: res.append(num) return res class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: return list(set(nums1) & set(nums2))总结：
字典遍历、字典相关操作一定要清楚。如，遍历键值对：
for key,value in dict.items()；遍历键：for key in dict.keys()；遍历值：for key in dict.values()字典元素删除，如：
del count1[2]删除key=2的元素项；count1.clear()：删除count1字典所有元素项；del count1：删除count1字典。字典内置函数：
dict1 == dict2：比较两个字典的元素；len(dict)：计算字典大小；其他如更新操作，这里暂不补充
这里卡哥使用set，相较于counter，set更加节省空间，而且set还可以直接进行交集计算。
关于
set()，刷题时凡是涉及到无序、不重复元素等要求，首先要想到set。其次，本文中set集合使用了&运算符，这里的&运算符是集合的特权运算符，与之相比，还有如下集中运算符：|：求并集；&：求交集；-：差集；^：对称集；<=子集判断；>=：超集判断；<：真子集；>：真超集。因此，处理关系运算，set有天然的优势。set()经典应用场景：去重问题、存在性检查、集合关系问题、
202. 快乐数
解析：
题解：
class Solution: def isHappy(self, n: int) -> bool: """ 注意审题，无限循环，则false """ rec = set() while True: n = self.getSum(n) if n == 1: return True if n in rec: return False else: rec.add(n) def getSum(self, n: int) -> int: """计算n每一位的平方之和""" sum = 0 while n != 0: sum += (n % 10) * (n % 10) n = n // 10 return sum总结：
本题主要是从文中获取有关判定的提示，将数学问题转换为无限循环判定问题，从而引入
set进行解决。本题主要难点，一个在于根据题目提示，转换为
无线循环判定问题；另一个难点在于对数值各位进行求和，这里通过一次%10求个位，通过//10将原先十位将为个位，然后逐步求解。路漫漫其修远兮
1. 两数之和
解析：
题解：
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: """ 两数之和为target，采用map，key=num，value=index；每次遍历，确认map中是否有该值 """ rec = {} for i, num in enumerate(nums): if target - num not in rec: rec[num] = i else: return [i, rec[target - num]] return None总结：
本题没什么好说的，做了第二遍了，主要问题还是在对于返回类型的把控上、字典的操作上，只能多多练习。
day6 --- 10.04
454. 四数相加 II
题解：
class Solution: def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int: """ 思路： 1.四数相加转换为两数相加，与前面有题类似做一个哈希表，key= - (num1[i]+num2[j]), value = count，记录出现次数 然后计算nums3[k] + nums4[l] 的值是否在value里面，是则count++ """ record_dict = defaultdict(int) for first in nums1: for second in nums2: record_dict[-(first + second)] += 1 count = 0 for first in nums3: for second in nums4: if (first + second) in record_dict.keys() and record_dict[(first + second)] > 0: # count += 1 # record_dict[(first + second)] -= 1 count += record_dict[(first + second)] # 此步是重点，没有AC的原因重点在这里 return count总结：
本题做的时候思路基本无误，但是最后计算次数的时候存在问题，这里重点注意
count += record_dict[(first + second)]，因为对于当前的nums3+nums4而言，nums1+nums2有record_dict[(first + second)种匹配模式，原先的写法只能匹配到一种组合方式。本题还需要重点学习
record_dict = defaultdict(int)这种默认字典的命名方式，此外还可以用dict.get(key, 0)方式设置字典value初始值访问的返回值。
383. 赎金信
题解：
class Solution: def canConstruct(self, ransomNote: str, magazine: str) -> bool: """ 思路： 1.对两字符串分别建立字典，key=字符，value=出现次数， 2.遍历ransomNote的字典，若key不在magazine中，或者value大于magazine的value则false """ note_dict = defaultdict(int) magazine_dict = defaultdict(int) for ch in ransomNote: note_dict[ch] = note_dict.get(ch, 0) + 1 for ch in magazine: magazine_dict[ch] = magazine_dict.get(ch, 0) + 1 for key, value in note_dict.items(): if key not in magazine_dict or note_dict[key] > magazine_dict[key]: return False return True总结：
比较简单
此外，卡哥用数组做哈希，因为英文字符仅有26个，因此可以用index来作为每个字母的key，数组上存放的值则为其出现次数。相较于map，这样写更加的节省空间、时间。
15. 三数之和
解析：https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html#%E6%80%9D%E8%B7%AF
题解
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: """ 思路： 卡哥做排序，采用双指针 :param nums: :return: """ nums.sort() result = [] for i in range(len(nums)): left = i + 1 right = len(nums) - 1 if nums[i] > 0: return result if i > 0 and nums[i] == nums[i - 1]: # a去重 continue while left < right: if (nums[i] + nums[left] + nums[right]) == 0: result.append([nums[i], nums[left], nums[right]]) # left += 1 这里的left应该移动到下一个不同的值上面 while left < right and nums[left + 1] == nums[left]: left += 1 while right > left and nums[right - 1] == nums[right]: right -= 1 left += 1 right -= 1 elif (nums[i] + nums[left] + nums[right]) > 0: right -= 1 else: left += 1 return result总结：
本题，a、b、c的去重需要考虑清楚，如果考虑不到位很容易出现重复结果
做本题时，没想到将无序数组进行排序，从而简化编写难度。
对于此类数组求和等运算类题目，首先因考虑是否可以将其先行进行排序，然后进行操作。
18. 四数之和
解析：https://programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html#%E6%80%9D%E8%B7%AF
题解：
# 暴力。。。。超时套餐， # 卡哥用set没超时，我还没研究明白 class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: """ 审题：（1）一个数组nums；（2）找出四个值，其和为target；（3）最终结果需要去重；（4）每组中的每个元素可以重复 思路：索引和值未进行强绑定，先排序; 然后直接暴力哈希，使用set存储[nums[a], nums[b], nums[c], nums[d]] """ nums.sort() result_set = set() for a in range(len(nums)): if a <= len(nums) - 4: b = a + 1 while b <= len(nums) - 3: c = b + 1 while c <= len(nums) - 2: d = c + 1 while d <= (len(nums) - 1) and (nums[a] + nums[b] + nums[c] + nums[d]) <= target: if nums[a] + nums[b] + nums[c] + nums[d] == target: result_set.add((nums[a], nums[b], nums[c], nums[d])) # 列表不可哈希，元组可以 d += 1 c += 1 b += 1 result = [] for res in result_set: result.append(list(res)) return result # 方法，四数之和问题转换未三数之和问题。。。。。 class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: """ 审题：（1）一个数组nums；（2）找出四个值，其和为target；（3）最终结果需要去重；（4）每组中的每个元素可以重复 思路：索引和值未进行强绑定，先排序; 然后转换为三数之和问题，[a, b, c, d] """ nums.sort() size = len(nums) result = [] for i in range(size): if i > 0 and nums[i] == nums[i - 1]: # a去重 continue for j in range(i+1, size - 2): if j > (i + 1) and nums[j] == nums[j - 1]: # b去重 continue left = j + 1 right = size - 1 while left < right: gropu_sum = nums[i] + nums[j] + nums[left] + nums[right] if gropu_sum > target: right -= 1 elif gropu_sum == target: # 记得bc也要去重 result.append([nums[i], nums[j], nums[left], nums[right]]) while left < right and nums[left] == nums[left + 1]: left += 1 while right > left and nums[right] == nums[right - 1]: right -= 1 left += 1 right -= 1 else: left += 1 return result总结：
从本题处理来看，三数之和还没有掌握。另外，对于这类问题，最重要的时去重，每一层的去重都要考虑到。
处理此类问题的核心：排序、去重。排序我们用sort即可，对于去重，可以考虑的方式有哈希
set、数组排序+双指针本题尚未掌握
day7---10.05
344. 反转字符串
解析：
题解：
class Solution: def reverseString(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead. 思路： 1.偷懒直接用python自带的库。。。。 2.双指针 3.新空间+逆序输出 4.栈 """ if len(s) == 0: return first = 0 last = len(s) - 1 while first < last: temp = s[first] s[first] = s[last] s[last] = temp first += 1 last -= 1总结：
这才是easy题！！！
