PerfectPan
;

那些年邂逅的 LeetCode 趣/难题

March 30, 2020

1397.找到所有好字符

题目链接:https://leetcode-cn.com/problems/find-all-good-strings/

题目难度:Hard

题意:

给你两个长度为 n 的字符串 s1 和 s2 ,以及一个字符串 evil 。请你返回 好字符串 的数目。

好字符串 的定义为:它的长度为 n ,字典序大于等于 s1 ,字典序小于等于 s2 ,且不包含 evil 为子字符串。

由于答案可能很大,请你返回答案对 109+710^9 + 7 取余的结果。

数据范围:

  • s1.length==ns1.length == n

  • s2.length==ns2.length == n

  • s1<=s2s1 <= s2

  • 1<=n<=5001 <= n <= 500

  • 1<=evil.length<=501 <= evil.length <= 50

  • 所有字符串都只包含小写英文字母。

思路:

首先这个问题可以按套路差分成两个问题,cal(s) 表示统计所有长度为 n 的字典序小于等于 s 且不包含字符串 evil 的答案,那么最后答案就是 cal(s2) - cal(s1) + check(s1),check(s1) 表示如果 s1 包含 evil 则返回 0,否则返回 1,那么剩下就是要解决 cal(s) 怎么计算的问题了。我们可以建出 evil 字符串的状态自动机,主要就是 trans[i][j]trans[i][j] 表示当前在 i 节点,出边是 j 走到的节点,这部分和 AC 自动机基本是一致的。

我们先用 kmp 预处理出 evil 的 next 数组,那么我们可以分类讨论得出

