代码随想录算法训练营第二十三天 | 额外题目系列

1365. 有多少小于当前数字的数字

借着本题，学习一下各种排序

未看解答自己编写的青春版

class Solution:def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:temp = sorted(nums)n = len(temp)haxi = [0]*101for i in range(n-1,-1,-1) :haxi[temp[i]] = ires = [0]*ncount = 0for i in nums :res[count] = haxi[i]count += 1return res

重点

排序之后加哈希，一开始加哈希是没想到的，光排序是不够的，在哈希赋值中，利用倒序遍历的小技巧，就可以避免值相同的情况。

代码随想录的代码

class Solution:def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:res = nums[:]hash = dict()res.sort() # 从小到大排序之后，元素下标就是小于当前数字的数字for i, num in enumerate(res):if num  not in hash.keys(): # 遇到了相同的数字，那么不需要更新该 number 的情况hash[num] = i       for i, num in enumerate(nums):res[i] = hash[num]return res

我的代码(当天晚上理解后自己编写)

941.有效的山脉数组

未看解答自己编写的青春版

条件判断大法。

class Solution:def validMountainArray(self, arr: List[int]) -> bool:flag = 0n = len(arr)if n < 3 :return Falsefor i in range(1,n):next_diff = arr[i]-arr[i-1]if flag == 0 :if next_diff > 0 :continueelif next_diff < 0 and i != 1 :flag = 1else :return Falseelse :if next_diff < 0 :continueelse :return Falseif flag == 0 :return Falsereturn True

重点

代码随想录给出了双指针的思路，确实一开始没想到！这种判断序列的整体趋势的，都可以思考双指针法。

代码随想录的代码

class Solution:def validMountainArray(self, arr: List[int]) -> bool:left, right = 0, len(arr)-1while left < len(arr)-1 and arr[left+1] > arr[left]:left += 1while right > 0 and arr[right-1] > arr[right]:right -= 1return left == right and right != 0 and left != len(arr)-1

我的代码(当天晚上理解后自己编写)

1207. 独一无二的出现次数

未看解答自己编写的青春版

class Solution:def uniqueOccurrences(self, arr: List[int]) -> bool:haxi = [0]*2001n = len(arr)for i in range(n):haxi[arr[i]] += 1index = [0]*nfor i in haxi :if i != 0 :if index[i-1] != 0 :return Falseindex[i-1] = 1return True

重点

两次哈希，我的想法和代码随想录的思路一模一样。

代码随想录的代码

# 方法 1: 数组在哈西法的应用
class Solution:def uniqueOccurrences(self, arr: List[int]) -> bool:count = [0] * 2002for i in range(len(arr)):count[arr[i] + 1000] += 1 # 防止负数作为下标freq = [False] * 1002 # 标记相同频率是否重复出现for i in range(2001):if count[i] > 0:if freq[count[i]] == False:freq[count[i]] = Trueelse:return Falsereturn True

# 方法 2： map 在哈西法的应用
class Solution:def uniqueOccurrences(self, arr: List[int]) -> bool:ref = dict()for i in range(len(arr)):ref[arr[i]] = ref.get(arr[i], 0) + 1value_list = sorted(ref.values())for i in range(len(value_list) - 1):if value_list[i + 1] == value_list[i]:return False return True 

我的代码(当天晚上理解后自己编写)

283. 移动零

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]fast += 1slow += 1else :fast += 1for i in range(slow,n):nums[i] = 0

重点

一开始其实没啥思路，没想到用双指针，还是水平太菜。

代码随想录的代码

def moveZeroes(self, nums: List[int]) -> None:slow = 0for fast in range(len(nums)):if nums[fast] != 0:nums[slow] = nums[fast]slow += 1for i in range(slow, len(nums)):nums[i] = 0

交换前后变量，避免补零

def moveZeroes(self, nums: List[int]) -> None:slow, fast = 0, 0while fast < len(nums):if nums[fast] != 0:nums[slow], nums[fast] = nums[fast], nums[slow]slow += 1 # 保持[0, slow)区间是没有0的fast += 1

我的代码(当天晚上理解后自己编写)

189. 轮转数组

未看解答自己编写的青春版

我自己想的额外申请空间版：

class Solution:def rotate(self, nums: List[int], k: int) -> None:"""Do not return anything, modify nums in-place instead."""n = len(nums)k = k % ntemp = nums[n-k:n]if n > k :for i in range(n-k-1,-1,-1):nums[i+k] = nums[i]nums[:k] = temp

重点

这题还是得看代码随想录的解答。
旋转子串我是没想到的，当时左旋转字符串那道题，就没想到，隔了这么久又该复习了。

代码随想录的代码

方法一：局部翻转 + 整体翻转

class Solution:def rotate(self, A: List[int], k: int) -> None:def reverse(i, j):while i < j:A[i], A[j] = A[j], A[i]i += 1j -= 1n = len(A)k %= nreverse(0, n - 1)reverse(0, k - 1)reverse(k, n - 1)

方法二：利用余数
申请copy数组了，而且比我的额外空间还大一些。

