简介：算法是解决特定问题或执行特定任务的一系列明确步骤或规则。在计算机科学中，算法是指能够被计算机程序实现的解决问题的方法。一个有效的算法应该具有以下特性：

输入：有一个或多个输入。
输出：至少产生一个输出。
确定性：算法中的每一步都必须明确定义，且只能以一种方式解释。
有限性：算法必须在有限步骤之后结束，即它不能无限期地运行下去。
有效性：算法应在合理的时间和空间内解决问题。

算法

算法入门的社会实验

实验具体过程：
一开始有100人，每个人有100块钱。在每一轮做的事情是，每个人随机给别人一块钱，如果在该轮此人钱数为0，则不给，但可以正常接受
别人给的钱。经过很多人后，这个社会财富很均匀吗？算出经过多少轮后，社会的基尼系数超过0.5？
下面是社会基尼系数的定义：

基尼系数（Gini Coefficient）是一种用来衡量收入分配或财富分配不平等程度的统计指标。它由意大利统计学家科拉多·基尼（Corrado Gini）1912
年提出，广泛应用于经济学和社会科学领域，尤其是在研究收入分配不平等问题时。
基尼系数的定义
基尼系数的取值范围从0到1（或0%到100%）：

0 表示完全平等，即所有人的收入或财富完全相同。

1 表示完全不平等，即一个人拥有所有的收入或财富，其他人一无所有。

代码如下：

#include <iostream>
#include <random>
#include <vector>
#include <format>
#include <algorithm>

int gen_random(int max)
{
    std::random_device rd;
    std::mt19937 engine{rd()};
    std::uniform_int_distribution<int> dist(0, max);
    return dist(engine);
}

void experiment(std::vector<double> &all, int loops)
{
    int n = static_cast<int>(all.size());
    std::vector<bool> has_money(n, false);
    for (int k = 0; k < loops; ++k)
    {
        std::fill(has_money.begin(), has_money.end(), false);
        for (int i = 0; i < n; ++i)
        {
            if (all[i] > 0)
                has_money[i] = true;
        }
        for (int i = 0; i < n; ++i)
        {
            if (has_money[i])
            {
                int j = i;
                do
                {
                    j = gen_random(n-1);
                } while (j == i);
                --all[i];
                ++all[j];
            }
        }
    }
}


double calc_gini(const std::vector<double> &all)
{
    double sum = 0;
    double total_diff = 0;
    int n = static_cast<int>(all.size());
    for (int i = 0; i < n; ++i)
    {
        sum += all[i];
        for (int j = 0; j < n; ++j)
        {
            total_diff += std::abs(all[i] - all[j]);
        }
    }

    double gini = total_diff / (1.0 * 2 * n * sum);
    return gini;
}

void entry()
{
    std::cout << "一个社会的基尼系数是在0-1之间的小数；"  << std::endl;
    std::cout << "基尼系数为0代表所有人的财富绝对均匀，"  << std::endl;
    std::cout << "基尼系数为1代表1个人掌握了社会所有的财富。"  << std::endl;
    std::cout << "基尼系数越小，代表社会财富分布越均匀；反之，代表社会财富分布越不均匀；"  << std::endl;
    std::cout << "在2022年，世界各国的平均基尼为0.44。目前普遍认为，"  << std::endl;
    std::cout << "当基尼系数达到0.5时，就意为着社会财富分布非常不均匀。"  << std::endl;
    std::cout << "社会可能陷入危机，比如大量的犯罪或社会动荡。"  << std::endl;
    std::cout << "测试开始......"  << std::endl;

    int n = 100;
    std::vector<double> money(n, 100);
    long t = 1;

    double gini = 0;
    do
    {
        experiment(money, t);
        gini = calc_gini(money);
        ++t;
    } while (gini <= 0.5);

    std::cout << "此时社会已经达到很危险的程度了！！！" << std::endl;
    std::cout << std::format("此时经历的轮数为：{}， 人数：{}\n", t, n);
    std::cout << std::format("此时社会实验的基尼系数为：{:.6f}.\n", gini);

    std::sort(money.begin(), money.end());
    for (int i = 0; i < money.size(); ++i)
    {
        std::cout << money[i] << " ";
        if (i && i % 10 == 0)
            std::cout << std::endl;
    }
}

int main()
{
    entry();
    return 0;
}

二进制和位运算

正数在计算机内存中的表示比较简单，就是原码的二进制表示

假设是4位，可以表示多少个数呢？ $2^4 = 16$
如果是无符号数 0 - 15；如果是有符号数，最高位固定1，后三位的可以表示 $2^3 = 8$ ，所以负数有8个；
非负数有8个。

负数计算过程

比如 -7，先计算 7 的二进制为：0111，减去1为：0110，取反为：1001
比如 -1，先计算 1 的二进制位：0001，减去1为：0000，取反为：1111
或者这样计算：-x= ~x + 1

根据二进制计算数值的过程

比如 0111，符号位是：0，非负数，直接进行进制运算： $2^0 + 2^1 + 2^2 + 0*2^3 = 7$
比如 1000，符号位是：1，负数，取反为：0111，加上1为：1000，直接进行进制运算为：8，所以为：-8
比如 1001，符号位是：1，负数，取反为：0110，加上1为：0111，直接进行进制运算为：7，所以为：-7

选择、冒泡、插入排序

选择排序：i ~ n-1 范围，找到最小值和 i 位置交换，然后 i+1 ~ n-1范围继续
冒泡排序：0 ~ i 范围，相邻位置较大的数滚下去，最大值最终来到 i 位置，然后在 0 ~ i-1 范围继续
插入排序：0 ~ i 范围上以及有序，新来的数从右向左滑到不在小的位置插入

二分搜索

在有序数组中查找特定的元素num存在还是不存在
在有序数组中查找>=num最左的位置
在有序数组中查找<=num最右的位置
二分搜索不一定发生在有序数组上（比如寻找峰值问题）

单双链表及其反转-堆栈诠释

按值传递，按引用传递
单，双链表的定义
根据反转功能，彻底从系统的角度解释链表是如何调整的
相关题目：
入门题目：
21. Merge Two Sorted Lists
206. Reverse Linked List
2. Add Two Numbers
86. Partition List

队列和栈-链表、数组的实现

队列的介绍
栈的介绍
队列的链表实现和数组实现
栈的数组实现
环形队列用数组实现
用栈实现队列
232. Implement Queue using Stacks
用队列实现栈
225. Implement Stack using Queues
最小栈
155. Min Stack

双端队列

双端队队列的介绍
双端队列用双链表的实现
双端队列用固定数组的实现
641. Design Circular Deque

二叉树及其三种遍历

二叉树的节点
二叉树的先序、中序、后序遍历
递归序加工出的三种序的遍历

二叉树的非递归三种遍历及其时间复杂度分析

