通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

算法学习之最小(大)表示法

5395人浏览 / 0人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法  | 

作者:因情语写

链接:https://www.proprogrammar.com/article/382

声明:请尊重原作者的劳动,如需转载请注明出处


    最小与最大只是判断条件不一样,其实质是一样的,以最小表示法为例。

    用途:

    给出一个字符串,求与它循环同构的串中字典序最小的串

    求一个字符串的最大(小)后缀子串

    下面给出最小表示法的java实现

int minRepresent(String s) {
    int i = 0, j = 1, k = 0, len = s.length();
    while (i < len && j < len && k < len) {
        int t = s.charAt((i+k) % len) - s.charAt((j+k) % len);
        if (t == 0) {
            k++;
        }else {
            if (t < 0){
                j = Math.max(j+k+1, i+1);
            }else{
                i = Math.max(i+k+1, j+1);
            }
            k = 0;
        }
    }
    return Math.min(i, j);
}

    算法解释

  • 令i=0,j=1表示最小的字符串可能的位置;
  •      找到一个k使得s[i+1]==s[j+1],s[i+2]==s[j+2] ,..., s[i+k-1]==s[j+k-1] ;
  •      但是s[i+k]!=s[j+k];
  •      如果此时s[i+k]<s[j+k],对于j' = j + 1 到 j + k 的位置一定不是最优解,因为i+j'-j位置的串一定比j'位置的更优;且如果i+j'-j位置的串更优一定会被i选到。那么我们就可以 j=j+k+1
  •     s[i+k]>s[j+k]就i=i+k+1,注意i==j时要再向后移动一位
  •     事实上你可以理解成i和j是互相独立的只是其中的某一个为最小的串的待定值,另一个为用来比较的串;

     解释一下为什么i, j取值时会是Math.max()的形式,对i,j两个可能的最小子串位置,当出现t != 0的情况时,说明其中一处不满足最小子串的条件,不妨设i处不满足,此时可能的最小子串位置是j,所以另一个可能的最小子串位置一定在j的后面,j的前面可不可能呢,不可能,如果可能最小子串位置就不会是到j,而是在j前的那个位置了,能到j说明从i+1到j-1的位置都不是最小子串位置,此时i不满足条件,可能位置一定在j之后,又上面分析知i+1到i+k也不会是最小子串位置,所以最小子串位置是Math.max(i+k+1, j+1),对j位置不满足最小子串时的分析也一样

    最后给出最大表示法的实现

int minRepresent(String s) {
    int i = 0, j = 1, k = 0, len = s.length();
    while (i < len && j < len && k < len) {
        int t = s.charAt((i+k) % len) - s.charAt((j+k) % len);
        if (t == 0) {
            k++;
        }else {
            // t与0的关系是最大表示法与最小表示法唯一的不同
            if (t > 0){
                j = Math.max(j+k+1, i+1);
            }else{
                i = Math.max(i+k+1, j+1);
            }
            k = 0;
        }
    }
    return Math.min(i, j);
}

 


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告