1. kmp 模式匹配

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

class Solution {
    /**
     * 使用KMP算法在haystack中查找needle的首次出现位置
     * @param haystack 主字符串
     * @param needle 要查找的子串
     * @return 首次出现的位置索引，未找到返回-1
     */
    public int strStr(String haystack, String needle) {
        // 处理特殊情况：空子串直接返回0
        if (needle.length() == 0) return 0;

        // 生成KMP算法的next数组（部分匹配表）
        int[] next = new int[needle.length()];
        getNext(next, needle);

        int j = -1; // 模式串指针，初始化为-1（表示尚未开始匹配）
        for (int i = 0; i < haystack.length(); i++) { // 主串指针i永不回退
            // 当字符不匹配时，根据next数组回退模式串指针
            while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {
                j = next[j]; // 核心操作：利用前缀信息跳过不可能的比较
            }
            
            // 当前字符匹配，模式串指针前进
            if (haystack.charAt(i) == needle.charAt(j + 1)) {
                j++;
            }
            
            // 完全匹配时返回起始位置
            if (j == needle.length() - 1) {
                // 计算起始位置：当前i的位置减去模式串长度 + 1
                return i - needle.length() + 1;
            }
        }
        return -1;
    }

    /**
     * 生成KMP算法的next数组（部分匹配表）
     * 核心思想：计算模式串的最长相同前后缀长度，用于失配时快速跳转
     * @param next 生成的next数组
     * @param s 模式串
     */
    private void getNext(int[] next, String s) {
        int j = -1; // 前缀末尾位置（同时表示当前最长相同前后缀长度）
        next[0] = j; // 初始化第一个位置的next值为-1
        for (int i = 1; i < s.length(); i++) { // i表示后缀末尾位置
            // 前后缀不相同，回退到前一个匹配位置
            while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
                j = next[j]; // 核心操作：利用已计算的next信息快速回退
            }
            
            // 找到相同的前后缀，j前进
            if (s.charAt(i) == s.charAt(j + 1)) {
                j++;
            }
            
            // 记录当前位置的最长相同前后缀长度
            next[i] = j; 
        }
    }
}

2. 滑动窗口最大值

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

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums==null||nums.length==0||k<=0) return new int[0];
        int n = nums.length;
        int[] res = new int[n-k+1];
        Deque<Integer> q = new LinkedList<>();
        for(int i=0;i<n;i++){
            // 范围是[i-k+1, i]，删掉不匹配的下标
            while(!q.isEmpty() && q.peekFirst()<i-k+1){
                q.pollFirst();
            }
            // 维护队列的单调性，队首下标对应的元素最大
            while(!q.isEmpty() && nums[q.peekLast()]<nums[i]){
                q.pollLast();
            }
            // 将当前下标插入到合适位置（从后往前看）
            q.offerLast(i);
            // 从i=k-1开始就已经遍历完第一个窗口了
            // 此后隔一步添加一个res值就是目标值
            if(i>=k-1){
                res[i-k+1] = nums[q.peekFirst()];
            }
        }
        return res;
    }
}

3. 优先队列寻找前k个高频元素

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

public class Solution {
    /**
     * 使用最大堆策略获取前K个高频元素
     * 时间复杂度：O(n log n) 适用于n个不同元素的情况
     * 空间复杂度：O(n) 用于存储哈希表和优先队列
     * @param nums 输入数组
     * @param k 需要返回的高频元素个数
     * @return 前k个高频元素数组
     */
    public int[] topKFrequent(int[] nums, int k) {
        // 步骤1：频率统计 - 使用哈希表记录每个数字出现次数
        // 关键点：getOrDefault方法简化计数逻辑
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // 步骤2：创建最大堆 - 按频率降序排列
        // 比较器说明：pair2[1] - pair1[1]实现最大堆（每次取频率最高的元素）
        // 空间权衡：将所有元素入堆，当k<<n时可考虑最小堆优化（见注释说明）
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (pair1, pair2) -> pair2[1] - pair1[1]
        );
        
        // 将哈希表条目转换为堆元素 [数字, 频率]
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()){
            maxHeap.add(new int[]{entry.getKey(), entry.getValue()});
        }

        // 步骤3：提取结果 - 从堆中取出前k个元素
        int[] result = new int[k];
        for(int i = 0; i < k; i++){
            // 每次poll操作时间复杂度O(log n)
            result[i] = maxHeap.poll()[0]; // 提取数字部分
        }
        
        return result;
    }
}

// 算法优化提示：
// 当k远小于不同元素数量n时，建议使用最小堆优化（时间复杂度降为O(n log k)）
// 实现方式：
// 1. 创建大小为k的最小堆（Comparator维持堆顶为当前最小频率）
// 2. 遍历频率哈希表：
//    - 当堆大小<k时直接添加
//    - 否则比较当前元素频率与堆顶频率，保留更大的
// 3. 最后将堆中元素输出

// 边界条件注意：
// 1. 题目保证k在有效范围内（1 ≤ k ≤ 不同元素个数）
// 2. 结果数组元素顺序不影响答案正确性（本题只要求元素集合）

