LeetCode热题HOT100:76. 最小覆盖子串,84.柱状图中最大的矩形、96. 不同的二叉搜索树

LeetCode 热题 HOT 100

76. 最小覆盖子串

题目:给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:“BANC”

package ricky.com.Hot100;

/**
 * @Author xdg
 */
public class minWindow {
    /*
     * 76. 最小覆盖子串
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。
     * 注意:
     * 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
     * 如果 s 中存在这样的子串,我们保证它是唯一的答案。
     */
    class Solution {
        public String minWindow(String s, String t) {
            if (t == null || t.length() == 0) {
                return "";
            }

            //把t中的每个字符出现的次数统计出来
            int[] arr = new int[128];
            for (int i = 0; i < t.length(); i++) {
                arr[t.charAt(i)]++;
            }

            int l = 0;
            int r = 0;
            //记录t中所有字符出现的次数,为0时说明找到一个答案
            int total = t.length();
            int len = Integer.MAX_VALUE;
            //字符串的起始位置
            int start = 0;
            for (r = 0; r < s.length(); r++) {
                //此时s.charAt(r)字符在t串中,total--
                if (arr[s.charAt(r)] > 0) {
                    total--;
                }
                //arr中t串中对应的字符数量也要减一,但它始终是>=0的,如果字符不在t串中,会减成负数
                arr[s.charAt(r)]--;

                //找到答案,记录
                while (total == 0) {
                    //因为是最小子串,所以取小值
                    if (len > r - l + 1) {
                        //字符串的长度
                        len = r - l + 1;
                        //记录起始位置
                        start = l;
                    }

                    //在将字符移出窗口之前,先要加1,不然移出后就晚了
                    arr[s.charAt(l)]++;
                    if (arr[s.charAt(l)] > 0) {
                        total++;
                    }
                    //窗口右移一位
                    l++;
                }

            }

            return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);

        }
    }
}

代码解释:

if (t == null || t.length() == 0) {
    return "";
}

如果 t 为空或长度为0,则直接返回空字符串。

int[] arr = new int[128];
for (int i = 0; i < t.length(); i++) {
    arr[t.charAt(i)]++;
}

定义一个长度为128的整型数组 arr,用于统计字符串 t 中每个字符出现的次数。遍历字符串 t,将 arr 中对应字符的计数加1。

int l = 0;
int r = 0;
int total = t.length();
int len = Integer.MAX_VALUE;
int start = 0;

定义五个变量,分别是左指针 l、右指针 r、字符串 t 的长度 total、最小子串长度 len 和最小子串的起始位置 start

for (r = 0; r < s.length(); r++) {
    if (arr[s.charAt(r)] > 0) {
        total--;
    }
    arr[s.charAt(r)]--;
    while (total == 0){
        if (len > r - l + 1){
            len = r - l + 1;
            start = l;
        }
        arr[s.charAt(l)]++;
        if (arr[s.charAt(l)] > 0){
            total++;
        }
        l++;
    }
}

遍历字符串 s,用滑动窗口的方法查找最小子串。当右指针 r 指向的字符在 t 中出现时,将 total 减1;同时将数组 arr 中对应字符的计数减1。当 total 等于0时,表示当前窗口包含了 t 中的所有字符,需要将左指针 l 向右移动,缩小窗口范围。每次移动左指针 l 时,需要将数组 arr 中对应字符的计数加1,如果加1后该字符的计数大于0,则将 total 加1。此外,还需要更新最小子串的长度和起始位置。

return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);

返回最小子串,如果 len 的值没有被更新过,即没有找到符合要求的子串,则返回空字符串。

84. 柱状图中最大的矩形

题目:给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
**示例 1:
在这里插入图片描述

输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10

package ricky.com.Hot100;

/**
 * @Author xdg
 */
