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

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

时间：2024-08-24 21:55:36浏览次数：13  
标签：子串 java 22 get charR charL 秋招 import 指针

文章目录

引言

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

正文

基本思路

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

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

查找最短包含子串

在这里插入图片描述

考试实现代码

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

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();

        Map<Character, Integer> mapTar = new HashMap<>();
        Map<Character, Integer> mapSour = new HashMap<>();

        for(int i = 0;i < str2.length(); i++){
            mapTar.put(str2.charAt(i),mapTar.getOrDefault(str2.charAt(i), 0 ) + 1);
        }

        // 逐个进行遍历
        int count = 0;
        int minLen = Integer.MAX_VALUE;
        String res = "";

        for (int l = 0,r = 0;l <= r && r < str1.length();r ++){
            char charR = str1.charAt(r);
            if(mapTar.containsKey(charR)){
                // 记录更新对应的字符
                mapSour.put(charR,mapSour.getOrDefault(charR,0) + 1) ;
                if(mapSour.get(charR) == mapTar.get(charR)){
                    count ++;
                }

                if(count == mapTar.size()) {

                    // 判定是否需要移动对应的l,保证对应l是相同的
                    char charL = str1.charAt(l );
                    while(l< r ) {
                        if (!mapTar.containsKey(charL)) {
                            // 当前的字符是无效的字符
                            l++;
                        } else{
                            //如果下一个字符还是对应的字符，就直接跳过，然后输出对应结果
                            if(mapSour.get(charL) - 1 < mapTar.get(charL)) break;
                            else{
                                l ++;
                                mapSour.put(charL,mapSour.get(charL) - 1);
                            }
                        }
                        charL = str1.charAt(l);
                    }

                    // 比较长度，确定最小的长度
                    int len = r - l + 1;
                    if(len < minLen){
                        res = str1.substring(l,r + 1);
                        minLen = len;
                    }

                    // 在往后移动对应的L即可，同时更新对应的字符
                    l ++;
                    mapSour.put(charL,mapSour.get(charL) - 1);
                    if(mapSour.get(charL) < mapTar.get(charL)) count --;
                }
            }
        }

        System.out.println(res);

    }
}

在这里插入图片描述

找到字符串中所有字母异位词

复习实现

思路分析

  • 不能代入一个思维定式，觉得每一次遍历右边都是对的，这里应该根据情况进行确定
  • 首先这里判定的子串有以下几个特征
    • 仅仅包含目标字符串内容
    • 长度是固定的
  • 基于以上两个特征可以想着从左边指针进行遍历，因为长度一定，右指针的位置就是固定的了！
import java.io.IOException;
import java.net.ServerSocket;
import java.net.Socket;
import java.util.*;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;


public class Main {


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String p = in.nextLine();
        List<Integer> res = new ArrayList<>();


        // 记录每一个字符出现的频率
        Map<Character, Integer> mapS = new HashMap<>();
        Map<Character, Integer> mapP = new HashMap<>();
        for (char x: p.toCharArray()) mapP.put(x,mapP.getOrDefault(x,0) + 1);

        int count = 0;
        for(int r = 0,l = 0;l <= s.length() - p.length();l ++){
            char charL = s.charAt(l);
            if(mapP.containsKey(charL)) {
                // 处理一下一开始的情况
                if (l >= r) {
                    mapS.clear();
                    count = 0;
                    r= l + 1;

                    // 包含对应字符，只有第一次运行的时候才会这样
                    mapS.put(charL,mapS.getOrDefault(charL,0) + 1);
                    if(mapP.get(charL) == mapS.get(charL)) count ++;
                }


                // 在合法长度内部
                while (r - l + 1 <= p.length()){
                    // 匹配的是不在目标范围的字符，直接跳过
                    char charR = s.charAt(r);
                    if (mapP.containsKey(charR)){
                        // 这里是匹配到满足条件的字符串
                        mapS.put(charR,mapS.getOrDefault(charR,0) + 1);
                        if(mapP.get(charR) == mapS.get(charR)) count ++;
                        r ++;
                    }else{
                        // 这里匹配到不满足条件的字符串
                        l = r;
                        count = 0;
                        break;
                    }
                }

                // 满足条件再进行判定
                if(count == mapP.size()) {
                    res.add(l);
                }

                // 下一步i ++ 需要进行定点清除,并判定是否需要维护count
                if(mapP.containsKey(s.charAt(l))){
                    mapS.put(charL,mapS.getOrDefault(charL,0) - 1);
                    // 原来比他大的减掉他，变成相等的了，不用边，如果原来是跟他相等的，就要改变
                    if (mapP.get(charL) == mapS.get(charL) + 1) count --;
//                    else count --;
                }

            }
        }
        System.out.println(res.toString());
    }
}

