【Java刷题篇】串联所有单词的子串

这篇具有很好参考价值的文章主要介绍了【Java刷题篇】串联所有单词的子串。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

📃1.题目

力扣链接: 串联所有单词的子串
【Java刷题篇】串联所有单词的子串,Java刷题篇,java,开发语言
【Java刷题篇】串联所有单词的子串,Java刷题篇,java,开发语言

📜2.分析题目

阅读题目后,可以拿到一个关键信息–words中所有字符串长度相等,这后续解题思路的一大关键,还有就是串联字串的字符串顺序可以不同。得到这两个关键信息后,我们就很容易联想到运用滑动窗口这个算法来解决问题。
好分析完题目后,我们就开始讲解算法的原理,如果你懂得滑动窗口的原理话,可以跳过直接观看算法原理的讲解。

📜3.算法原理

在此篇文章前,已经发布关于滑动窗口的讲解。
博客链接: 滑动窗口

🧠4.思路叙述

先前滑动窗口解决的问题,要么是一个数字一个数字进行遍历,要么是一个字符一个字符进行遍历,今天这题与众不同的是以一个字符串为单位进行遍历,使用哈希表来进行存储。

  • 我们创建两个哈希表。
  • 我们将words中的字符串存入哈希表1中。
  • 我们在循环遍历s的过程中,每遍历一个字符串就将其加入哈希表2中
  • 并且同时进行有效个数的判断以及维护窗口
  • 最后通过有效个数的比较返回值

✍1.进窗口

还是定义left和right左右指针来对窗口进行划分。每一次right和left指针递增的长度是words中字符串的长度,此时有一个难题,那就是从什么位置开始遍历呢?从第一个字符的位置开始遍历?
【Java刷题篇】串联所有单词的子串,Java刷题篇,java,开发语言
那么这种情况该如何处理?这种情况行不通,我们可以每个位置都进行尝试
从0–len的位置都进行尝试,这样就完美的解决了这个问题。
【Java刷题篇】串联所有单词的子串,Java刷题篇,java,开发语言

 int len = words[0].length();
 for (int i = 0; i < len; i++) {
 //整体大循环控制
 }

✍2.判断有效个数

我们创建两个哈希表。

HashMap<String,Integer> hashMap1 = new HashMap<>();
HashMap<String,Integer> hashMap2 = new HashMap<>();

我们将words中的字符串存入哈希表1中。

for (String ss:words) {
            hashMap1.put(ss, hashMap1.getOrDefault(ss,0)+1);
        }

首先确定循环的条件,由上述讲解中已经提到right的起始位置

 for (int right = i,left = i,count = 0; right+len <= s.length() ; right+= len) {
 
 }

我们在循环遍历s的过程中,每遍历一个字符串就将其加入哈希表2中,并且与哈希表1中存入的字符串进行比较,如果相同,有效个数就+1

   String in = s.substring(right,right+len);
       hashMap2.put(in,hashMap2.getOrDefault(in,0)+1);
   if (hashMap2.get(in) <= hashMap1.getOrDefault(in,0)){
   count++;
  }

✍3.维护窗口

再次过程中,我们要保证窗口的大小。同words中字符个数相等的窗口。

     int len = words[0].length();
     int m = words.length;
     if (right - left +1 > m*len){
        //出窗口
     }

✍4.出窗口

  String out = s.substring(left,left+len);
  if (hashMap2.get(out) <= hashMap1.getOrDefault(out,0)){
        count--;
     }
      hashMap2.put(out,hashMap2.get(out)-1);
     left+= len;

💥5.完整代码

 public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int len = words[0].length();
        int m = words.length;
        HashMap<String,Integer> hashMap1 = new HashMap<>();
        for (String ss:words) {
            hashMap1.put(ss, hashMap1.getOrDefault(ss,0)+1);
        }
        //大条件
        for (int i = 0; i < len; i++) {
            HashMap<String,Integer> hashMap2 = new HashMap<>();
            //入口位置的处理
            for (int right = i,left = i,count = 0; right+len <= s.length() ; right+= len) {
            //进窗口
                String in = s.substring(right,right+len);
                hashMap2.put(in,hashMap2.getOrDefault(in,0)+1);
                //有效个数的判断
                if (hashMap2.get(in) <= hashMap1.getOrDefault(in,0)){
                    count++;
                }
                //窗口大小的维护
                if (right - left +1 > m*len){
                //出窗口
                    String out = s.substring(left,left+len);
                    if (hashMap2.get(out) <= hashMap1.getOrDefault(out,0)){
                        count--;
                    }
                    hashMap2.put(out,hashMap2.get(out)-1);
                    left+= len;
                }
                //判断条件是否符合要求
                if (count == m){
                    list.add(left);
                }
            }
        }
        return list;
    }

