3193.统计逆序对的数目 &无重复字符的最长子串

3193 统计逆序对的数目

思路：

首先将问题分解为子问题，考虑第i位放什么，如示例1整个排列[0，1，2]，恰好有2个逆序对，分情况讨论
● 末尾元素为0，前面两个元素(1,2)都会与0组成一对逆序对，也就是增加两点贡献值，此时[1，2]还需要贡献0（2-2)对贡献值，
● 末尾元素为1，前面两个元素(0,2)中2可以与1组成一对逆序对，贡献值为1，此时[0,2]还需要贡献1(2-1)贡献值。
● 末尾元素为2，前面两个元素(0,1)中没有可以与2组成逆序对的，贡献值为0，此时[0,1]还需要贡献2(2-0)贡献值。

以此类推，i=1时，我们不需要知道排列中的元素是那些，只需要知道排列长度，以及需要构造出多少逆序对。
构造函数dfs(end,cnt)，用于计算排列逆序对为cnt且满足requirements的排列[0...end]的个数，从示例一中得，dfs(2,2)=dfs(1,0)+dfs(1,1)+dfs(1,2)得递推公式，一般化对公式：

● 如果end-1在requirements有所要求，且对应得逆序对要求数量为r，那么我们计算dfs(end,cnt),此时最后一个元素(end)的取值最多只有一种可能，(因为end-1位置要求了r个逆序对，在end位置位置上，我们想要cnt个逆序对，所以最后一个元素需要产生cnt-r个逆序对，所以最多一种可能)。
如果0<=cnt-r<=end也就是r<=cnt<=end+r就说明有一个数放在end位置上能符合条件，dfs(end,cnt)=dfs(end-1,r);否则就说明不存在这种情况，dfs(end,cnt)=0
● 如果end-1不在requirements的要求中，那么我们需要遍历末尾元素所有的可能性，及遍历的范围为$$(0~min(end,cnt))$$, 递推公式$$dfs(end,cnt)=\sum_{i=0}^{min(end,cnt)} dfs(end-1,cnt-i)$$.
边界条件：当end=0时如果cnt！=0，那么不存在这样的排列，(因为长度为1，没法构成逆序对),那么[end=0,cnt=0]一定是1.所以边界条件是，dfs(0,0)=1.
优化记忆化搜索。
上面递推公式中，
● 如果cnt>=end:
$$dfs(end,cnt)=\sum_{i=0}^{end}dfs(end-1,cnt-i),$$ $$dfs(end,cnt-1)=\sum_{i=0}^{end}dfs(end-1,cnt-i-1)$$
$$dfs(end,cnt)=dfs(end,cnt-1)-dfs(end-1,cnt-1-end)+dfs(end-1,cnt)$$
● 如果cnt<=end：
$$dfs(end,cnt)=\sum_{i=0}^{cnt}dfs(end-1,cnt-i),$$
$$dfs(end,cnt)=\sum_{i=0}^{cnt-1}dfs(end-1,cnt-i-1),$$
可以得到：$$dfs(end,cnt)=dfs(end,cnt-1)+dfs(end-1,cnt)$$

class Solution {
public:
    int numberOfPermutations(int n, vector<vector<int>>& requirements) {
        map<int,int> mp;
        int len=requirements.size();
        int maxx=0;
        mp[0]=0;
        for(int num=0;num<len;num++){
            mp[requirements[num][0]]=requirements[num][1];
            maxx=max(maxx,requirements[num][1]);
        }
        if(mp[0]) return 0;
        const long long mod=1e9+7;
        vector<vector<long long> > dp(n+2,vector<long long>(maxx+2,-1));
        function<int(int,int)>dfs = [&](int end,int  cnt)->int{
            if(cnt<0) return 0;
            if(end==0) return 1;
            if(dp[end][cnt]!=-1)return dp[end][cnt];
            if(mp.count(end-1)){
                int r = mp[end-1];
                if(r<=cnt&&cnt<=end+r){//可以用end-1，r转移过来
                    return dp[end][cnt]=dfs(end-1,r);
                }
                return 0;
            }else {
                if(cnt>end) return dp[end][cnt]=(dfs(end,cnt-1)-dfs(end-1,cnt-1-end)+dfs(end-1,cnt)+mod)%mod;
                else {
                    return dp[end][cnt]=(dfs(end,cnt-1)+dfs(end-1,cnt))%mod;
                }
            }
        };
        return dfs(n-1,mp[n-1]);
    }
};

无重复字符的最长子串 - 力扣（LeetCode）

题解：这个题是个滑动窗口的典型题，
左右两个指针维护滑动窗口，这个滑动窗口内是符合条件的(这个题是窗口里无重复字符)。右指针添加新的元素，左指针排除不符合的元素。这里使用mp来判断窗口中的无重复子串。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n=s.size();
        int l=0,r=0;
        map<char,int>mp;
        int ans=0;
        int res=0;
        while(r<n){
            if(mp[s[r]]==0){
                ans++;
                mp[s[r]]=1;
                r++;
            }else {
                mp[s[l]]=0;
                l++;
                ans--;
            }
            res= max(res,ans);
        }
        return res;
    }
};