Fork me on GitHub
image frame

EightyNinth

Transfer Learning of Graph Neural Networks with Ego-graph Information Maximization

文献阅读

论文地址: 2009.05204.pdf

代码地址: EGI

摘要

  1. GNN效果良好, 但针对大规模图的训练消耗良多.

  2. 在近年进行GNN预训练的研究中, 一是没有提供模型设计的理论支撑, 二是没有清楚地提出模型可转移性的要求和保证.

  3. 本文观点: 首先, 对基本图信息提出一个新的观点, 主张捕获基本图信息作为迁移GNN训练的目标. 这启发了EGI的设计, 使用EGI实现此目标.
    其次, 当节点特征与结构相关时, 对目标图和源图局部拉普拉斯的不同进行EGI可转移性分析.

介绍

此次工作为迁移学习GNN构建了一个有理论支撑的框架, 并具现化为一个可实际应用的迁移学习GNN模型.

下图为模型的概览, 其基于一个新的视角: 把图视作节点特征和k阶ego-图结构的联合分布采样.
这样的观点使得我们可以通过定义图的信息和相似度来分析图的可迁移性.

(图1: 图迁移学习框架图)

我们所设计的模型称作EGI.其利用基于ego-图信息最大化的训练目标来有效捕获图信息.

然后我们进一步具体说明了对可迁移节点特征的要求，并分析了依赖于源图和目标图的本地图拉普拉斯算子的 EGI 的可迁移性.

迁移GNN

在图迁移学习设置中, 预训练过程是无法得知下游任务的.我们认为应该优化和量化GNN的一般效用(general utility).
而他捕获基础图信息的能力与图的拓扑结构和节点特征有关.

基于上述观点, 我们设计了ego-图信息最大化模型( ego-graph information maximization model, EGI).
然后通过其对目标图和源图建模能力的差距来衡量GNN模型的一般迁移性.

EGI

此项工作关注于在原图上进行无监督预训练过后的GNN, 在直接迁移设置下, 不经过微调, 直接应用于目标图上.

含 义 公 式
源图 $ G_{a} $
目标图 $ G_{b} $
节点特征 $ X $
节点集 $ V $
边集 $ E $
图 $ G = \lbrace V, E \rbrace $

直觉上来说, 只有在源图$ G_{a} $和目标图$ G_{b} $的特征和结构在某些方面相似时, 迁移学习才会成功.
因此, 在图$ G_{a} $上进行学习的GNN图滤波( graph filters)能够兼容$ G_{b} $的特征和结构.

我们提出了一个新的观点: 图可以视为节点特征和k阶ego-图结构的联合分布采样.
由于这样操作本质是对k阶ego图采样进行编码, 可以帮助我们在迁移学习下对图的结构信息进行具体定义.
这样有利于图之间的相似/不相似性度量.

我们设计了EGI, 此网络通过互信息最大化用以代替k阶图的恢复.

k阶ego图: 对于节点$ v_{i} $, 只要它具有k层质心扩展, 使得$ v_{i} $到ego图中的人任何节点的最好距离是k ($ \forall v_{i} \in V(g_{i}), |distance(v_{i}, v_{j})| \leq k $), 它的k阶ego图定义为$g_{i} = \lbrace V(g_{i}), E(g_{i}) \rbrace $.

在此次工作中, 我们使用k阶有向图, 其方向由是否到中心节点的输入边还是输出边决定. 当然, 其结果同样适用于无向图.

结构信息: $ \mathcal{G} $是拓扑空间的子图, $ G $ 视作按照概率$ \mu $从$ \mathcal{G} $采样的独立同分布的k阶ego图$ \lbrace g_{i} \rbrace_{i=1}^{n} $. 从而$ G $的结构信息定义为k阶ego图集合$ \lbrace g_{i} \rbrace_{i=1}^{n} $和经验分布.

如图1所示, $ G_{0} $, $ G_{1} $, $ G_{2} $通过1阶ego图的集合和经验分布进行区分, 这使得我们能够衡量图之间的结构相似性.

