本文涉及知识点 简单的数学知识。 题目 给你一个整数n，请你在无限的整数序列[1,2,3,4,5,6,7,8,9,10,11,...]中找出并返回第n位上的数字。 示例1： 输入：n=3 输出：3 示例2： 输入：n=11 输出：0 解释：第11位数字在序列1,2,3,4,5,6,7,8,9,10,11,...里是0，它是10的一部分。 提示： 1<=n<=231–1 分析 位数 最小数 数量 n位数的数量等于：最小数9。总位数等于：数量位数。 一位数(1到9) 1 9 两位数(10到99) 10 90 三位数(100到999) 100 900 ...

本文涉及知识点 深度优先搜索(DFS)状态压缩 题目 给你一棵树（即，一个连通、无向且无环的图），根节点为0，由编号从0到n1的n个节点组成。这棵树用一个长度为n、下标从0开始的数组parent表示，其中parent[i]为节点i的父节点，由于节点0为根节点，所以parent[0]-1。另给你一个长度为n的字符串s，其中s[i]是分配给i和parent[i]之间的边的字符。s[0]可以忽略。找出满足u<v，且从u到v的路径上分配的字符可以重新排列形成回文的所有节点对(u,v)，并返回节点对的数目。如果一个字符串正着读和反着读都相同，那么这个字符串就是一个回文。示例1：输入：parent...

涉及知识点 二分查找并集查找或BFS。 题目 在一个nxn的整数矩阵grid中，每一个方格的值grid[i][j]表示位置(i,j)的平台高度。当开始下雨时，在时间为t时，水池中的水位为t。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。你从坐标方格的左上平台(0，0)出发。返回你到达坐标方格的右下平台(n-1,n-1)所需的最少时间。示例1:输入:grid=[[0,2],[1,3]]输出:3解释:时间为0时，你位于坐标方格的位置为(0,0)。此时...

涉及知识点 深度优先搜索(DFS) 题目 有一棵n个节点的无向树，节点编号为0到n1，根节点编号为0。给你一个长度为n1的二维整数数组edges表示这棵树，其中edges[i]=[ai,bi]表示树中节点ai和bi有一条边。同时给你一个长度为n下标从0开始的整数数组values，其中values[i]表示第i个节点的值。一开始你的分数为0，每次操作中，你将执行：选择节点i。将values[i]加入你的分数。将values[i]变为0。如果从根节点出发，到任意叶子节点经过的路径上的节点值之和都不等于0，那么我们称这棵树是健康的。你可以对这棵树执行任意次操作，但要求执行完所有操作以后树是健康的，...

