3.20 字节笔试总结

1. 除字母外，所有字符均可变成 '*'

2. 字母大小写不敏感

3. 求是否能在有限次数交换位置，使得原字符串变成回文串

其实就是包含 '*' 和 各种字母的字符串，判断能否变成回文串；最多一种字符数量为奇数，则可以构成回文串

1. m 天，n 补给站

2. a 第几天，b 该补给站粮食价格

3. 0 ~ n 代表第 0 ~ n 经过的补给站

4. 求最少花多少钱，能到达第 m 天

样例：

5 4

0 2

1 3

2 1

3 2

从后往前暴力水了 80；没往单调栈上想，其实证明一下就够了

单调栈：从后往前，对于每一个补给站找后面第一个更便宜的补给站
1. 为什么？
    [1] 假设当前在 i 号店；后面有 j 号店、k 号店更便宜
    [2] 如果选择到 k 号店，则花费：vi * (k - i) = vi * (j - i) + vi * (k - j)
    [3] 如果选择到 j 号店，则花费：               vi * (j - i) + vj * (k - j)
    vi > vj 所以 [2] 的花费 > [2] 的花费恒成立
2. 一个怎样的单调栈？
    [1] 单调递增，保证了栈顶会是前面补给站后面第一个更便宜的补给站
    [2] 从后往前，遇到更便宜的补给站，直接计算当前补给站到终点的花费，弹栈；
   [3] 每次计算花费：当前补给站到栈顶补给站的花费 + 栈顶补给站到终点的花费

并查集没啥好说的

1. 给定一个字符串

2. 给出一组 [l, r]

3. 将这些区间内的字符，大小写转换

暴力水了 50

差分：对于数组 a[n]，差分即为 div[i] = a[i] - a[i - 1]
差分常用来计算区间处理相关值

    [1] 由 div[i] = a[i] - a[i - 1]；得 a[i] = div[i] + a[i - 1]。
    [2] 对 a[i]、a[i - 1] 同时 + x，即 a[i] + x、a[i - 1] + x；可以发现 div[i] = a[i] - a[i - 1] 不变 -> a[i] = div[i] + a[i - 1] + x。
    [3] div[i - 1] = a[i - 1] - a[i - 2] + 5；div[i + 1] = a[i + 1] - a[i] - 5。
    [4] 由上，差分数组除了左边界、右边界 + 1，其他位置均不变。
    所以对于区间 [p, q] 所有位置 + x；只要知道首位置新值以及差分数组，即可求得全部位置新值