ego图信息最大化

(图2: EGI框架图)

给定从经验联合分布$ (g_{i}, x_{i}) \backsim \mathbb{P} $采样的ego图集合$ \lbrace (g_{i}, x_{i}) \rbrace_{i} $.
GNN编码器$ \Psi $的训练目标为最大化定义为结构信息的k阶ego图$ g_{i} $和节点嵌入$ z_{i} = \Psi(g_{i}, x_{i}) $的互信息$ MI(g_{i}, \Psi(g_{i}, x_{i}))$.
为了最大化互信息$ MI $, 引入判别器$ \mathcal{D}(g_{i}, z_{i}): E(g_{i}) \times z_{i} \rightarrow \mathbb{R}^{+} $来计算边$ e $属于ego图$ g_{i} $的概率.
EGI模型损失函数使用JS散度:

$$ \mathcal{L}_{EGI} = -MI^{(JSD)}( \mathcal{G}, \Psi ) = \frac{1}{N} \sum_{i=1}^{N} [sp( \mathcal{D}(g_i, z_{i}^{‘})) + sp(-\mathcal{D}(g_i, z_{i}))] \tag{1} \label{eq:one} $$

其中, $ sp(x) = \log(1 + e^{x}) $ 是softplus function(一种激活函数), $ (g_{i}, z_{i}^{‘}) $是从边缘分布的乘积中随机抽取的, 即$ z_{i}^{‘} = \Psi (g_{i^{‘}}, x_{i^{‘}}), (g_{i^{‘}}, x_{i^{‘}}) \backsim \mathbb{P}, i^{‘} \neq i $.

在$ 式 \eqref{eq:one} $中, 对边是否属于k阶ego图$ E(g_i) $进行计算的判别器$ \mathcal{D} $依赖于节点顺序.
以固定的图顺序来描述判别器$ \mathcal{D} $的决策过程.具体来说, $ E(g_i) $的顺序是广度优先遍历(BFS-ordering) $ \pi $.

$ \mathcal{D} = f \circ \Phi $, 通过另一个GNN编码器$ \Phi $和对边序列$ E^{\pi}: \lbrace e_1 , e_2 , \cdots , e_n \rbrace $在有向图层面是否属于k阶ego图进行预测的得分函数$ f $ 输出的准确度得到的召回率进行相乘.

根/ 中心节点编码器$ \Psi $输入$ (g_i, x_i) $, 在判别器$ \mathcal{D} $中对邻域节点处理的编码器$ \phi $输入$ (\tilde{g_i}, x_i) $：

$$ \Psi(g_i , x_i ) = GNN_{\Psi} (A_i, X_i ), \Phi (\tilde{g_i}, x_i ) = GNN_{\Phi} (A_{i}^{‘}, X_i) $$

$ A_i, A_{i}^{‘} $是$ g_i, \tilde{g_i} $包括自向边的邻接矩阵.同时$ A_i = A_{i}^{‘T}$.自向边的存在使得GNN可以关注到根节点自身的影响.

$ \Psi $ 的输出为$ z_i \in \mathbb{R}^n $ 是根节点的节点嵌入, $ \Phi $ 的输出$ K \in \mathbb{R}^{|g_i| \times n} $ 为ego图邻域节点的表示.

得到$ H $ 后, 就可以计算得分函数$ f $: 对于每个在边序列的节点对$ (p, q) \in E^{\pi} $, $ h_p $是从$ \Phi $得到的源节点表示, $ x_q $是目标节点特征.

$$ f(h_p, x_q, z_i) = \sigma (U^T \cdot \tau (W^T [h_p || x_q || z_i])) \tag{2} \label{eq:two}$$

$ \sigma $ 和 $ \tau $ 是Sigmoid和ReLU激活函数.

然后, 判别器$ \mathcal{D} $用以区分$ g_i $中边的正负对:正对-$ ((p, q), z_i) $,负对-$ ((p, q), z_{i}^{‘}) $:

