Jian Li (李健)

Jian Li (李健)

Associate Professor at School of Artificial Intelligence, Beijing Normal University (BNU)

Posts by Tags

Algorithms

Algorithms: Substring

5 minute read

Published:

字串问题有个通用的滑动窗口算法，时间复杂度$O(n^2)$

其中关键：

Algorithms: Two Pointers

12 minute read

Published:

  • 两个指针的问题：通过2个指针同步或不同步的移动，得到结果。时间复杂度一般会降低一个数量级。

  • 适用于排好序的情况

    86. Partition List

  • 解析: 使用x进行划分，小的在前面，大的在后面，x两边的相对顺序不变。
  • 边界：链表为空
  • 思路：两个指针，一个负责小于x的情况，一个负责大于等于x的情况，之后连起来即可。注意！！！使用创建ListNode的对象，返回该对象的next
  • 时间复杂度：$O(n)$

Algorithms: Math

8 minute read

Published:

  1. 位运算
  2. 10进制进位，取余

  3. 找规律题目

    136. Single Number

    Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
    • 利用取余操作的特性相同为0，不同为1。可以得出，只出现一次的数字。
      int singleNumber(vector<int>& nums) {
 int start = 0;
 for (auto n:nums) {
   start ^= n;
 }
 return start;
}

      137. Single Number II

      Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
    • 136的升级版，可以使用32bit保存对应每个bit之和取余进行操作。对重复出现的那个的值进行取余，如本题中的3，上题中的2。 ```c++ int singleNumber(vector& nums) { vector table(32, 0); int res = 0;

    for (int i = 0; i < 32; ++i) { for (auto j = 0; j < nums.size(); ++j) { table[i] += ((nums[j] » i)&1); table[i] %= 3; } res |= (table[i] « i); } return res; } ``` —

    29. Divide Two Integers

    ```c++ Divide two integers without using multiplication, division and mod operator.

Algorithms: Search

2 minute read

Published:

查找的题目基本是二分查找，排序一般是快排或归并

快排是left = 0, right = x.size() - 1; while(low <= high); high = mid - 1; low = mid + 1;

结果是

Algorithms: Backtracking

15 minute read

Published:

遍历全部情况

  1. 定义解空间，包含全部解
  2. 利用深度优先搜索解空间
  3. Trial，减枝。（避免访问不可能产生解的子空间）
    • 而根据条件有选择的遍历，叫做剪枝或分枝定界。

Algorithms: Greedy

3 minute read

Published:

动态规划： 每一步都进行选择，依赖于子问题的解。通常使用自底向上求解，先求较小的子问题，然后是较大的子问题。

贪心： 每次找出局部最优解。

Algorithms: Dynamic Programming

19 minute read

Published:

分治方法

  1. 将问题划分成互不相交的子问题
  2. 递归地求解子问题
  3. 将子问题的解组合起来

    动态规划(两个要素：最优子结构、子问题重叠)

  4. 应用于子问题重叠的情况，对于每个子问题求解一次，并将结果放在表格中
  5. 通常用于求解最优化问题或和问题
  6. 找出子问题，定义最优子结构=> 给出最优子结构的递推公式 => 计算最优解（通常Bottom-top）

Algorithms: Divide and Conquer

2 minute read

Published:

  1. Divide: 将问题划分为一些子问题，子问题的形式和原问题一样，只是规模更小。
  2. Conquer：递归地求解出子问题。如果子问题的规模足够小，则停止递归进行求解。
  3. Combine：将子问题的解组合合并成原问题的解

Algorithms: Linked List

7 minute read

Published:

链表题目是有套路的，如下4个方法：

  • 链表逆序 (n个节点进行逆序，实际上循环进行n-1次)
  • 2个指针 (拆分、拼接、合并、求中点)
  • 链表成环
  • 使用额外空间保存

Algorithms: Hash Table

3 minute read

Published:

概述

  • 要对每种基础数据结构有深刻的理解。主要应对设计题：
  • HashTable： 增、删、查都是O(1)，但是是无序的
  • vector: 增(尾部增O(1)、其他O(n))、删(尾部删O(1)、其他O(n))、查(O(n)),可以有序可以无序
  • list: 增、删(头尾O(1)、其他O(n))、查(O(n))

Algorithms: Stack

2 minute read

Published:

概述

什么情况使用栈？

  1. 利用栈的后进先出性质。
  2. 输入：数组，输出：与数组下标和元素都相关。而且栈中构成一定的顺序比如递增、递减，如果不满足则出栈进行计算。

    需要注意的情况

  3. 搞清楚什么时候需要入栈、出栈
  4. 搞清楚栈中应该放元素or下标
  5. 什么时候更新结果

Colab

Github Pages

个人网站搭建

1 minute read

Published:

1. 博客分类

常见的博客平台有几种：

  • 类似新浪博客、网易博客这样的网页版博客
  • 自己购买主机、域名，用WordPress搭建博客

  • 在GitHub等网站上使用其Pages功能搭建静态博客

Google GPU

Google Scholar

学术搜索技巧

1 minute read

Published:

1. 搜索技巧

Google scholar本质上还是一个搜索引擎，所以可以将搜索引擎常用的关键词、技巧加以应用

  1. site: 搜索指定的网站
    如"kernel method" site:nips.cc，搜索nips包含kernel method全部论文
  2. source: 搜索指定来源，与site类似，有时site范围太广，使用source更精确。 如"kernel method" source:"Advances in Neural Information Processing"，搜索nips包含kernel method全部论文
  3. filetype：搜索制定的文件类型
    如"kernel method" filetype:pdf，搜索包含kernel method且有pdf的论文
  4. 双引号完全匹配
    如"kernel method"而不是kernel method，搜索包含kernel method的论文
  5. intile：限定标题
    如intitle:"kernel method"
  6. intext: 限定内容 如intext:("kernel method" -"semi-supervised learning")，搜索内容中包含kernel mehtod且不包含semi-supervised learning的论文
  7. author: 限定作者
    如author:"Jian Li" AND intitle:"Multi-class"
  8. AND & + , 空格都表示“与”关系
  9. OR |表示“或”关系
  10. NOT -表示“非”关系
  11. 使用左侧选择时间限制及排序条件
  12. 对于某网址对应多个期刊的情况，使用source而不是site进行界定。如TPAMI对应网址ieee.org有很多期刊，而其对应来源为IEEE Transactions on Pattern Analysis and Machine Intelligence

IPv6

Jupyter Notebook

LeetCode

Algorithms: Substring

5 minute read

Published:

字串问题有个通用的滑动窗口算法，时间复杂度$O(n^2)$

其中关键：

Algorithms: Two Pointers

12 minute read

Published:

  • 两个指针的问题：通过2个指针同步或不同步的移动，得到结果。时间复杂度一般会降低一个数量级。

  • 适用于排好序的情况

    86. Partition List

  • 解析: 使用x进行划分，小的在前面，大的在后面，x两边的相对顺序不变。
  • 边界：链表为空
  • 思路：两个指针，一个负责小于x的情况，一个负责大于等于x的情况，之后连起来即可。注意！！！使用创建ListNode的对象，返回该对象的next
  • 时间复杂度：$O(n)$

Algorithms: Math

8 minute read

Published:

  1. 位运算
  2. 10进制进位，取余

  3. 找规律题目

    136. Single Number

    Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
    • 利用取余操作的特性相同为0，不同为1。可以得出，只出现一次的数字。
      int singleNumber(vector<int>& nums) {
 int start = 0;
 for (auto n:nums) {
   start ^= n;
 }
 return start;
}

      137. Single Number II

      Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
    • 136的升级版，可以使用32bit保存对应每个bit之和取余进行操作。对重复出现的那个的值进行取余，如本题中的3，上题中的2。 ```c++ int singleNumber(vector& nums) { vector table(32, 0); int res = 0;

    for (int i = 0; i < 32; ++i) { for (auto j = 0; j < nums.size(); ++j) { table[i] += ((nums[j] » i)&1); table[i] %= 3; } res |= (table[i] « i); } return res; } ``` —

    29. Divide Two Integers

    ```c++ Divide two integers without using multiplication, division and mod operator.

