关于java:给定m个不重复的字符-abcd以及一个长度为n的字符串tbcacbdata滑动窗口

48次阅读

共计 988 个字符,预计需要花费 3 分钟才能阅读完成。

题目

给定 m 个不反复的字符 [a, b, c, d],以及一个长度为 n 的字符串 tbcacbdata,问是否在这个字符串中找到一个长度为 m 的间断子串,使得这个子串刚好由下面 m 个字符组成,程序无所谓,返回任意满足条件的一个子串的起始地位,未找到返回 -1。比方下面这个例子,返回 3。

本题的子串须要满足长度为 m,字符不反复,能够应用长为 m 的滑动窗口遍历字符串,窗口内每个字符都要呈现一次,如果符合条件,就返回窗口起始地位。

滑动窗口算法

滑动问题蕴含一个滑动窗口,它是一个运行在一个大数组上的子列表,该数组是一个底层元素汇合。

假如有数组 [a b c d e f g h],一个大小为 3 的滑动窗口在其上滑动,则有:

[a b c]
  [b c d]
    
      [d e f]
        [e f g]
          [f g h]

个别状况下就是应用这个窗口在数组的非法区间内进行滑动,同时动静地记录一些有用的数据,很多状况下,可能极大地提高算法地效率。

代码

/**
     * 给定 m 个不反复的字符 [a, b, c, d],以及一个长度为 n 的字符串 tbcacbdata,* 是否在这个字符串中找到一个长度为 m 的间断子串,使得这个子串刚好由下面 m 个字符组成.
     * 程序无所谓,返回任意满足条件的一个子串的起始地位,未找到返回 -1。比方下面这个例子,acbd,3.
     *
     * @param ch
     * @param s
     * @return
     */
    private int findIndex(char[] ch, String s) {

        int targetCharSize = ch.length;
        int totalCharSize = s.length();

        if (targetCharSize > totalCharSize) {return -1;}

        for (int i = 0; i < totalCharSize - targetCharSize; i++) {
            // 滑动窗口的思维,每次取指标数组大小进行比拟,不符后再向后挪动
            if (checkSubStr(ch, s.substring(i, i + targetCharSize))) {return i;}
        }
        return -1;

    }

    private boolean checkSubStr(char[] ch, String s) {for (int i = 0; i < ch.length; i++) {if (s.indexOf(ch[i]) == -1) {return false;}
        }
        return true;
    }

本篇文章如有帮忙到您,请给「翎野君」点个赞,感谢您的反对。

正文完
 0