$$ \mathcal{D} (g_i, z_i) = \sum_{(p,q) \in E^{\pi}} \log f(h_p, x_q, z_i), \mathcal{D} (g_i, z_{i}^{‘}) = \sum_{(p,q)}^{E^{\pi}} \log f(h_p, x_q, z_{i}^{‘}) \tag{3} \label{eq:three} $$

在节点序列中, 我们考虑了两种边$ (p, q) $, 第一种: 边连接了对于根节点来说跨阶的节点; 第二种: 边连接了对于根节点来说同阶的节点.

前述提及了节点对的广度优先遍历(BFS-ordering), 而在$ 式 \eqref{eq:three} $中, 对第一种边的序列变化很敏感, 对第二种不敏感.

基于上述事实, 由于k层GNN的输出仅取决于编码器$ \Psi $和$ \Phi $的k阶ego图, 因此可以通过对$ g_i $的批量采样来并行训练EGI.

EGI 的使用场合

EGI 的使用场合为直接迁移, 即目标领域标签未知, 其可迁移性是通过没有进行微调的模型性能差异来衡量的.

基于局部图的拉普拉斯可迁移性分析

此次工作主要为基于源图$ G_a $和目标图$ G_b $之间相似性的GNN的可迁移性.

我们认为GNN的输出由三部分构成: 输入的节点特征, 固定的图拉普拉斯, 学习到的图过滤器.
GNN的效用由这三者决定.
为了实现这种兼容性，我们要求节点特征与结构有关.

结构相关节点特征: $g_i$表示有序的中间结点为$ v_i $的ego图, 其节点特征为$ \lbrace x_{p,q}^{i} \rbrace_{p=0,q=1}^{k,|V_p(g_i)|} $, 其中$ V_p(g_i) $是$ g_i $的k阶节点集合. 只有对于任意属于ego图的节点$ v_q \in V_p(g_i) $有$ x_{p,q}^{i} = [f(g_i)]_{p,q} \in \mathbb{R}^d $, 其中$ f: \mathcal{G} \rightarrow \mathbb{R}^{d \times |V(g_i)|} $, 这样的节点特征才可称为结构相关.

结构相关节点特征要求节点特征是图结构的函数.
这样的节点对图结构的变化很敏感, 同时在理想的情况下, 节点特征对图结构是内射的(映射不同的图到不同的特征).
这样, 当一个迁移GNN学习到的图过滤器兼容$ G $的结构时, 同样能够兼容$ G $的节点特征.

GNN可迁移性: 源图$ G_a = \lbrace (g_, x_i) \rbrace_{i=1}^{n} $和目标图$ G_b = \lbrace (g_{i’}, x_{i’}) \rbrace_{i’=1}^{m} $以及假设与结构相关的节点特征, k层GCN $ \Psi_{\theta} $, 一阶多项式$ \phi $
在以上对$ G_a $和$ G_b $的局部谱域合理的假设下, $ \Psi_{\theta} $的经验性能差异通过$ \mathcal{L}_{EGI} $评估, 满足:

$$ | \mathcal{L}_{EGI} (G_{a}) - \mathcal{L}_{EGI} (G_{b})| \leq \mathcal{O}( \Delta_{ \mathcal{D}} (G_{a}, G_{b}) + C) \tag{4} \label{eq:four} $$

论文原文, RHS表示公式右侧

其中, $ C $只依赖于图编码器和节点特征.

$ \Delta_{ \mathcal{D}}(G_a ,G_b) $衡量源图和目标图结构区别的方式:

$$ \Delta_{\mathcal{D}}(G_a, G_b) = \tilde{C} \frac{1}{nm} \sum_{n}^{i=1} \sum_{m}^{i^{‘}=1} \lambda_{max} (\tilde{L}_{g_i} - \tilde{L}_{g_{i^{‘}}}) \tag{5} \label{eq:five} $$

其中, $ \lambda_{max} (A) : \lambda_{max}(A^T A)^(1/2) $, $ \tilde{L}_{g_i} $通过入度表示$\tilde{g}_i$的归一化图拉普拉斯, $ \tilde{C}$ 一直依赖于 $ \lambda_{max}( \tilde{L}_{g_i}) $ 和 $\mathcal{D}$.