1.背景

Gin 是一个 golang 的 web 框架，封装比较优雅，API 友好，源码注释比较明确，具有快速灵活，容错方便等特点。它的主要作者是 Manu，Javier 和 Bo-Yi Wu，2016 年发布第一个版本，目前是最受欢迎的开源 Go 框架。

根据 Round 22 results - TechEmpower Framework Benchmarks 对现存的 web 框架的排名，Gin 框架以 95900 分的成绩位列第 185 名，与之相对的，业界常用的其他 web 框架比如 Spring 仅有 24082 分，位列第 381 名，可见 Gin 的效率远高于 spring 框架。

考虑到采用 go 进行开发时，其他排名靠前的 web 框架的生态并不如 Gin 完善，因此采用 Gin 是一个不错的选择。Gin 包含的组件和支持的功能如下：

1. vscode If you continue to see this message, you can try toggling the remote.SSH.useFloc

• 现象描述：循环报错无法上传新版本服务端

• 故障原因：ssh链接使用的文件锁失效

• 解决方案：在本地ctrl+shift+p打开控制面板，输入Kill VS Code Server on Host，关闭连不上的服务器上面的vscode服务端。此时重新连接即可。

Accuracy, Efficiency, and Expansion: Surveying the Advancements in DETR during 2021-2023

Abstract

DEtection TRansformer (DETR) is a framework for object detection that views it as a direct set prediction problem, removing the need for hand-designed components and utilizing a transformer encoder-Decoder architecture to improve the accuracy and efficiency of object detection. Within two years, Detection Transformer (DETR) has undergone a remarkable transformation. This survey dissects key advancements, analyzes its current state, and ponders its future, revealing how DETR redefines object detection.

Key Words: Object Detection, Transformer, Detection Transformer

Introduction

Object Detection refers to the task of automatically identifying and localizing objects within an image or video. It involves using computer vision techniques, such as deep learning models, to analyze and classify regions of an image that contain objects of interest. As a fundamental building block of computer vision, object detection has undergone a remarkable transformation in recent years. Early efforts relied on meticulously crafted features and laborious two-stage pipelines, struggling to achieve both accuracy and efficiency. However, the emergence of DETR (Detection Transformer) in 2020 marks a pivotal moment, introducing a novel paradigm that transcends limitations and unveils exciting possibilities for the future of object detection.

DETR views object detection as a set prediction problem and introduces a remarkably concise pipeline for object detection. It involves using a Convolutional Neural Network (CNN) to extract foundational features, which are then input into a Transformer for relationship modeling. The resulting output is matched with ground truth on the image using a bipartite graph matching algorithm. The detailed methodology of DETR is illustrated in the above diagram, and its key design inceptions include:

1. Modeling object detection as a set prediction problem:

   DETR conceptualizes object detection as a set prediction problem. Instead of treating each object individually, DETR aims to predict the entire set of objects collectively. This global perspective is a departure from the conventional paradigm.

2. Bipartite Matching for Label Assignment:

   To accomplish label assignment, DETR employs a bipartite matching strategy. This involves using the Hungarian algorithm, a combinatorial optimization algorithm, to determine the optimal matching between the predicted objects and the ground truth. This approach ensures effective and accurate label assignment.

3. Transformer-based Encoder-Decoder Structure:

   DETR leverages the Transformer architecture with an encoder-Decoder structure. This choice transforms object detection into an end-to-end problem, eliminating the need for post-processing steps like Non-Maximum Suppression (NMS). The Transformer's attention mechanism enables global context understanding, contributing to improved detection accuracy.

4. Avoidance of handcrafted anchor priors:

   Unlike traditional methods that rely on manually defined anchor priors, DETR avoids such handcrafted position prior information. This is achieved through its set-based approach, making the model more flexible and less dependent on predefined anchor boxes.

1. Background

   目的：从背景信息中挑选对当前任务目标更关键的信息。

   应用场景：序列数据处理

   机制分类：自注意力机制、空间注意力机制、时间注意力机制。

2. Classificiation

• 点积自注意力机制

  NLP中自注意力机制的计算步骤：

  • 预处理输入数据X

  • 初始化权重\(W_Q,W_K,W_V\)

  • 计算K,Q,V矩阵（仅限于输入部分的编码过程，encoder输出到decoder时的QKV不通过该方式计算）

    \[ \begin{cases}K=XW_K\\Q=XW_Q\\V=XW_V\end{cases} \]

  • 计算注意力得分：\(softmax(\frac{QK^T}{\sqrt{d_k}})\)，然后再和V相乘

  • 得到自注意力矩阵\(softmax(\frac{QK^T}{\sqrt{d_k}})V\)

  其中，输入矩阵X通过乘以对应权重会生成对应的QKV矩阵，分别表征：

  • Q：查询向量，代表需要关注的元素或者位置。
  • K：键向量，代表参考元素或者位置。作用是用于提供参考信息，来确定序列中某一位置的元素相比于其他位置的元素的相关性。
  • V：值向量，表示实际信息。输入向量X所在的空间不一定适用所有类型的任务的需要，比如一个数据在低秩空间可能是线性不可分的，但将其映射到高维空间后就可以找到一个明显的分界点。因此通过乘以一个可学习的权重矩阵\(W_V\)，我们可以自适应的调节模型对输入向量的映射，从而提升模型对输入信息的学习能力。

  然后，我们关注一下注意力得分的计算公式：

  • 首先是Q和\(K^T\)的内积，这一项的意义在于度量Q和K两个向量的相似度。

    考虑一组简单的二维向量：

    Read more »

