新知识列表

新知识列表

树状数组（与前缀和、逆序对有关）

相关知识

树状数组学习笔记

树状数组(推荐)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int lowbit(int x) {
    return x & (-x);
}

public void update(int i, int delta) {
    // len 为数组长度
    while (i <= len) {
        tree[i] += delta;
        i += lowbit(i);
    }
}

public int query(int i) {
    // 从右到左查询
    int sum = 0;
    while (i > 0) {
        sum += tree[i];
        i -= lowbit(i);
    }
    return sum;
}

应用

并查集（与深度优先搜索，集合合并有关）

相关知识

通俗易懂地讲解《并查集》

并查集

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
public void init(int n){
    int[]father=new int[n];
    // 初始化，每个人的父节点都是自己
    for(int i = 1; i <= n; i++)
        father[i] = i;
}


public void Union(int a, int b) {
    int faA = find(a);
    int faB = find(b);
    if(faA != faB) father[faA] = faB;
}

public int find(int x) {
    int a = x;
    // 寻找当前节点的根节点
    // x 就是要找的根节点
    while(x != father[x])
        x = father[x];
    // 找到根节点后，把当前集合点的根节点都改为 x  
    while(a != father[a]) {
        int z = a;
        a = father[a];
        father[z] = x;
    }
    return x;
}
1
2
3
4
// 查找根节点这句的理解
while(x != father[x])
        x = father[x];
//因为我们在初始化的时候，每个节点的根节点初始化为它自己，即我爸爸是我自己，这就是根节点和其他节点的不同之处！！！当 x == parent[x] 的时候，不就说明x是根节点了吗.

应用

并查集应用列表

字典树(前缀树)（与字符串前后缀和字符串匹配有关）

相关知识

字典树

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
public class Trie {
    private boolean isEnd = false;
    private Trie next[] = new Trie[26];

    public Trie() {
    }

    public void insert(String word) {               // 插入单词
        Trie root = this;
        char w[] = word.toCharArray();
        for (int i = 0; i < w.length; ++i) {
            int index = w[i] - 'a';
            if (root.next[index] == null)root.next[index] = new Trie();
            root = root.next[index];
        }
        root.isEnd = true;
    }

    public boolean search(String word) {            // 查找单词
        Trie root = this;
        char w[] = word.toCharArray();
        for (int i = 0; i < w.length; ++i) {
            int index = w[i] - 'a';
            if (root.next[index] == null)return false;
            root = root.next[index];
        }
        return root.isEnd;
    }

    public boolean startsWith(String prefix){       //查找前缀
        Trie root=this;
        char p[]=prefix.toCharArray();
        for(int i=0; i < p.length; ++i){
            int index = p[i]-'a';
            if(root.next[index] == null)return false;
            root = root.next[index];
        }
        return true;
    }
}

Trie (发音为 “try”) 或前缀树是一种树数据结构，用于检索字符串数据集中的键。这一高效的数据结构有多种应用：

  1. 自动补全
  2. 拼写检查
  3. IP 路由 (最长前缀匹配)
  4. T9 (九宫格) 打字预测
  5. 单词游戏

还有其他的数据结构，如平衡树和哈希表，使我们能够在字符串数据集中搜索单词。为什么我们还需要 Trie 树呢？尽管哈希表可以在 O(1) 时间内寻找键值，却无法高效的完成以下操作：

  • 找到具有同一前缀的全部键值。
  • 按词典序枚举字符串的数据集。

应用

摩尔投票

核心就是对拼消耗。玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。最后能剩下的必定是自己人。

作者：胡新辰来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

应用

滑动窗口

先向右扩展窗口，当窗口的值满足条件时，收缩左边界，并记录所要求的最优质，直至窗口内的值刚好满足条件。 然后继续向右移动右边界，收缩左边界，$…$

应用

5.数组中数字出现的次数

6.拼车问题

思路：不管上车人是谁，也不管下车人是谁，上车的时候加人，下车的时候减人。然后遍历行程序列，对路途中的在行程中的人数计数，如果大于capacity就不能顺利接收

应用

拓扑排序

思路：对于每个节点维护一个入度数组，如果入度数组的值为0，将其加入队列。从队列取出元素，将依赖该节点的所有节点的入度减一，如果某个节点的入度为0，那么将该节点加入到队列中去。
在这个过程中记录每次出队的元素即为拓扑排序的顺序，如果最后排序完的数量小于原始节点的数量，那么无法完成拓扑排序

应用

判断链表是否存在环路

思路：一个快指针 $f$ 每次走两步，一个慢指针 $s$ 每次走一步，如果快指针和慢指针相遇了 $（f==s）$ ，那么说明链表存在环路

如何寻找进入环的第一个节点？

思路：快指针 $f$ 每次走两步，慢指针 $s$ 每次走一步，快慢指针相遇的时候 $(f==s)$ ，一个每次走一步的慢指针 $ps$ 从头节点出发，当慢指针 $s$ 与 $ps$ 相遇的时候，就是第一个进入环路的节点