class Solution:def rotate(self, nums: List[int], k: int) -> None:copy = nums[:]for i in range(len(nums)):nums[(i + k) % len(nums)] = copy[i]return nums# 备注：这个方法会导致空间复杂度变成 O(n) 因为我们要创建一个 copy 数组。但是不失为一种思路。

我的代码(当天晚上理解后自己编写)

724. 寻找数组的中心下标

class Solution:def pivotIndex(self, nums: List[int]) -> int:total = sum(nums)leftsum = 0index = 0for i in nums :rightsum = total - i - leftsumif rightsum == leftsum :return indexelse :leftsum += iindex += 1return -1

重点

先算总和，再遍历数组，和代码随想录的思路一模一样。

代码随想录的代码

class Solution:def pivotIndex(self, nums: List[int]) -> int:numSum = sum(nums) #数组总和leftSum = 0for i in range(len(nums)):if numSum - leftSum -nums[i] == leftSum: #左右和相等return ileftSum += nums[i]return -1

我的代码(当天晚上理解后自己编写)

34. 在排序数组中查找元素的第一个和最后一个位置

未看解答自己编写的青春版

一开始没思路。想到二分法了，但是觉得二分法，无法处理有相同值的情况。

重点

看了解答，两次二分法啊！先确定左边界，再确定右边界。

看了思路之后，自己写写试试？

没写出来，二分法不会写了，下面是没写完的代码：

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:n = len(nums)minima = nums[0]maxima = nums[-1]if target >= minima and target <= maxima :left_edge = -2left = 0right = n-1while left < right :middle = left + (right-left)//2if target > nums[middle] :left = middleelse :right = middleleft_edge = leftright_edge = -2left = 0right = n-1while left < right :middle = left + (right-left)//2if target < nums[middle] :left = middleelse :right = middleright_edge = rightif else :return [-1,-1]

这个题目暴露了我二分法不会写

代码随想录的代码

本题的其他方法先暂时不看，先搞懂这一种方法。

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:def getRightBorder(nums:List[int], target:int) -> int:left, right = 0, len(nums)-1rightBoder = -2 # 记录一下rightBorder没有被赋值的情况while left <= right:middle = left + (right-left) // 2if nums[middle] > target:right = middle - 1else: # 寻找右边界，nums[middle] == target的时候更新leftleft = middle + 1rightBoder = leftreturn rightBoderdef getLeftBorder(nums:List[int], target:int) -> int:left, right = 0, len(nums)-1 leftBoder = -2 # 记录一下leftBorder没有被赋值的情况while left <= right:middle = left + (right-left) // 2if nums[middle] >= target: #  寻找左边界，nums[middle] == target的时候更新rightright = middle - 1leftBoder = rightelse:left = middle + 1return leftBoderleftBoder = getLeftBorder(nums, target)rightBoder = getRightBorder(nums, target)# 情况一if leftBoder == -2 or rightBoder == -2: return [-1, -1]# 情况三if rightBoder -leftBoder >1: return [leftBoder + 1, rightBoder - 1]# 情况二return [-1, -1]

我的代码(当天晚上理解后自己编写)

目前的欠债：排序学习，二分法学习

922. 按奇偶排序数组 II

未看解答自己编写的青春版

不需要额外存储空间，但是时间只打败5%

class Solution:def sortArrayByParityII(self, nums: List[int]) -> List[int]:n = len(nums)for i in range(n):if nums[i]%2 == 0 and i%2 == 0:continueelif nums[i]%2 == 1 and i%2 == 1:continueelif nums[i]%2 == 0 and i%2 == 1:j = i+1while j < n :if nums[j]%2 == 1 and j%2 == 0 :breakj += 1nums[i],nums[j] = nums[j],nums[i]else :j = i+1while j < n :if nums[j]%2 == 0 and j%2 == 1 :breakj += 1nums[i],nums[j] = nums[j],nums[i]return nums

申请一块额外数组的方法很好写。

重点

三种方法。

发现了我自己写的代码的问题了，我只要对奇数or偶数，操作就可以了，不需要全部操作。我写的代码太复杂了，没有利用好题目的特性。

修改加速版，方法三真牛逼。

class Solution:def sortArrayByParityII(self, nums: List[int]) -> List[int]:n = len(nums)index = 1for i in range(0,n,2):if nums[i] % 2 == 1 :while nums[index] %2 == 1 :index += 2nums[i],nums[index]=nums[index],nums[i]return nums

代码随想录的代码

过。

我的代码(当天晚上理解后自己编写)

35.搜索插入位置

未看解答自己编写的青春版

还行，这是最基础的二分法，写出来了

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:nums.sort()n = len(nums)mini = nums[0]maxi = nums[-1]if target < mini :return 0elif target > maxi :return nleft = 0right = n-1while left <= right :middle = left + (right-left)//2if nums[middle] > target :right = middle-1elif nums[middle] < target :left = middle + 1else :return middle# 这里直接return left就行return max(left,right)

重点

以后大家只要看到面试题里给出的数组是有序数组，都可以想一想是否可以使用二分法。

同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的。

代码随想录的代码

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1while left <= right:middle = (left + right) // 2if nums[middle] < target:left = middle + 1elif nums[middle] > target:right = middle - 1else:return middlereturn right + 1