GNN可迁移性的分析自然举例了我们对于结构相似性和GNN可迁移性之间对应关系的理解.
这使得我们可以告知EGI怎样把在源图上训练好的GNN仅仅通过衡量源图和目标图之间的局部拉普拉斯差异, 而不需要任何微调, 就可以在目标图上很好地工作.

实验

直接迁移的图编码器为GIN,
存在微调迁移的图编码器为GCN,
自监督GNN为GVAE, DGI,
互信息衡量方法为GMI, MVC,
对于预训练GNN, 有MaskGNN和ContextGNN,
此外, 对比方法还有Structural Pre-train.

(图3: 实验图)

github + hexo 简单搭建 github.io 网站

网站

系统配置

这里先说一下我的系统配置以供参考

Ubuntu 20.04 5.13.0-51-generic x86_64

本地前置要求

  • node.js >= 10.13

  • Git

  • hexo

node.js

按照 官方安装方式 , Ubuntu 采用安装命令行, 这里安装的版本是18.4.0.

1
2
curl -fsSL https://deb.nodesource.com/setup_18.x | sudo -E bash -
sudo apt-get install -y nodejs

进行测试

1
npm --version

出现版本号, 即为安装成功.

Git

Ubuntu 安装命令

1
sudo apt-get install git

hexo

创建一个空文件夹作为 hexo 安装路径的同时也会是网站根目录.

为了后述具体,此时假设新建的目录路径为: /example

github前置要求

  • github账号

    为了后述具体,此时假设github账号

    用户名为: test

    邮箱为: test@163.com

    密码为: 123456

  • ssh密匙

新建网站远程仓库

  1. New Repository, 命名为

    1
    test.github.io

  2. 打开 test.github.io , 在与 code 同级的 Settings下打开与 General 同级的 Pages. 在Theme Chooser 下选择Choose a theme.

  3. 选择好主题后, 把新弹出的界面拉到底部, 选择commit changes, 网站就可以访问了.

  4. 输入 test.github.io 访问.

设置ssh密匙

为了hexo能够顺利push到我们的仓库, 需要在本地电脑设置ssh密匙

  1. 检查本机是否有ssh密匙

    1
    cd ~/.ssh #检查本机已存在的ssh密钥

    如果存在 No such file or directory, 说明你是第一次使用git, 需要创建ssh.


    或者

    1
    2
    cd ~/.ssh #检查本机已存在的ssh密钥
    ls

    没有任何输出, 需要创建ssh.


    若有ssh密匙, 直接跳转至第 3 步.

  2. 创建ssh密匙

    1
    ssh-keygen -t rsa -C test@163.com

    然后连续3次回车, 最终会生成一个文件在 ~ 下.

  3. 打开 ~ , 找到 .ssh\id_rsa.pub 文件.

    注: 如果打开 ~ ,没有 .ssh 文件夹, 需要 Ctrl + H 显示隐藏文件夹.

    使用记事本一类的程序打开, 复制所有内容.

  4. 打开 github , 点击右上角个人头像, 在弹出的窗口中选择 Settings.
    然后选择与Public profile 同级 Access 下的
    SHH and GPG keys.

  5. 选择 New SSH key .

    title: 随便填

    Key: 粘贴从 .ssh\id_rsa.pub 文件复制的内容

    Add SSH key .

  6. 测试

    1
    ssh -T git@github.com # 注意邮箱地址不用改

    如果提示Are you sure you want to continue connecting (yes/no)?，输入yes, 然后会看到:

    Hi test! You’ve successfully authenticated, but GitHub does not provide shell access.

    看到这个信息说明SSH已配置成功!

Git本地配置：

打开命令行, 输入

1
2
git config --global user.name "test"            // 你的github用户名，非昵称
git config --global user.email  "test@163.com"  // 填写你的github注册邮箱

网站搭建

初始化