public class largestRectangleArea {
    /*84. 柱状图中最大的矩形
    给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
    求在该柱状图中,能够勾勒出来的矩形的最大面积。*/
    class Solution {
        public int largestRectangleArea(int[] heights) {
            // 定义两个数组,分别用来存储当前柱子左边第一个小于其高度的柱子的下标和右边第一个小于其高度的柱子的下标
            int[] leftMin = new int[heights.length];
            int[] rightMin = new int[heights.length];
            // 初始化左边第一个小于其高度的柱子的下标,第一个柱子左边没有小于其高度的柱子
            leftMin[0] = -1;
            // 初始化右边第一个小于其高度的柱子的下标,最后一个柱子右边没有小于其高度的柱子
            rightMin[heights.length - 1] = heights.length;

            // 遍历所有柱子,计算左边第一个小于其高度的柱子的下标
            for (int i = 1; i < heights.length; i++) {
                int temp = i - 1;
                // 如果当前柱子的高度大于等于左边某个柱子的高度,则将左边柱子的左边第一个小于其高度的柱子的下标作为当前柱子的左边第一个小于其高度的柱子的下标
                while (temp >= 0 && heights[temp] >= heights[i]) {
                    temp = leftMin[temp];
                }
                leftMin[i] = temp;
            }

            // 遍历所有柱子,计算右边第一个小于其高度的柱子的下标
            for (int i = heights.length - 2; i >= 0; i--) {
                int temp = i + 1;
                // 如果当前柱子的高度大于等于右边某个柱子的高度,则将右边柱子的右边第一个小于其高度的柱子的下标作为当前柱子的右边第一个小于其高度的柱子的下标
                while (temp < heights.length && heights[temp] >= heights[i]) {
                    temp = rightMin[temp];
                }
                rightMin[i] = temp;
            }

            // 遍历所有柱子,计算能够勾勒出来的矩形的最大面积
            int res = 0;
            for (int i = 0; i < heights.length; i++) {
                // 当前柱子的高度乘以左边第一个小于其高度的柱子和右边第一个小于其高度的柱子之间的距离就是当前能够勾勒出来的矩形的面积
                res = Math.max(res, heights[i] * (rightMin[i] - leftMin[i] - 1));
            }

            // 返回最大面积
            return res;
        }
    }
}

96. 不同的二叉搜索树

题目:给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?
返回满足题意的二叉搜索树的种数。
**示例 1:在这里插入图片描述

输入:n = 3
输出:5

思路分析: 使用一个一维数组 dp 来记录每个节点数能够构成的二叉搜索树的个数。在遍历每个节点数的过程中,枚举左子树节点数 j 和右子树节点数 i-1-j,然后将左右子树能够构成的所有情况之和累加到 dp[i] 中,最终返回 dp[n] 即可。

package ricky.com.Hot100;

/**
 * @Author xdg
 */