我的代码(当天晚上理解后自己编写)

24. 两两交换链表中的节点

未看解答自己编写的青春版

这次写，竟然有些磕磕绊绊，不过稍微调了调，还是AC了。

class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:if head==None :return headif head.next == None :return headvirtual = ListNode(0,head)cur = virtualwhile head and head.next :temp = head.next.nextcur.next = head.nexthead.next.next = headhead.next = tempcur = headhead = cur.nextreturn virtual.next

重点

这道题只要画图，逻辑就能明白。

代码随想录的代码

递归版本还是不太好理解的，我感觉。

# 递归版本
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = nextclass Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:if head is None or head.next is None:return head# 待翻转的两个node分别是pre和curpre = headcur = head.nextnext = head.next.nextcur.next = pre  # 交换pre.next = self.swapPairs(next) # 将以next为head的后续链表两两交换return cur

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = nextclass Solution:def swapPairs(self, head: ListNode) -> ListNode:dummy_head = ListNode(next=head)current = dummy_head# 必须有cur的下一个和下下个才能交换，否则说明已经交换结束了while current.next and current.next.next:temp = current.next # 防止节点修改temp1 = current.next.next.nextcurrent.next = current.next.nextcurrent.next.next = temptemp.next = temp1current = current.next.nextreturn dummy_head.next

我的代码(当天晚上理解后自己编写)

234. 回文链表

未看解答自己编写的青春版

失败失败，用链表不行，想错了，只考虑了“1221”的情况，没考虑“12121”的情况。错误代码如下：

class Solution:def isPalindrome(self, head: Optional[ListNode]) -> bool:stack = []while head :if stack == []:stack.append(head.val)else :node = stack[-1]if node == head.val :stack.pop()else :stack.append(head.val)head = head.nextn = len(stack)if n == 0 :return Trueelse :return False

重点

翻转链表的方法细节很多，还是用数组承接是最简单的方法，不做翻转链表可以作为代码练习。

代码随想录的代码

#数组模拟
class Solution:def isPalindrome(self, head: Optional[ListNode]) -> bool:list=[]while head: list.append(head.val)head=head.nextl,r=0, len(list)-1while l<=r: if list[l]!=list[r]:return Falsel+=1r-=1return True   #反转后半部分链表
class Solution:def isPalindrome(self, head: Optional[ListNode]) -> bool:fast = slow = head# find mid point which including (first) mid point into the first half linked listwhile fast and fast.next:fast = fast.next.nextslow = slow.nextnode = None# reverse second half linked listwhile slow:slow.next, slow, node = node, slow.next, slow# 这个翻转链表的代码也太复杂了，太难理解了，还是展开写，感觉翻转操作很好写啊'''while slow:temp = slow.nextslow.next = nodenode = slowslow = temp'''# compare reversed and original half; must maintain reversed linked list is shorter than 1st halfwhile node:if node.val != head.val:return Falsenode = node.nexthead = head.nextreturn True

我的代码(当天晚上理解后自己编写)

143. 重排链表

未看解答自己编写的青春版

没什么思路

重点

主要有三个思路：数组模拟、双向队列模拟、直接分割链表。

把链表放进数组中，然后通过双指针法，一前一后，来遍历数组，构造链表。

把链表放进双向队列，然后通过双向队列一前一后弹出数据，来构造新的链表。这种方法比操作数组容易一些，不用双指针模拟一前一后了。

代码随想录的代码

# 方法二 双向队列
class Solution:def reorderList(self, head: ListNode) -> None:"""Do not return anything, modify head in-place instead."""d = collections.deque()tmp = headwhile tmp.next: # 链表除了首元素全部加入双向队列d.append(tmp.next)tmp = tmp.nexttmp = headwhile len(d): # 一后一前加入链表tmp.next = d.pop()tmp = tmp.nextif len(d):tmp.next = d.popleft()tmp = tmp.nexttmp.next = None # 尾部置空# 方法三 反转链表
class Solution:def reorderList(self, head: ListNode) -> None:if head == None or head.next == None:return Trueslow, fast = head, headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextright = slow.next # 分割右半边slow.next = None # 切断right = self.reverseList(right) #反转右半边left = head# 左半边一定比右半边长, 因此判断右半边即可while right:curLeft = left.nextleft.next = rightleft = curLeftcurRight = right.nextright.next = leftright = curRightdef reverseList(self, head: ListNode) -> ListNode:cur = head   pre = Nonewhile(cur!=None):temp = cur.next # 保存一下cur的下一个节点cur.next = pre # 反转pre = curcur = tempreturn pre

方法三，稍微练了一下

class Solution:def reorderList(self, head: Optional[ListNode]) -> None:"""Do not return anything, modify head in-place instead."""fast = slow = head# find mid point which including (first) mid point into the first half linked listwhile fast and fast.next:fast = fast.next.nextslow = slow.next# 下面两句代码别忘了，一个是取右半边，这样取的右半边一定是短的那一方# 这样连接也符合题目要求right = slow.next # 获取后半天的头slow.next = None # 切断！这句话很重要，不然就成环了node = Nonewhile right:temp = right.nextright.next = nodenode = rightright = temphead2 = nodehead1 = headwhile head1 and head2:temp1 = head1.nexttemp2 = head2.nexthead1.next = head2head2.next = temp1head1 = temp1head2 = temp2

