【每日算法】理论：AIGC模型 刷题：力扣链表操作

上期文章

【每日算法】理论：图像分割相关 刷题：设计链表

---

一、上期问题

• 变形自注意力模块的特别之处
• GroundingDino模型的损失函数是什么
• Dice Loss
• UNet的网络架构
• VQVAE模型相对于VAE的改进
• Deepfloyd-if模型

二、理论问题

1、LAMA Inpaint

LAMA方法主要适用于大范围的inpainting工作。在LAMA Inpaint提出之前，图像修复技术主要受阻于大缺失区域、复杂几何结构和高分辨率图像，主要受阻原因是修复网络和损失函数都缺乏有效的感受野。LaMa方法基于FFC（快速傅立叶卷积）提出了新的图像修复网络，FFC具有覆盖整幅图像的感受野，因此允许网络在 early layers 使用全局上下文，从而实现正确修复大mask。

LAMA Inpaint：大型掩模修复

2、IP adapter模型

IP-Adapter是图像提示适配器，将图像作为prompt来驱动diffusion model。IP-adapter包含编码器和适配器两个部分，将图像特征通过Image Encoder、线性层和LN得到图像特征，文本通过文本编码器得到文本特征，图像特征和文本特征通过解耦交叉注意力的适配模块注入到unet中。在此之前的模型大多是先将图像特征和文本特征进行拼接，然后再通过cross-attention的方式进行相加。而IP-Adapte中的图像和文本分别提供了各自的K、V，Q是unet网络中共享的部分。

IP-Adapter：用于文本到图像扩散模型的文本兼容图像提示适配器

3、Anydoor

AnyDoor就是“任意门”算法，它可以将任意目标传送到指定场景的指定位置，无需微调，被传送的目标会自动对新的场景进行姿态、角度、动作等方面的调整，确保生成图像的多样性以及和谐度。AnyDoor方法的核心思想在于将目标表征成“ID相关”和“细节相关”的特征，然后将他们组合到与背景场景的交互中。对于给定的一张目标图，Anydoor首先通过一个分割模块去除目标物体的背景，然后用ID extractor提取物体的ID特征。与此同时使用高频滤波器提取参考图的高频细节分类，将该高频图拼贴到背景图的指定位置，送入Detail extractor进行细节提取。将提取的ID特征和细节特征注入预训练的文生图大模型以控制最终的生成结果。

AnyDoor任意门：零样本物体级图像定制化

4、vit（Vision Transformer）架构

Vision Transformer将自注意力机制引入计算机视觉领域，通过将图像划分为patch并应用Transformer模型，实现了在图像分类和目标检测等任务上的出色表现。对于给定的一张图片输入，先将图片划分成patch，然后将其转换为序列。序列中的每个patch会通过一个线性投射层得到一个特征，为了确保图片的位置信息得到保留，因此需要加上一个位置编码。将处理后的token输入transformer的encoder当中，将其中的class token经过一个mlp模块得到最终的分类。

【论文精读】VIT：vision transformer论文

5、MAE

MAE是带掩码的自动编码器。将输入图像的patch进行随机屏蔽，并重建丢失的像素。与所有自动编码器一样，MAE方法由编码器和解码器组成。编码器将观察到的信号映射到潜在表示，解码器从潜在表示中重建原始信号。与经典自动编码器的不同之处在于，MAE采用的是非对称设计，编码器作用于可见的patch，轻量级解码器用于用于根据潜在表示和掩码标记重建原始图像。

【论文精读】MAE：Masked Autoencoders Are Scalable Vision Learners 带掩码的自动编码器是可扩展的视觉学习器

6、CLIP模型

CLIP 模型是结合了图像和文本的对比学习，通过训练一个模型，使其能够根据图像和文本之间的相互关系进行推理，实现了图像与文本之间的联合理解和表示学习。在训练模型时，图片通过图像编码器（可以是resnet，也可以是vision transformer）得到一些图像特征，文本通过文本编码器（CBOW或者文本transformer）得到文本特征。对得到的特征进行归一化操作后，计算文本特征和图像特征的相似性。尽量使得正样本的图像和文本特征距离接近，负样本的图像和文本特征距离拉远。在预测时，对于输入的图像，在通过图像编码器之后得到的图像特征可以直接取跟文本特征求相似性，选择相似性最高的句子作为分类结果。

【论文精读】CLIP：Learning Transferable Visual Models From Natural Language Supervision 从自然语言监督中学习可迁移的视觉模型

三、力扣刷题回顾-链表操作

上期涉及题目：

• 707.设计链表

本期题目：

• 203.移除链表元素
• 206.反转链表
• 24. 两两交换链表中的节点
• 19.删除链表的倒数第N个节点

---

203.移除链表元素：

• 给定输入：一个链表的头节点head和一个整数val
• 要求输出：删除链表中所有满足 Node.val == val 的节点，并且返回新的头节点

206.反转链表

• 给定输入：一个单链表的头节点 head
• 要求输出：返回反转后的链表

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

• 给定输入：一个链表
• 要求输出：两两交换其中相邻的节点，并返回交换后链表的头节点
• 注意事项：必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）

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

• 给定输入：一个链表
• 要求输出：删除链表的倒数第 n 个结点，并且返回链表的头结点。

对比分析：
203.移除链表元素和19.删除链表的倒数第N个节点都是删除链表中元素的操作，只不过一道是根据值进行删除，一道是根据节点位置进行删除。为了避免头节点这种特殊情况，可以采用虚拟头节点降低复杂度。206.反转链表和19.删除链表的倒数第N个节点都是对链表中元素进行调换的操作，这两道题都需要设置暂存节点，以防节点释放后找不到。在具体的调换过程中，最好将调换的过程和顺序用图表示出来，不画图，操作多个指针很容易乱。

---

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]:
        while head != None and head.val==val:
            head=head.next
        current=head
        while current and current.next:
            if current.next.val == val:
                current.next=current.next.next
            else:
                current=current.next
        return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

使用虚拟头节点的方法：

# 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]:
        dummy_head=ListNode(0,head)
        current=dummy_head
        while current and current.next:
            if current.next.val == val:
                current.next=current.next.next
            else:
                current=current.next
        return dummy_head.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

206.反转链表

只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表

# 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]:
        cur=head
        prev=None
        while cur:
            temp=cur.next
            cur.next=prev
            prev=cur
            cur=temp
        return prev
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

# 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]:
        cur=head
        prev=None
        while cur:
            temp=cur.next
            cur.next=prev
            prev=cur
            cur=temp
        return prev
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

核心思想：如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

# 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]:
        dummy_head=ListNode(next=head)
        fast=dummy_head
        slow=dummy_head
        while n and fast.next is not None:
            fast=fast.next
            n-=1
        while fast.next is not None:
            fast=fast.next
            slow=slow.next
        slow.next=slow.next.next
        return dummy_head.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

参考：
代码随想录算法训练营第三天|链表理论基础，203.移除链表元素，707.设计链表，206.反转链表
代码随想录算法训练营第四天|24. 两两交换链表中的节点，19.删除链表的倒数第N个节点，面试题 02.07. 链表相交，142.环形链表II，总结