代码编织梦想

 目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣


描述:

给你一个整数数组 nums 和两个整数:left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组,并返回满足条件的子数组的个数。

生成的测试用例保证结果符合 32-bit 整数范围。

示例 1:

输入:nums = [2,1,4,3], left = 2, right = 3
输出:3
解释:满足条件的三个子数组:[2], [2, 1], [3]

示例 2:

输入:nums = [2,9,2,5,6], left = 2, right = 8
输出:7

提示:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109
  • 0 <= left <= right <= 109

解题思路:

* 解题思路:
* 我们首先可以把nums分为若干小的数组,分割的依据就是以>right的来分割。
* 找到这样的小数组a中,再把数分为两种,在[left,right]范围内和不再范围内的。
* 首先这个小数组a长度为4的情况下,一共有1+2+3+4种子数组可能,
* 我们在继续分割,找出这个小数组a中不包含任何[left,right]范围内数值的更小数组b。
* 数组a所有的可能性,减去数组b所有的可能性,就是包含[left,right]的可能性。
* 所有符合的可能性累加,就是我们想要的结果

代码:

public class Solution795 {
    int[] times;

    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        times = new int[nums.length + 1];
        int sum = 0;
        for (int i = 1; i <= nums.length; i++) {
            sum += i;
            times[i] = sum;
        }
        int start = 0;
        int index = 0;
        int result = 0;
        while (index < nums.length) {
            int value = nums[index++];
            if (value <= right) {
                continue;
            }
            result += search(nums, start, index - 1, left);
            start = index;
        }
        result += search(nums, start, nums.length, left);
        return result;
    }

    private int search(int[] nums, int start, int end, int left) {
        if (start == end) {
            return 0;
        }
        int result = 0;
        int index = start;
        int num = 0;
        while (index < end) {
            if (nums[index] >= left) {
                result += times[num];
                num = 0;
                index++;
                continue;
            }
            index++;
            num++;
        }
        result += times[num];
        return times[end - start] - result;
    }
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/rzleilei/article/details/128012804

【算法&面试】分治算法 归并 递归 力扣 493. 翻转对 327. 区间和的个数-爱代码爱编程

分治算法是啥? 分治算法也有动态规划和贪心算法的概念,动态规划:把大问题分解成一步一步的小问题,递归解决。贪心算法:每次得到局部最优解。 分治算法:把大问题分解成小问题,汇总所有小问题的结果。快排、二分查找都是典型的分治算法。 JDK中的Fork-Join就是一个典型的并行的分治框架。它的主要作用是把大任务分割成若干个小任务,再对每个小任务得到的结果

​力扣解法汇总10-盛最多水的容器-爱代码爱编程