我的代码(当天晚上理解后自己编写)

141. 环形链表

未看解答自己编写的青春版

只判断是否有环，简单

注意判断条件，当循环里需要用到 fast.next.next 时，while 的判断条件要是：while fast and fast.next 。切记切记。

class Solution:def hasCycle(self, head: Optional[ListNode]) -> bool:if head == None :return Falseif head.next == None:return Falseslow = fast = head# 注意判断条件，当循环里需要用到 fast.next.next 时，while 的判断条件要是：# while fast and fast.next 。切记切记。while fast and fast.next :slow = slow.nextfast = fast.next.nextif slow == fast :return Truereturn False

重点

如何找入口？自己画一个图，分成三段，x y z ，则有： 2(x+y) = x + y + z + y ，所以 x = z 。那么从头结点出发一个slow，从相遇节点出发一个fast，两个指针每次都移动一格，相遇节点即为环的入口！

代码随想录的代码

class Solution:def hasCycle(self, head: ListNode) -> bool:if not head: return Falseslow, fast = head, headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif fast == slow:return Truereturn False

我的代码(当天晚上理解后自己编写)

面试题 02.07. 链表相交

未看解答自己编写的青春版

我的这个代码，内存占用很高。

class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:count1 = count2 = 0cur1 = headAcur2 = headBwhile cur1 :count1 += 1cur1 = cur1.nextwhile cur2 :count2 += 1cur2 = cur2.nextif count1 >= count2 :diff = count1 - count2while diff > 0 :headA = headA.nextdiff -= 1while headA :if headA == headB :return headAheadA = headA.nextheadB = headB.nextreturn Noneelse :diff = count2 - count1while diff > 0 :headB = headB.nextdiff -= 1while headA :if headA == headB :return headAheadA = headA.nextheadB = headB.nextreturn None

重点

代码随想录的最冗余版本都比我的简洁！这题一定要学习他的写法。

代码随想录的代码

（版本一）求长度，同时出发class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:lenA, lenB = 0, 0cur = headAwhile cur:         # 求链表A的长度cur = cur.next lenA += 1cur = headB while cur:         # 求链表B的长度cur = cur.next lenB += 1curA, curB = headA, headBif lenA > lenB:     # 让curB为最长链表的头，lenB为其长度curA, curB = curB, curAlenA, lenB = lenB, lenA for _ in range(lenB - lenA):  # 让curA和curB在同一起点上（末尾位置对齐）curB = curB.next while curA:         #  遍历curA 和 curB，遇到相同则直接返回if curA == curB:return curAelse:curA = curA.next curB = curB.nextreturn None 

（版本二）求长度，同时出发 （代码复用）
class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:lenA = self.getLength(headA)lenB = self.getLength(headB)# 通过移动较长的链表，使两链表长度相等if lenA > lenB:headA = self.moveForward(headA, lenA - lenB)else:headB = self.moveForward(headB, lenB - lenA)# 将两个头向前移动，直到它们相交while headA and headB:if headA == headB:return headAheadA = headA.nextheadB = headB.nextreturn Nonedef getLength(self, head: ListNode) -> int:length = 0while head:length += 1head = head.nextreturn lengthdef moveForward(self, head: ListNode, steps: int) -> ListNode:while steps > 0:head = head.nextsteps -= 1return head

（版本三）求长度，同时出发 （代码复用 + 精简）
class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:dis = self.getLength(headA) - self.getLength(headB)# 通过移动较长的链表，使两链表长度相等if dis > 0:headA = self.moveForward(headA, dis)else:headB = self.moveForward(headB, abs(dis))# 将两个头向前移动，直到它们相交while headA and headB:if headA == headB:return headAheadA = headA.nextheadB = headB.nextreturn Nonedef getLength(self, head: ListNode) -> int:length = 0while head:length += 1head = head.nextreturn lengthdef moveForward(self, head: ListNode, steps: int) -> ListNode:while steps > 0:head = head.nextsteps -= 1return head

最后这个方法，理解不了，不知道在干什么。

（版本四）等比例法
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:# 处理边缘情况if not headA or not headB:return None# 在每个链表的头部初始化两个指针pointerA = headApointerB = headB# 遍历两个链表直到指针相交while pointerA != pointerB:# 将指针向前移动一个节点pointerA = pointerA.next if pointerA else headBpointerB = pointerB.next if pointerB else headA# 如果相交，指针将位于交点节点，如果没有交点，值为Nonereturn pointerA

我的代码(当天晚上理解后自己编写)

205. 同构字符串

未看解答自己编写的青春版

自己的思路是错的！

因为题目中没有给出：字符串一定由英文字母组成，所以不能使用哈希！

重点

字符串没有说都是小写字母之类的，所以用数组不合适了，用map来做映射。

使用两个map 保存 s[i] 到 t[j] 和 t[j] 到 s[i] 的映射关系，如果发现对应不上，立刻返回 false

