Day48_1211
专注时间：6H33min，破纪录了，非常好
每日任务：1h=二刷2道力扣hot100(如果是hard，只做一道就好，完成情况及时长：1.5)；【学习资源：PyTorch官方文档：https://docs.pytorch.ac.cn/tutorials/beginner/basics/intro.html】1.5h=PyTorch工程实操(完成情况及时长：40)；1h=周志华机器学习(完成情况及时长：0)；【按照Claude的路线】1h=手撕机器学习算法（完成情况及时长：？？）；计算机网络45分钟（完成情况及时长：？？）
学完机器学习，然后是深度学习、搜广推经典模型（也有很多要手撕的，见Claude生成的）。学完PyTorch，之后是Transformer与大模型架构（见Gemini3pro生成的阶段2）。学快一点，学完还要做搜广推的实战项目。准备一个GitHub Repo把所有手撕过的算法整理进去，这会是最好的复习资料。
必须熟记的API、最简洁的GPT实现、带注释的Transformer实现、推荐系统模型库（包含主流模型实现）还有“Let's build GPT”系列学习视频见Claude的第20页。
学习内容： 如上
总结与心得：算法题花太多时间了，没事，已经克服了（成功做完，完美吸收知识点）继续加油！
《138.随机链表的复制》
这个解法要注意恢复链表的语法逻辑，见第三个while
""" # Definition for a Node. class Node: def __init__(self, x, next=None, random=None): self.val = int(x) self.next = next self.random = random """ class Solution(object): def copyRandomList(self, head): """ :type head: Node :rtype: Node """ #S3: 先创建：A-copyA-B-copyB-null #然后再断开。这样copy next就接上了，但是random该怎么复制呢？根据断开之前的数据结构特性copy的random = cur.random.next。那这样是不是要遍历三趟？还真是 if not head: return head p = head while p: cp = Node(p.val) tmp = p.next p.next = cp cp.next = tmp p = p.next.next p = head while p: if p.random is None: p.next.random = None else: p.next.random = p.random.next p = p.next.next copy_head = head.next p = head while p: cp = p.next p.next = cp.next p = p.next if p: cp.next = p.next return copy_head哈希真是巧妙map{node2copynode}
""" # Definition for a Node. class Node: def __init__(self, x, next=None, random=None): self.val = int(x) self.next = next self.random = random """ class Solution(object): def copyRandomList(self, head): """ :type head: Node :rtype: Node """ #之前的想法是错误的，应当是第一趟存哈希map（仅复制VAL），第二趟再去复制next和random，因为第一趟已经建立了映射，第二趟复制next,random时候就不会出现找不到的情况。核心还是map {原节点，复制节点} if not head: return head node2copy_map = {} p = head while p: node2copy_map[p] = Node(p.val) p = p.next p = head #当遇到两种场景时，代码会报错： #原节点是链表最后一个节点 → p.next = None → node2copy_map[p.next] 等价于 node2copy_map[None]， #但 None 不在哈希表中； #原节点的 random = None → node2copy_map[p.random] 等价于 node2copy_map[None]，同样触发 KeyError。 #而你写的 if node2copy_map[p.next] else None 是先访问 key 再判断，此时已经触发 KeyError，判断逻辑根本没机会执行。 #字典的 dict.get(key, default) 方法是「安全访问」： #若 key 存在，返回对应值； #若 key 不存在，返回 default（这里设为 None） while p: node2copy_map[p].next = node2copy_map[p.next] if p.next else None node2copy_map[p].random = node2copy_map.get(p.random,None) p = p.next return node2copy_map[head]递归要自己去写，边写变想，空想是很难写的，我现在（第二天再写一遍试试）
""" # Definition for a Node. class Node: def __init__(self, x, next=None, random=None): self.val = int(x) self.next = next self.random = random """ class Solution(object): def __init__(self): self.Node2copy_node = {} def copyRandomList(self, head): """ :type head: Node :rtype: Node """ #S1：如果两趟遍历，第一趟不管random，第二趟处理。那么：怎么根据原来节点的random 去找复制节点该指向哪个random? #还需要继续去思考两趟遍历的做法:原链表跳到random，然后按next走直至next = None，这样就定位了random。 #S2：顺序遍历，如果发现该节点的random节点还未被复制，则先复制;*对于其next也是这样* #其实应当想到递归：发现某个节点的next,random不存在，则递归地创建相应的节点 #为什么我没做出来：想到了哈希，但是用错了数据结构，不能用set，否则找不到指向关系。 #应该用map{原链表Node->copy_Node} 而不是原链表之间的映射。因为我们只想知道原链表的某个节点是否已经被复制 #S3：A->Acopy->B->Bcopy->C->Ccopy->null #依旧是感觉逻辑和语句复杂无从下手 #S2怎么递归？？？ #终止条件：空节点 if not head: return None #边界条件：已经复制过 if head in self.Node2copy_node: return self.Node2copy_node[head] copy = Node(head.val) self.Node2copy_node[head] = copy copy.next = self.copyRandomList(head.next) copy.random = self.copyRandomList(head.random) #会一直往深处走，去复制链表。那么最终return copy就实现了“返回复制链表的头结点” return copy3个关于归并排序的题目。3个题都是模版
《912.排序数组》
class Solution(object): def sortArray(self, nums): """ :type nums: List[int] :rtype: List[int] """ def merge_sort(arr): if len(arr)<=1: return arr mid = len(arr)//2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left,right) def merge(left,right): res = [] l = r = 0 while l<len(left) and r<len(right): if left[l]<=right[r]: res.append(left[l]) l+=1 else: res.append(right[r]) r+=1 res+=left[l:] res+=right[r:] return res return merge_sort(nums)《148.排序链表》
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def sortList(self, head): """ :type head: Optional[ListNode] :rtype: Optional[ListNode] """ def merge_sort(head,tail): if not head: return head #这里一定要把head和tail断开 不然会死循环。 if head.next == tail: head.next = None return head #找到链表中点，把这个模版积累下来 slow = fast = head while fast!=tail: slow = slow.next fast = fast.next if fast != tail: fast = fast.next #slow就是中点 mid = slow return merge(merge_sort(head,mid),merge_sort(mid,tail)) def merge(head1,head2): #合并两个有序链表 dummyhead = ListNode(0) res = dummyhead p,q= head1,head2 #一定要记得去移动res指针 while p and q: # '<=' 保证归并排序的稳定性 if p.val <= q.val: res.next = p p = p.next else: res.next = q q = q.next res = res.next if p: res.next = p else: res.next = q return dummyhead.next return merge_sort(head,None)# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def sortList(self, head): """ :type head: Optional[ListNode] :rtype: Optional[ListNode] """ n=[] p=head if not p or not p.next: return p while p: n.append(p.val) p=p.next n.sort() nh=ListNode(n[0]) p=nh for i in range(len(n)-1): p.next=ListNode(n[i+1]) p=p.next return nh
