秋招突击——8/22——算法整理——滑动窗口类型题目思维方式——查找最短包含子串、找到字符串中所有字母异位词、无重复最长子串、01的得分

引言

• 今天面试字节，被老师指出来代码能力薄弱，确实如此。后续应当多加练习！
• 今天的问题框架没有想好，然后直接上了优化策略，然后在那里缝缝补补！错过了机会！

正文

基本思路

问题简化==》控制不了双指针，先控制一个指针，实现单循环！

• 先控制一个指针，实现单循环，将问题简化
• 然后在增加一个指针，不断将问题进行优化，并且满足更多得条件

查找最短包含子串

leetcode原题

考试实现代码

这个代码是我当时直接想的，我就说怎么越写越熟悉，合着我当时做这道题就是按照这个错误的代码写的，然后印象太深刻了，还是按照这个错误的代码写的，这个印象太深刻了！

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
   


    public static void main(String[] args) {
   
        Scanner in = new Scanner(System.in);
        String str1 = in.nextLine();
        String str2 = in.nextLine();

        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < str2.length(); i++) {
   
            map.put(str2.charAt(i), map.getOrDefault(str2.charAt(i), 0) + 1);
        }

        int minLen = Integer.MAX_VALUE;
        int count = map.size();
        String res = "";

        int l = 0, r = 0;

        while (l < str1.length()) {
   
            // 遍历找到第一个包含l的值
            char charL = str1.charAt(l);
            while (!map.containsKey(charL)) {
   
                l++;
                charL = str1.charAt(l);
            }
            map.put(charL,map.get(charL) - 1);
            if(map.get(charL) == 0) count--;

            // 往后继续遍历l
            while (r < str1.length() && count != 0) {
   
                // 遍历找到第一个包含字母的值
                char charR = str1.charAt(r);
                while (!map.containsKey(charR)) {
   
                    r++;
                    charR = str1.charAt(r);
                }

                // 更新对应编码
                map.put(charR,map.get(charR) - 1);
                if(map.get(charR) == 0) count--;
                r ++;
            }

            // 比较最大值
            if (r < str1.length() && r - l + 1 < minLen){
   
                minLen = r - l + 1;
                res = str1.substring(l ,r + 1);
            }

            l ++;
            charL = str1.charAt(l);
            map.put(charL,map.get(charL) + 1);
            count ++;
        }

        System.out.println(res);


    }
}

总结

• 上述代码中，同时写了左指针的优化方式，又写了右指针的优化方式，但是两个连在一块就开始缝缝补补了，这样只会让问题更加复杂，并不好写代码，并不好解决。
• 跑步的时候想了很久，具体思维方式见下一节！

考试反思代码===》先确定一边的指针，然后再移动另外一个指针修改

终于写出来了

• 先实现一个指针，然后根据第一个指针的条件，再决定第二个指针的运动过程！

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
   


    public static void main(String[] args) {
   
        Scanner in = new Scanner(System.in);
        String str1 = in.nextLine();
        String str2 = in.nextLine