总结

  • 这个是我今天有做了一遍这个题目，然后按照昨天晚上想的思路做的，我先根据情况分析了应该先确定左指针的操作，进而根据左指针的相关操作来决定右指针在不同情况下的操作，但是这个编程方式更像是打补丁，差不多用了四十分钟，中间遇到了很多问题，只能一个一个调试出来，还是不行，主要是很多细节没有想清楚！

在这里插入图片描述

  • 看了以前的一些做题记录，发现以前真厉害，想的真清楚，一下子就做出来了，我靠！真厉害！现在怎么想不明白了！是我变笨了吗？
参考实现
  • 移动的右指针，然后再根据不同的情况移动左指针，具体思路如下
    • 如果右指针的字符串不在目标字典中，直接跳过，移动l和r到下一个位置，并且清空原来的字典
    • 如果右指针的字符串在目标字典中，就移动左指针，让特定的字符串满足目标，因为这里数量是一一对应的
import java.io.IOException;
import java.net.ServerSocket;
import java.net.Socket;
import java.util.*;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;


public class Main {


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String p = in.nextLine();
        List<Integer> res = new ArrayList<>();


        // 记录每一个字符出现的频率
        Map<Character, Integer> mapS = new HashMap<>();
        Map<Character, Integer> mapP = new HashMap<>();
        for (char x: p.toCharArray()) mapP.put(x,mapP.getOrDefault(x,0) + 1);

        for (int r = 0,l = 0;r < s.length();r ++){
            char charR = s.charAt(r);
            if (mapP.containsKey(charR)){
                // 移动l，控制r的次数是相同
                mapS.put(charR,mapS.getOrDefault(charR,0) + 1);
                while(l < r && mapS.get(charR) != mapP.get(charR)){
                    char charL = s.charAt(l ++);
                    mapS.put(charL,mapS.get(charL) - 1);
                    if (mapS.get(charL) == 0) mapS.remove(charL);
                }

                // 判定是否完全相等
                int len = r - l + 1;
                if (len == p.length() && mapS.size() == mapP.size()){
                    res.add(l);
                }
            }else{
                // 不包含对应的字符，直接跳过，并清空字典
                l = r + 1;
                mapS.clear();
            }
        }
        
        System.out.println(res.toString());
    }
}

总结

  • 写的真的是简洁，这个思路真的是简洁，确定了是滑动窗口，也就是说右指针和左指针是同向运动的，就先走右指针，然后根据不同的情况来制定左指针的运动过程，左指针就是用来纠正右指针的。
  • 没记住这个基本的代码结构，还是不行的！然后出了记住这个基本的代码结构，还应该能够有一个固定的思维顺序和方式。

无重复最长子串

题目链接

个人实现
  • 这次实现是建立在之前已经忘得一干二净的基础上的，总体来说实现的还不错，至少对滑动窗口的思维逻辑还有代码框架，有了更加熟悉的认知！
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int res = 0;
        for (int l = 0, r = 0; r < s.length(); r++) {
            char charR = s.charAt(r);
            map.put(charR, map.getOrDefault(charR, 0) + 1);
            // 需要移动l来纠正
            while (map.get(charR) > 1) {
                char charL = s.charAt(l++);
                map.put(charL, map.get(charL) - 1);
            }

            // 计算长度
            res = Math.max(r - l + 1, res);
        }
        return res;
    }
}

在这里插入图片描述

总结

  • 历时大半天，从昨晚面试完字节自闭，到现在完整地整理完这类题目，我对这类问题有了更加清晰的认知，再来一个新类型的题目，就算一时间想不起来任何更好地方法，但是最朴素的方法还是能够想到的！
  • 很多代码问题，都是这样的！有的时候整体揉在一块，你想不清楚怎么做，但是你可以把这个问题简化，先简化一个条件或者某一个状态去考虑，等这个简单的考虑清楚了，就可以考虑复杂的了。这类思想在很多地方都是适用的。本章讲的双指针问题，便是如此，先是想清楚一个指针是什么样，然后在想另外一个指针基于这个指针应该怎么运作！然后动态规划也是差不多，先清楚最后一个状态是啥，有什么推导出来的，就可以推出来状态转移方程。
  • 当然这些东西都是大而全的东西，实际上还是要多做题，多看题！