class Solution {
    public int numTrees(int n) {
        // 如果输入 n 为 0,返回 0
        if (n == 0) {
            return 0;
        }

        // 定义数组 dp,dp[i] 表示 i 个节点能够构成的二叉搜索树的个数
        int[] dp = new int[n + 1];

        // 初始化 dp[0] 为 1,表示空树也算一种二叉搜索树
        dp[0] = 1;

        // 遍历每个节点数量,从 1 到 n
        for (int i = 1; i <= n; i++) {
            // 遍历左子树节点数量 j,从 0 到 i-1
            for (int j = 0; j < i; j++) {
                // dp[j] 表示左子树能够构成的二叉搜索树的个数
                // dp[i - 1 - j] 表示右子树能够构成的二叉搜索树的个数
                // 二者相乘即为以 j 为根节点,左子树有 dp[j] 种情况,右子树有 dp[i - 1 - j] 种情况的所有情况之和
                dp[i] += dp[j] * dp[i - 1 - j];
            }
        }

        // 返回 dp[n],即 n 个节点能够构成的二叉搜索树的个数
        return dp[n];
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

ADManager Plus:简化 Active Directory 管理的完美工具

在企业中&#xff0c;Active Directory&#xff08;AD&#xff09;是一个非常重要的组件&#xff0c;用于管理和控制所有计算机和用户的访问权限。然而&#xff0c;AD的管理和维护需要一定的技术能力和时间成本。为了简化这个过程&#xff0c;ManageEngine 推出了 ADManager Pl…

Leetcode-二叉树

1.中序-后序构建二叉树 106. 从中序与后序遍历序列构造二叉树 - 力扣&#xff08;LeetCode&#xff09; 1. 首先根据后序&#xff08;左右中&#xff09;确定顶点元素&#xff1b; 2. 根据顶点元素划分中序序列&#xff1b; 3. 根据划分中序序列中-左子树的长度&#xff0c;进…

数据类型及变量的定义、使用和注意事项

数据类型 计算机存储单元 变量的定义格式&#xff1a; 数据类型 变量名数据值; 我们知道计算机是可以用来存储数据的&#xff0c;但是无论是内存还是硬盘&#xff0c;计算机存储设备的最小信息单元叫“位( bit ) "&#xff0c;我们又称之为“比特位”&#xff0c;通常用…

除了Java,还可以培训学习哪些IT技术?

除了Java&#xff0c;还可以培训学习哪些IT技术&#xff1f; 转行IT学Java似乎已经成为很多人的首选&#xff0c;原因无非是开发技术含量高、开发有前景、开发是一个互联网企业的核心岗位&#xff0c;最重要的是开发薪资待遇高。但其实只单纯因为薪资选择Java的话&#xff0c;小…

百万赞同:网络安全为什么缺人? 缺什么样的人?

1.网络安全为什么缺人? 缺人的原因是有了新的需求 以前的时候&#xff0c;所有企业是以产品为核心的&#xff0c;管你有啥漏洞&#xff0c;管你用户信息泄露不泄露&#xff0c;我只要做出来的产品火爆就行。 这一切随着《网络安全法》、《数据安全法》、《网络安全审查办法》…

什么是机器学习?

目录 简介 机器学习可以做什么 机器学习未来的趋势 总结 简介 机器学习是一种人工智能领域中的技术&#xff0c;其主要目的是让计算机能够自动进行模式识别、数据分析和预测。 机器学习的起源可以追溯到20世纪50年代&#xff0c;当时美国的Arthur Samuel在一篇论文中提出了相关…

静态时序分析Static Timing Analysis4——多时钟域和多时钟时序检查

文章目录 前言一、多时钟域时序分析1、慢时钟域到快时钟域1.1 建立时间检查1.2 保持时间检查1.3 多周期检查 2、快时钟域到慢时钟域2.1 建立时间检查2.2 保持时间检查2.3 合理的约束 3、总结 二、多时钟1、整数倍关系2、非整数倍关系 三、相位移动 前言 2023.4.12 这里讲的多时…

助力研发效能变革,第七届Techo TVP 开发者峰会圆满落下帷幕

引言 在互联网数字企业结束“野蛮扩张”、追求高质量增长的今天&#xff0c;研发效能已然成为企业关注的核心命题。伴随着云原生概念在软件领域的落地生根&#xff0c;云原生正驱动软件应用设计、实现、部署及运维方式的巨变&#xff0c;为研发效能治理带来了新的挑战与机遇&am…

vue-router3.0处理页面滚动部分源码分析

在使用vue-router3.0时候&#xff0c;会发现不同的路由之间来回切换&#xff0c;会滚动到上次浏览的位置&#xff0c;今天就来看看这部分的vue-router中的源码实现。 无论是基于hash还是history的路由切换&#xff0c;都对滚动进行了处理&#xff0c;这里分析其中一种即可。 无…

SpringBoot

文章目录 创建SpringBoot项目快速入门创建Controller启动项目 打包项目创建工件 SpringBoot概述SpringBoot优点起步依赖切换Web服务器 配置文件配置文件application.propertiesapplication.ymlapplication.yaml 三种配置文件优先级yaml格式读取配置数据&#xff08;yml为例&…

windows系统管理_Windows server 2016 组管理与授权

组账户的概述 在 windows 服务器中&#xff0c;当我们需要为多个用户设置相同的权限时&#xff0c;一个一个的逐一设置会比较 麻烦&#xff0c;这个时候我们就需要用到另一种模式&#xff0c;组账户&#xff0c;使用此账户来进行简化操作。 在以后的职场中&#xff0c;每家公司…

Windows环境下调试DAB-DETR与Deformable-DETR

先前都是在服务器上运行DETR的相关程序&#xff0c;服务器使用的是Linux&#xff0c;所以运行较为简单&#xff0c;但如果想要简单的debug的话就没必要使用服务器了&#xff0c;今天便来在Winodws环境下调试DETR类项目&#xff0c;这里以Deformable-DETR与DAB-DETR为例。 首先是…

I.MX6U开发板使用OTG烧写系统

1.系统烧写 在实际的产品开发中肯定不可能通过网络来运行&#xff0c;否则没网的时候产品岂不 是就歇菜了。因此我们需要将 uboot、linux kernel、.dtb(设备树)和 rootfs 这四个文件烧写到板子 上的 EMMC、NAND 或 QSPI Flash 等其他存储设备上&#xff0c;这样不管有没有网络我…

R语言ggplot2 | 绘制随机森林重要性+相关性热图

&#x1f4cb;文章目录 原图复现准备数据集及数据处理构建不同分类随机森林模型的并行计算绘制随机森林变量重要性柱状图计算数据集的相关性热图可视化合并随机森林重要性和热图 附上所有代码 在文献中&#xff0c;我们经常遇到随机森林和相关性热图的组合图片(下图)&#xff0…

Vue3——一文入门Vue3

Vue3的优势 1. 性能的提升 打包大小减少41% 初次渲染快55%&#xff0c;更新渲染快133% 内存减少54% … 2. 源码的升级 使用Proxy代替defineProperty实现响应式 重写虚拟DOM的实现和Tree-Shaking … 3. 拥抱TypeScript Vue3可以更好的支持TypeScript 4. 新的特性 1.C…

什么是文件共享软件?文件传输软件如何共享?

它是一个文件共享软件应用程序&#xff0c;可让强大的数据保护层下将任何大小的文件发送到世界上的任何地方。以光速发送和共享无限数量的文件。可以提交门户并使用语言&#xff0c;品牌&#xff0c;存储等自定义门户。可以选择一个存储点&#xff0c;例如文件传输软件&#xf…

零基础可以学习数据分析吗,有没有好的培训机构推荐?

数据分析从沿海火到了中西部的软件园&#xff0c;从传统互联网企业火到了新经济领域&#xff0c;火到了第一二产业。数字化成为这个时代的标签&#xff0c;而数据也成为了最有价值的资源&#xff0c;更多企业重视数据&#xff1b;因为有了真实数据的支撑&#xff0c;所有的决策…

【软考备战·希赛网每日一练】2023年4月19日

文章目录 一、今日成绩二、错题总结第一题第二题第三题 三、知识查缺 题目及解析来源&#xff1a;2023年04月19日软件设计师每日一练 一、今日成绩 二、错题总结 第一题 解析&#xff1a; 第二题 解析&#xff1a; server-side n.服务器端 enterprise n.企业 client n.客户 d…

常见排序算法

目录 一、插入排序 1、直接插入排序 2、希尔排序(缩小增量插入排序&#xff09; 二、选择排序 三、堆排序 四、冒泡排序 五、快速排序&#xff08;递归&#xff09; 1、交换法 2、挖坑法 3、前后指针法&#xff08;推荐&#xff09; 4、快排再优化 六、快速排序&…

树上差分(点差分/边差分)

树上差分一般有两种类型的题目&#xff0c;一种是对边进行差分&#xff0c;另一种就是对点进行差分。 对应的操作也有两种&#xff0c;对边进行差分的对应操作就是给定一对节点(u,v)&#xff0c;让我们把u到v之间路径上的边权都加val&#xff0c;对点进行差分的对应操作就是给…
最新文章