题目 数对(a,b)由整数a和b组成，其数对距离定义为a和b的绝对差值。给你一个整数数组nums和一个整数k，数对由nums[i]和nums[j]组成且满足0<=i<j<nums.length。返回所有数对距离中第k小的数对距离。示例1：输入：nums=[1,3,1],k=1输出：0解释：数对和对应的距离如下：(1,3)->2(1,1)->0(3,1)->2距离第1小的数对是(1,1)，距离为0。示例2：输入：nums=[1,1,1],k=2输出：0示例3：输入：nums=[1,6,1],k=3输出：5参数范围nnums.length2<=n<...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频 题目 一张桌子上总共有n个硬币栈。每个栈有正整数个带面值的硬币。每一次操作中，你可以从任意一个栈的顶部取出1个硬币，从栈中移除它，并放入你的钱包里。给你一个列表piles，其中piles[i]是一个整数数组，分别表示第i个栈里从顶到底的硬币面值。同时给你一个正整数k，请你返回在恰好进行k次操作的前提下，你钱包里硬币面值之和最大为多少。示例1：输入：piles=[[1,100,3],[7,8,9]],k=2输出：101解释：上图展示了几种选择k个硬币的不同方法。我们可以得到的最大面值为101。示例2：输...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频 题目 给你n个包裹，你需要把它们装在箱子里，每个箱子装一个包裹。总共有m个供应商提供不同尺寸的箱子（每个规格都有无数个箱子）。如果一个包裹的尺寸小于等于一个箱子的尺寸，那么这个包裹就可以放入这个箱子之中。包裹的尺寸用一个整数数组packages表示，其中packages[i]是第i个包裹的尺寸。供应商用二维数组boxes表示，其中boxes[j]是第j个供应商提供的所有箱子尺寸的数组。你想要选择一个供应商并只使用该供应商提供的箱子，使得总浪费空间最小。对于每个装了包裹的箱子，我们定义浪费的空间等于箱子...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频 题目 给你一个下标从0开始且长度为n的整数数组nums。分割数组nums的方案数定义为符合以下两个条件的pivot数目：1<=pivot<nnums[0]+nums[1]+…+nums[pivot1]nums[pivot]+nums[pivot+1]+…+nums[n1]同时给你一个整数k。你可以将nums中一个元素变为k或不改变数组。请你返回在至多改变一个元素的前提下，最多有多少种方法分割nums使得上述两个条件都满足。示例1：输入：nums=[2,-1,2],k=3输出：1解释：一个最...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频动态规划，日后完成。 题目 给定三个整数n、m和k。考虑使用下图描述的算法找出正整数数组中最大的元素。请你构建一个具有以下属性的数组arr：arr中包含确切的n个整数。1<=arr[i]<=m其中(0<=i<n)。将上面提到的算法应用于arr之后，search_cost的值等于k。返回在满足上述条件的情况下构建数组arr的方法数量，由于答案可能会很大，所以必须对10^9+7取余。示例1：输入：n=2,m=3,k=1输出：6解释：可能的数组分别为[1,1],[2,1],[2,2],...