两个链表的第一个公共节点

思路：两个节点同时走，即指针 $P_A$ 走 $A$ 链表，指针 $P_B$ 走 $B$ 链表，$P_A$ 走到末尾时，切换到B链表上，$P_B$ 走到末尾时切换到 $A$ 链表上，这时如果链表有交点，两个指针将会在交点相遇。

你变成我，走过我走过的路。

我变成你，走过你走过的路。

然后我们便相遇了..

或许这就是程序员的浪漫吧

应用

链表的转置（reverse）

汉诺塔

八皇后

对角线的计算方式是：

主对角线的计算方式是：$row-cloumn$ 在主对角线上的点的坐标的$row-column$的差值相同

副对角线的计算方式是：$row+column$在副对角线上的点的坐标的$row+column$的差值相同

应用

求模运算的性质

模运算与基本四则运算有些相似，但是除法例外。其规则如下：

$(a + b) % p = (a % p + b % p) % p （1）$

(重要，求模时每一步求模，最后对结果求模所得的结果和最后一次求模的计算结果相同)

$(a - b) % p = (a % p - b % p) % p （2）$

$(a b) % p = (a % p b % p) % p （3）$

$a ^ b % p = ((a % p)^b) % p （4）$

结合律：

$((a+b) % p + c) % p = (a + (b+c) % p) % p （5）$

$((ab) % p c)% p = (a (bc) % p) % p （6）$

交换律：

$(a + b) % p = (b+a) % p （7）$

$(a b) % p = (b a) % p （8）$

分配律：

$((a +b)% p c) % p = ((a c) % p + (b * c) % p) % p （9）$

重要定理

若$a≡b (% p)$，则对于任意的$c$，都有$(a + c) ≡ (b + c) (%p)；（10）$

若$a≡b (% p)$，则对于任意的$c$，都有$(a c) ≡ (b c) (%p)；（11）$

若$a≡b (% p)$，$c≡d (% p)$，则

$(a + c) ≡ (b + d) (%p)$，

$(a - c) ≡ (b - d) (%p)$，

$(a c) ≡ (b d) (%p)$，

$(a / c) ≡ (b / d) (%p)； （12）$

0-1背包问题的递推关系

0-1背包问题的递推关系

定义子问题$P(i,W)$为：在前$i$个物品中挑选总重量不超过$w$的物品，每种物品至多只能挑选1个，使得总价值最大；这时的最优值记作$dp(i,W)$，其中$1<=i<=n$ , $1<=w<=c$

考虑第$i$件物品，无外乎两种可能：选，或者不选。

  • 不选的话，背包的容量不变，改变为问题$P(i-1,W)$
  • 选的话，背包的容量变小，改变为问题$P(i-1,W-w_i)$

最优方案就是比较这两种方案，哪个会更好些：

$dp(i,W)=max{dp(i-1,W),dp(i-1,W-w_i)+v_i}$

得到

$dp(i, W)=\left{\begin{array}{ll}
0 & \text { if } i=0 \
0 & \text { if } W=0 \
dp(i-1, W) & \text { if } w_{i}>W \
\max \left{dp(i-1, W), v_{i}+dp\left(i-1, W-w_{i}\right)\right} & \text { otherwise }
\end{array}\right.$

应用

二分查找

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int binarySearch(int[] arr, int start, int end, int target) {
    int result = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;    //防止溢位
        if (arr[mid] > target)
            end = mid - 1;
        else if (arr[mid] < target)
            start = mid + 1;
        else {
            result = mid;
            break;
        }
    }
    return result;
}

变种以及应用

差分数组

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

这里就需要差分数组的技巧，类似前缀和技巧构造的 prefix 数组，我们先对 nums 数组构造一个 diff 差分数组，diff[i] 就是 nums[i] 和 nums[i-1] 之差：

定义

差分数组
差分数组

对于已知有n个元素的数列d，建立记录它每项与前一项差值的差分数组f：显然，f[1]=d[1]-0=d[1];对于整数i∈[2,n]，我们让f[i]=d[i]-d[i-1]。

1
2
3
4
5
6
int[] diff = new int[nums.length];
// 构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
    diff[i] = nums[i] - nums[i - 1];
}
1
2
3
构造差分数组：
nums:   8   2   6   3   1
diff:   8   -6  4   -3  -2

通过这个 diff 差分数组是可以反推出原始数组 nums 的，代码逻辑如下：

1
2
3
4
5
6
int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
    res[i] = res[i - 1] + diff[i];
}

这样构造差分数组 diff，就可以快速进行区间增减的操作，如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3

1
2
3
nums:   8   5   9   6   1
diff:   8   -3  4   -3  -5
            i        j
赏

谢谢你请我吃糖果

微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走