leetcode 记录 day1

记录一下刷题过程中遇到的一些值得思考的点，以便之后复习用。

同时回顾一下每天遇到的问题，来重新整理自己的思路。

题目1

求数组中的波谷，但是波谷要满足一定的长度

分别求出来每一个位置上，最长的非递增序列和非递减序列的长度。最后遍历一遍就可以

题目2

对于每一个位置，求出数组中所有数除去当前数的乘积

这个最简单的方法就是求出前缀积和后缀积，然后单独计算就行

一个优化是可以只用一个变量来保存前缀积或后缀积，然后给对应的位置乘上贡献即可

题目3

投n个骰子，问每种点数出现的概率是多少

设dp[i, j]为当前投了i个骰子，点数为j的概率

转移就是dp[i, j] = sum(dp[i - 1, j - k]) * (1 / 6) where 1 <= k <= 6

即当前骰子的点数为k，总点数为j，那么就从前面骰子中的j - k转移来就行

题目4

字符串转化成整数，这个比较容易，模拟就行

题目5

求数据流中的中位数

这个有点像以前的一道题叫黑匣子

可以转化为一个一般化的问题就是求第k大

但是不一样的是数据是由数据流给出来的，所以不能离散化后用权值bit去求kth

当然了可以维护一个平衡树

更简单的方法是维护两个堆，一个堆的大小就是k，存最大的k个元素

当新的元素加入的时候，如果他比最大的k个元素中最小的那个还大，那么他就可以把最小的那个挤到另一个堆中

这样我们就可以用两个堆把数据话分开

题目6

求逆序对

离散化之后用树状数组

在这贴一下代码吧，感觉之后会比较常用

class Solution {
public:
    vector<int> bit;
    int lowbit(int x) {
        return x & -x;
    }
    void add(int pos, int x) {
        for (int i = pos; i < bit.size(); i += lowbit(i)) {
            bit[i] += x;
        }
    }
    int sum(int pos) {
        int ans = 0;
        for (int i = pos; i; i -= lowbit(i)) {
            ans += bit[i];
        }
        return ans;
    }
    int reversePairs(vector<int>& nums) {
        int n = nums.size();

        vector<int> discrete = nums;
        sort(discrete.begin(), discrete.end());
        discrete.erase(unique(discrete.begin(), discrete.end()), discrete.end());

        for (auto &x : nums) {
            // make range to [1, xx]
            x = lower_bound(discrete.begin(), discrete.end(), x) - discrete.begin() + 1;
        }

        bit = vector<int> (discrete.size() + 1);
        int ans = 0;

        for (int i = n - 1; i >= 0; i--) {
            ans += sum(nums[i] - 1);
            add(nums[i], 1);
        }

        return ans;
    }
};

题目7

滑动窗口最大值

最简单的做法就是用map或者set这样的平衡树，可加可减可以求最值

还可以用单调队列来获得更好的复杂度，因为滑动窗口本身就是一个固定长度的队列，我们维护一下队列中的单调性

当一个新的元素加入进来的时候，那么在队列中所有比他小的元素都不可能成为最大值，因为他们必定会被先pop出去，我们就直接pop掉这些元素就行

所以维护的是一个单调递减的队列，队首永远是最大值

题目8

正则表达式匹配

由于有*，所以每次匹配的字符个数是不确定的，要用dp来解决

设dp[i, j]为当前s匹配到i，p匹配到j的时候是否可以匹配成功

如果当前p[j]是*的话，就要检查p[j - 1]是不是可以匹配s[i]

首先可以确定的情况是*代表0个字符，那么dp[i, j]就可以从dp[i, j - 2]继承过来，表示去掉这两个字符