在 /example 目录下, 打开命令行, 输入

1
2
sudo npm install -g hexo-cli
hexo init

加载主题

在Hexo官网选择喜欢的主题, 这里以Ayer 主题为例, 输入

1
npm i hexo-theme-ayer -S

主题设置

  1. 主题使用


    将 /example 目录下的 _config.yml 里的 theme 值修改成 ayer

    1
    theme: ayer

  2. 必要插件


    在 /example 目录下, 打开命令行, 输入


    1
    npm install hexo-generator-searchdb --save
    1
    npm install hexo-generator-feed --save

    打开/example 目录下的 _config.yml, 输入


    1
    2
    3
    4
    5
    # hexo-generator-searchdb
    search:
    path: search.xml
    field: post
    format: html
    1
    2
    3
    4
    5
    6
    7
    8
    9
    feed:
    type: atom
    path: atom.xml
    limit: 20
    hub:
    content:
    content_limit: 140
    content_limit_delim: " "
    order_by: -date

  3. 可选插件


    在 /example 目录下, 打开命令行, 输入


    1
    npm install hexo-generator-index-pin-top --save
    1
    2
    npm install --save hexo-helper-live2d
    npm install npm install --save live2d-widget-model-xxx  # xxx为你选择的模型

    打开/example 目录下的 _config.yml, 输入


    1
    2
    3
    4
    5
    # 已存在
    index_generator:
    path: ''
    per_page: 10
    order_by: -date
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    live2d:
    enable: true
    scriptFrom: local
    pluginRootPath: live2dw/
    pluginJsPath: lib/
    pluginModelPath: assets/
    tagMode: false
    debug: false
    model:
      use: live2d-widget-model-wanko  # 选择模型
    display:
      position: right
      width: 150
      height: 300
    mobile:
      show: true
    react:
      opacity: 0.7

    更多插件查看 hexo 插件市场.

  4. 菜单处理


    Ayer 初始情况下, 菜单的分类(categories), 标签(tags), 旅行(tags/旅行), 友链(friends), 关于我(2019/about), 点击全部显示 error, 需要初始化.

    模板, 对 XX(path) 的初始化:


    a. 在 /example 目录下, 打开命令行, 输入

    1
    hexo new page XX

    b. 打开 /example/source/XX, 复制 index.md 到 /example/source/path, 删除 /example/source/XX 目录.


    c. 打开 index.md, 全部替换输入

    1
    2
    3
    4
    5
    ---
    title: XX
    type: "XX"
    layout: "XX"
    ---

  5. 本地测试


    在完成上述操作后网站模板搭建完毕, 可以在本地查看网站效果.


    在 /example 目录下, 打开命令行, 输入

    1
    2
    3
    4
    # hexo 网站生成命令
    hexo g
    # hexo 网站本地部署命令
    hexo s -p 8008

    打开 http://localhost:8008/ 即可查看部署效果.

  6. 部署处理


    在push网站到git之前, 要在/example 目录下的 _config.yml, 输入

    1
    2
    3
    4
    deploy:
    type: git
    repository: git@github.com:test/test.github.io.git
    branch: master

    在 /example 目录下, 打开命令行, 输入下述命令部署到云端.


    1
    2
    3
    4
    # hexo 网站生成命令
    hexo g
    # hexo 网站云端部署命令
    hexo d

    打开 https://test.github.io/ 即可查看部署效果.

新增页面

文章页面的新增和菜单的处理不同.

  1. 在 /example/source/_posts 目录下, 新建md文件.

  2. md写入:

    1
    2
    3
    4
    5
    6
    7
    ---
    title: 文章名
    date: 2022-07-02 21:22:45       # 时间
    tags: [网站, hexo, github]      # 标签, 可以填入多个
    categories: [网站]              # 只能填入一个
    ---
    正文

以上, 网站搭建完成.

实现Mask RCNN Pytorch版本

语义分割

整体架构

本次实现的Mask RCNN主要分为以下几个部分：

  • backbone

  • RPN

backbone