本文涉及的基础知识点 动态规划 题目 得到K个半回文串的最少修改次数给你一个字符串s和一个整数k，请你将s分成k个子字符串，使得每个子字符串变成半回文串需要修改的字符数目最少。请你返回一个整数，表示需要修改的最少字符数目。注意：如果一个字符串从左往右和从右往左读是一样的，那么它是一个回文串。如果长度为len的字符串存在一个满足1<=d<len的正整数d，len%d0成立且所有对d做除法余数相同的下标对应的字符连起来得到的字符串都是回文串，那么我们说这个字符串是半回文串。比方说“aa”，“aba”，“adbgad”和“abab”都是半回文串，而“a”，“ab”和“abca”不是。子...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频 题目 向下取整数对和给你一个整数数组nums，请你返回所有下标对0<=i,j<nums.length的floor(nums[i]/nums[j])结果之和。由于答案可能会很大，请你返回答案对109+7取余的结果。函数floor()返回输入数字的整数部分。 示例 示例1：输入：nums=[2,5,9]输出：10解释：floor(2/5)=floor(2/9)=floor(5/9)=0floor(2/2)=floor(5/5)=floor(9/9)=1floor(5/2)=2floor(9/2...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频双指针单调双向队列 题目 你有一辆货运卡车，你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有箱子数目的限制和总重量的限制。给你一个箱子数组boxes和三个整数portsCount,maxBoxes和maxWeight，其中boxes[i]=[portsi,weighti]。portsi表示第i个箱子需要送达的码头，weightsi是第i个箱子的重量。portsCount是码头的数目。maxBoxes和maxWeight分别是卡车每趟运输箱子数目和重量的限制。箱子需要按照数组顺序运输，同时每...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频滑动窗口 题目 给你一个整数数组nums和一个整数k。nums仅包含0和1。每一次移动，你可以选择相邻两个数字并将它们交换。请你返回使nums中包含k个连续1的最少交换次数。示例1：输入：nums=[1,0,0,1,0,1],k=2输出：1解释：在第一次操作时，nums可以变成[1,0,0,0,1,1]得到连续两个1。示例2：输入：nums=[1,0,0,0,0,0,1,1],k=3输出：5解释：通过5次操作，最左边的1可以移到右边直到nums变为[0,0,0,0,0,1,1,1]。示例3： 输入：nu...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频动态规划，日后完成。 题目 有n堆石头排成一排，第i堆中有stones[i]块石头。每次移动需要将连续的k堆石头合并为一堆，而这次移动的成本为这k堆中石头的总数。返回把所有石头合并成一堆的最低成本。如果无法合并成一堆，返回-1。示例1：输入：stones=[3,2,4,1],K=2输出：20解释：从[3,2,4,1]开始。合并[3,2]，成本为5，剩下[5,4,1]。合并[4,1]，成本为5，剩下[5,5]。合并[5,5]，成本为10，剩下[10]。总成本20，这是可能的最小值。示例2：输入：stone...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频 题目 在一个无限的x坐标轴上，有许多水果分布在其中某些位置。给你一个二维整数数组fruits，其中fruits[i]=[positioni,amounti]表示共有amounti个水果放置在positioni上。fruits已经按positioni升序排列，每个positioni互不相同。另给你两个整数startPos和k。最初，你位于startPos。从任何位置，你可以选择向左或者向右走。在x轴上每移动一个单位，就记作一步。你总共可以走最多k步。你每达到一个位置，都会摘掉全部的水果，水果也将从该位置...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频 题目 一个数组的分数定义为数组之和乘以数组的长度。比方说，[1,2,3,4,5]的分数为(1+2+3+4+5)5=75。给你一个正整数数组nums和一个整数k，请你返回nums中分数严格小于k的非空整数子数组数目。子数组是数组中的一个连续元素序列。示例1：输入：nums=[2,1,4,3,5],k=10输出：6解释：有6个子数组的分数小于10： [2]分数为21=2。 [1]分数为11=1。 [4]分数为41=4。 [3]分数为31=3。 [5]分数为51=5。 [2,1]分数为(2+1)2=6。注...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频 题目 给你一个下标从0开始的二进制字符串floor，它表示地板上砖块的颜色。floor[i]=‘0’表示地板上第i块砖块的颜色是黑色。floor[i]=‘1’表示地板上第i块砖块的颜色是白色。同时给你numCarpets和carpetLen。你有numCarpets条黑色的地毯，每一条黑色的地毯长度都为carpetLen块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余白色砖块的数目最小。地毯相互之间可以覆盖。请你返回没被覆盖的白色砖块的最少数目。示例1：输入：floor=“10110101”,n...

本文涉及的基础知识点 C算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频 题目 Alice和Bob玩一个游戏，两人轮流操作，Alice先手。总共有n个石子排成一行。轮到某个玩家的回合时，如果石子的数目大于1，他将执行以下操作：选择一个整数x>1，并且移除最左边的x个石子。将移除的石子价值之和累加到该玩家的分数中。将一个新的石子放在最左边，且新石子的值为被移除石子值之和。当只剩下一个石子时，游戏结束。Alice和Bob的分数之差为(Alice的分数Bob的分数)。Alice的目标是最大化分数差，Bob的目标是最小化分数差。给你一个长度为n的整数数组stones，其中st...

 说明 此文是课程的讲义。 源码下载： 题目 长度为n的数组nums，请返回任意一峰值的索引。符合以下条件之一i便是峰值的索引。 n等于1 i等于0 n>1 i等于0 nums[i]>nums[i+1] n>1 i等于n-1 nums[i]>nums[i-1] 0<i<n-1 nums[i]>nums[i-1] nums[i]>nums[i+1] 题目保证nums[i]不等于nums[i+1]。 分析 假定： nums[left,r)符合nums[left]>nums[left-1]，且num...

题目序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列/反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。提示:输入输出格式与LeetCode目前使用的方式一致，详情请参阅LeetCode序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。示例1：输入：root=[1,2,3,null,null,4,5]输出：[1,2,3...