以上就是所有内容,如果对你有帮助的话,点赞收藏支持一下吧!💞💞💞文章来源地址https://www.toymoban.com/news/detail-842302.html

到了这里,关于【Java刷题篇】串联所有单词的子串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++ | Leetcode C++题解之第30题串联所有单词的子串

    题目: 题解:

    2024年04月15日
    浏览(49)
  • 每日OJ题_算法_滑动窗口⑦_力扣30. 串联所有单词的子串

    目录 力扣30. 串联所有单词的子串 解析及代码 30. 串联所有单词的子串 - 力扣(LeetCode) 难度 困难 给定一个字符串  s   和一个字符串数组  words 。   words  中所有字符串  长度相同 。   s   中的  串联子串  是指一个包含   words  中所有字符串以任意顺序排列连接起来的

    2024年01月21日
    浏览(45)
  • 30. 串联所有单词的子串【memset(hash, 0, sizeof(hash)) 这样的方式真的不要再使用、leetcode有时真的会g的】

    30. 串联所有单词的子串 C代码:滑动窗口、字符串异位段 C代码:失败案例:哈希表保存重复出现

    2024年02月02日
    浏览(41)
  • 【新2023Q2模拟题JAVA】华为OD机试 - 符合条件的子串长度

    华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单 华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典 【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南 华为od机试,独家整理 已参加机试人员的实战技巧 给定字符串 A 、 B 和正整数 V , 字符串 A 和 B 的长度相

    2023年04月18日
    浏览(74)
  • java数据结构与算法刷题-----LeetCode209. 长度最小的子数组

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 代码:时间复杂度O(n).空间复杂度O(1)

    2024年01月21日
    浏览(54)
  • 对字符串中所有单词进行倒排-C语言/Java

    描述         输入一个字符串,输出字符串中单词的倒序。 要求 构成单词的字符只有26个大写或小写英文字母。 非构成单词的字符均视为单词间隔符; 倒排后的单词间隔符以一个空格表示;如果原字符串中相邻单词间有多个间隔符时,倒排转换后也只允许出现一个空格间隔

    2024年02月12日
    浏览(47)
  • 【刷题篇】贪心算法(一)

    假设1元、2元、5元、10元、20元、50元、100元的纸币分别由c0,c1,c2,c3,c4,c5,c6张。现在要用这些钱来支付K元,至少要用多少张纸币?

    2024年02月09日
    浏览(45)
  • 【刷题篇】贪心算法

    假设1元、2元、5元、10元、20元、50元、100元的纸币分别由c0,c1,c2,c3,c4,c5,c6张。现在要用这些钱来支付K元,至少要用多少张纸币?

    2024年02月09日
    浏览(37)
  • 【刷题篇】链表(下)

    各位读者们好,本期我们来填填之前留下的坑,继续来讲解几道和链表相关的OJ题。但和上期单向链表不一样的是,我们今天的题目主要是于环形链表有关,下面让我们一起看看吧。 💻本期的题目有: 环形链表 、 环形链表II 、 求环形链表环长 a.题目 b.题解分析 第一种方法

    2024年01月25日
    浏览(43)
  • 蓝桥杯刷题篇①

    前言:hello各位童学们好呀!许久不见!本文为本人的蓝桥杯OJ的刷题笔记!文章隶属于专栏蓝桥杯,该专栏的目的是为了记录自己的刷题记录和学习过程,激励自己不断前行,为明年的ACM、ICPC、蓝桥杯等比赛做足准备,也希望可以帮助到一些同样在刷题道路上的小伙伴们!

    2024年02月09日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包