原题链接:力扣 描述: 给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 说明:你不能倾斜容器。 实例1:   输入:[1,8,6,2,

​力扣解法汇总689-三个无重叠子数组的最大和-爱代码爱编程

原题链接:力扣 描述: 给你一个整数数组 nums 和一个整数 k ,找出三个长度为 k 、互不重叠、且全部数字和(3 * k 项)最大的子数组,并返回这三个子数组。 以下标的数组形式返回结果,数组中的每一项分别指示每个子数组的起始位置(下标从 0 开始)。如果有多个结果,返回字典序最小的一个。 示例 1: 输入:nums = [1,2,1

力扣解法汇总33-搜索旋转排序数组-爱代码爱编程

原题链接:力扣 描述: 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k

力扣解法汇总39-组合总和-爱代码爱编程

原题链接:力扣 描述: 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同

力扣解法汇总41-缺失的第一个正数-爱代码爱编程

原题链接:力扣 描述: 给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。   示例 1: 输入:nums = [1,2,0] 输出:3 示例 2: 输入:nums = [3,4,-1,1] 输出:2 示例 3: 输入:nums = [7,8,9

力扣解法汇总2100-适合打劫银行的日子-爱代码爱编程

原题链接:力扣 描述: 你和一群强盗准备打劫银行。给你一个下标从 0 开始的整数数组 security ,其中 security[i] 是第 i 天执勤警卫的数量。日子从 0 开始编号。同时给你一个整数 time 。 如果第 i 天满足以下所有条件,我们称它为一个适合打劫银行的日子: 第 i 天前和后都分别至少有 time 天。 第 i 天前连续

​力扣解法汇总436-寻找右区间_失落夏天的博客-爱代码爱编程

 目录链接: 力扣编程题-解法汇总_分享+记录-CSDN博客 GitHub同步刷题项目: https://github.com/September26/java-algorithms 原题链接:力扣 描述: 给你一个区间数组 intervals ,其中 intervals[i] = [starti, endi] ,且每个 starti

​力扣解法汇总532-数组中的 k-diff 数对_失落夏天的博客-爱代码爱编程

目录链接: 力扣编程题-解法汇总_分享+记录-CSDN博客 GitHub同步刷题项目: https://github.com/September26/java-algorithms 原题链接:力扣 描述: 给你一个整数数组 nums 和一个整数 k,请你在数组中找出 不同的 k-diff 数对,并返回不同的 k-diff 数对 的数目

leetcode 494.目标和 动态规划背包问题 (c++版本)_学不完了ccccc的博客-爱代码爱编程

题目描述 说白了就是让一部分数减去剩下的一部数使得差值为target,计算有多少中组合的方法 下面来个数学公式推导一下 l

刷题看力扣,刷了两个月 leetcode 算法,顺利拿下百度、阿里等大厂的 offer_java程序v的博客-爱代码爱编程

随着互联网寒潮的到来, 越来越多的互联网公司提高了面试的难度,其中之一就是加大了面试当中手撕算法题的比例。这里说的算法题不是深度学习,机器学习这类的算法,而是排序,广度优先,动态规划这类既考核数据结构也考核编程能力的题目。刷题的网址非常的多,其中以 leetcode 是最为出名的。 在刷题上,我花了大量的时间,蹚了许多的坑,总结了一下,主要有这三个问题:

代码随想录算法训练营第四十四天| leetcode518. 零钱兑换 ii、leetcode377. 组合总和 Ⅳ_喵的博客-爱代码爱编程

一、LeetCode518. 零钱兑换 II         1:题目描述(518. 零钱兑换 II)         给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。         请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。         假设每一种面额的

leetcode 刷题 log day 44_音音子-的博客-爱代码爱编程

【完全背包问题】完全背包问题是指不限制物品的数量,可以无限制取物品。而 01 背包问题是每个物品只能取一次。 【求放满背包共有几种方法】: 递推公式:一般都是 dp[j] += dp[j - weight[i]];遍历顺序

【leetcode】1824. minimum sideway jumps_记录算法题解的博客-爱代码爱编程

题目地址: https://leetcode.com/problems/minimum-sideway-jumps/description/ 给定一条宽为

leetcode hot 100 —— 23.合并k个升序链表_hdu-五七小卡的博客-爱代码爱编程

题目 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 思路 在做本题之前,先考虑一下,如何合并两个有序链表,见 21.合并两个有序链表 最直接的思路就是,用一

算法学习 | 深度优先搜索~一条道走到黑_li_yizya的博客-爱代码爱编程

目录 员工的重要性 图像渲染  岛屿的周长  被围绕的区域 岛屿数量    深度优先搜索(Depth First Search):深度优先搜索属于图算法的一种,其过程主要是对每一个可能的分支路径深入到不能再深入到为止,而且每个节点只能访问一次。深度优先搜索本质上就是暴力搜索,遍历了所有可能的情况,必然能得到解。DFS搜索的流程是一

【leetcode】882. 细分图中的可到达节点_schanappi的博客-爱代码爱编程

题目描述 给你一个无向图(原始图),图中有 n 个节点,编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链,每条边之间的新节点数各不相同。 图用由边组成的二维数组 edges 表示,其中 edg

leetcode337打家劫舍3刷题打卡_水番茄的博客-爱代码爱编程

337. 打家劫舍 III - 力扣(Leetcode) 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。 除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明