代码随想录的代码

class Solution:def isIsomorphic(self, s: str, t: str) -> bool:default_dict1 = defaultdict(str)default_dict2 = defaultdict(str)if len(s) != len(t): return falsefor i in range(len(s)):if not default_dict1[s[i]]:default_dict1[s[i]] = t[i]if not default_dict2[t[i]]:default_dict2[t[i]] = s[i]if default_dict1[s[i]] != t[i] or default_dict2[t[i]] != s[i]:return Falsereturn True

用Python中最基础的{}作为字典的自己写版本

class Solution:def isIsomorphic(self, s: str, t: str) -> bool:dic1 = {}dic2 = {}n = len(s)m = len(t)if m!=n :return Falsefor i in range(n):if not dic1.get(s[i],0):dic1[s[i]] = t[i]if not dic2.get(t[i],0):dic2[t[i]] = s[i]if dic1[s[i]]!=t[i] or dic2[t[i]]!=s[i]:return Falsereturn True

我的代码(当天晚上理解后自己编写)

1002. 查找共用字符

未看解答自己编写的青春版

这道题在编写能力上要求很高，因为如果是N个字符串，要有N个哈希表。

重点

哈希哈希，看到字符串全部由小学字母组成没有？这么明显的提示，不用哈希用什么？

主要注意的点是，如果两个字符串为 [ ‘ll’ , ‘ll’ ] , 结果应该是: [ ‘l’ , ‘l’ ] , 而不是 [ ‘l’ ] 。

所以要取每个哈希中的最小值。

注意：思路是取三个哈希，不能只取一个计数！（我一开始是这样想的），因为这样会有问题，假如第一个字符串出现两个
‘a’ , 如果只有一个哈希表，会计数为2 ， 和两个字符串中都出现一个 ‘a’ 的结果一样。

代码随想录的代码

看懂了，但应该还没掌握。

class Solution:def commonChars(self, words: List[str]) -> List[str]:if not words: return []result = []hash = [0] * 26 # 用来统计所有字符串里字符出现的最小频率for i, c in enumerate(words[0]):  # 用第一个字符串给hash初始化hash[ord(c) - ord('a')] += 1# 统计除第一个字符串外字符的出现频率for i in range(1, len(words)):hashOtherStr = [0] * 26for j in range(len(words[i])):hashOtherStr[ord(words[i][j]) - ord('a')] += 1# 更新hash，保证hash里统计26个字符在所有字符串里出现的最小次数for k in range(26):hash[k] = min(hash[k], hashOtherStr[k])# 将hash统计的字符次数，转成输出形式for i in range(26):while hash[i] != 0: # 注意这里是while，多个重复的字符result.extend(chr(i + ord('a')))hash[i] -= 1return result

class Solution:def commonChars(self, words: List[str]) -> List[str]:tmp = collections.Counter(words[0])l = []for i in range(1,len(words)):# 使用 & 取交集tmp = tmp & collections.Counter(words[i])# 剩下的就是每个单词都出现的字符（键），个数（值）for j in tmp:v = tmp[j]while(v):l.append(j)v -= 1return l

我的代码(当天晚上理解后自己编写)

925. 长按键入

未看解答自己编写的青春版

class Solution:def isLongPressedName(self, name: str, typed: str) -> bool:n = len(name)m = len(typed)i = j =0while i < n and j < m :if name[i] == typed[j] :i += 1j += 1else :if j == 0 :return Falsewhile j < m and typed[j]==typed[j-1] :j += 1# 这个判断是要加的，不加会报 index 的错误# 笑死了，C++不加就不会报错，python不加就会报错# 不同语言的测试用例还不一样# 不过应该是需要加的我认为if j == m :return False# 移动后要再次匹配，关键if typed[j] != name[i] :return Falseelse :i += 1j += 1# 排除最后一个字符重复的情况，移动jif j < m :while j < m and typed[j]==typed[j-1]:j+=1if i < n or j < m:return Falseelse :return True

重点

代码随想录的代码

代码随想录这题给的代码不好，看我上面自己写的就行，思路和代码随想录的完全一致。

我的代码(当天晚上理解后自己编写)

844. 比较含退格的字符串

未看解答自己编写的青春版

用栈模拟很简单，只要注意，只有当栈非空时，再对栈进行操作就可以避免bug。

重点

这道题要学习使用双指针法的思路。

代码随想录的代码

class Solution:def get_string(self, s: str) -> str :bz = []for i in range(len(s)) :c = s[i]if c != '#' :bz.append(c) # 模拟入栈elif len(bz) > 0: # 栈非空才能弹栈bz.pop() # 模拟弹栈return str(bz)def backspaceCompare(self, s: str, t: str) -> bool:return self.get_string(s) == self.get_string(t)pass

