逗比学长的博客

此人有“亿”点强迫症

leetcode的奇怪操作

发表于 更新于 分类于 阅读次数：

写两个字收缩

记录了一些刷题时遇到的算法。

快速幂取余

题目：剑指 Offer 14- II. 剪绳子 II、50. Pow(x, n)

定理：

引理：

证明：

结论：积的取余等于取余的积的取余。

可以推知：。

快速幂取余：

根据求余运算性质可以推出：

当 为奇数时 不是整数，所以分为以下两种情况：

利用以上公式进行循环迭代，可以将时间复杂度降低至对数级别O(logn)，并且能够避免溢出。

C++实现：

1
2
3
4
5
6
7
8
9
10
// 求 a ^ b % c
int powerMod(long long a, long long b, long long c) {
    long long res = 1;
    while(b > 0) {
        if (b % 2 == 1)  res = (res * a) % c;
        a = a * a % c;
        b /= 2;
    }
    return (int) res;
}

参考:

Morris 中序遍历

题目：99. Recover Binary Search Tree

manacher 算法

用于匹配回文串。

题目：336. Palindrome Pairs

KMP算法

题目：用于匹配字符串。

推导：

  • 当T[i] != P[j]时
  • 有T[i-j ~ i-1] == P[0 ~ j-1]
  • 由P[0 ~ k-1] == P[j-k ~ j-1]
  • 必然：T[i-k ~ i-1] == P[0 ~ k-1]

28. Implement strStr()

459. Repeated Substring Pattern

796. Rotate String

KMP由两部分组成，第一部分是是构建next数组，第二部分是进行匹配。

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
class Solution {
public:
    // char:  a b a b a b c a
    // index: 0 1 2 3 4 5 6 7
    // pmt:   0 0 1 2 3 4 0 1   字符串前后缀中匹配最大长度
    // next: -1 0 0 1 2 3 4 0   pmt矩阵右移一位，值的含义，匹配失败时，重新开始匹配的索引。
    //                          其记录着上一段拥有相同序列特征的位置。
    bool kmp(const string &query, const string &pattern) {
        // 构建next数组
        int n = query.size();
        int m = pattern.size();
        vector<int> next(m, -1);
        int j = 0, i = -1;
        while (j < m - 1) {
            if (i == -1 || pattern[j] == pattern[i])
                next[++j] = ++i;
            else
                i = next[i];
        }
        
        // 匹配
        i = 0;  // 主串位置
        j = 0;  // 模式串位置
        while (i < n && j < m) {
            if (j == -1 || query[i] == pattern[j]) { // 当j为-1时，要移动的是i，当然j也要归零
                i++;
                j++;
            } else {
                j = next[j]; // j回溯
            }
        }

        // 匹配成功
        if (j == pattern.size()) return true;
        else return false;

    }
};

Hierholzer 算法

用于寻找欧拉通路。

题目：332. Reconstruct Itinerary

Rabin-Karp 字符串哈希算法

用于匹配字符串。思路将字符串看成一个 进制的数，它对应的十进制值就是哈希值。显然，两个字符串的哈希值相等，当且仅当这两个字符串本身相同。然而如果字符串本身很长，其对应的十进制值在大多数语言中无法使用内置的整数类型进行存储。因此，我们会将十进制值对一个大质数 进行取模。

题目：214. Shortest Palindrome

最大流之Ford-Fulkerson算法

bfptr找中位数算法

快速选择找中位数算法

该算法与快速排序算法类似，在一次递归调用中，首先进行partition过程，即利用一个元素将原数组划分为两个子数组，然后将这一元素放在两个数组之间。两者区别在于快速排序接下来需要对左右两个子数组进行递归，而快速选择只需要对一侧子数组进行递归，所以快速选择的时间复杂度为O(n)。

在C++中，可以用STL的nth_element()

1
2
3
auto midptr = nums.begin() + nums.size() / 2;
nth_element(nums.begin(), midptr, nums.end());
int mid = *midptr;

三向切分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int i = 0, j = 0, k = n - 1;
while (j < k) {
    // 如果大于中位数，则放在右边
    if (nums[j] > mid) {
        swap(nums[j], nums[k]);
        k--;
    // 如果小于中位数，则放在左边
    } else if (nums[j] < mid) {
        // 让中位数向中间靠拢
    	swap(nums[j], nums[i]);
        i++;
        j++;
    // 如果等于中位数，不处理
    } else {
    	j++;
    }
}

约瑟夫环

  1. 剑指 Offer 62. 圆圈中最后剩下的数字

  2. 390. 消除游戏