Algorithms: Search

2 minute read

Published:

查找的题目基本是二分查找，排序一般是快排或归并

快排是left = 0, right = x.size() - 1; while(low <= high); high = mid - 1; low = mid + 1;

结果是

Algorithms: Backtracking

15 minute read

Published:

遍历全部情况

  1. 定义解空间，包含全部解
  2. 利用深度优先搜索解空间
  3. Trial，减枝。（避免访问不可能产生解的子空间）
    • 而根据条件有选择的遍历，叫做剪枝或分枝定界。

Algorithms: Greedy

3 minute read

Published:

动态规划： 每一步都进行选择，依赖于子问题的解。通常使用自底向上求解，先求较小的子问题，然后是较大的子问题。

贪心： 每次找出局部最优解。

Algorithms: Dynamic Programming

19 minute read

Published:

分治方法

  1. 将问题划分成互不相交的子问题
  2. 递归地求解子问题
  3. 将子问题的解组合起来

    动态规划(两个要素：最优子结构、子问题重叠)

  4. 应用于子问题重叠的情况，对于每个子问题求解一次，并将结果放在表格中
  5. 通常用于求解最优化问题或和问题
  6. 找出子问题，定义最优子结构=> 给出最优子结构的递推公式 => 计算最优解（通常Bottom-top）