class Solution:def backspaceCompare(self, s: str, t: str) -> bool:s_index, t_index = len(s) - 1, len(t) - 1s_backspace, t_backspace = 0, 0 # 记录s,t的#数量while s_index >= 0 or t_index >= 0: # 使用or，以防长度不一致while s_index >= 0: # 从后向前，消除s的#if s[s_index] == '#':s_index -= 1s_backspace += 1else:if s_backspace > 0:s_index -= 1s_backspace -= 1else:breakwhile t_index >= 0: # 从后向前，消除t的#if t[t_index] == '#':t_index -= 1t_backspace += 1else:if t_backspace > 0:t_index -= 1t_backspace -= 1else:breakif s_index >= 0 and t_index >= 0: # 后半部分#消除完了，接下来比较当前位的值if s[s_index] != t[t_index]:return Falseelif s_index >= 0 or t_index >= 0: # 一个字符串找到了待比较的字符，另一个没有，返回Falsereturn Falses_index -= 1t_index -= 1return True

我的代码(当天晚上理解后自己编写)

129. 求根节点到叶节点数字之和

未看解答自己编写的青春版

挺简单的，但是递归结束条件，一开始写错了。

class Solution:def sumNumbers(self, root: Optional[TreeNode]) -> int:self.res = 0if root == None :return 0if root.left == None and root.right == None :return root.vallevel = [str(root.val)]self.digui(root,level)return self.resdef digui(self,root,level):# 注意这里的递归结束条件，是叶子节点，不是Noneif root.left == None and root.right == None:self.res += int(''.join(level))returnif root.left :level.append(str(root.left.val))self.digui(root.left,level)level.pop()if root.right :level.append(str(root.right.val))self.digui(root.right,level)level.pop()

重点

本题主要注意的就是：递归结束条件，遇到叶子节点则返回。

代码随想录的代码

class Solution:def sumNumbers(self, root: TreeNode) -> int:res = 0path = []def backtrace(root):nonlocal resif not root: return # 节点空则返回path.append(root.val)if not root.left and not root.right: # 遇到了叶子节点res += get_sum(path)if root.left: # 左子树不空backtrace(root.left)if root.right: # 右子树不空backtrace(root.right)path.pop()def get_sum(arr):s = 0for i in range(len(arr)):s = s * 10 + arr[i]return sbacktrace(root)return res

我的代码(当天晚上理解后自己编写)

1382.将二叉搜索树变平衡

未看解答自己编写的青春版

先将二叉搜索树，中序遍历为有序数组，再利用有序数组，构造二叉平衡搜索树

class Solution:def balanceBST(self, root: TreeNode) -> TreeNode:if root == None :return Noneif root.left == None and root.right == None :return rootself.nums = []self.get_num(root)head = self.compute_tree(self.nums)return headdef get_num(self,root):if root == None:returnself.get_num(root.left)self.nums.append(root.val)self.get_num(root.right)def compute_tree(self,nums):if len(nums) == 0:return Nonen = len(nums)middle = n//2value = nums[middle]node = TreeNode(value)left = self.compute_tree(nums[:middle])right = self.compute_tree(nums[middle+1:])node.left = leftnode.right = rightreturn node

重点

代码随想录的代码

class Solution:def balanceBST(self, root: TreeNode) -> TreeNode:res = []# 有序树转成有序数组def traversal(cur: TreeNode):if not cur: returntraversal(cur.left)res.append(cur.val)traversal(cur.right)# 有序数组转成平衡二叉树def getTree(nums: List, left, right):if left > right: return mid = left + (right -left) // 2root = TreeNode(nums[mid])root.left = getTree(nums, left, mid - 1)root.right = getTree(nums, mid + 1, right)return roottraversal(root)return getTree(res, 0, len(res) - 1)

我的代码(当天晚上理解后自己编写)

100. 相同的树

未看解答自己编写的青春版

写是写出来了，但是内存占用过高？

class Solution:def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:if p == None and q == None :return Trueelif p == None and q != None :return Falseelif p != None and q == None :return Falseelse :if p.val != q.val :return Falseleft = self.isSameTree(p.left,q.left)right = self.isSameTree(p.right,q.right)return left and right

重点

本题的迭代法，有坑，要多练

代码随想录的代码

class Solution:def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:if not p and not q: return Trueelif not p or not q: return Falseelif p.val != q.val: return Falsereturn self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

本题的迭代法注意：不能像遍历那里一样，空节点不入栈，这里空节点必须入栈，然后加判断加continue

# 迭代法
class Solution:def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:if not p and not q: return Trueif not p or not q: return Falseque = collections.deque()que.append(p)que.append(q)while que:leftNode = que.popleft()rightNode = que.popleft()# 这句话太关键了，必须加判断空节点和continueif not leftNode and not rightNode: continue if not leftNode or not rightNode or leftNode.val != rightNode.val: return False # 不能像之前的写法一样，空节点不入栈que.append(leftNode.left)que.append(rightNode.left)que.append(leftNode.right)que.append(rightNode.right)return True

我的代码(当天晚上理解后自己编写)

116. 填充每个节点的下一个右侧节点指针

未看解答自己编写的青春版

这道题和之前做过的那道题略有不同，这道题要求只能使用常量级的存储空间，说白了就是明着告诉你：给老子用递归写！不能像之前的题目一样使用层序遍历了。

但是用递归，就没什么思路了，明显就是层序遍历的模板题，怎么用递归？

重点

