滑动窗口

3. 无重复字符的最长子串

/**
 *
给定一个字符串，找出不含有重复字符的最长子串的长度。
示例 1:

输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc"，其长度为 3。

示例 2:
输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b"，其长度为 1。

示例 3:
输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke"，其长度为 3。
     请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。

 * @author zeroheart
 *
 */
public class Question3 {

   public static int lengthOfLongestSubstring(String s) {
      int low = 0;
      int high = 0;
      // 滑动窗口

      /**
       1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,
       此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；

       2、如果当前字符 ch 包含在 map中，此时有2类情况：
       1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，
       那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；
       2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，
       而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0；
       随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时
       应该不变，left始终为2，子段变成 ba才对。

       为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1).
       另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，
       因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中
       */

      int max = 0;
      HashMap charmap = new HashMap();
      for(high = 0; high < s.length(); high++){
         if(charmap.containsKey(s.charAt(high))){
            // 这里是关键，没有max的话，low会往后退
            low = Math.max(((int)charmap.get(s.charAt(high)) + 1), low);
            // low = (int)charmap.get(s.charAt(high)) + 1;
         }
         charmap.put(s.charAt(high), high);
         max = Math.max(max, high - low + 1);
      }
      return max;
    }


   public static void main(String args[]){
//    System.out.println(lengthOfLongestSubstring("abcabcbb"));
//    System.out.println(lengthOfLongestSubstring("bbbbb"));
//    System.out.println(lengthOfLongestSubstring("pwwkew"));
//    System.out.println(lengthOfLongestSubstring("dvdf"));
      System.out.println(lengthOfLongestSubstring("abba"));
   }
}

567. 字符串的排列

这题自己做了一个版本，效率太低，击败5%。。。。抄了一个大神的版本 ，可以理解一下，注意一句话，滑动窗口左右边界都不需要会退，这个是滑动的关键。也就是对于滑动的串一次遍历就行。

大神的思路是这样的，先统计子串中每个字符的个数，然后滑动，滑动时候，如果右侧坐标的字符在子串中，就个数-1，向后移动一位，指导到达所需要的窗口大小（字串长度），如果这时候r==l+len1，就直接返回，否则左侧滑动，左侧出去了，个数+1。

/**
 *
 567. 字符串的排列
 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

 换句话说，s1 的排列之一是 s2 的 子串 。



 示例 1：

 输入：s1 = "ab" s2 = "eidbaooo"
 输出：true
 解释：s2 包含 s1 的排列之一 ("ba").
 示例 2：

 输入：s1= "ab" s2 = "eidboaoo"
 输出：false


 提示：

 1 <= s1.length, s2.length <= 10^4
 s1 和 s2 仅包含小写字母


 * @author zeroheart
 *
 */
public class Question567 {
   // 这题没看题解，利用map写出来的，不过效率低下，效率高的滑动，直接遍历就完事了。。。以下注释部分是抄来的
   /**

    题目没有昨天的题那么费脑子。滑动窗口，双指针 left、right交替向右滑动即可。

    客观上来说，最终的答案如果是true，则s2中必然存在某个位置 i 使得以 i 开始的子串s2[i ... i+len1)是s1的排列。

    依次尝试固定以s2中的每一个位置 l 作为左端点开始的len1长度的子串s2[l ... l+len1)是否是s1的排列，最终必然不会错过所有的可能性。

    如果固定 l 做左端点，尝试失败，继续尝试 l+1 位置，【左右边界都不需要回退】，这是滑动窗口的前提。

    通过一个记账本 charCount 做为【总账表】维护s1的词频表；
    滑动窗口内每一个右边界字符进入窗口后，【还账】：charCount[str2[r] - 'a']--
    如果某个字符多还了（变成负值），即尝试失败，开始尝试下一个左端点（l++）;
    左边界字符出窗口后，表示【重新赊账】：charCount[str2[l] - 'a']++
    最终如果欠账还足了（窗口长度达到len1），则尝试成功，直接返回true。

    public static boolean checkInclusion(String s1, String s2) {
    char[] str1 = s1.toCharArray();
    char[] str2 = s2.toCharArray();
    int len1 = s1.length();
    int len2 = s2.length();
    int[] charCount = new int[26]; // 【总欠账表】：s1的词频表
    for (char c : str1) { // 统计s1的词频
    charCount[c - 'a']++;
    }
    int l = 0, r = 0; // 滑动窗口左右边界
    // 依次尝试固定以s2中的每一个位置l作为左端点开始的len1长度的子串s2[l ... l+len1)是否是s1的排列
    while (l <= len2 - len1) { // 固定左端点只需要尝试到len2-len1即可
    // 右边界s2[r]字符进入窗口【还账】
    while (r < l + len1 && charCount[str2[r] - 'a'] >= 1) {
    charCount[str2[r] - 'a']--; // 【"还账"】
    r++;
    }
    if (r == l + len1) return true;
    // 左边界s2[l]字符出窗口【赊账】，l++，开始尝试固定下一个位置做左端点
    charCount[str2[l] - 'a']++; // 重新【"赊账"】
    l++;
    }
    return false; // 所有的左端点均尝试还账失败，不可能再有答案了
    }

    */
   public boolean checkInclusion(String s1, String s2) {
      int len1 = s1.length();
      int len2 = s2.length();

      int diff  = len2 - len1;

      boolean result = false;

      for(int i = 0; i<=diff; i++){
         String src = s2.substring(i, i+len1);
         if(check(s1, src)){
            return true;
         }
      }

      return false;

   }

   private boolean check(String s1, String src) {
      int len = s1.length();
      HashMap<Character, Integer> charMap = new HashMap();

      for(int i = 0; i<len; i++){
         char c1 = s1.charAt(i);
         char c2 = src.charAt(i);

         if(charMap.containsKey(c1)){
            charMap.put(c1, charMap.get(c1) + 1);
         }else {
            charMap.put(c1, 1);
         }

         if(charMap.containsKey(c2)){
            charMap.put(c2, charMap.get(c2) - 1);
         }else {
            charMap.put(c2, -1);
         }
      }
      Long collect = charMap.values().stream().filter(integer -> integer != 0).collect(Collectors.counting());
      return collect == 0;
   }

   public static void main(String[] args) {
//    System.out.println(checkInclusion("adc", "dcda"));
   }
   
}