Algorithms: Divide and Conquer

2 minute read

Published:

  1. Divide: 将问题划分为一些子问题，子问题的形式和原问题一样，只是规模更小。
  2. Conquer：递归地求解出子问题。如果子问题的规模足够小，则停止递归进行求解。
  3. Combine：将子问题的解组合合并成原问题的解

Algorithms: Linked List

7 minute read

Published:

链表题目是有套路的，如下4个方法：

  • 链表逆序 (n个节点进行逆序，实际上循环进行n-1次)
  • 2个指针 (拆分、拼接、合并、求中点)
  • 链表成环
  • 使用额外空间保存

Algorithms: Hash Table

3 minute read

Published:

概述

  • 要对每种基础数据结构有深刻的理解。主要应对设计题：
  • HashTable： 增、删、查都是O(1)，但是是无序的
  • vector: 增(尾部增O(1)、其他O(n))、删(尾部删O(1)、其他O(n))、查(O(n)),可以有序可以无序
  • list: 增、删(头尾O(1)、其他O(n))、查(O(n))

Algorithms: Stack

2 minute read

Published:

概述

什么情况使用栈？

  1. 利用栈的后进先出性质。
  2. 输入：数组，输出：与数组下标和元素都相关。而且栈中构成一定的顺序比如递增、递减，如果不满足则出栈进行计算。

    需要注意的情况

  3. 搞清楚什么时候需要入栈、出栈
  4. 搞清楚栈中应该放元素or下标
  5. 什么时候更新结果

Markdown

Python

Shadowsocks

Tensorflow

Tensorflow安装

less than 1 minute read

Published:

基础环境环境

VPS

vscode

VSCode使用

less than 1 minute read

Published:

1. 常用命令

个人网站

个人网站搭建

1 minute read

Published:

1. 博客分类

常见的博客平台有几种：

  • 类似新浪博客、网易博客这样的网页版博客
  • 自己购买主机、域名，用WordPress搭建博客

  • 在GitHub等网站上使用其Pages功能搭建静态博客

中文

学术搜索技巧

1 minute read

Published:

1. 搜索技巧