标签：子串,java,22,get,charR,charL,秋招,import,指针
From： https://blog.csdn.net/Blackoutdragon/article/details/141437552

相关文章

  • VS2022 Visual Studio Installer 一直卡在0%，或者下载速度慢的问题解决办法
    C:\Users\Administrator\AppData\Local\Temp到c盘查看日志，发现是下载一个叫vs_installer.opc的东西失败了， 直接复制日志里的https://aka.ms/vs/17/release/installer，下载，发现成功下载，然后放到installer安装器同级目录，重新打开setup安装，就成功了打开了，然后会一直正在准备中，......
  • 数据库系统 第22节 事务隔离级别案例分析
    1.读未提交(ReadUncommitted)场景：假设有两个事务，事务A正在更新账户余额，事务B正在读取账户余额。事务A（未提交）：开始更新账户余额，将余额从$1000减少到$900。事务B（读取）：读取账户余额，看到余额为$900（事务A未提交的更改）。问题：如果事务A最终回滚，事务B读取到的$900将是无效的，这就......
  • 全新Versal HBM 系列自适应 SoC：XCVH1542-1MSEVSVA3697、XCVH1542-2MLELSVA4737、XCVH1
    系列概述VersalHBM系列具有快速内存、安全连接和自适应计算的异构集成，可消除内存绑定的计算密集型工作负载（如机器学习、数据库加速、下一代防火墙和高级网络测试仪）的处理和内存瓶颈。它从底层开始构建，以适应不断发展的算法、协议和数据速率。与VersalPremium系列*相比，通过集......
  • 代码随想录第15天，110.平衡二叉树，257. 二叉树的所有路径， 404.左叶子之和， 222.完全二叉
    110.平衡二叉树//平衡二叉树，理解稍微有点难度#include<iostream>#include<algorithm>//Forstd::absandstd::maxfunctionsstructTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr......
  • SQL Server 2019及Solidworks 2022安装错误解决
    问题关键词：SQLServer2019;Solidworks2022;WaitontheDatabaseEnginerecoveryhandlefailed.TLDR：Windows11系统扇区过大导致SQLServer无法处理。参考这一个StackOverflow问题中的相关回答。问题解决（SQLServer2019安装问题）：以管理员身份运行CommandPrompt或者......
  • 【LeetCode面试150】——3无重复数组的最长子串
    博客昵称：沈小农学编程作者简介：一名在读硕士，定期更新相关算法面试题，欢迎关注小弟！PS：哈喽！各位CSDN的uu们，我是你的小弟沈小农，希望我的文章能帮助到你。欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！......
  • 解决方案 | VS2022 社区版 获取工具和功能找不到visual stdio安装程序的终极解决办法
      首先这是一种解决方法：https://blog.csdn.net/Wysnbb/article/details/124588395 其次，如果上面方法解决不了，那么可以重新下载vs社区版。（不要误会，并不是下载10G+的东西）https://visualstudio.microsoft.com/zh-hans/vs/community/  下载得到：  安装VisualStud......
  • 线性dp：最长公共子串
    最长公共子串本文讲解的题与leetcode718.最长重复子数组，题意一模一样，阅读完本文以后可以去挑战这题。力扣链接题目叙述：给定两个字符串，输出其最长公共子串的长度。输入ABACCBAACCAB输出3解释最长公共子串是ACC，其长度为3。与最长公共子序列的区别公共子串：字符必须......
  • 【C语言初级课程详解】第22课时-C语言结构体
    C 结构体C数组允许定义可存储相同类型数据项的变量，结构是C编程中另一种用户自定义的可用的数据类型，它允许您存储不同类型的数据项。结构体中的数据成员可以是基本数据类型（如int、float、char等），也可以是其他结构体类型、指针类型等。结构用于表示一条记录，假设您想要跟......
  • 24年顺丰秋招入职SHL测评题库：综合能力Verify测评+性格测试OPQ测评题型分析
    顺丰秋招入职测评通常包括综合能力测评和性格测试两个部分。综合能力测评主要考察应聘者的基础认知能力，题型包括日历题、排序题、时间题、图形题、比例题和连线题，测试时间通常为46分钟，实际作答时间为36分钟，共24题。性格测试则采用OPQ（OccupationalPersonalityQuestionnaire）测......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99