首先原文提出了四种backbone：

  • resnet50
  • resnet50 + FPN
  • resnet101
  • resnet101 + FPN

本次基于resnet101 + FPN实现

resnet101[1]

就是基础的resnet模型, 可借用torchvision实现

(resnet模型图)

特征金字塔(FPN)[2]

FPN, 又称特征金字塔, 初始的FPN使用来进行目标检测的, 但由于其性能, 现大多用来做特征提取.

(FPN模型图)

基础的FPN先对高层特征图上采样(2倍的最邻近插值), 再对低层特征图升维(1 * 1 卷积), 最后对维度, 高度, 宽度一致的两个特征图进行元素对应相加, 得到融合特征图.

(resnet模型图)<sup id="fnref:3"><a href="#fn:3" rel="footnote"><span class="hint--top hint--error hint--medium hint--rounded hint--bounce" aria-label="[Mask-RCNN 算法及其实现详解](https://blog.csdn.net/remanented/article/details/79564045) ">[3]</span></a></sup>

Mask RCNN内的FPN上采样部分不变, 在升维部分, 这里的处理是把所有特征图维度处理至256.

在得到第一次P5, P4, P3, P2后, 对每一个特征图作3 * 3 卷积, 输出仍为256.

如图示, P6, P5, P4, P3, P2会送至RPN层.

RPN

力扣 1. 两数之和

leetcode

使用快速排序 + 原数组index记录 + 双指针

  1. 快速排序 + 原数组index记录
1
2
3
4
5
6
7
8
9
10
11
12
13
def quick_sort(left, right):
    if left >= right: return
    i, j = left, right
    while i < j:
        while nums[j] > nums[left] and i < j: j -= 1
        while nums[i] <= nums[left] and i < j: i += 1
        nums[i], nums[j] = nums[j], nums[i]
        idx[i], idx[j] = idx[j], idx[i]
    nums[left], nums[i] = nums[i], nums[left]
    idx[i], idx[left] = idx[left], idx[i]

    quick_sort(left, i - 1)
    quick_sort(i + 1, right)
  1. 双指针
1
2
3
4
5
6
7
8
9
i, j = 0, len(nums) - 1
while 0 <= i < j < len(nums):
    cur = nums[i] + nums[j]
    if cur > target:
        j -= 1
    elif cur < target:
        i += 1
    else:
        break

官方解法: hash表

1
2
3
4
5
6
in_ = {}
for i in range(len(nums)):
    if target - nums[i] in in_:
        return [in_[target - nums[i]], i]
    else:
        in_[nums[i]] = i

力扣 10. 正则表达式匹配

leetcode

动态规划-二维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def isMatch(s, p):
    def match(i, j):
        # 指针未指向字符串s
        if i == 0:
            return False
        # 单个字符匹配任意字符
        if p[j - 1] == ".":
            return True
        # 单个字符一对一匹配
        return s[i - 1] == p[j - 1]
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    for i in range(m + 1):
        for j in range(1, n + 1):
            # 零到多字符匹配
            if p[j - 1] == "*":
                dp[i][j] |= dp[i][j - 2] # 匹配零个
                if match(i, j - 1):     # 要进行匹配
                    dp[i][j] |= dp[i - 1][j]
            else:
                # 一对一字符匹配
                if match(i, j):
                    dp[i][j] |= dp[i - 1][j - 1]

    return dp[m][n]

力扣 11. 盛最多水的容器

leetcode

枚举: time N/A

1
2
3
4
5
6
7
def maxArea(height):
    cur = 0
    for i in range(len(height)):
        for j in range(i, len(height)):
            cur = max(cur, (j - i) * min(height[j], height[i]))
    
    return cur

双指针收缩

1
2
3
4
5
6
7
8
9
def maxArea(height):
    i, j = 0, len(height) - 1
    res = (j - i) * min(height[i], height[j])
    while i < j:
        if height[i] >= height[j]: j -= 1
        else: i += 1
        res = max(res, (j - i) * min(height[i], height[j]))
    
    return res

力扣 15. 三数之和

leetcode