Google scholar本质上还是一个搜索引擎，所以可以将搜索引擎常用的关键词、技巧加以应用

  1. site: 搜索指定的网站
    如"kernel method" site:nips.cc，搜索nips包含kernel method全部论文
  2. source: 搜索指定来源，与site类似，有时site范围太广，使用source更精确。 如"kernel method" source:"Advances in Neural Information Processing"，搜索nips包含kernel method全部论文
  3. filetype：搜索制定的文件类型
    如"kernel method" filetype:pdf，搜索包含kernel method且有pdf的论文
  4. 双引号完全匹配
    如"kernel method"而不是kernel method，搜索包含kernel method的论文
  5. intile：限定标题
    如intitle:"kernel method"
  6. intext: 限定内容 如intext:("kernel method" -"semi-supervised learning")，搜索内容中包含kernel mehtod且不包含semi-supervised learning的论文
  7. author: 限定作者
    如author:"Jian Li" AND intitle:"Multi-class"
  8. AND & + , 空格都表示“与”关系
  9. OR |表示“或”关系
  10. NOT -表示“非”关系
  11. 使用左侧选择时间限制及排序条件
  12. 对于某网址对应多个期刊的情况，使用source而不是site进行界定。如TPAMI对应网址ieee.org有很多期刊，而其对应来源为IEEE Transactions on Pattern Analysis and Machine Intelligence

个人网站搭建

1 minute read

Published:

1. 博客分类

常见的博客平台有几种：

  • 类似新浪博客、网易博客这样的网页版博客
  • 自己购买主机、域名，用WordPress搭建博客

  • 在GitHub等网站上使用其Pages功能搭建静态博客

Tensorflow安装

less than 1 minute read

Published:

基础环境环境

VSCode使用

less than 1 minute read

Published:

1. 常用命令

Algorithms: Substring

5 minute read

Published:

字串问题有个通用的滑动窗口算法，时间复杂度$O(n^2)$

其中关键：

Algorithms: Two Pointers

12 minute read

Published:

  • 两个指针的问题：通过2个指针同步或不同步的移动，得到结果。时间复杂度一般会降低一个数量级。

  • 适用于排好序的情况

    86. Partition List

  • 解析: 使用x进行划分，小的在前面，大的在后面，x两边的相对顺序不变。
  • 边界：链表为空
  • 思路：两个指针，一个负责小于x的情况，一个负责大于等于x的情况，之后连起来即可。注意！！！使用创建ListNode的对象，返回该对象的next
  • 时间复杂度：$O(n)$

Algorithms: Math

8 minute read

