本文涉及的基础知识点 二分查找算法合集动态规划 题目 给你一个下标从0开始的mxn整数矩阵grid。你一开始的位置在左上角格子(0,0)。 当你在格子(i,j)的时候，你可以移动到以下格子之一： 满足j<k<=grid[i][j]+j的格子(i,k)（向右移动），或者 满足i<k<=grid[i][j]+i的格子(k,j)（向下移动）。 请你返回到达右下角格子(m1,n1)需要经过的最少移动格子数，如果无法到达右下角格子，请你返回-1。 示例1： 输入：grid=[[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]] 输出：4 解释：上图...

作者推荐 [二分查找]LeetCode2040:两个有序数组的第K小乘积 本文涉及的基础知识点 二分查找算法合集 题目 给你n个任务和m个工人。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从0开始的整数数组tasks中，第i个任务需要tasks[i]的力量才能完成。每个工人的力量值保存在下标从0开始的整数数组workers中，第j个工人的力量值为workers[j]。每个工人只能完成一个任务，且力量值需要大于等于该任务的力量要求值（即workers[j]>=tasks[i]）。除此以外，你还有pills个神奇药丸，可以给一个工人的力量值增加strength。你可以决定给哪些...

本题不同解法 包括题目及代码 C二分查找算法：132模式解法一枚举3 C二分查找算法：132模式解法二枚举2 代码简洁 C二分查找算法：132模式解法三枚举1 性能最佳 C单调向量算法：132模式解法三枚举1 代码更简洁 C二分查找算法：132模式枚举3简洁版 代码简洁，性能优越 C单调向量：132模式枚举1简洁版 分析 时间复杂度 枚举1一轮，总时间复杂度O(n)。 步骤 for循环分三步：一，if语句，判断是否存在比iValue大的2。二，while循环，更新iMax2。三，if语句，当前值加到vRight中。 变量解释 ...

