算法day07

 第一题

30. 串联所有单词的子串

        上题题意如下:

         将w数组里面的字符串随机排列,只要在s字符串中找到相对应的w组成的字符串,则返回s中对应字符串首位元素的第一个下标;

        

        有上述题意所知,解题思路如上一题故事,本题采用hash表和滑动窗口的模型;

        首先对于words字符串数组进行处理:

        

        由于这里面的字符串的长度一样,所以我们将每一个字符串一组放在hash1表中,并记录其存放的个数;

        其次就是对s字符串的处理分析:

        如下图所示:

        由于我们存放在hash1中的字符串的长度是len,所以我们在开始左右指针进行移动时,从s的第一个位置和第二个位置开始移动时,结果是不一样的;所以我们分别要从其实位置为0->len-1,分别开始移动左右指针;

        且接下来分析右指针所移动的随后判断结束点,如下图所示,

        最理想的结果莫过于移动到上图n处,但是也可能移动到m和a处,所以最后的right指针应该移动范围是right+len < n;

        关于分析综上所述:

       解题步骤如下:

步骤一:

        使用hash表来存放words和s里面的字符串;

步骤二:

        左右指针移动,移动的长度是words里面字符串的长度;

步骤三:

        滑动窗口执行的次数,即外循环,len次;

代码如下所示:

class Solution
{public List<Integer> findSubstring(String s, String[] words) {List<Integer> ret = new ArrayList<Integer>();// 保存字典中所有单词的频次Map<String, Integer> hash1 = new HashMap<String, Integer>(); for(String str : words) hash1.put(str, hash1.getOrDefault(str, 0) + 1);int len = words[0].length(), m = words.length;for(int i = 0; i < len; i++) // 执⾏次数{// 保存窗⼝内所有单词的频次Map<String, Integer> hash2 = new HashMap<String, Integer>(); for(int left = i, right = i, count = 0; right + len <= s.length(); 
right += len){// 进窗⼝ + 维护 countString in = s.substring(right, right + len);hash2.put(in, hash2.getOrDefault(in, 0) + 1);if(hash2.get(in) <= hash1.getOrDefault(in, 0)) count++; // 判断if(right - left + 1 > len * m){// 出窗⼝ + 维护 countString out = s.substring(left, left + len);if(hash2.get(out) <= hash1.getOrDefault(out, 0)) count--;hash2.put(out, hash2.get(out) - 1);left += len;}// 更新结果if(count == m) ret.add(left);}}return ret;}
}

第二题

        题目如上图所示:

        本题我们采用滑动窗口和hash表的解题方法:

步骤一:

        将t字符串里面的字符放在hash2表中,使用hash2记录每一个元素出现的次数,并使用kinds变量来记录t字符串中字符的种类;

        同时定义左右指针;

步骤二:

        进窗口:

        右指针移动一位,将所指的字符存于hash1表中,并记录当前所指元素出现在hash表中的次数;同时使用count来记录hash1表中的有效种类;(使用两个hash中同一个元素存放的次数相同时,我们就判定该元素满足t字符串中的种类饱和,故此count++)

步骤三:判断:

        当有效种类count==kinds时,记录当前左指针的位置为满足条件字符串的首位置,同时记录当前窗口的长度,最后进行出窗口操作;

        左指针所指的元素的两个hash值相同时,count--,同时该元素的hash值-1,左指针左移;

步骤四:

        返回数值;