Published:

  1. 位运算
  2. 10进制进位，取余

  3. 找规律题目

    136. Single Number

    Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
    • 利用取余操作的特性相同为0，不同为1。可以得出，只出现一次的数字。
      int singleNumber(vector<int>& nums) {
 int start = 0;
 for (auto n:nums) {
   start ^= n;
 }
 return start;
}

      137. Single Number II

      Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
    • 136的升级版，可以使用32bit保存对应每个bit之和取余进行操作。对重复出现的那个的值进行取余，如本题中的3，上题中的2。 ```c++ int singleNumber(vector& nums) { vector table(32, 0); int res = 0;

    for (int i = 0; i < 32; ++i) { for (auto j = 0; j < nums.size(); ++j) { table[i] += ((nums[j] » i)&1); table[i] %= 3; } res |= (table[i] « i); } return res; } ``` —

    29. Divide Two Integers

    ```c++ Divide two integers without using multiplication, division and mod operator.

Algorithms: Search

2 minute read

Published:

查找的题目基本是二分查找，排序一般是快排或归并

快排是left = 0, right = x.size() - 1; while(low <= high); high = mid - 1; low = mid + 1;

结果是

Algorithms: Backtracking

15 minute read

Published:

遍历全部情况

  1. 定义解空间，包含全部解
  2. 利用深度优先搜索解空间
  3. Trial，减枝。（避免访问不可能产生解的子空间）
    • 而根据条件有选择的遍历，叫做剪枝或分枝定界。

Algorithms: Greedy

3 minute read

Published:

动态规划： 每一步都进行选择，依赖于子问题的解。通常使用自底向上求解，先求较小的子问题，然后是较大的子问题。

贪心： 每次找出局部最优解。

Algorithms: Dynamic Programming

19 minute read

Published:

分治方法

  1. 将问题划分成互不相交的子问题
  2. 递归地求解子问题
  3. 将子问题的解组合起来

    动态规划(两个要素：最优子结构、子问题重叠)

  4. 应用于子问题重叠的情况，对于每个子问题求解一次，并将结果放在表格中
  5. 通常用于求解最优化问题或和问题
  6. 找出子问题，定义最优子结构=> 给出最优子结构的递推公式 => 计算最优解（通常Bottom-top）

Algorithms: Divide and Conquer

2 minute read

Published:

  1. Divide: 将问题划分为一些子问题，子问题的形式和原问题一样，只是规模更小。
  2. Conquer：递归地求解出子问题。如果子问题的规模足够小，则停止递归进行求解。
  3. Combine：将子问题的解组合合并成原问题的解

Algorithms: Linked List

7 minute read

Published:

链表题目是有套路的，如下4个方法：

  • 链表逆序 (n个节点进行逆序，实际上循环进行n-1次)
  • 2个指针 (拆分、拼接、合并、求中点)
  • 链表成环
  • 使用额外空间保存

Algorithms: Hash Table

3 minute read

Published:

概述

  • 要对每种基础数据结构有深刻的理解。主要应对设计题：
  • HashTable： 增、删、查都是O(1)，但是是无序的
  • vector: 增(尾部增O(1)、其他O(n))、删(尾部删O(1)、其他O(n))、查(O(n)),可以有序可以无序
  • list: 增、删(头尾O(1)、其他O(n))、查(O(n))

Algorithms: Stack

2 minute read

Published:

概述

什么情况使用栈？

  1. 利用栈的后进先出性质。
  2. 输入：数组，输出：与数组下标和元素都相关。而且栈中构成一定的顺序比如递增、递减，如果不满足则出栈进行计算。

    需要注意的情况

  3. 搞清楚什么时候需要入栈、出栈
  4. 搞清楚栈中应该放元素or下标
  5. 什么时候更新结果

免流量上网

域名

个人网站搭建

1 minute read

Published:

1. 博客分类

常见的博客平台有几种：

  • 类似新浪博客、网易博客这样的网页版博客
  • 自己购买主机、域名，用WordPress搭建博客

  • 在GitHub等网站上使用其Pages功能搭建静态博客

学术

学术搜索技巧

1 minute read

Published:

1. 搜索技巧

Google scholar本质上还是一个搜索引擎，所以可以将搜索引擎常用的关键词、技巧加以应用

  1. site: 搜索指定的网站
    如"kernel method" site:nips.cc，搜索nips包含kernel method全部论文
  2. source: 搜索指定来源，与site类似，有时site范围太广，使用source更精确。 如"kernel method" source:"Advances in Neural Information Processing"，搜索nips包含kernel method全部论文
  3. filetype：搜索制定的文件类型
    如"kernel method" filetype:pdf，搜索包含kernel method且有pdf的论文
  4. 双引号完全匹配
    如"kernel method"而不是kernel method，搜索包含kernel method的论文
  5. intile：限定标题
    如intitle:"kernel method"
  6. intext: 限定内容 如intext:("kernel method" -"semi-supervised learning")，搜索内容中包含kernel mehtod且不包含semi-supervised learning的论文
  7. author: 限定作者
    如author:"Jian Li" AND intitle:"Multi-class"
  8. AND & + , 空格都表示“与”关系
  9. OR |表示“或”关系
  10. NOT -表示“非”关系
  11. 使用左侧选择时间限制及排序条件
  12. 对于某网址对应多个期刊的情况，使用source而不是site进行界定。如TPAMI对应网址ieee.org有很多期刊，而其对应来源为IEEE Transactions on Pattern Analysis and Machine Intelligence