Just for Life.

之前从未意识到位运算的强大威力，认为与或非只存在大一 C 语言的考试或单片机的设计中，直到今天才发现我错了。做一个常用的位运算和数学运算的整理。

听到滑动窗口这个词，让我想起了计算机网络中的 TCP 传输和拥塞控制，可惜时隔多年还给老师了，那老师讲课还很不错。我的大部分本科老师都有着很多年的工作经验，并不像部分硕博留校那种只擅长验证玩具理论和咬文嚼字，而从未到实际环境中实习过一次。所以他们讲课十分形象具体，结合理论和实际环境告诉你这是个什么东西。

说远了，回到正题。滑动窗口一般用于求接子串中满足某种情况的最值，可以简单的划分为三类：

1. 给一个字符串，求满足条件的最长子串
2. 给两个字符串，求其中一个字符串是否能覆盖另一个字符串
3. 给定一个数组和窗口大小，窗口没滑动一次，求一次最值

今晚翻了一下 todo list，发现这个条目堆积在未完成列表的末尾，于是来学习一下 C++ 中的四种类型转化方式，而 C++ 的复习也告一段落。我知道我还差得很远，等某天 C++ 功底足够深厚，来写一下 C++ 的内存模型。

之前没有很留意，没想到大一学过的数组也能有很多精彩的算法题。本文收录了数组类算法常见的：前缀和、差分数组、常数时间查找和删除数组元素和数组去重问题。

• 前缀和数组：用于频繁求解给定区间内，数组元素的和
• 差分数组：用于频繁更改给定区间内数组元素的取值，最后得到数组

前面两个侧重频繁修改数组，常规模拟算法必然超时。而至于常数时间内查找和删除数组元素，数组元素去重已经是固定要求的题目了，文末直接给出题解。

栈有着广泛的应用，比如逆波兰表达式，表达式求值，迷宫问题求解，程序调用等，不过这些问题今天都不涉及哈哈哈哈。关于程序执行期间，各个函数的相互调用使用的调用栈，可以参考这里。

单调栈属于栈的具体应用，而非栈这种数据结构的简单使用。此类问题一般用于求解以下场景：序列中某个元素的下一个最大元素，元素间的最大跨度，维持某一状态持续的最长时间等。以序列 [2,1,3,4] 为例，1 的下一个最大元素就是 3，而不是 4；最大上升的跨度为从 2 到 4，跨越了 2 个数。对于这种问题都可以用单调栈求解。

动态规划作为算法中较难的部分，还是下定决心慢慢整理。人生建议：遇到太难的动态规划，建议直接放弃。动态规划解题也有技巧，一般而言题目的问题都是：移动最少的次数到达终点。此时我们只需要：

1. 设置 dp 数组，数组大小一般和输入相同，但细节需要微操。dp[i] 的含义是，到达 i 的最少次数
2. 对 dp 数组进行初始化，即开始动态规划时，起始所需的次数，一般为 0，不过也有特殊情况
3. dp 的转移，如何从上一状态计算当前状态

掌握这三点，一般难度的动态规划是可以做出来的。

算法继续整理系列之区间问题。这类问题可以总结或者变化为：给定多个区间，求满足覆盖范围的最小相交区间的数量。一般而言都是：题目给定一个乱序的区间。我们需要对区间进行排序调整和统计结果，来满足题目条件。其中变化的部分只有如何处理相交区间，因此整理一个通用的算法模板。