        代码如下所示:

           
class Solution {public String minWindow(String s, String t) {char[] s1 = s.toCharArray();char[] t1 = t.toCharArray();int[] hash2 = new int[128];int kinds = 0;//表示t中元素的种类for(char ch: t1){if(hash2[ch] == 0){kinds++;}hash2[ch] ++;}int[] hash1 = new int[128];int minLen = Integer.MAX_VALUE,begin = -1;for(int left = 0,right = 0,count = 0;right < s1.length;right++){char in = s1[right];hash1[in]++;if(hash2[in] == hash1[in]){count++ ;}while(kinds == count){if(right-left+1 < minLen){begin = left;minLen = right-left+1;}char out = s1[left++];if(hash2[out] == hash1[out]){count--;}hash1[out]--;}}if(begin == -1){return new String();}else{return s.substring(begin,begin+minLen);}}
}

ps:本次的内容就到这里了,如果大家感兴趣的话就请一键三连哦!!! 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1425308.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

在澳门写代码;技术入股2次融资被踢;现在只想做独立开发

本期我们邀请的程序员是Albert&#xff0c;先后在广州、澳门、珠海、香港工作过&#xff0c;打工上班、合伙创业、远程工作、独立开发&#xff0c;工作经历丰富&#xff0c;如果你想知道哪些程序员踩过的坑&#xff0c;请别错过他的故事。 广州&#xff1a;第一份工作2000块一…

代码随想录-算法训练营day41【动态规划04:01背包问题-滚动数组、分割等和子集】

代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客 第九章 动态规划part04● 01背包问题,你该了解这些! ● 01背包问题,你该了解这些! 滚动数组 ● 416. 分割等和子集 正式开始背包问题,背包问题还是挺难的,虽然大家可能看了很多背包问题模板代码,感觉挺简单,…

【附poc】H5 云商城漏洞

漏洞描述 H5 云商城 file.php 文件上传,攻击者可通过此漏洞上传恶意脚本文件&#xff0c;对服务器的正常运行造成安全威胁&#xff01;漏洞可在圈子中获取&#xff0c;8000陆续更新中&#xff01; 漏洞复现 语法及其界面 1、fofa&#xff08;会员可在圈子获取&#xff09; b…

Java JDK下载安装教程(2024年)

博主介绍&#xff1a;✌Java老徐、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&…

这10款安卓APP,简直好用到爆!

AI视频生成&#xff1a;小说文案智能分镜智能识别角色和场景批量Ai绘图自动配音添加音乐一键合成视频http://AI视频生成&#xff1a;小说文案智能分镜智能识别角色和场景批量Ai绘图自动配音添加音乐一键合成视频 1.追书——追书神器 追书神器是小说追新大神&#xff0c;全网实…

520告白好物有哪些?收下这份清单不迷茫!

在这个充满爱意的日子里&#xff0c;你是否正在为如何向心仪的人表达深情而犯愁&#xff1f;别担心&#xff0c;我们为你精心准备了一份520告白好物清单都是一些实用的礼品&#xff0c;为你提供多样化的选择&#xff0c;助你轻松传达爱意&#xff0c;让告白不再迷茫。快来看看吧…

软考电商考前冲刺20问!看看你能答上多少?

距离软考考试的时间越来越近了&#xff0c;趁着最后的时间赶紧冲刺起来&#xff0c;今天给大家整理了——电子商务设计师考前20问 一、考前20问是什么&#xff1f; 考前几页纸是各科目考点的高度精华总结。也是我们今年考前冲刺蕞后一份资料 二、考前20问好在哪里&#xff1f;…

面对《消费者告知法》严查与技术BUG频发,亚马逊卖家如何巧妙应对挑战?

五一假期期间&#xff0c;亚马逊大量发送《美国消费者告知法案》验证邮件通知&#xff0c;在这个本该是卖家们忙碌而喜悦的时刻&#xff0c;亚马逊平台上的卖家们却遭遇了一场前所未有的“灾难”——《消费者告知法》验证问题的爆发&#xff0c;以及随之而来的一系列技术BUG&am…

JL-杰理芯片-认识TA的SDK的第四天

无蓝牙连接关机时间 关机时间&#xff1a;3分钟 60 * 5 300 低功耗 进入低功耗前&#xff0c;要关闭打印 内存D2、D4、D8 芯片&#xff08;主控&#xff09;的内存不能超过一定的数值&#xff0c;超过后就不能烧录 jl_isd.bin这个文件不能超过内存大小 而杰理的内存是…

剑指Offer打卡day34——AcWing 66. 两个链表的第一个公共结点

AcWing 66. 两个链表的第一个公共结点 暴力做法&#xff0c;两层for循环 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/ class Solutio…

IEEE(电气电子工程师学会)数据库文献去哪里查询下载

IEEE数据库简介&#xff1a; IEEE&#xff08;电气电子工程师学会&#xff09;是目前全球科学技术领域领先的专业机构。其期刊在电气电子工程、计算机科学、人工智能、机器人、自动化控制、遥感和核工程领域的期刊影响因子和被引用量都名列前茅。而其学术会议涉及领域广&#…

package-lock.json导致npm install安装nyc出现超时错误

一、背景 前端项目在npm install安装依赖&#xff0c;无法下载组件nyc&#xff0c;详细报错信息&#xff1a; npm ERR! code CERT_HAS_EXPIRED npm ERR! errno CERT_HAS_EXPIRED npm ERR! request to https://registry.npm.taobao.org/nyc/download/nyc-13.3.0.tgz?cache0&a…

Windows下配置TortoiseGit 访问Ubuntu虚拟机下Samba共享目录

前言&#xff1a; 本文记录学习使用 Git 版本管理工具的学习笔记&#xff0c;通过阅读参考链接中的博文和实际操作&#xff0c;快速的上手使用 Git 工具。 本文参考了引用链接博文里的内容。 引用: 【TortoiseGit】TortoiseGit安装和配置详细说明-CSDN博客 Git版本管理可视…

Spring框架学习笔记(三):AOP编程

1 动态代理 1.1 通过案例理解动态代理 &#xff08;1&#xff09;需求说明&#xff1a; 1. 有 Vehicle接口(交通工具接口, 有一个 run 方法), 下面有两个实现类 Car 和 Ship 2. 当运行 Car 对象 的 run 方法和 Ship 对象的 run 方法时&#xff0c;输入如下内容, 注意观察前后…

了解RFID技术如何改善危化品仓储管理效率

随着科学的发展&#xff0c;我国化工行业也迎来飞速进步的黄金时期&#xff0c;而生产加工快速化的同时也导致一些危险化学品的使用量与存储量不断增加。由于危险化学品种类较多&#xff0c;使用和存储的方法都不一样&#xff0c;还具有易燃、易爆、腐蚀、毒害等特性&#xff0…

系统架构师考试(二)

敏捷方法 CMMI代表Capability Maturity Model Integration&#xff0c;是一种用于评估和改进组织软件工程和系统工程的模型。CMMI提供一个框架&#xff0c;帮助组织评估其软件和系统工程的成熟度&#xff0c;该模型基于过程成熟度模型&#xff08;CMM&#xff09;和集成项目管理…

数据中台管理系统原型

数据中台是一个通用性的基础平台&#xff0c;适用于各类行业场景&#xff0c;数据中台包含多元数据汇聚、数据标准化、数据开发、数据共享、数据智能、数据资产管理等功能&#xff0c;助力企业数字化转型。 数据汇聚 数据汇聚是将不同系统、不同类型的多元源数据汇聚至目标数据…

Flink 高可用之StandAlone-HA模式(一)

Flink 高可用之StandAlone-HA模式 压缩包: tar -xvzf flink-1.9.1-bin-scala_2.11.tgz -C /opt && cd /opt/flink-1.9.1 集群规划: 1.集群规划 - 服务器: node1(Master Slave): JobManager TaskManager- 服务器: node2(Master Slave): JobManager TaskManager- …

【WEB前端2024】开源智体世界:乔布斯3D纪念馆-第23课-烟花插件的售卖效果优化

【WEB前端2024】开源智体世界&#xff1a;乔布斯3D纪念馆-第23课-烟花插件的售卖效果优化 使用dtns.network德塔世界&#xff08;开源的智体世界引擎&#xff09;&#xff0c;策划和设计《乔布斯超大型的开源3D纪念馆》的系列教程。dtns.network是一款主要由JavaScript编写的智…

盘点2024年自动猫砂盆品牌,哪个牌子自动猫砂盆比较好?

养猫之路漫漫&#xff0c;无论是新手还是老手&#xff0c;都需要细心照料猫咪的每一个需求。特别是在选择自动猫砂盆这个问题上&#xff0c;更是让人头疼不已。因为每只猫咪的喜好和习惯都不同&#xff0c;如果猫砂盆选得不对&#xff0c;猫咪可能会拒绝使用&#xff0c;导致家…