本题的其它解法 C二分算法：得到山形数组的最少删除次数 题目 我们定义arr是山形数组当且仅当它满足：arr.length>=3存在某个下标i（从0开始）满足0<i<arr.length1且：arr[0]<arr[1]<…<arr[i1]<arr[i]arr[i]>arr[i+1]>…>arr[arr.length1]给你整数数组nums，请你返回将nums变成山形状数组的最少删除次数。示例1：输入：nums=[1,3,1]输出：0解释：数组本身就是山形数组，所以我们不需要删除任何元素。示例2：输入：nums=[2,1,1,5,6,...

题目 我们定义arr是山形数组当且仅当它满足：arr.length>=3存在某个下标i（从0开始）满足0<i<arr.length1且：arr[0]<arr[1]<…<arr[i1]<arr[i]arr[i]>arr[i+1]>…>arr[arr.length1]给你整数数组nums，请你返回将nums变成山形状数组的最少删除次数。示例1：输入：nums=[1,3,1]输出：0解释：数组本身就是山形数组，所以我们不需要删除任何元素。示例2：输入：nums=[2,1,1,5,6,2,3,1]输出：3解释：一种方法是将下标为0，1和5的...

本文涉及的基础知识点 二分查找算法合集 题目 给你一个数组target，包含若干互不相同的整数，以及另一个整数数组arr，arr可能包含重复元素。每一次操作中，你可以在arr的任意位置插入任一整数。比方说，如果arr=[1,4,1,2]，那么你可以在中间添加3得到[1,4,3,1,2]。你可以在数组最开始或最后面添加整数。请你返回最少操作次数，使得target成为arr的一个子序列。一个数组的子序列指的是删除原数组的某些元素（可能一个元素都不删除），同时不改变其余元素的相对顺序得到的数组。比方说，[2,7,4]是[4,2,3,7,2,1,4]的子序列（加粗元素），但[2,4,2]不是子序列。...

本文涉及的基础知识点 二分查找算法合集离线查询 题目 给你一个下标从0开始的正整数数组heights，其中heights[i]表示第i栋建筑的高度。如果一个人在建筑i，且存在i<j的建筑j满足heights[i]<heights[j]，那么这个人可以移动到建筑j。给你另外一个数组queries，其中queries[i]=[ai,bi]。第i个查询中，Alice在建筑ai，Bob在建筑bi。请你能返回一个数组ans，其中ans[i]是第i个查询中，Alice和Bob可以相遇的最左边的建筑。如果对于查询i，Alice和Bob不能相遇，令ans[i]为-1。示例1：输入：heights...

本题不同解法 包括题目及代码 C二分查找算法：132模式解法一枚举3 C二分查找算法：132模式解法二枚举2 代码最简洁 C二分查找算法：132模式解法三枚举1 性能最佳 C单调向量算法：132模式解法三枚举1 分析 时间复杂度 2轮循环时间复杂度都是O(n)。 步骤 第一步 枚举32，再将2to3，转成3to2。枚举2。v3ValueIndex|记录nums[0,k)所有的值的索引。然后在v3ValueIndex中寻找值大于iValue，如果有多个结果取索引最大的。如果value0<=value1且index0<=index1，则val...

本文涉及的基础知识点 二分查找算法合集 本题不同解法 包括题目及代码 C二分查找算法：132模式解法一枚举3 C二分查找算法：132模式解法二枚举2 代码最简洁 C二分查找算法：132模式解法三枚举1 性能最佳 C单调向量算法：132模式解法三枚举1 分析 时间复杂度 两轮循环时间复杂度都是O(nlogn)。 步骤 第一轮，枚举3，nums(j,m_c)中小于nums[j]的元素都可以成为2，如果有多个合法2，选择最大的2。如果不存在2，设置成比最小值还小的值。[begin,it)是所有合法的2，由于是升序，最大的2就是最后一个。第二轮，枚举1，nu...

二分查找也称折半查找（BinarySearch），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。 时间复杂度 O(logn) 自己写二分算法 左闭右开左开右闭 C算法：二分查找旋转数组 左闭右开 C二分查找算法的应用：长度递增组的最大数目 左闭右开 C二分查找算法的应用：最小好进制 左开右闭 C二分查找算法：阶乘函数后K个零 左开右闭 C二分查找算法的应用：第N个神奇数字 一题三解(暴力、二分查找算法、单指针):鸡蛋掉落 左闭右开左开右闭 C二分查找算法：山脉数组中查找目标值 左开右...

题目 设计一个数据结构，有效地找到给定子数组的多数元素。子数组的多数元素是在子数组中出现threshold次数或次数以上的元素。实现MajorityChecker类:MajorityChecker(int[]arr)会用给定的数组arr对MajorityChecker初始化。intquery(intleft,intright,intthreshold)返回子数组中的元素arr[left…right]至少出现threshold次数，如果不存在这样的元素则返回-1。示例1：输入:[“MajorityChecker”,“query”,“query”,“query”][[[1,1,2,2,1,1]]...

涉及知识点 暴力、二分查找算法、单指针 题目 给你k枚相同的鸡蛋，并可以使用一栋从第1层到第n层共有n层楼的建筑。已知存在楼层f，满足0<=f<=n，任何从高于f的楼层落下的鸡蛋都会碎，从f楼层或比它低的楼层落下的鸡蛋都不会破。每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层x扔下（满足1<=x<=n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中重复使用这枚鸡蛋。请你计算并返回要确定f确切的值的最小操作次数是多少？示例1：输入：k=1,n=2输出：2解释：鸡蛋从1楼掉落。如果它碎了，肯定能得出f=0。否则，鸡蛋从2楼掉落。如果...

本题不同解法 包括题目及代码 C二分查找算法：132模式解法一枚举3 C二分查找算法：132模式解法二枚举2 代码最简洁 C二分查找算法：132模式解法三枚举1 性能最佳 C单调向量算法：132模式解法三枚举1 分析 第一步，选择各3对应的1，如果有多个符合对应最小的1，记录num[0,j)中的最小值iMin，如果nums[j]大于iMin，则m3To1[nums[j]]=iMin，否则等于一个不存在的大数，比如：100010001000+1。第二步，枚举2，m31的key是3的值，value是1的值，寻找key大于nums[k]中，是否存在valu...

涉及知识点 数学字典树 题目 给你一个下标从0开始的整数数组nums。如果一对整数x和y满足以下条件，则称其为强数对：|xy|<=min(x,y)你需要从nums中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（XOR）值是在该数组所有强数对中的最大值。返回数组nums所有可能的强数对中的最大异或值。注意，你可以选择同一个整数两次来形成一个强数对。示例1：输入：nums=[1,2,3,4,5]输出：7解释：数组nums中有11个强数对：(1,1),(1,2),(2,2),(2,3),(2,4),(3,3),(3,4),(3,5),(4,4),(4,5)和(5,5...

涉及知识点 数学 题目 给你两个下标从0开始的整数数组nums1和nums2，这两个数组的长度都是n。你可以执行一系列操作（可能不执行）。在每次操作中，你可以选择一个在范围[0,n1]内的下标i，并交换nums1[i]和nums2[i]的值。你的任务是找到满足以下条件所需的最小操作次数：nums1[n1]等于nums1中所有元素的最大值，即nums1[n1]=max(nums1[0],nums1[1],…,nums1[n1])。nums2[n1]等于nums2中所有元素的最大值，即nums2[n1]=max(nums2[0],nums2[1],…,nums2[n1])。以整数形式，表示并返回...

题目 你打算利用空闲时间来做兼职工作赚些零花钱。这里有n份兼职工作，每份工作预计从startTime[i]开始到endTime[i]结束，报酬为profit[i]。给你一份兼职工作表，包含开始时间startTime，结束时间endTime和预计报酬profit三个数组，请你计算并返回可以获得的最大报酬。注意，时间上出现重叠的2份工作不能同时进行。如果你选择的工作在时间X结束，那么你可以立刻进行在时间X开始的下一份工作。示例1：输入：startTime=[1,2,3,3],endTime=[3,4,5,6],profit=[50,10,40,70]输出：120解释：我们选出第1份和第4份工作，...

题目 请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。实现AllOne类：AllOne()初始化数据结构的对象。inc(Stringkey)字符串key的计数增加1。如果数据结构中尚不存在key，那么插入计数为1的key。dec(Stringkey)字符串key的计数减少1。如果key的计数在减少后为0，那么需要将这个key从数据结构中删除。测试用例保证：在减少计数前，key存在于数据结构中。getMaxKey()返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串“”。getMinKey()返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字...

题目 给你一个数组rectangles，其中rectangles[i]=[xi,yi,ai,bi]表示一个坐标轴平行的矩形。这个矩形的左下顶点是(xi,yi)，右上顶点是(ai,bi)。如果所有矩形一起精确覆盖了某个矩形区域，则返回true；否则，返回false。示例1：输入：rectangles=[[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]输出：true解释：5个矩形一起可以精确地覆盖一个矩形区域。示例2：输入：rectangles=[[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]输出：false解...

涉及知识点 有序集合字符串 题目 给你三个字符串a，b和c，你的任务是找到长度最短的字符串，且这三个字符串都是它的子字符串。如果有多个这样的字符串，请你返回字典序最小的一个。请你返回满足题目要求的字符串。注意：两个长度相同的字符串a和b，如果在第一个不相同的字符处，a的字母在字母表中比b的字母靠前，那么字符串a比字符串b字典序小。子字符串是一个字符串中一段连续的字符序列。示例1：输入：a=“abc”,b=“bca”,c=“aaa”输出：“aaabca”解释：字符串“aaabca”包含所有三个字符串：a=ans[2…4]，b=ans[3…5]，c=ans[0…2]。结果字符串的长度至少为6，且...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频二分法 题目 给你一个下标从0开始长度为n的整数数组stations，其中stations[i]表示第i座城市的供电站数目。每个供电站可以在一定范围内给所有城市提供电力。换句话说，如果给定的范围是r，在城市i处的供电站可以给所有满足|ij|<=r且0<=i,j<=n1的城市j供电。|x|表示x的绝对值。比方说，|75|=2，|310|=7。一座城市的电量是所有能给它供电的供电站数目。政府批准了可以额外建造k座供电站，你需要决定这些供电站分别应该建在哪里，这些供电站与已经存在的供电站有相...