if (cur->left) cur->left->next = cur->right; // 操作1
if (cur->right) {if (cur->next) cur->right->next = cur->next->left; // 操作2else cur->right->next = NULL;
}

代码随想录的代码

# 递归法
class Solution:def connect(self, root: 'Node') -> 'Node':def traversal(cur: 'Node') -> 'Node':if not cur: return []if cur.left: cur.left.next = cur.right # 操作1if cur.right:if cur.next:cur.right.next = cur.next.left # 操作2else:cur.right.next = Nonetraversal(cur.left) # 左traversal(cur.right) # 右traversal(root)return root

这道题是经典，之前没做过类似的！

我的代码(当天晚上理解后自己编写)

52. N皇后II

未看解答自己编写的青春版

class Solution:def totalNQueens(self, n: int) -> int:if n == 1 :return 1self.res = 0level = []self.backtracking(level,n)return self.resdef backtracking(self,level,n):m = len(level)if m >= n :print(level)self.res += 1returnrow = mfor i in range(n):col = ilevel.append([row,col])# 下面那里，参数要传入 m+1 , 因为level已经加入一个数值了，Debug了好久if self.is_right(level,n,m+1):        self.backtracking(level,n)level.pop()else :level.pop()def is_right(self,level,n,m):for i in range(m):for j in range(i+1,m):if level[i][1]==level[j][1] :return Falseif abs((level[i][1]-level[j][1])/(level[i][0]-level[j][0])) == 1 :return Falsereturn True

重点

同N皇后。

代码随想录的代码

没有Python的代码。

我的代码(当天晚上理解后自己编写)

649. Dota2 参议院

未看解答自己编写的青春版

没写出来，这道题还是很有难度的。

重点

没想到用一个循环来控制轮数。

这道题真的很妙

代码随想录的代码

class Solution:def predictPartyVictory(self, senate: str) -> str:# R = true表示本轮循环结束后，字符串里依然有R。D同理R , D = True, True# 当flag大于0时，R在D前出现，R可以消灭D。当flag小于0时，D在R前出现，D可以消灭Rflag = 0senate = list(senate)while R and D: # 一旦R或者D为false，就结束循环，说明本轮结束后只剩下R或者D了R = FalseD = Falsefor i in range(len(senate)) :if senate[i] == 'R' :if flag < 0: senate[i] = '0' # 消灭R，R此时为falseelse: R = True # 如果没被消灭，本轮循环结束有Rflag += 1if senate[i] == 'D':if flag > 0: senate[i] = '0'else: D = Trueflag -= 1# 循环结束之后，R和D只能有一个为truereturn "Radiant" if R else "Dire"

我的代码(当天晚上理解后自己编写)

1221. 分割平衡字符串

未看解答自己编写的青春版

class Solution:def balancedStringSplit(self, s: str) -> int:res = 0s = list(s)n = len(s)i = 0count = 0while i < n :if s[i] == 'R':count += 1else :count -= 1if count == 0 :res += 1i += 1return res

重点

贪心就好，这道题一开始被示例迷惑了，都是对称的字符串，但是一般情况是，不对称的字符串，比如 “RRLRLL”

代码随想录的代码

class Solution:def balancedStringSplit(self, s: str) -> int:diff = 0 #右左差值ans = 0for c in s:if c == "L":diff -= 1else:diff += 1if diff == 0:ans += 1return ans

我的代码(当天晚上理解后自己编写)

5. 最长回文子串

这种题到现在还是不会写，看着答案写一写

class Solution:def longestPalindrome(self, s: str) -> str:n = len(s)if n <= 1 :return sdp = [[False]*n for _ in range(n)]maxd = 0left = 0right = 0for i in range(n-1,-1,-1):# 注意这里 j 的取值范围，是从i开始的，包括i，因为dp[i][j]定义的是[i,j]闭区间# 所以 i=j 是可行的，也是必须要考虑的for j in range(i,n):if s[j]==s[i]:if j-i <= 1 :dp[i][j]=True# 一定注意这里是 elif 而不是 if , if 会出现数组越界elif dp[i+1][j-1] == True :dp[i][j]=Trueif dp[i][j] and j-i+1 > maxd :maxd = j-i+1left = iright = jreturn s[left:right+1]

class Solution:def longestPalindrome(self, s: str) -> str:n = len(s)if n <= 1 :return sstart = 0end = 0for i in range(n):left,right = self.find_point(i,i,s)start,end = self.compare(end,start,right,left)left,right = self.find_point(i,i+1,s)# 注意这里，第二次比较，其实这次比较的，已经是前面，以单字符为中心的最大结果了# 即是上一次的 left 和 right 结果，和这次的 left right 进行比较start,end = self.compare(end,start,right,left)return s[start:end]def find_point(self,i,j,s):while i >= 0 and j < len(s) and s[i]==s[j] :i -= 1j += 1return i+1,jdef compare(self,a,b,c,d):if a-b > c-d :return b,aelse :return d,c

重点

对于回文子串的题，要学会这种动态规划的写法，dp[i][j]，代表 [ i , j ] 的子串，是否为回文串。这里一定要注意，这里有一个循环不变量，关系着代码的编写，注意这里是，左闭右闭区间！

