涉及知识点 归并排序 题目 给你一个整数数组nums以及两个整数lower和upper。求数组中，值位于范围[lower,upper]（包含lower和upper）之内的区间和的个数。区间和S(i,j)表示在nums中，位置从i到j的元素之和，包含i和j(i≤j)。示例1：输入：nums=[-2,5,-1],lower=-2,upper=2输出：3解释：存在三个区间：[0,0]、[2,2]和[0,2]，对应的区间和分别是：-2、-1、2。示例2：输入：nums=[0],lower=0,upper=0输出：1参数范围1<=nums.length<=105-231<=nums[...

涉及知识点 二分查找 题目 给定一个整数n和一个无重复黑名单整数数组blacklist。设计一种算法，从[0,n1]范围内的任意整数中选取一个未加入黑名单blacklist的整数。任何在上述范围内且不在黑名单blacklist中的整数都应该有同等的可能性被返回。优化你的算法，使它最小化调用语言内置随机函数的次数。实现Solution类:Solution(intn,int[]blacklist)初始化整数n和被加入黑名单blacklist的整数intpick()返回一个范围为[0,n1]且不在黑名单blacklist中的随机整数示例1：输入[“Solution”,“pick”,“pick”,“...

本文涉及的基础知识点 二分查找 题目 给你一个下标从0开始、长度为n的数组usageLimits。你的任务是使用从0到n1的数字创建若干组，并确保每个数字i在所有组中使用的次数总共不超过usageLimits[i]次。此外，还必须满足以下条件：每个组必须由不同的数字组成，也就是说，单个组内不能存在重复的数字。每个组（除了第一个）的长度必须严格大于前一个组。在满足所有条件的情况下，以整数形式返回可以创建的最大组数。示例1：输入：usageLimits=[1,2,5]输出：3解释：在这个示例中，我们可以使用0至多一次，使用1至多2次，使用2至多5次。一种既能满足所有条件，又能创建最多组的方式是：...

涉及知识点 二分查找 题目 一个正整数如果能被a或b整除，那么它是神奇的。给定三个整数n,a,b，返回第n个神奇的数字。因为答案可能很大，所以返回答案对109+7取模后的值。示例1：输入：n=1,a=2,b=3输出：2示例2：输入：n=4,a=2,b=3输出：6提示：1<=n<=1092<=a,b<=4104 分析 令f(x)等于[1,x]神奇数字的数量，寻找第一个f(x)大于等于n的x，用左开右闭的二分查找。结果一定在[1,max(a,b)n]中。 神奇数字数量 神奇数字数量等于=被a整除+被b整除同时被a和b整除同时被a和b整除：被a和b的最小公倍数整除，不是被a...

涉及知识点 二分查找 题目 几乎每一个人都用乘法表。但是你能在乘法表中快速找到第k小的数字吗？乘法表是大小为mxn的一个整数矩阵，其中mat[i][j]ij（下标从1开始）。给你三个整数m、n和k，请你在大小为mxn的乘法表中，找出并返回第k小的数字。示例1：输入：m=3,n=3,k=5输出：3解释：第5小的数字是3。示例2：输入：m=2,n=3,k=6输出：6解释：第6小的数字是6。参数范围：1<=m,n<=31041<=k<=mn 分析 二分枚举乘积，若果小于当前乘积的数量小于k，则不是。如果有个乘积的数量大于等于k，则取第一个，用左开右闭空间，(0,mm]。由于...

本文涉及的基础知识点 二分查找 题目 以字符串的形式给出n,以字符串的形式返回n的最小好进制。如果n的k(k>=2)进制数的所有数位全为1，则称k(k>=2)是n的一个好进制。示例1：输入：n=“13”输出：“3”解释：13的3进制是111。示例2：输入：n=“4681”输出：“8”解释：4681的8进制是11111。示例3：输入：n=“1000000000000000000”输出：“999999999999999999”解释：1000000000000000000的999999999999999999进制是11。参数范围：n的取值范围是[3,10^18]n没有前导0 分析 值相...

涉及知识点 二分动态规划题目给你一个下标从0开始的整数数组nums。nums一个长度为k的子序列指的是选出k个下标i0<i1<…<ik-1，如果这个子序列满足以下条件，我们说它是平衡的：对于范围[1,k1]内的所有j，nums[ij]nums[ij-1]>=ijij-1都成立。nums长度为1的子序列是平衡的。请你返回一个整数，表示nums平衡子序列里面的最大元素和。一个数组的子序列指的是从原数组中删除一些元素（也可能一个元素也不删除）后，剩余元素保持相对顺序得到的非空新数组。示例1：输入：nums=[3,3,5,6]输出：14解释：这个例子中，选择子序列[3,5,6...

题目 给定长度分别为m和n的两个数组，其元素由0-9构成，表示两个自然数各位上的数字。现在从这两个数组中选出k(k<=m+n)个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。求满足该条件的最大数。结果返回一个表示该最大数的长度为k的数组。说明:请尽可能地优化你算法的时间和空间复杂度。示例1:输入:nums1=[3,4,6,5]nums2=[9,1,2,5,8,3]k=5输出:[9,8,6,5,3]示例2:输入:nums1=[6,7]nums2=[6,0,4]k=5输出:[6,7,6,0,4]示例3:输入:nums1=[3,9]nums2=[8,9]k=3...

本文涉及的基础知识点 二分查找 题目 给你一个二维整数数组envelopes，其中envelopes[i]=[wi,hi]，表示第i个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。注意：不允许旋转信封。示例1：输入：envelopes=[[5,4],[6,4],[6,7],[2,3]]输出：3解释：最多信封的个数为3,组合为:[2,3]=>[5,4]=>[6,7]。示例2：输入：envelopes=[[1,1],[1,1...

题目 给定长度分别为m和n的两个数组，其元素由0-9构成，表示两个自然数各位上的数字。现在从这两个数组中选出k(k<=m+n)个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。求满足该条件的最大数。结果返回一个表示该最大数的长度为k的数组。说明:请尽可能地优化你算法的时间和空间复杂度。示例1:输入:nums1=[3,4,6,5]nums2=[9,1,2,5,8,3]k=5输出:[9,8,6,5,3]示例2:输入:nums1=[6,7]nums2=[6,0,4]k=5输出:[6,7,6,0,4]示例3: 输入:nums1=[3,9]nums2=[8,9]k=...

题目 有n个气球，编号为0到n1，每个气球上都标有一个数字，这些数字存在数组nums中。现在要求你戳破所有的气球。戳破第i个气球，你可以获得nums[i1]nums[i]nums[i+1]枚硬币。这里的i1和i+1代表和i相邻的两个气球的序号。如果i1或i+1超出了数组的边界，那么就当它是一个数字为1的气球。求所能获得硬币的最大数量。示例1：输入：nums=[3,1,5,8]输出：167解释：nums=[3,1,5,8]-->[3,5,8]-->[3,8]-->[8]-->[]coins=315+358+138+181=167示例2：输入：nums=[1,5]输出：1...

题目 给你一个整数数组nums，按要求返回一个新数组counts。数组counts有该性质：counts[i]的值是nums[i]右侧小于nums[i]的元素的数量。示例1：输入：nums=[5,2,6,1]输出：[2,1,1,0]解释：5的右侧有2个更小的元素(2和1)2的右侧仅有1个更小的元素(1)6的右侧有1个更小的元素(1)1的右侧有0个更小的元素示例2：输入：nums=[-1]输出：[0]示例3：输入：nums=[-1,-1]输出：[0,0]参数范围1<=nums.length<=105-104<=nums[i]<=104 2023年3月版 用的树状数组 ...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频 题目 给你一个长度为n的数组nums，该数组由从1到n的不同整数组成。另给你一个正整数k。统计并返回nums中的中位数等于k的非空子数组的数目。注意：数组的中位数是按递增顺序排列后位于中间的那个元素，如果数组长度为偶数，则中位数是位于中间靠左的那个元素。例如，[2,3,1,4]的中位数是2，[8,4,3,5,1]的中位数是4。子数组是数组中的一个连续部分。示例1：输入：nums=[3,2,1,4,5],k=4输出：3解释：中位数等于4的子数组有：[4]、[4,5]和[1,4,5]。示例2：输入：num...

涉及知识点 深度优化(DFS)记忆化 题目 节点0处现有一棵由n个节点组成的无向树，节点编号从0到n1。给你一个长度为n1的二维整数数组edges，其中edges[i]=[ai,bi]表示在树上的节点ai和bi之间存在一条边。另给你一个下标从0开始、长度为n的数组coins和一个整数k，其中coins[i]表示节点i处的金币数量。从根节点开始，你必须收集所有金币。要想收集节点上的金币，必须先收集该节点的祖先节点上的金币。节点i上的金币可以用下述方法之一进行收集：收集所有金币，得到共计coins[i]k点积分。如果coins[i]k是负数，你将会失去abs(coins[i]k)点积分。收集所有...

涉及知识点 单调向量 题目 一个长度为n下标从0开始的整数数组arr的不平衡数字定义为，在sarr=sorted(arr)数组中，满足以下条件的下标数目：0<=i<n1，和sarr[i+1]sarr[i]>1这里，sorted(arr)表示将数组arr排序后得到的数组。给你一个下标从0开始的整数数组nums，请你返回它所有子数组的不平衡数字之和。子数组指的是一个数组中连续一段非空的元素序列。示例1：输入：nums=[2,3,1,4]输出：3解释：总共有3个子数组有非0不平衡数字： 子数组[3,1]，不平衡数字为1。 子数组[3,1,4]，不平衡数字为1。 子数组[1,4]...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频 题目 给你两个下标从0开始的数组nums和cost，分别包含n个正整数。你可以执行下面操作任意次：将nums中任意元素增加或者减小1。对第i个元素执行一次操作的开销是cost[i]。请你返回使nums中所有元素相等的最少总开销。示例1：输入：nums=[1,3,5,2],cost=[2,3,1,14]输出：8解释：我们可以执行以下操作使所有元素变为2： 增加第0个元素1次，开销为2。 减小第1个元素1次，开销为3。 减小第2个元素3次，开销为1+1+1=3。总开销为2+3+3=8。这是最小开销。示例...

涉及知识点 二分查找单调映射 源码下载 点击下载源码 题目 给你一个整数数组nums，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。 示例1： 输入：nums=[10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是[2,3,7,101]，因此长度为4。 示例2： 输入：nums=[0,1,0,3,2,3] 输出：4 示例3： 输入：nums=[7,7,7,7,7,7,7] 输出：1 参数范围： 1<=nums.length&...

本文涉及的基础知识点 二分查找 题目 给你一个由非负整数a1,a2,…,an组成的数据流输入，请你将到目前为止看到的数字总结为不相交的区间列表。实现SummaryRanges类：SummaryRanges()使用一个空数据流初始化对象。voidaddNum(intval)向数据流中加入整数val。int[][]getIntervals()以不相交区间[starti,endi]的列表形式返回对数据流中整数的总结。示例：输入：[“SummaryRanges”,“addNum”,“getIntervals”,“addNum”,“getIntervals”,“addNum”,“getInterval...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频排序 题目 英雄的力量给你一个下标从0开始的整数数组nums，它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的力量定义为：i0，i1，…ik表示这组英雄在数组中的下标。那么这组英雄的力量为max(nums[i0],nums[i1]…nums[ik])2min(nums[i0],nums[i1]…nums[ik])。请你返回所有可能的非空英雄组的力量之和。由于答案可能非常大，请你将结果对109+7取余。示例1：输入：nums=[2,1,4]输出：141解释：第1组：[2]的力量为222=8。第2组：...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频单调双向队列滑动窗口 题目 你有n个机器人，给你两个下标从0开始的整数数组chargeTimes和runningCosts，两者长度都为n。第i个机器人充电时间为chargeTimes[i]单位时间，花费runningCosts[i]单位时间运行。再给你一个整数budget。运行k个机器人总开销是max(chargeTimes)+ksum(runningCosts)，其中max(chargeTimes)是这k个机器人中最大充电时间，sum(runningCosts)是这k个机器人的运行时间之和。请你返回...