用栈实现二叉树先序遍历
144. Binary Tree Preorder Traversal
用栈实现二叉树中序遍历
94. Binary Tree Inorder Traversal
用栈实现二叉树后序遍历
145. Binary Tree Postorder Traversal
遍历二叉树时间复杂度分析
a. 时间复杂度O(n)
b. 空间复杂度O(h)
c. 存在时间复杂度O(n),空间复杂度O(1)的方式，Morris遍历

递归和Master公式

从思想上理解递归
从实际上理解递归
任何递归函数，都一定可以改成非递归
递归改成非递归的条件
a. 工程上几乎一定要改，除非数据量很大递归深度也很小，归并排序，快速排序，线段树，平衡树
b. 算法笔试中能过就不用该
Master公式
a．所有子问题规模相同的递归才能用master公式，T(n）=aT(n/b）+O(n^c)，a、b、c都是常数
b．如果log(b,a）<c，复杂度为：O(n^c)
c．如果log(b,a）>c，复杂度为：0(n^log(b,a))
d．如果log(b,a）==c，复杂度为：0(n^clogn)
一个补充
T(n) = 2T(n/2) + O(nlogn),时间复杂度是O(n(logn)^2)

归并排序

912. Sort an Array

归并分治

1）思考一个问题在大范围上的答案，是否等于，左部分的答案+右部分的答案+跨越左右产生的答案
2）计算“跨越左右产生的答案”时，如果加上左、右各自有序这个设定，会不会获得计算的便利性
493. Reverse Pairs

随机快速排序

912. Sort an Array

随机选择算法

无序数组中寻找第K大的数或第K小的数
215. Kth Largest Element in an Array

堆结构和堆排序

912. Sort an Array

哈希表、有序表和比较器的用法

堆结构常见题

合并K个链表
23. Merge k Sorted Lists
线段最多重合问题
线段重合
让数组整体累加和减半的最少操作次数
2208. Minimum Operations to Halve Array Sum

基数排序

912. Sort an Array

重要排序算法总结

稳定性：同样大小的样本在排序后不改变原有的相对次序。总结如下表：

算法	时间	空间	稳定性
SelectSort	$O(N^2)$	$O(1)$	无
BubbleSort	$O(N^2)$	$O(1)$	有
InsertSort	$O(N^2)$	$O(1)$	有
MergeSort	$O(N*logN)$	$O(n)$	有
QuickSort	$O(N*logN)$	$O(1)$	无
HeapSort	$O(N*logN)$	$O(1)$	无
CountSort	$O(N)$	$O(M)$	有
RadixSort	$O(N)$	$O(M)$	有

异或运算哪些骚操作

异或运算的性质：

异或运算可理解为无进位相加
满足交换律、结合律
0^n = n, n^n = 0
整体异或和如果是x，整体中某个部分的异或和如果是y，那么剩下部分的异或和是x^y
a ^ b = c => a = c ^ b, b = c ^ a;
相关题目：

交换两个数（注意a, b 地址不能相同）

void swap_integers(int &a, int &b)
{
    b = a ^ b;
    a = a ^ b;
    b = a ^ b;
}

不用判断和比较，返回两个数的较大值

/*
 * n is 0 or 1.
 */
int flip(int n)
{
    return n ^ 1;
}
// 非负为1，负为0
int sign(int n)
{
    int bit = ((1 << 31) & n) == 0 ? 0 : 1;
    return flip(bit);
}

/*
 * This function has overflow risk.
 */
int max_v0(int a, int b)
{
    int c = a - b;
    int ra = sign(c);
    int rb = flip(ra);
    return a * ra + b * rb;
}
/*
 * better
 */
int max_v1(int a, int b)
{
    int c = a - b;
    int sa = sign(a);
    int sb = sign(b);
    int sc = sign(c);

    int diffab = sa ^ sb;
    int sameab = flip(diffab);

    int ra = diffab * sa + sameab * sc;
    int rb = flip(ra);

    return ra * a + rb * b;
}

找到缺失的数字
268. Missing Number
找到只出现一次的数字
136. Single Number
数组中有2个数出现了奇数次，其他的数都出现了偶数次，返回这2个出现了奇数次的数
260. Single Number III
数组中只有1种数出现次数少于m次，其他数都出现了m次，返回出现次数小于m次的那种数
137. Single Number II

位运算的骚操作

判断一个整数是不是2的幂
231. Power of Two
判断一个整数是不是3的幂
326. Power of Three
返回大于等于n的最小的2幂

int latest2pow(int n)
{
    if (n <= 1)
        return 1;
    --n;

    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}

区间[left，right]内所有数字&的结果
201. Bitwise AND of Numbers Range
反转一个二进制的状态，不是0变1、1变0，是逆序。超自然版
190. Reverse Bits
返回一个数二进制中有几个1。超自然版，看完佩服大牛的脑洞，能爽一整天
461. Hamming Distance

位图

位图原理：其实就是用bit组成的数组来存放值，用bit状态1、0代表存在、不存在，取值和存值操作都用位运算限制是必须为连续范围且不能过大。好处是极大的节省空间，因为1个数字只占用1个bit的空间。
2166. Design Bitset

位运算实现加减乘除

29. Divide Two Integers
代码如下：

int add(int a, int b)
{
    int ans = a;
    while (b)
    {
        ans = a ^ b;
        b = (a & b) << 1;
        a = ans;
    }
    return ans;
}

int negative(int a)
{
    return add(~a, 1);
}

int minus(int a, int b)
{
    return add(a, negative(b));
}

int multiply(int a, int b)
{
    int ans = 0;
    unsigned bu = b;
    while (bu)
    {
        if ((bu & 1))
            ans = add(ans, a);

        bu >>= 1;
        a <<= 1;
    }
    return ans;
}

// a != Integer.min, b != Integer.min
int div(int a, int b)
{
    int x = a < 0 ? negative(a) : a;
    int y = b < 0 ? negative(b) : b;

    int ans = 0;
    for (int i = 30; i >= 0; i = minus(i, 1))
    {
        if ((x >> i) >= y)
        {
            ans |= (1 << i);
            x = minus(x, y << i);
        }
    }
    return a < 0 ^ b < 0 ? negative(ans) : ans;
}

int divide(int a, int b)
{
    auto MIN = std::numeric_limits<int>::min();
    auto MAX = std::numeric_limits<int>::max();
    if (a == MIN && b == MIN)
        return 1;
    if (a != MIN && b != MIN)
        return div(a, b);
    if (b == MIN)
        return 0;
    if (b == negative(1))
        return MAX;

    a = add(a, b < 0 ? negative(b) : b);
    int ans = div(a, b);
    int offset = b > 0 ? negative(1) : 1;
    return add(ans, offset);
}

链表高频题目和必备技巧

返回两个无环链表相交的第一个节点
160. Intersection of Two Linked Lists
每k个节点一组翻转链表
25. Reverse Nodes in k-Group

ListNode* reverseKGroup(ListNode* head, int k) {
    if (head == nullptr || head->next == nullptr || k < 2)
        return head;

    auto tail = head;
    for (int i = 0; i < k; ++i)
    {
        if (tail == nullptr)
            return head;
        tail = tail->next;
    }
    ListNode *pre{nullptr};
    auto cur = head;
    while (cur != tail)
    {
        auto next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }

    head->next = reverseKGroup(tail, k);
    return pre;
}

复制带随机指针的链表
138. Copy List with Random Pointer
判断链表是否是回文结构。这个题的流程设计甚至是考研常用。快慢指针找中点。
234. Palindrome Linked List
返回链表的第一个入环节点。快慢指针找中点。
142. Linked List Cycle II

ListNode *detectCycle(ListNode *head) {
        auto slow = head;
        auto fast = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
                break;
        }
        if (fast == nullptr || fast->next == nullptr)
            return nullptr;
        slow = head;
        while (slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }

在链表上排序。要求时间复杂度0（n*1ogn)，额外空间复杂度0（1），还要求排序有稳定性
148. Sort List

ListNode* sortList(ListNode* head) {
    return sort_list(head, nullptr);
}

ListNode *sort_list(ListNode *head, ListNode *tail)
{
    if (head == nullptr)
        return head;
    if (head->next == tail)
    {
        head->next = nullptr;
        return head;
    }

    auto slow = head;
    auto fast = head;
    while (fast != tail && fast->next != tail)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    auto mid = slow;
    auto h1 = sort_list(head, mid);
    auto h2 = sort_list(mid, tail);

    return merge(h1, h2);
}

ListNode *merge(ListNode *h1, ListNode *h2)
{
    ListNode dummyhead;
    auto cur = &dummyhead;
    auto cur1 = h1;
    auto cur2 = h2;

    while (cur1 && cur2)
    {
        if (cur1->val <= cur2->val)
        {
            cur->next = cur1;
            cur1 = cur1->next;
        }
        else
        {
            cur->next = cur2;
            cur2 = cur2->next;
        }
        cur = cur->next;
    }

    if (cur1)
        cur->next = cur1;
    else if (cur2)
        cur->next = cur2;

    return dummyhead.next;
}

数据结构设计高频题

setAll功能的哈希表
设计有setAll功能的哈希表
实现LRU结构
146. LRU Cache
插入、删除和获取随机元素0(1)时间的结构
380. Insert Delete GetRandom O(1)
插入、删除和获取随机元素0(1)时间且允许有重复数字的结构
381. Insert Delete GetRandom O(1) - Duplicates allowed
快速获得数据流的中位数的结构
295. Find Median from Data Stream
最大频率栈
895. Maximum Frequency Stack
全0(1)的数据结构
432. All O`one Data Structure

二叉树高频题目-上-不含树型dp

二叉树的层序遍历
102. Binary Tree Level Order Traversal
二叉树的锯齿形层序遍历
103. Binary Tree Zigzag Level Order Traversal
二叉树的最大特殊宽度
662. Maximum Width of Binary Tree
求二叉树的最大深度、求二叉树的最小深度
104. Maximum Depth of Binary Tree
111. Minimum Depth of Binary Tree
二叉树先序序列化和反序列化
297. Serialize and Deserialize Binary Tree
二叉树按层序列化和反序列化
449. Serialize and Deserialize BST
利用先序与中序遍历序列构造二叉树
105. Construct Binary Tree from Preorder and Inorder Traversal
验证完全二叉树
958. Check Completeness of a Binary Tree
求完全二叉树的节点个数，要求时间复杂度低于 $O(n)$
222. Count Complete Tree Nodes

int countNodes(TreeNode* root) {
        if (root == nullptr)
            return 0;

        int level = 0;
        auto node = root;
        while (node->left)
        {
            node = node->left;
            ++level;
        }

        int low = 1 << level;
        int high = (1 << (level+1)) - 1;
        while (low < high)
        {
            int mid = (high - low + 1) / 2 + low;
            if (exists(root, level, mid))
                low = mid;
            else
                high = mid - 1;
        }
        return low;
    }

    bool exists(TreeNode *root, int level, int k)
    {
        int bits = 1 << (level-1);
        auto node = root;
        while (node && bits)
        {
            if ((k & bits) == 0)
                node = node->left;
            else
                node = node->right;
            bits >>= 1;
        }
        return node != nullptr;
    }

二叉树高频题目-下-不含树型dp

普通二叉树上寻找两个节点的最近公共祖先。
236. Lowest Common Ancestor of a Binary Tree
搜索二叉树上寻找两个节点的最近公共祖先
235. Lowest Common Ancestor of a Binary Search Tree
收集累加和等于aim的所有路径（递归恢复现场）
113. Path Sum II
验证平衡二叉树（树型dp沾边）
110. Balanced Binary Tree
验证搜索二叉树（树型dp沾边）
98. Validate Binary Search Tree
修剪搜索二叉树
669. Trim a Binary Search Tree
二叉树打家劫舍问题（树型dp沾边)
337. House Robber III

常见经典递归过程解析

返回字符串全部子序列，子序列要求去重。时间复杂度 $0(2^n*n)$
字符串的全部子序列
返回数组的所有组合，可以无视元素顺序，但要求去重。时间复杂度 $0(2^n*n)$
90. Subsets II
返回没有重复值数组的全部排列。时间复杂度 $0(n!*n)$
46. Permutations
返回可能有重复值数组的全部排列，排列要求去重。时间复杂度 $0(n!*n)$
47. Permutations II
用递归逆序一个栈。时间复杂度 $0(n^2)$

void reverse(std::stack<int> &stack)
{
    if (stack.empty())
        return ;

    auto val = bottom_out(stack);
    reverse(stack);
    stack.push(val);
}

int bottom_out(std::stack<int> &stack)
{
    auto val = stack.top();
    stack.pop();
    if (stack.empty())
        return val;

    auto next = bottom_out(stack);
    stack.push(val);
    return next;
}

用递归排序一个栈。时间复杂度 $0(n^2)$

int deep(std::stack<int> &);
int max(std::stack<int> &, int deep);
int times(std::stack<int> &, int max, int deep);
void down(std::stack<int> &, int max, int times, int deep);

void sort(std::stack<int> &stack)
{
    int d = deep(stack);
    while (d)
    {
        auto m = max(stack, d);
        auto t = times(stack, m, d);
        down(stack, m, t, d);
        d -= t;
    }
}


int deep(std::stack<int> &stack)
{
    if (stack.empty())
        return 0;
    auto top = stack.top();
    stack.pop();
    auto d = deep(stack) + 1;
    stack.push(top);
    return d;
}

int max(std::stack<int> &stack, int deep)
{
    if (deep == 0)
        return std::numeric_limits<int>::min();

    auto top = stack.top();
    stack.pop();
    auto restmax = max(stack, deep - 1);
    stack.push(top);
    return std::max(top, restmax);
}

int times(std::stack<int> &stack, int max, int deep)
{
    if (deep == 0)
        return 0;

    auto num = stack.top();
    stack.pop();
    auto resttimes = times(stack, max, deep - 1);
    stack.push(num);

    return (num == max ? 1 : 0) + resttimes;
}

void down(std::stack<int> &stack, int max, int times, int deep)
{
    if (deep == 0)
    {
        for (int i = 0; i < times; ++i)
            stack.push(max);
        return;
    }

    auto num = stack.top();
    stack.pop();
    down(stack, max, times, deep - 1);
    if (num != max)
        stack.push(num);
}

打印n层汉诺塔问题的最优移动轨迹。时间复杂度 $0(2^n)$

namespace hanoi {
void move(int n, char from, char to, char other);

void hanoi_do(int n)
{
    if (n <= 0)
        return ;
    std::cout << std::format("注意盘子是从小到大编号为1-{}，移动过程如下:\n", n);
    move(n, 'A', 'B', 'C');
}

void move(int n, char from, char to, char other)
{
    if (n == 1)
    {
        std::cout << std::format("圆盘: {}: {} -> {}\n", n, from, to);
        return ;
    }

    move(n-1, from, other, to);
    std::cout << std::format("圆盘: {}: {} -> {}\n", n, from, to);
    move(n-1, other, to, from);
}

void test_hanoi()
{
    int n = 3;
    hanoi_do(n);
}
/*
 * Output: 
 * 注意盘子是从小到大编号为1-3，移动过程如下:
 * 圆盘: 1: A -> B
 * 圆盘: 2: A -> C
 * 圆盘: 1: B -> C
 * 圆盘: 3: A -> B
 * 圆盘: 1: C -> A
 * 圆盘: 2: C -> B
 * 圆盘: 1: A -> B
 */
}

嵌套类问题的递归解题套路

含有嵌套的表达式求值。时间复杂度 $O(n)$
772. 基本计算器 III - 力扣（LeetCode）Plus会员
含有嵌套的字符串解码。时间复杂度 $O(n)$
394. Decode String
含有嵌套的分子式求原子数量。时间复杂度 $O(n)$
726. Number of Atoms

N皇后问题-重点是位运算的版本

[52. N-Queens II](https://leetcode.cn/problems/n-queens-ii/description
用位运算的方法（巧妙、常数时间快，推荐）

intcol：0．.i-1行皇后放置的位置因为正下方向延伸的原因，哪些列不能再放皇后
int1eft：0…i-1行皇后放置的位置因为左下方向延伸的原因，哪些列不能再放皇后
intright：0…i-1行皇后放置的位置因为右下方向延伸的原因，哪些列不能再放皇后
根据col、left、right，用位运算快速判断能放哪些列
把能放的列都尝试一遍，每次尝试修改3个数字表示当前的决策，后续返回的答案都累加返回

最大公约数、同余原理

878. Nth Magical Number
求最大公约数

欧几里得算法的过程：辗转相除法
正确性的证明过程见代码注释部分，我润色的证明过程非常好懂，不过直接记忆过程即可
求 $gcd(a,b)$ ，其中a>b，时间复杂度为 $O((loga)^3)$ ，时间复杂度证明略，这个复杂度足够好了
简单转化就可以求最小公倍数
更高效求最大公约数的Stein算法、由最大公约数扩展出的“裴蜀定理”，比赛同学有兴趣可以继续研究
不比赛的同学，哪怕你的目标是最顶级的公司应聘、还是考研，掌握这个只有一行的函数已经足够！

同余原理

绍背景
法、乘法每一步计算完后直接取模，减法则为 $(a-b+m)\%m$
要确保过程中不溢出，所以往往乘法运算的用long类型做中间变量
除法的同余需要求逆元，会在【扩展】课程里讲述，较难的题目才会涉及

对数器打表找规律的技巧

对数器打表找规律的过程

可以用最暴力的实现求入参不大情况下的答案，往往只需要最基本的递归能力
打印入参不大情况下的答案，然后观察规律
规律变成代码，就是最优解了

题目1：使用规格8和规格6的袋子买苹果问题

解法如题目2，不在展示代码；

题目2：A和B轮流吃草最终谁会赢

Onamespace whowineatinggrass {
/*
 * 草一共有n的重量，两只牛轮流吃草，A牛先吃，B牛后吃
 * 每只牛在自己的回合，吃草的重量必须是4的幂，1、4、16、64。。。
 * 谁在自己的回合正好把草吃完谁赢，根据输入的n，返回谁赢
 */
char whowin(int grassn);
char simple_f(int grassn, char cur);
char whowin_v(int grassn);

char whowin(int grassn)
{
    return simple_f(grassn, 'A');
}

char simple_f(int grassn, char cur)
{
    char enemy = cur == 'A' ? 'B' : 'A';
    if (grassn < 5)
        return ( grassn == 0 || grassn == 2 ) ? enemy : cur;

    int pick = 1;
    while (pick <= grassn)
    {
        if (simple_f(grassn - pick, enemy) == cur)
            return cur;

        pick *= 4;
    }

    return enemy;
}

char whowin_v(int grassn)
{
    if (((grassn % 5) & 1) == 0)
        return 'B';

    return 'A';
}

void test_who_win()
{
    for (int i = 0; i < 50; ++i)
    {
        std::cout << std::format("{}: {}\n", i, whowin(i));
        std::cout << std::format("{}: {}\n", i, whowin_v(i));

    }
}
}

题目3：判断一个数字是否是若干数量（数量>1)的连续正整数的和

namespace continuous_sum {
bool is_continuous_sum(int n)
{
    return n > 0 && n == (n & -n);
}

void test_continuous_sum()
{
    for (int i = 1; i < 100; ++i)
    {
        std::cout << std::format("{}: {}\n", i, is_continuous_sum(i) ? "T" : "F");
    }
}
}

题目4：要求只有一个长度>=2的回文子串，求所有长度为n的red字符串中好串的数量

/*
 * 可以用r、e、d三种字符拼接字符串，如果拼出来的字符串中
 * 有且仅有1个长度>=2的回文子串，那么这个字符串定义为"好串”
 * 1 7 1/ I/ 1///
 * 返回长度为n的所有可能的字符串中，好串有多少个
 * 结果对1000000007取模，1<=n<=10^9 示例：n =1，输出0 n=2，输出3  n=3，输出18
 */
namespace palindrome_string {
int count_better_str(int len)
{
    if (len == 1)
        return 0;
    if (len == 2)
        return 3;
    if (len == 3)
        return 18;

    return (long)(len + 1) * 6 % 1000'000'007;
}

void test_count_better_str()
{
    for (int i = 1; i < 100; ++i)
    {
        std::cout << std::format("{}: {}\n", i, count_better_str(i));
    }
}
}

根据数据量猜解法的技巧-天字第一号重要技巧

一个基本的事实

C/C++运行时间1s，java/python/go等其他语言运行时间1s~2s，对应的常数指令操作量是10^7～108，不管什么测试平台，不管什么cpu，都是这个数量级;
题目要给定各个入参的范围最大值，正式笔试、比赛的题目一定都会给，面试中要和面试官确认
对于自己设计的算法，时间复杂度要有准确的估计

这个技巧太重要了！既可以提前获知自己的方法能不能通过，也可以对题目的分析有引导作用！

题目1：最优的技能释放顺序
nowcoder消灭怪物
题目2：超级回文数的数目
906. Super Palindromes
9. Palindrome Number

前缀树原理和代码详解

前缀树的使用场景：需要根据前缀信息来查询的场景
前缀树的优点：根据前缀信息选择树上的分支，可以节省大量的时间
前缀树的缺点：比较浪费空间，和总字符数量有关前缀树的定制：pass、end等信息
LeetCode 1804. Implement Trie II (Prefix Tree)-Plus

前缀树的实现方式：
1）类描述的实现方式（动态结构）。不推荐！虽然最常用。

路的可能性范围较小，用固定数组实现路
路的可能性范围较大，用哈希表实现路

namespace prefix_tree {
class trie
{
public:
    trie() : root(new trie_node) {}

    void insert(std::string_view word)
    {
        auto node = root;
        node->pass++;
        for (int i = 0, idx; i < word.size(); ++i)
        {
            idx = word[i] - 'a';
            if (node->next[idx] == nullptr)
                node->next[idx] = new trie_node;
            node = node->next[idx];
            node->pass++;
        }
        node->end++;
    }

    [[nodiscard]]
    int count_words_equal_to(std::string_view word) const
    {
        auto node = root;
        for (char i : word)
        {
            auto idx = i - 'a';
            if (node->next[idx] == nullptr)
                return 0;
            node = node->next[idx];
        }
        return node->end;
    }

    [[nodiscard]]
    int count_words_starting_with(std::string_view prefix) const
    {
        auto node = root;
        for (int i = 0, idx; i < prefix.size(); ++i)
        {
            idx = prefix[i] - 'a';
            if (node->next[idx] == nullptr)
                return 0;
            node = node->next[idx];
        }
        return node->pass;
    }
    

    void erase(std::string_view word)
    {
        if (count_words_equal_to(word) > 0)
        {
            auto node = root;
            node->pass--;
            for (int i = 0, idx; i < word.size(); ++i)
            {
                idx = word[i] - 'a';
                if (--node->next[idx]->pass == 0)
                {
                    delete_nodes(node->next[idx], i, word);
                    node->next[idx] = nullptr;
                    return ;
                }
                node = node->next[idx];
            }
            --node->end;
        }
    }
private:
    struct trie_node
    {
        int pass{0};
        int end{0};
        trie_node *next[26]{};
    };

    static void delete_nodes(trie_node *node, int start, std::string_view word)
    {
        for (int i = start + 1, idx; i < word.size(); ++i)
        {
            idx = word[i] - 'a';
            auto p = node;
            if (node->next[idx])
                node = node->next[idx];
            else
                break;
            delete p;
        }
    }

    trie_node *root;
};
}

2）静态数组的实现方式。推荐！不仅笔试，就连比赛也能保证使用。

一切都是静态数组来实现，提交准备好够用的空间
如果路的可能性范围较大，就用每一位的信息建树。下节课前缀树的题目里展示
字典树的实现-nowcoder

namespace static_trie {
constexpr int N = 150000;

int trie[N][26];
int pass[N], end[N];
int cnt = 0;

void rebuild()
{
    for (int i = 1; i <= cnt; ++i)
    {
        std::fill_n(trie[i], 3, 0);
        pass[i] = end[i] = 0;
    }
    cnt = 1;
}

void insert(std::string_view word)
{
    int node = 1;
    pass[node]++;
    for (int i = 0, path; i < word.size(); ++i)
    {
        path = word[i] - 'a';
        if (trie[node][path] == 0)
            trie[node][path] = ++cnt;
        node = trie[node][path];
        pass[node]++;
    }
    end[node]++;
}

int search(std::string_view word)
{
    int node = 1;
    for (int i = 0, path; i < word.size(); ++i)
    {
        path = word[i] - 'a';
        if (trie[node][path] == 0)
            return 0;
        node = trie[node][path];
    }
    return end[node];
}


int prefix_number(std::string_view word)
{
    int node = 1;
    for (int i = 0, path; i < word.size(); ++i)
    {
        path = word[i] - 'a';
        if (trie[node][path] == 0)
            return 0;
        node = trie[node][path];
    }
    return pass[node];
}

void delete_word(std::string_view word)
{
    if (search(word))
    {
        int node = 1;
        for (int i = 0, path; i < word.size(); ++i)
        {
            path = word[i] - 'a';
            if (--pass[trie[node][path]] == 0)
            {
                trie[node][path] = 0;
                return;
            }
            node = trie[node][path];
        }
        end[node]--;
    }
}

void entry()
{
    int m, op;
    char str[25];
    scanf("%d", &m);
    rebuild();
    while (m--)
    {
        scanf("%d%s", &op, str);
        switch (op)
        {
            case 1:
                insert(str);
                break;
            case 2:
                delete_word(str);
                break;
            case 3:
                if (search(str))
                    printf("YES\n");
                else
                    printf("NO\n");
                break;
            case 4:
                printf("%d\n", prefix_number(str));
                break;
            default:
                break;
        }
    }
}
}

前缀树的相关题目

题目1：接头密匙-nowcoder
题目2：数组中两个数的最大异或值
421. Maximum XOR of Two Numbers in an Array
题目3 在二维字符数组中搜索可能的单词
212. Word Search II

构建前缀信息的技巧-解决子数组相关问题

前置知识：讲解026-哈希表的用法解决如下问题，时间复杂度0（n）

题目1：构建前缀和数组。快速解决子数组范围求和的问题
303. Range Sum Query - Immutable
题目2：构建前缀和最早出现的位置。返回无序数组中累加和为给定值的最长子数组长度
未排序数组中累加和为给定值的最长子数组长度-nowcoder
题目3：构建前缀和出现的次数。返回无序数组中累加和为给定值的子数组数量
560. Subarray Sum Equals K
题目4：构建前缀和最早出现的位置。返回无序数组中正数和负数个数相等的最长子数组长度
转化为 1，-1 求最长子数组和为0的最大长度
题目5：构建前缀和最早出现的位置。表现良好的最长时间段问题
1124. Longest Well-Performing Interval
题目6：构建前缀和余数最早出现的位置。移除的最短子数组长度，使得剩余元素的累加和能被p整除
1590. Make Sum Divisible by P
题目7：构建前缀奇偶状态最早出现的位置。每个元音包含偶数次的最长子串长度
1371. Find the Longest Substring Containing Vowels in Even Counts

一维差分与等差数列差分

一维差分：太简单了，没有理解难度
1109. Corporate Flight Bookings

等差数列差分问题描述：
一开始1~n范围上的数字都是0。接下来一共有m个操作。
每次操作：l_{r范围上依次加上首项s、末项e、公差d的数列最终1}n范围上的每个数字都要正确得到

等差数列差分的过程：
每个操作调用set方法
所有操作完成后在arr上生成两遍前缀和，即调用build方法 arr里就是最终1~n范围上的每个数字

void set(int l，int r，int s，int e, int d)
{ 
    arr[l]   += s;
    arr[l+1] += d - s; 
    arr[r+1] -= d + e;
    arr[r+2] += e; 
}

void build()
{
    for（int i = 1；i <= n；i++）
        arr[i] += arr[i - 1];
    for（int i = 1；i <= n；i++）
        arr[i] += arr[i - 1];
}

二维前缀和

304. Range Sum Query 2D - Immutable
1139. Largest 1-Bordered Square

目的是预处理出一个结构，以后每次查询二维数组任何范围上的累加和都是0（1）的操作

根据原始状况，生成二维前缀和数组sum，
sum[i][]：代表左上角（0，0)到右下角（i，j)这个范围的累加和
sum[i][j] += sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
查询左上角(a,b)到右下角（c,d)这个范围的累加和
sum[c][d] - sum[c][b-1] - sum[a-1][d] + sum[a-1][b-1];
实际过程中往往补第0行、第0列来减少很多条件判断。当然也可以不补。根据个人习惯决定。

滑动窗口技巧与相关题目

滑动窗口：维持左、右边界都不回退的一段范围，来求解很多子数组（串）的相关问题
滑动窗口的关键：找到范围和答案指标之间的单调性关系 (类似贪心)
滑动过程：滑动窗口可以用简单变量或者结构来维护信息

求解大流程：求子数组在每个位置开头或结尾情况下的答案（开头还是结尾在于个人习惯）
注意：
滑动窗口维持最大值或者最小值的更新结构
209. Minimum Size Subarray Sum
3. Longest Substring Without Repeating Characters
134. Gas Station
1234. Replace the Substring for Balanced String
992. Subarrays with K Different Integers
395. Longest Substring with At Least K Repeating Characters

双指针技巧与相关题目

设置两个指针的技巧，其实这种说法很宽泛，似乎没什么可总结的

有时候所谓的双指针技巧，就单纯是代码过程用双指针的形式表达出来而已。
没有单调性（贪心）方面的考虑
有时候的双指针技巧包含单调性（贪心）方面的考虑，牵扯到可能性的取舍。对分析能力的要求会变高。其实是先有的思考和优化，然后代码变成了双指针的形式。
所以，双指针这个“皮”不重要，分析题目单调性（贪心）方面的特征，这个能力才重要。常见的双指针

类型：

同向双指针
快慢双指针
从两头往中间的双指针
其他

922. Sort Array By Parity II
287. Find the Duplicate Number
42. Trapping Rain Water
881. Boats to Save People
11. Container With Most Water
475. Heaters
41. First Missing Positive

二分答案法与相关题目

二分答案法
1）估计最终答案可能的范围是什么
2）分析问题的答案和给定条件之间的单调性，大部分时候只需要用到自然智慧
3）建立一个f函数，当答案固定的情况下，判断给定的条件是否达标
4）在最终答案可能的范围上不断二分搜索，每次用f函数判断，直到二分结束，找到最合适的答案
875. Koko Eating Bananas
410. Split Array Largest Sum
719. Find K-th Smallest Pair Distance
2141. Maximum Running Time of N Computers

单调栈-上

单调栈最经典的用法是解决如下问题：
每个位置都求：
0）当前位置的左侧比当前位置的数字小，且距离最近的位置 在哪
1）当前位置的右侧比当前位置的数字小，且距离最近的位置 在哪
或者
每个位置都求：
0）当前位置的左侧比当前位置的数字大，且距离最近的位置 在哪
1）当前位置的右侧比当前位置的数字大，且距离最近的位置 在哪

用单调栈的方式可以做到：求解过程中，单调栈所有调整的总代价为0 $(n)$ ，单次操作的均摊代价为 $0(1)$

并查集-上

并查集的使用是如下的场景

一开始每个元素都拥有自己的集合，在自己的集合里只有这个元素自己
find(i)：查找i所在集合的代表元素，代表元素来代表i所在的集合
boolean isSameSet(a，b)：判断a和b在不在一个集合里
void union(a，b)：a所在集合所有元素与b所在集合所有元素合并成一个集合
各种操作单次调用的均摊时间复杂度为0(1)

并查集的两个优化，都发生在find方法里

扁平化 (一定要做)
小挂大 (可以不做，原论文中是秩的概念，可以理解为粗略高度或者大小)

并查集时间复杂度的理解
作为如此简单、小巧的结构

感性理解单次调用的均摊时间复杂度为O(1)即可，其实为α(n)，阿克曼函数。
当 $n=10^{ 80 }$ 次方即可探明宇宙原子量，α（n）的返回值也不超过6，那就可以认为是O(1)

并查集-下

并查集的小扩展

可以定制信息：并查集目前有多少个集合，以及给每个集合打上标签信息
相关题目
947. Most Stones Removed with Same Row or Column
2092. Find All People With Secret
2421. Number of Good Paths

洪水填充

前置知识：讲解038-常见经典递归过程解析，其中的带路径的递归过程解析

洪水填充是一种很简单的技巧，设置路径信息进行剪枝和统计，类似感染的过程路径信息不撤销，来保证每一片的感染过程可以得到区分
看似是暴力递归过程，其实时间复杂度非常好，遍历次数和样本数量的规模一致
相关题目
200. Number of Islands
130. Surrounded Regions
827. Making A Large Island
803. Bricks Falling When Hit

建图、链式前向星、拓扑排序

前置知识：讲解013-数组方式实现队列、讲解019-算法笔试更推荐静态空间的方式、025-堆结构

有向Vs无向、不带权Vs带权。入参一般为节点数量n和所有的边或者直接给图建图的三种方式，我们图解一下！

邻接矩阵 (适合点的数量不多的图)
邻接表 (最常用的方式)
链式前向星(空间要求严苛情况下使用。比赛必用，大厂笔试、面试不常用)

【必备】课程里涉及图的内容：

建图、链式前向星、拓扑排序、最小生成树、bfs、双向广搜
最短路(Dijkstra、A*、Floyd、Bellman-Ford、SPFA)

拓扑排序

每个节点的前置节点都在这个节点之前
要求：有向图、没有环
拓扑排序的顺序可能不只一种。拓扑排序也可以用来判断有没有环。
- 在图中找到所有入度为0的点
- 把所有入度为0的点在图中删掉，重点是删掉影响！继续找到入度为0的点并删掉影响
- 直到所有点都被删掉，依次删除的顺序就是正确的拓扑排序结果
- 如果无法把所有的点都删掉，说明有向图里有环

相关题目
210. Course Schedule II
936. Stamping The Sequence

拓扑排序的扩展技巧

重要技巧：
利用拓扑排序的过程，上游节点逐渐推送消息给下游节点的技巧
相关题目
851. Loud and Rich
2050. Parallel Courses III
2127. Maximum Employees to Be Invited to a Meeting

最小生成树

最小生成树：在无向带权图中选择择一些边，在保证联通性的情况下，边的总权值最小
最小生成树可能不只一棵，只要保证边的总权值最小，就都是正确的最小生成树
如果无向带权图有 $n$ 个点，那么最小生成树一定有 $n-1$ 条边
常用算法

Kruskal算法（最常用）
- 把所有的边，根据权值从小到大排序，从权值小的边开始考虑
- 如果连接当前的边不会形成环，就选择当前的边
- 如果连接当前的边会形成环，就不要当前的边
- 考察完所有边之后，最小生成树的也就得到了
Prim算法 (不算常用)
1. 解锁的点的集合叫set（普通集合）、解锁的边的集合叫heap（小根堆）。set和heap都为空。
2. 可从任意点开始，开始点加入到set，开始点的所有边加入到heap
3. 从heap中弹出权值最小的边e，查看边e所去往的点x
  - 如果x已经在set中，边e舍弃，重复步骤3
  - 如果x不在set中，边e属于最小生成树，把x加入set，重复步骤3
4. 当heap为空，最小生成树的也就得到了

宽度优先遍历及其扩展

单源、多源宽度优先遍历基本过程
01bfs，宽度优先遍历与双端队列结合宽度优先遍历与优先级队列结合
宽度优先遍历与深度优先遍历结合，去生成路径

宽度优先遍历基本内容

bfs的特点是逐层扩散，从源头点到目标点扩散了几层，最短路就是多少
bfs可以使用的特征是任意两个节点之间的相互距离相同（无向图）
bfs开始时，可以是单个源头、也可以是多个源头
bfs频繁使用队列，形式可以是单点弹出或者整层弹出
bfs进行时，进入队列的节点需要标记状态，防止同一个节点重复进出队列
bfs进行时，可能会包含剪枝策略的设计
1162. As Far from Land as Possible- 地图分析
 691. Stickers to Spell Word- 贴纸拼词

01bfs算法

distance[i]表示从源点到i点的最短距离，初始时所有点的distance设置为无穷大
源点进入双端队列，distance[源点]=0
双端队列头部弹出 ×,
- 如果x是目标点，返回distance[x]表示源点到目标点的最短距离
- 考察从x出发的每一条边，假设某边去y点，边权为w
  - 如果 distance[y］ >distance[x］ + w，处理该边；否则忽略该边
  - 处理时，更新distance[y］= distance[x］ + w
    如果w==0，y从头部进入双端队列。继续重复步骤3
    如果w==1，y从尾部进入双端队列。继续重复步骤3
双端队列为空停止

Dijkstra算法、分层图最短路

从递归入手一维动态规划

509. Fibonacci Number- 斐波那契数
 983. Minimum Cost For Tickets- 最低票价
 91. Decode Ways- 解码方法I
639. Decode Ways II- 解码方法II
264. Ugly Number II- 丑数II
32. Longest Valid Parentheses- 最长有效括号
 467. Unique Substrings in Wraparound String- 环绕字符串中唯一的子字符串
 940. Distinct Subsequences II- 不同的子序列II

从递归入手二维动态规划

64. Minimum Path Sum- 最小路径和
 79. Word Search- 单词搜索 (无法改成动态规划）
1143. Longest Common Subsequence- 最长公共子序列
 516. Longest Palindromic Subsequence- 最长回文子序列
 329. Longest Increasing Path in a Matrix- 矩阵中的最长递增路径
 115. Distinct Subsequences- 不同的子序列
 72. Edit Distance- 编辑距离
 97. Interleaving String- 交错字符串

从递归入手三维动态规划

大体过程都是：

写出尝试递归
记忆化搜索（从顶到底的动态规划）
严格位置依赖的动态规划（从底到顶的动态规划）
空间、时间的更多优化

474. Ones and Zeroes-一和零（多维费用背包)
879. Profitable Schemes-盈利计划（多维费用背包）
688. Knight Probability in Chessboard-骑士在棋盘上的概率
 2435. Paths in Matrix Whose Sum Is Divisible by K-矩阵中和能被K整除的路径
 87. Scramble String-扰乱字符串

子数组最大累加和问题与扩展-上

53. Maximum Subarray-子数组最大累加和
 198. House Robber-不能选相邻元素的最大累加和问题
 918. Maximum Sum Circular Subarray-环形数组的子数组最大累加和
 213. House Robber II-环形数组中不能选相邻元素的最大累加和
 2560. House Robber IV-打家劫舍IV
面试题 17.24. Max Submatrix LCCI-子矩阵最大累加和问题

子数组最大累加和问题与扩展-下

152. Maximum Product Subarray-乘积最大子数组
大厂笔试：子序列累加和必须被7整除的最大累加和

namespace max_sum_divided_by7 {
// 子序列累加和必须被7整除的最大累加和
// 给定一个非负数组nums
// 可以任意选择数字组成子序列，但是子序列的累加和必须被7整除
// 返回最大累加和
class solution
{
public:
    static int max_sum(std::vector<int> &nums)
    {
        int n = static_cast<int>(nums.size());
        // dp[i][j]:
        // nums.前i个数形成的子序列一定要做到，子序列累加和%7==j
        // 这样的子序列最大累加和是多少
        // 注意：dp[i][j]==-1代表不存在这样的子序列
        std::vector<std::vector<int>> dp(n + 1, std::vector<int>(MOD, -1));
        dp[0][0] = 0;
        for (int i = 1, x, curmod, need; i <= n; ++i)
        {
            x = nums[i-1];
            curmod = nums[i-1] % MOD;
            for (int j = 0; j < MOD; ++j)
            {
                dp[i][j] = dp[i-1][j];
                need = (j - curmod + MOD) % MOD;
                if (dp[i-1][need] != -1)
                    dp[i][j] = std::max(dp[i][j], dp[i-1][need] + x);
            }
        }
        return dp[n][0];
    }
private:
    static constexpr int MOD = 7;
};
}

大厂笔试：魔法卷轴

namespace magic_scroll_problem {
// 魔法卷轴
// 给定一个数组nums，其中可能有正、负、0
// 每个魔法卷轴可以把nums中连续的一段全变成0 你希望数组整体的累加和尽可能大
// 卷轴使不使用、使用多少随意，但一共只有2个魔法卷轴
// 请返回数组尽可能大的累加和
class solution
{
public:
    static int max_sum(std::vector<int> &nums)
    {
        int n = static_cast<int>(nums.size());
        if (n == 0)
            return 0;
        // 情况1：完全不使用卷轴
        int p1 = 0;
        for (auto x : nums)
            p1 += x;
        // prefix[i]：0~i范围上一定要用1次卷轴的情况下，0~i范围上整体最大累加和多少
        std::vector<int> prefix(n);
        // 每一步的前缀和
        int sum = nums[0];
        // maxpresum：之前所有前缀和的最大值
        int maxpresum = std::max(0, nums[0]);
        for (int i = 1; i < n; ++i)
        {
            prefix[i] = std::max(prefix[i-1] + nums[i], maxpresum);
            sum += nums[i];
            maxpresum = std::max(maxpresum, sum);
        }
        // 情况二：必须用1次卷轴
        int p2 = prefix[n-1];
        // suffix[i]：i~n-1范围上一定要用1次卷轴的情况下，i~n-1范围上整体最大累加和多少
        std::vector<int> suffix(n);
        sum = nums[n-1];
        maxpresum = std::max(0, nums[n-1]);
        for (int i = n - 2; i >= 0; --i)
        {
            suffix[i] = std::max( suffix[i+1] + nums[i], maxpresum );
            sum += nums[i];
            maxpresum = std::max(sum, maxpresum);
        }
        // 情况二：必须用2次卷轴
        int p3 = std::numeric_limits<int>::min();
        for (int i = 1; i < n; ++i)
            p3 = std::max(p3, prefix[i-1] + suffix[i]);

        return std::max(p1, std::max(p2, p3));
    }
};
}

689. Maximum Sum of 3 Non-Overlapping Subarrays-三个无重叠子数组的最大和
大厂笔试：可以翻转1次的情况下子数组最大累加和

namespace max_sum_reverse {
// 可以翻转1次的情况下子数组最大累加和给定一个数组nums，
// 现在允许你随意选择数组连续一段进行翻转，也就是子数组逆序的调整
// 比如翻转[1，2,3，4，5，6]的[2~4]范围，得到的是[1,2，5，4,3，6]
// 返回必须随意翻转1次之后，子数组的最大累加和
class solution
{
public:
    static int max_sum(std::vector<int> &nums)
    {
        int n = static_cast<int>(nums.size());
        // start[i]：所有必须以i开头的子数组中，最大累加和是多少
        std::vector<int> start(n);
        start[n-1] = nums[n-1];
        for (int i = n - 2; i >= 0; --i)
        {
            start[i] = nums[i] + std::max(0, start[i+1]);
        }
        int ans = start[0];
        //end：子数组必须以i结尾，其中的最大累加和
        int end = nums[0];
        int maxend = nums[0];
        // maxEnd:
        // 0~i-1范围上
        // 子数组必须以0结尾，其中的最大累加和
        // 子数组必须以1结尾，其中的最大累加和
        // ...
        // 子数组必须以i-1结尾，其中的最大累加和
        // 所有情况中，最大的那个累加和就是maxEnd
        for (int i = 1; i < n; ++i)
        {
            // maxend       i...
            // 枚举划分点：  i...
            ans = std::max(ans, maxend + start[i]);
            //子数组必须以i结尾，其中的最大累加和
            end = nums[i] + std::max(0, end);
            maxend = std::max(end, maxend);
        }
        ans = std::max(ans, maxend);
        return ans;
    }
};
}

最长递增子序列问题与扩展

300. Longest Increasing Subsequence-最长递增子序列
 354. Russian Doll Envelopes-俄罗斯套娃信封问题
 2111. Minimum Operations to Make the Array K-Increasing-使数组K递增的最少操作次数
 646. Maximum Length of Pair Chain-最长数对链

01背包、有依赖的背包

01背包：每个物品要和不要两种可能性展开
有依赖的背包：多个物品变成一个复合物品（互斥），每件复合物品要和怎么要多种可能性展开
不能用01背包来解，但是非常重要的问题：非负数组前k个最小的子序列和问题

01背包（模版）
bytedance-006. 夏季特惠
 494. 目标和
 1049. 最后一块石头的重量 II
有依赖的背包（模版）

贪心经典题目专题1

狭义的贪心
每一步都做出在当前状态下最好或最优的选择，从而希望最终的结果是最好或最优的算法
广义的贪心
通过分析题目自身的特点和性质，只要发现让求解答案的过程得到加速的结论，都算广义的贪心

179. 最大数
 1029. 两地调度
 1553. 吃掉 N 个橘子的最少天数
 253. 会议室 II - 力扣（LeetCode-Plus）
630. 课程表 III
1167. 连接木棍的最低费用 - 力扣（LeetCode-Plus）
LCR 132. 砍竹子 II
1353. 最多可以参加的会议数目
 502. IPO
题目6 加入差值绝对值直到长度固定
给定一个非负数组arr，计算任何两个数差值的绝对值
如果arr中没有，都要加入到arr里，但是只加一份然后新的arr，继续计算任何两个数差值的绝对值如果arr中没有，都要加入到arr里，但是只加一份一直到arr大小固定，返回arr最终的长度
来自真实大厂笔试，没有在线测试，对数器验证.

namespace AbsoluteValueAddToArray {
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int lenof(std::vector<int> &arr)
{
    int max = 0;
    //找到任意一个非0的值
    int gcd = 0;
    for (auto num : arr)
    {
        max = std::max(max, num);
        if (num)
            gcd = num;
    }
    if (gcd == 0)
        return (int)arr.size();
    std::unordered_map<int, int> cnts;
    for (auto num : arr)
    {
        if (num)
            gcd = AbsoluteValueAddToArray::gcd(gcd, num);
        cnts[num]++;
    }
    int ans = max / gcd;
    int maxcnt = 0;
    for (auto [ key, val ] : cnts)
    {
        if (key)
            ans += cnts[key] - 1;
        maxcnt = std::max(maxcnt, cnts[key]);
    }
    ans += cnts[0] > 0 ? cnts[0] : (maxcnt > 1 ? 1 : 0);
    return ans;
}
}

581. 最短无序连续子数组
 632. 最小区间
 1675. 数组的最小偏移量
 781. 森林中的兔子
 2449. 使数组相似的最少操作次数
 1121. 将数组分成几个递增序列 - 力扣（LeetCode）
871. 最低加油次数
 45. 跳跃游戏 II
1326. 灌溉花园的最少水龙头数目

KMP算法原理和代码详解

s1字符串是否包含s2字符串，如果包含返回s1中包含s2的最左开头位置，不包含返回-1
暴力方法就是s1的每个位置都做开头，然后去匹配s2整体，时间复杂度O(n*m)
KMP算法可以做到时间复杂度 $O(n+m)$
KMP算法详解
1）理解next数组的定义，定义是一切的关键，不包括当前字符，前面字符串前缀和后缀的最大匹配长度（不含整体）
2）假设已经有了next数组，详解匹配过程是如何得到加速的，加速过程有2个理解核心
3）理解了匹配主流程之后，详解next数组如何快速生成，不停跳跃的过程有1个理解核心
4）KMP算法代码详解，主流程+next数组生成
5）时间复杂度0(n)的证明，直接从代码层次就可以分析出来，分析方式好理解，但是比较特别
KMP算法的相关题目
28. 找出字符串中第一个匹配项的下标
 572. 另一棵树的子树

AC自动机原理、优化

AC自动机原理讲解
自动机又叫确定有限状态自动机，是对信号序列进行判定的数学模型比如，判定s1是否包含s2、判定s是否是回文，等等;自动机并不是具体的算法、数据结构，只是数学模型，更多是概念上的内容每种自动机实现方式可能有多种
AC自动机中对于fail指针的理解，涉及KMP算法
AC自动机中防止fail指针绕圈的优化，涉及三个场景经过优化后
建立AC自动机+遍历文章，总的时间复杂度为O（所有目标字符串的总字符数量+文章长度）