注意处理三种情况，数值相等，那么下标相等或者相邻，都是回文；数值相等，如果里面也是回文，则是回文。

一定要注意，第三种情况，和前两种情况的关系，一定是 elif ，而不是 if , if 会出现数组越界。

本题的双指针法也值得学习

代码随想录的代码

class Solution:def longestPalindrome(self, s: str) -> str:dp = [[False] * len(s) for _ in range(len(s))]maxlenth = 0left = 0right = 0for i in range(len(s) - 1, -1, -1):for j in range(i, len(s)):if s[j] == s[i]:if j - i <= 1 or dp[i + 1][j - 1]:dp[i][j] = Trueif dp[i][j] and j - i + 1 > maxlenth:maxlenth = j - i + 1left = iright = jreturn s[left:right + 1]

class Solution:def longestPalindrome(self, s: str) -> str:def find_point(i, j, s):while i >= 0 and j < len(s) and s[i] == s[j]:i -= 1j += 1return i + 1, jdef compare(start, end, left, right):if right - left > end - start:return left, rightelse:return start, endstart = 0end = 0for i in range(len(s)):left, right = find_point(i, i, s)start, end = compare(start, end, left, right)left, right = find_point(i, i + 1, s)start, end = compare(start, end, left, right)return s[start:end]

我的代码(当天晚上理解后自己编写)

132. 分割回文串 II

自己看着解答写的不优秀代码

class Solution:def minCut(self, s: str) -> int:n = len(s)if n <= 1 :return 0dp = [[False]*n for _ in range(n)]for i in range(n-1,-1,-1):for j in range(i,n):if s[i]==s[j]:if j-i <= 1:dp[i][j]=Trueelif dp[i+1][j-1]==True:dp[i][j]=TrueDP = [inf]*nDP[0]=0for i in range(1,n):# 这里的if在我这里，应该是不能去掉的# 这里我是根据debug才发现的，解答里也是这么写的，要先进行一个判断，不然DP[i]最小就是 1 了。if dp[0][i] == True :DP[i] = 0else :       # 这里的下标也有一些混乱，我一直想着，dp的含义是[i,j]# DP的含义是[0,j]是回文串的最小分割# 始终明确数组的区间是否是闭的for j in range(i):if dp[j+1][i] == True :DP[i] = min(DP[i],DP[j]+1)return DP[n-1]

重点

本题的重点主要有两个：DP数组的含义，dp[i] : 范围是 [ 0 , i ] 的回文子串，最小分割次数是 dp[i] 。递推公式的话，就是去遍历每一个当前index前面的值，如果 [ i , j ] 是回文串，就是 dp[j] = dp[i] + 1。

那么怎么知道 [ i , j ] 是不是回文串呢 ？ 其实就是前一题的代码，一模一样，先用前一题的DP方法，把记录所有子串的回文情况的DP数组，先计算出来。

代码随想录的代码

要学习代码的细节！

class Solution:def minCut(self, s: str) -> int:isPalindromic=[[False]*len(s) for _ in range(len(s))]for i in range(len(s)-1,-1,-1):for j in range(i,len(s)):if s[i]!=s[j]:isPalindromic[i][j] = Falseelif  j-i<=1 or isPalindromic[i+1][j-1]:isPalindromic[i][j] = True# print(isPalindromic)dp=[sys.maxsize]*len(s)dp[0]=0for i in range(1,len(s)):if isPalindromic[0][i]:dp[i]=0continuefor j in range(0,i):if isPalindromic[j+1][i]==True:dp[i]=min(dp[i], dp[j]+1)return dp[-1]

我的代码(当天晚上理解后自己编写)

673. 最长递增子序列的个数

未看解答自己编写的青春版

不会。

这题记录一下吧，没心情看了，思路还没看懂，本题也很重要

重点

本题是第一次接触，同时维护两个数组的动态规划的题目。

代码随想录的代码

class Solution:def findNumberOfLIS(self, nums: List[int]) -> int:size = len(nums)if size<= 1: return sizedp = [1 for i in range(size)]count = [1 for i in range(size)]maxCount = 0for i in range(1, size):for j in range(i):if nums[i] > nums[j]:if dp[j] + 1 > dp[i] :dp[i] = dp[j] + 1count[i] = count[j]elif dp[j] + 1 == dp[i] :count[i] += count[j]if dp[i] > maxCount:maxCount = dp[i];result = 0for i in range(size):if maxCount == dp[i]:result += count[i]return result;

我的代码(当天晚上理解后自己编写)

657. 机器人能否返回原点

未看解答自己编写的青春版

重点

用坐标模拟就好。

代码随想录的代码

# 时间复杂度：O(n)
# 空间复杂度：O(1)
class Solution:def judgeCircle(self, moves: str) -> bool:x = 0 # 记录当前位置y = 0for i in range(len(moves)):if (moves[i] == 'U'):y += 1if (moves[i] == 'D'):y -= 1if (moves[i] == 'L'):x += 1if (moves[i] == 'R'):x -= 1return x == 0 and y == 0

我的代码(当天晚上理解后自己编写)

剩下的几道题都很难，都是没接触过的题，后面再单开一个文章记录。