随笔

今儿休息的不错。中午吃的重庆火锅，晚上吃的鱼香肉丝。今天还是以算法为主。
数学考研辅导教材让我有点失望，简单的地方太基础，复杂的地方又有点简略，而且有点只见树木不见森林。我今天又花了200元买了普林斯顿的微积分，MIT的线性代数和一本概率导论。也是趁这个机会再学习一下，把基础打牢打扎实。估计7月6日就送到了。
王道的计算专业教材让我太失望了，错误太多，有很多离谱的话，比如“高级语言的效率一定比低级语言低”等。把它当成真题集看看还行，要是以它为准复习我觉得不行。我还是觉得csapp不错，打算每天看20页，差不多月底就看完了。
今天算法主要总结三个，动态规划，寻找缺失的第一个正数，KMP。动态规划简略一些，主要讲讲遇到的题。
先从最简单的first-missing-positive开始。

缺失的第一个正数

本题也是18年统考的一道题。很简单就能想到o(n)算法，类似于桶排序的思路。一个正数一个坑。然而这里用了一点巧方法降低空间复杂度到常数，那就是交换。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int size = nums.size();
        for (int i = 0; i < size; i++) 
            while (nums[i] > 0 && nums[i] <= size && nums[nums[i] - 1] != nums[i])
                swap(nums[i], nums[nums[i] - 1]);
        for (int i = 0; i < size; i++) 
            if (nums[i] != i + 1) 
                return i + 1;
        return size + 1;
    }
};

简单来说，如果把当前元素换到对应的坑中去，直到不能换为止。最后找找第一个没有匹配上的坑就可以了。在交换的时候可能会反复交换，对于这种情况记得判断一下。总体来说比较简单。

动态规划

最长有效括号问题。这个题读错题了，状态方程就写错了，离谱。没啥好说的。https://leetcode-cn.com/problems/longest-valid-parentheses/
这个还有点巧妙，dp[i]表达的是以i结尾的最长有效括号串。最后o(n)就可以解决问题。

class Solution {
public:
    int longestValidParentheses(string s) {
        int ans = 0, n = s.length();
        vector<int> dp(n, 0);
        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                ans = max(ans, dp[i]);
            }
        }
        return ans;
    }
};

KMP

累了，不想写了。KMP也没写代码。留到明天吧。
值得一提的是next数组。next[i] 表示 P[0] ~ P[i] 这一个子串，使得前k个字符恰等于后k个字符的最大的k。换句话说，和前缀一致的后缀长度。根据这个信息可以最大化移动。
贴个知乎连接https://www.zhihu.com/question/21923021/answer/1032665486?utm_source=qq&utm_medium=social&utm_oi=74678236348416&utm_content=sec

洛谷

感觉leetcode不错，但是没有洛谷有意思。又回去刷洛谷了。以后leetcode每天一道打卡一道难题，洛谷两道题。先这样。等到轻松切leetcode难题时再说其他打算。
OI和leetcode风格还是不太一样，我写leetcode挺吃力，主要是对vector等不太熟悉。但是OI中c+stl我还可以，就还比较愉快。今天看了篇csdn，简单来说关闭流同步后cin和cout比cstdio要快。另外注意不要用endl，要用'\n'就可以直接起飞。cin.tie(NULL)也可以尝试。
今天还看到两个东西：莫比乌斯反演与迪利克雷卷积。有空研究一下。