快排 + 双指针

  1. 快排
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def quick_sort(left, right):
    if left >= right: return
    i, j = left, right

    while i < j:
        while nums[j] > nums[left] and i < j:
            j -= 1
        while nums[i] <= nums[left] and i < j:
            i += 1
        
        nums[i], nums[j] = nums[j], nums[i]
    nums[i], nums[left] = nums[left], nums[i]

    quick_sort(left, i - 1)
    quick_sort(i + 1, right)
  1. 双指针(三指针)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
res = []
for k in range(0, num_len - 2):
    if nums[k] > 0:
        break
    if k > 0 and nums[k] == nums[k - 1]: continue
    i, j = k + 1, num_len - 1
    while i < j:
        cur = nums[k] + nums[i] + nums[j]
        if cur > 0:
            j -= 1
            while i < j and nums[j] == nums[j + 1]: j -= 1
        elif cur < 0:
            i += 1
            while i < j and nums[i] == nums[i - 1]: i += 1
        else:
            res.append([nums[k], nums[i], nums[j]])
            i += 1
            j -= 1
            while i < j and nums[i] == nums[i - 1]: i += 1
            while i < j and nums[j] == nums[j + 1]: j -= 1

力扣 17. 电话号码的字母组合

leetcode

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def letterCombinations(digits):
    if not digits:
        return []
        
    hash_ = {"2": ["a", "b", "c"],
             "3": ["d", "e", "f"],
             "4": ["g", "h", "i"],
             "5": ["j", "k", "l"],
             "6": ["m", "n", "o"],
             "7": ["p", "q", "r", "s"],
             "8": ["t", "u", "v"],
             "9": ["w", "x", "y", "z"]}
    
    tmp, res = [""], []

    for d in digits:
        if d in hash_:
            for t in tmp:
                for ad in hash_[d]:
                    res.append(t + ad)
            # res += add_
            tmp = res
            res = []

    return tmp
  1. 回溯 + 队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def letterCombinations(digits):
    if not digits:
        return []

    hash_ = {"2": ["a", "b", "c"],
             "3": ["d", "e", "f"],
             "4": ["g", "h", "i"],
             "5": ["j", "k", "l"],
             "6": ["m", "n", "o"],
             "7": ["p", "q", "r", "s"],
             "8": ["t", "u", "v"],
             "9": ["w", "x", "y", "z"]}
    
    tmp, res, digit_len = [], [], len(digits)

    def back(idx, digit_len):
        if idx == digit_len:
            res.append("".join(tmp))
        else:
            digit = digits[idx]
            for d in hash_[digit]:
                tmp.append(d)
                back(idx + 1, digit_len)
                tmp.pop()
        

    back(0, digit_len)
    return res

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

leetcode

预置

1
2
3
4
5
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

链表基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def removeNthFromEnd(head, n):
    if not head: return
    node_len, node_cur = 0, head
    while node_cur:
        node_cur = node_cur.next
        node_len += 1
    
    top = ListNode(next=head)

    left_n, cur = node_len - n, top
    # print(node_len, left_n)

    while left_n > 0:
        cur = cur.next
        left_n -= 1
    
    # print(cur.val)
    cur.next = cur.next.next

    return top.next

力扣 2. 两数相加

leetcode

简单遍历链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
a, b, cur_num, next_ = l1, l2, 0, 0
while a and b:
    total = a.val + b.val + next_
    cur_num = total % 10
    next_ = total // 10

    a.val = cur_num
    b.val = cur_num

    a = a.next
    b = b.next

if a:
    while a:
        total = a.val + next_
        cur_num = total % 10
        next_ = total // 10

        a.val = cur_num
        a = a.next
    res = l1
else:
    while b:
        total = b.val + next_
        cur_num = total % 10
        next_ = total // 10

        b.val = cur_num
        b = b.next
    res = l2

if next_ > 0:
    cur = res
    while cur.next:
        cur = cur.next
    cur.next = ListNode(next_)

return res
  • Copyrights © 2022 eightyninth
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信