算法day04

第一题 :

209. 长度最小的子数组

有上题可知,我们会采用双指针和单调性的思路来解决

        我们本题采用左右双指针从数组的0位置同向前进,所以将此类模型称为滑块;

步骤思路如下:

步骤一:

        定义所有双指针都指向数组的0号位置;

步骤二:数组进窗口

        右指针开始向右移动;

步骤三:判断是否数组进窗口或者出窗口

        当当前窗口中的数字sum小于t时,右指针继续向右移动,直到数组之和大于等于t;

        如上图所示,当前的左指针向右移动,将左指针之前所指的元素退出窗口;

此时重复上述的操作,直到right指针到达数组的最右端;

同时我们每一次在判断sum和要要求值之后都要更新len变量的结果

        代码如下所示:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
         int n = nums.length,sum = 0,lenght = Integer.MAX_VALUE;
        for(int left = 0,right = 0;right < n;right++){
         sum +=nums[right];
            while(sum >= target){
                lenght = Math.min(lenght,(right-left+1));
                sum -=nums[left];
                left ++;
            }
        }
        return lenght == Integer.MAX_VALUE ? 0:lenght;
    }
}

第二题:

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

如上题所示:

        本题采用滑块的相关知识点,如上题故事;

本题主要会采用如下的创新点:

 //把字符串变成字符数组,s1里面的每一个元素都是每一个字符的ascall值

    char[] s = ss.toCharArray();

//用数组模拟哈希表

//即用数组的下标为0的字符来表示ascall值为1 的数组。。。

//用数组里面的数字来表示该字符在hash值里面出现的次数

    int[] hash = new int[128];

用ascall值来映射数组中的字符,同时用数组来类似于hash表,当hash表中存放相应字符的出现次数,每次有相应的字符进入滑块,该字符的出现次数加一,当该hash中相应的位置如果存放的数值大于一时,则滑块中有重复的字符,应该采取进一步的措施;

解题步骤如下:

步骤一:

        定义所有双指针都指向数组的0号位置;

步骤二:数组进窗口

        让字符开始进入hash表;该数组存放的hash表的位置上数据+1;

判断当右指针所指的hash表中数据>1时,我们要移动左指针,将之前进入到窗口里面的元素出去,同时hash表中的数据--;

        同时每一次元素出窗口之后要更新窗口长度并记录在案;

代码如下所示:

class Solution {
    public int lengthOfLongestSubstring(String ss) {
    //把字符串变成字符数组,s1里面的每一个元素都是每一个字符的ascall值
    char[] s = ss.toCharArray();
    //用数组模拟哈希表
    //即用数组的下标为0的字符来表示ascall值为1 的数组。。。
    //用数组里面的数字来表示该字符在hash值里面出现的次数
    int[] hash = new int[128];
   int n = s.length;
    int  res =  0;
    for(int left = 0,right = 0;right < n;){
        hash[s[right]] ++;
        while(hash[s[right]] > 1){
            hash[s[left]] --;
            left ++;
            res= Math.max(res,right-left+1); 
        }
         res= Math.max(res,right-left+1);
         right++;
    } 
    return res;
    }
}

ps:本次的内容就到这里了,如果对你有所帮助的话,就请一键三连哦,文章图片是我喜欢的xox,在这里给大家安利一下哦!!!

相关推荐

  1. 复试 || 就业day09(2024.01.04)算法

    2024-05-11 07:06:13       51 阅读
  2. 贪心算法day05

    2024-05-11 07:06:13       53 阅读
  3. 贪心算法day01

    2024-05-11 07:06:13       56 阅读
  4. 贪心算法Day02

    2024-05-11 07:06:13       62 阅读
  5. 贪心算法day03

    2024-05-11 07:06:13       54 阅读
  6. 贪心算法Day06

    2024-05-11 07:06:13       39 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-05-11 07:06:13       75 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-05-11 07:06:13       80 阅读
  3. 在Django里面运行非项目文件

    2024-05-11 07:06:13       64 阅读
  4. Python语言-面向对象

    2024-05-11 07:06:13       75 阅读

热门阅读

  1. 【C++刷题】优选算法——递归第一辑

    2024-05-11 07:06:13       30 阅读
  2. 开源工时填报管理系统部署

    2024-05-11 07:06:13       25 阅读
  3. leetcode刷题

    2024-05-11 07:06:13       27 阅读
  4. 设计模式-08 - 模板方法模式 Template Method

    2024-05-11 07:06:13       27 阅读
  5. 微服务全局异常处理

    2024-05-11 07:06:13       27 阅读
  6. 结合场景,浅谈深浅度拷贝

    2024-05-11 07:06:13       28 阅读