服务器网络相关

1. 用命令行终端登录校园网：

1

curl -X POST -d "DDDDD=【学号】&upass=【密码】&0MKKey=" 【校园网登录页】

2. 服务器vpn网络环境配置

clash GUI安装教程：Clash安装教程Win10,Linux. Windows版 | by van-der-Poel | Medium

clash 命令行使用方法：GLaDOS

安装好后，cd clash然后执行以下指令启动screen，在机器上运行一个命令行代理程序：

1
2
3

screen -S vpn
cd ~/clash
./clash-linux-amd64-v1.10.0 -f glados.yaml -d .

然后设置终端走的代理：

1

vi ~/.bashrc

添加以下两行：

1
2

export http_proxy='http://localhost:[你设置的http代理端口]'
export https_proxy='http://localhost:[你设置的http代理端口]'

这个端口有可能被占用，如果被占了就换一个，配置文件在~/clash/glados.yaml

测试:

1

wget www.google.com

代理端口失效时的修复方法

有时候可能会开着clash，网络也连上了但是没网的情况，这时候得重置一下代理端口：

可以查看当前系统中的代理设置，http_proxy/https_proxy这两个设置项应该是小写的:

1

env | grep -i proxy

如果和clash端口号对不上的话就清掉：

1
2
3
4

unset http_proxy
unset https_proxy
unset HTTP_PROXY
unset HTTPS_PROXY

然后再手动设置或者持久化到~/.bashrc里，7892换成glados.yaml里面规定的端口：

1
2
3
4

export http_proxy=http://127.0.0.1:7892
export https_proxy=http://127.0.0.1:7892
export HTTP_PROXY=http://127.0.0.1:7892
export HTTPS_PROXY=http://127.0.0.1:7892

1. hexo静态博客

使用hexo+git pages搭建，搭建过程参考以下文章：

(13 封私信) 博客 hexo - 搜索结果 - 知乎 (zhihu.com)

Hexo+Next主题搭建个人博客+优化全过程（完整详细版） - 知乎 (zhihu.com)

• 解决的问题清单：

  1. 图片插入问题

     hexo博客如何插入图片 - 知乎 (zhihu.com)

     在配置了相对资源路径后，如果直接使用md文件的插入方法会导致预览界面显示不出来图片。通过插件引入方式可以解决该问题：

     1	{% asset_img [img_name] [description] %}

  2. 公式渲染问题：

     Hexo显示latex公式 - 知乎 (zhihu.com)

     「博客搭建」Hexo Next主题配置Mathjax遇到的问题：pandoc exited with code null_pandoc exited with code null._Jannish的博客-CSDN博客

     记得要在本地下载配置pandoc

     配置完毕后，在md前面的注释处加上mathjax: true即可。

  3. 代码块显示：

     参考以下文章： https://hexo.io/zh-cn/docs/syntax-highlight.html

     通过以下方式修改next主题的配置文件可以在代码块外面显示一键复制：

     1 2 3 4 5 6 7 8 9 10 11 12

     codeblock: # Code Highlight theme # Available values: normal | night | night eighties | night blue | night bright | solarized | solarized dark | galactic # See: https://github.com/chriskempson/tomorrow-theme highlight_theme: normal # Add copy button on codeblock copy_button: enable: true # Show text copy result. show_result: true # Available values: default | flat | mac style:

NLP中seq2seq结构对self attention机制的引入

序列转序列结构常用于机器翻译，其分为编码器和解码器两部分。其中，编码器负责将输入文本转译为上下文编码向量，解码器负责对其进行解码，翻译为目标语言。

该上下文编码向量长度一般是固定的，导致模型对于变长输入文本的处理能力不一致。为了提升模型对于该序列的利用能力，学界引入了注意力机制根据输入序列的不同部分为其赋予不同的注意力权重。

对注意力机制进行抽象，可以归结为Q,K,V三个矩阵的计算，如下图所示：

一个注意力层会在内部维护q,k,v三个权重矩阵，分别对应查询权重、键权重、值权重三方面权重。将输入序列向量与q,k,v矩阵分别相乘，就得到了Q（Query，查询向量，包含当前位置的输出序列信息，用于计算注意力权重）,K（Keys，键向量，包含序列中每个位置的信息，用于计算注意力权重）,V（Values，值向量，包含输入序列中每个位置的具体数值信息，用于根据注意力权重计算输出的上下文向量值）三个向量。