n 个数字排成一圈，从数字 0 开始，每次删除第 m 个数字，将问题的解记为f(n, m)，其表示N个人报数，每报到M时杀掉那个人，最终胜利者的编号，有以下递推公式：

卡特兰数

卡特兰数（Catalan number）是组合数学中一个常出现在各种计数问题中的数列。

https://leetcode.cn/circle/article/lWYCzv/

https://blog.csdn.net/cz9797/article/details/105366774/

并查集

参考：https://zhuanlan.zhihu.com/p/93647900/

初始化（按秩合并）

1
2
3
4
5
6
7
8
9
10
inline void init(int n)
{	
    fa.resize(n+1);
    rank.resize(n+1);
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}

查找（路径压缩）

1
2
3
4
int find(int x)
{
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

合并（按秩合并）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 秩：以当前结点为根节点的子树的高度(rank)
inline void merge(int i, int j)
{
    int x = find(i), y = find(j);    //先找到两个根节点
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;                   //如果深度相同且根节点不同，则新的根节点的深度+1
}

// 秩：以当前结点为根节点的子树的结点总数(size)，leetcode 803
inline void merge(int i, int j) {
	int x = find(i), y = find(j);
    if (x == y)  return;
    fa[x] = y;
    size[y] += size[x];
}

树状数组

其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和， 区间和。

简单介绍：https://blog.csdn.net/qq_40941722/article/details/104406126

建立树状数组

线状树

使用结构定义(待补充)：

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
struct SegNode {
    int lo, hi;
    SegNode* lchild, *rchild;
    SegNode(int left, int right): lo(left), hi(right), add(0), lchild(nullptr), rchild(nullptr) {}
};

SegNode* build(int left, int right) {
    SegNode* node = new SegNode(left, right);
    if (left == right) {
        return node;
    }
    int mid = (left + right) / 2;
    node->lchild = build(left, mid);
    node->rchild = build(mid + 1, right);
    return node;
}

void insert(SegNode* root, int val) {
    if (root->lo == root->hi) {
        return;
    }
    int mid = (root->lo + root->hi) / 2;
    if (val <= mid) {
        insert(root->lchild, val);
    } else {
        insert(root->rchild, val);
    }
}

使用数组定义：

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
int n = nums.size();
vector<int> segmenTree(4 * n);

void build(int node, int left, int right, vector<int> &nums) {
    if (left == right) {
        segmenTree[node] = nums[left];
        return;
    }
    int mid = (right - left) / 2 + left;
    build(node * 2 + 1, left, mid, nums);
    build(node * 2 + 2, mid + 1, right, nums);
    segmenTree[node] = segmenTree[node * 2 + 1] + segmenTree[node * 2 + 2];
}

void change(int index, int val, int node, int left, int right) {
    if (left == right) {
        segmenTree[node] = val;
        return;
    }
    int mid = (right - left) / 2 + left;
    if (index <= mid) change(index, val, node * 2 + 1, left, mid);
    else change(index, val, node * 2 + 2, mid + 1, right);
    segmenTree[node] = segmenTree[node * 2 + 1] + segmenTree[node * 2 + 2];
}
    
int range(int node, int start, int end, int left, int right) {
    if (left == start && right == end) {
    	return segmenTree[node];
    }
    int mid = (right - left) / 2 + left;
    if (end <= mid) {
    	return range(node * 2 + 1, start, end, left, mid);
    } else if (start > mid) {
    	return range(node * 2 + 2, start, end, mid + 1, right);
    } else {
    	return range(node * 2 + 1, start, mid, left, mid) + range(node * 2 + 2, mid + 1, end, mid + 1, right);
    }
}

sum型线状树：307. 区域和检索 - 数组可修改

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
62
63
64
65
// 线状树
// 时间复杂度：O(n)
// 空间复杂度：O(n)
class NumArray {
private:
    vector<int> segmenTree;
    int n;

    void build(int node, int left, int right, vector<int> &nums) {
        if (left == right) {
            segmenTree[node] = nums[left];
            return;
        }

        int mid = (right - left) / 2 + left;
        build(node * 2 + 1, left, mid, nums);
        build(node * 2 + 2, mid + 1, right, nums);
        segmenTree[node] = segmenTree[node * 2 + 1] + segmenTree[node * 2 + 2];
    }

    void change(int index, int val, int node, int left, int right) {
        if (left == right) {
            segmenTree[node] = val;
            return;
        }
        int mid = (right - left) / 2 + left;
        if (index <= mid) change(index, val, node * 2 + 1, left, mid);
        else change(index, val, node * 2 + 2, mid + 1, right);
        segmenTree[node] = segmenTree[node * 2 + 1] + segmenTree[node * 2 + 2];
    }

    int range(int node, int start, int end, int left, int right) {
        if (left == start && right == end) {
            return segmenTree[node];
        }
        int mid = (right - left) / 2 + left;
        if (end <= mid) {
            return range(node * 2 + 1, start, end, left, mid);
        } else if (start > mid) {
            return range(node * 2 + 2, start, end, mid + 1, right);
        } else {
            return range(node * 2 + 1, start, mid, left, mid) + range(node * 2 + 2, mid + 1, end, mid + 1, right);
        }
    }

public:
    NumArray(vector<int> &nums) : n(nums.size()), segmenTree(nums.size() * 4) {  // 极端情况下，要开4倍
        build(0, 0, n - 1, nums);
    }

    void update(int index, int val) {
        change(index, val, 0, 0, n - 1);
    }

    int sumRange(int start, int end) {
        return range(0, start, end, 0, n - 1);
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(index,val);
 * int param_2 = obj->sumRange(left,right);
 */

max型线状树：

239. 滑动窗口最大值

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
// 线段树
// 时间复杂度：O(nlogn)
// 空间复杂度：O(n)
class Solution {
private:
    vector<int> segmentTree;
    int n;

    void build(int node, int left, int right, vector<int> &nums) {
        if (left == right) {
            segmentTree[node] = nums[left];
            return;
        }
        int mid = (right - left) / 2 + left;
        build(node * 2 + 1, left, mid, nums);
        build(node * 2 + 2, mid + 1, right, nums);
        segmentTree[node] = max(segmentTree[node * 2 + 1], segmentTree[node * 2 + 2]);
    }

    int range(int node, int start, int end, int left, int right) {
        if (left == start && right == end) {
            return segmentTree[node];
        }
        int mid = (right - left) / 2 + left;
        if (end <= mid) {
            return range(node * 2 + 1, start, end, left, mid);
        } else if (start > mid) {
            return range(node * 2 + 2, start, end, mid + 1, right);
        } else {
            return max(range(node * 2 + 1, start, mid, left, mid), range(node * 2 + 2, mid + 1, end, mid + 1, right));
        }
    }

public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k) {
        n = nums.size();
        segmentTree = vector<int>(4 * n);
        build(0, 0, n - 1, nums);
        vector<int> res;
        for (int i = 0; i <= n - k; i++) {
            res.push_back(range(0, i, i + k - 1, 0, n - 1));
        }

        return res;
    }
};

二进制

原码、补码、反码的概念：https://blog.csdn.net/weixin_30940783/article/details/96858629

常见规则：

  • 相同的数异或相抵，如果 $x_1\oplus x_2=0$，则$x_1==x_2$
  • $x_1 \& -x_1$ 可以取出 $x$ 的二进制表示中最低位的那个 1。例子：12的二进制表示为 0000 1100，-12的二进制表示为12的反码+1为 1111 0011+1 = 1111 0100，使用上述公式得到最低位为 0000 0100。如果 $x_1==INT_MIN=-2147483648$会强制赋结果为

位运算

ASCII: 97~122小写字母，ASCII: 65~90大写字母

大写变小写、小写变大写 : 字符 ^= 32;
大写变小写、小写变小写 : 字符 |= 32;
小写变大写、大写变大写 : 字符 &= -33;

string toChangeCase(string str) {
    for (int i = 0; i < str.size(); i++)
    {
        //大转小
        if (str[i] >= 65 && str[i] <= 90)
        {
            str[i]=tolower(str[i]);
        }
        //小转大
        else if (str[i] >= 97 && str[i] <= 122)
        {
            str[i]=toupper(str[i]);
        }
    }
    return str;
}

会让最低位变成0，通过下列代码可以获得二进制的个数，类似__builtin_popcount(int n)

1
2
3
4
5
6
7
8
9
int __builtin_popcount(int num) {
    int count = 0;
    while (n) {
        n &= (n-1);
        count++;
    }
    return count;
}

可以取出最低位 1，如13的二进制表示为1101，那么-13的二进制表示为0010 + 0001 = 0011，那么1101 & 0011 = 0001，二进制末尾1的位置是：

1
2
3
int lowbit(int m) {
	return m & -m;
}

__builtin_ctz、__builtin_ctzl、__builtin_ctzll 返回输入数二进制表示从最低位开始(右起)的连续的0的个数

1
2
3
4
5
int __builtin_ctzl(unsigned long x) {
    for (int i = 0; i != 64; ++i)
    	if (x >> i & 1) return i;
    return 0;
}