trans[i][j]={i+1,evil[i]==a+jtrans[next[i1]+1][j],evil[i]a+jtrans[i][j]=\left\{\begin{matrix}i+1,evil[i]=='a'+j \\ trans[next[i-1]+1][j],evil[i]\neq 'a'+j\end{matrix}\right.

注意这里 trans[i][j]trans[i][j] 的 i 其实是字符串的第 i - 1 位,因为字符串下标从 0 开始,而这里我们需要一个额外的节点 0 代表其实节点。i - 1 的下一个即为 evil[i]evil[i],如果经过字符 j 能走到,那么就是 i + 1,否则要复用以前的信息,从失配的 next[i1]next[i - 1] 那里转移过来,由于下标整体加一了,所以是 next[i1]+1next[i - 1] + 1。 这样我们得到了关于 evil 的自动机的状态转移图,剩下就是在上面 dp 就好了。

我们定义 dp[i][j][0/1]dp[i][j][0/1] 表示我们在自动机上从起点 0 出发走了 i 步,当前在 j 节点,得到字符串字典序小于或者等于字符串 s 的前 i 个字符的方案数,转移就很显然了。如果小于那么我们可以从小于或等于的状态转移过来,否则只能从等于的状态转移过来, dp[i][j][0/1]dp[i][j][0/1] 转移到 dp[i+1][trans[j][k]][0/1]dp[i+1][trans[j][k]][0/1] ,即走下一步的时候我们从出边 k 走,那么由于有之前预处理好的转移数组,所以下一步走到的节点即为 trans[j][k]trans[j][k] ,最后答案就是

i=0evil.length1dp[n][i][0]+dp[n][i][1]\sum_{i=0}^{evil.length-1}dp[n][i][0]+dp[n][i][1]

即我们只要不走到最后一个节点即必不包含字符串 evil ,时间复杂度为 O(Snm)O(Snm) ,其中 SS 为字符集大小,nn 为字符串的长度,mm 为 evil 的长度。

代码:

class Solution {
public:
    const int P=1000000007;
    int i,j,k,m,dp[505][55][2],nxt[505],trans[55][26];
    void up(int&a,int b){a+=b;if(a>=P)a-=P;}
    int cal(string s,int n){
        memset(dp,0,sizeof(dp));
        int ans=0;
        dp[0][0][1]=1;
        for (int i=1;i<=n;++i){
            for (int j=0;j<26;++j){
                for (int k=0;k<m;++k){
                    up(dp[i][trans[k][j]][0],dp[i-1][k][0]);
                    if (j<s[i-1]-'a') up(dp[i][trans[k][j]][0],dp[i-1][k][1]);
                    else if (j==s[i-1]-'a') up(dp[i][trans[k][j]][1],dp[i-1][k][1]);
                }
            }
        }
        for (int i=0;i<m;++i){
            up(ans,dp[n][i][0]);
            up(ans,dp[n][i][1]);
        }
        return ans;
    }
    int findGoodStrings(int n, string s1, string s2, string evil) {
        m=(int)evil.length();
        for (nxt[0]=j=-1,i=1;i<m;nxt[i++]=j){
            while (~j&&evil[j+1]!=evil[i]) j=nxt[j];
            j+=(evil[j+1]==evil[i]);
        }
        trans[0][evil[0]-'a']=1;
        for (i=1;i<m;++i){
            for (j=0;j<26;++j){
                if (evil[i]-'a'==j) trans[i][j]=i+1;
                else trans[i][j]=trans[nxt[i-1]+1][j];
            }
        }
        int ans=cal(s2,n)-cal(s1,n);
        if (s1.find(evil)==string::npos) ans++;
        ans%=P;
        if (ans<0) ans+=P;
        return ans;
    }
};

1531. 压缩字符串II

题目链接:https://leetcode-cn.com/problems/string-compression-ii

题目难度:Hard

题意:

行程长度编码 是一种常用的字符串压缩方法,它将连续的相同字符(重复 2 次或更多次)替换为字符和表示字符计数的数字(行程长度)。例如,用此方法压缩字符串 “aabccc” ,将 “aa” 替换为 “a2” ,“ccc” 替换为` “c3” 。因此压缩后的字符串变为 “a2bc3” 。

注意,本问题中,压缩时没有在单个字符后附加计数 ‘1’ 。

给你一个字符串 s 和一个整数 k 。你需要从字符串 s 中删除最多 k 个字符,以使 s 的行程长度编码长度最小。

请你返回删除最多 k 个字符后,s 行程长度编码的最小长度 。

数据范围:

  • 1s.length1001 \le s.length \le 100

  • 0ks.length0 \le k \le s.length

  • s 仅包含小写英文字母

思路:

定义 dp[i][j]dp[i][j] 表示考虑字符串 [0,i][0,i] 的前缀,删除了 jj 个字符的行程长度编码的最小长度。

考虑转移方程,枚举第 ii 个字符删或不删,如果删除的话

dp[i][j]=min(dp[i][j],dp[i1][j1])\rm dp[i][j]=\min(\rm dp[i][j],\rm dp[i-1][j-1])

如果不删的话,我们从后往前枚举字符 ii 在末尾连续多少次,并将中间不是 ii 的字符删去,我们假设前者数量为 same\rm same,后者数量为 del\rm del,当前枚举到了 mm,那么转移方程即为

dp[i][j]=min(dp[i][j],dp[m1][jdel]+cal(same))\rm dp[i][j]=\min(\rm dp[i][j],\rm dp[m-1][j-\rm del]+cal(\rm same))

其中 cal(same)\rm cal(\rm same) 为压缩后的编码数量,不删转移的正确性有待研究,因为我们可以选择中间的一个子集来进行转移而不是连续段,但有时候就是要大但猜测一下才能过

时间复杂度 O(n2k)O(n^2k),其中 n=s.lengthn=s.length

代码:

class Solution {
public:
    #define INF 0x3f3f3f3f
    int len(int k){
        if (k <= 1) return 0;
        else if (k > 1 && k < 10) return 1;
        else if (k >= 10 && k < 100) return 2;
        else return 3;
    }
    int getLengthOfOptimalCompression(string s, int k) {
        int n = s.size();
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, INF));
        dp[0][0] = 0;
        for(int i = 1; i <= n; ++i) {
            for(int j = 0; j <= k && j <= i; ++j) {
                if (j > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
                int same = 0, del = 0;
                for(int m = i; m >= 1; --m) {
                    if (s[m - 1] == s[i - 1]) same++;
                    else del++;
                    if (j - del >= 0) {
                        dp[i][j] = min(dp[i][j], dp[m - 1][j - del] + 1 + len(same));
                    } else {
                        break;
                    }
                }
            }
        }
        return dp[n][k];
    }
};

1536. 排布二进制网格的最少交换次数

题目链接:https://leetcode-cn.com/problems/minimum-swaps-to-arrange-a-binary-grid/

题目难度:Hard

题意:

给你一个 n x n 的二进制网格 grid,每一次操作中,你可以选择网格的 相邻两行 进行交换。

一个符合要求的网格需要满足主对角线以上的格子全部都是 0 。

请你返回使网格满足要求的最少操作次数,如果无法使网格符合要求,请你返回 -1 。

主对角线指的是从 (1, 1) 到 (n, n) 的这些格子。

数据范围:

  • n==grid.lengthn == grid.length

  • n==grid[i].lengthn == grid[i].length

  • 1n2001 \le n \le 200

  • grid[i][j] 要么是 0 要么是 1

思路:

从上到下逐行确定,假设当前考虑到第 ii 行,第 0i10 \ldots i-1 行都已经确定好。按题意第 ii 行满足的条件为末尾连续零的个数大于等于 ni1n-i-1, 那么我们考虑将 [in1][i \ldots n-1] 中的离第 ii 行最近的且满足限制条件的那一行逐行交换到第 ii 行。

我们可以考虑假设当前有若干行都能满足第 ii 行,那么这些行一定都满足第 i+1n1i+1 \ldots n-1 的限制条件,也就是说能交换到第 ii 行的那些行一定也能交换到后面几行,因为随着行数的增加,限制条件越来越宽松。因此不会存在贪心地选择后,后面出现无法放置的情况。

代码:

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> pos(n, -1);
        for (int i = 0; i < n; ++i) {
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 1) {
                    pos[i] = j;
                    break;
                }
            }   
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int k = -1;
            for (int j = i; j < n; ++j) {
                if (pos[j] <= i) {
                    ans += j - i;
                    k = j;
                    break;
                }
            }
            if (~k) {
                for (int j = k; j > i; --j) {
                    swap(pos[j], pos[j - 1]);
                }
            } else {
                return -1;
            }
        }
        return ans;
    }
};

Yiming Pan

Written by Yiming Pan who lives and works in Hangzhou China. Welcome follow me on Github

Cannot load comments. Please check you network.