0%

    6359. 最小化数对的最大差值


    给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对,每个下标对对应数值取差值,你需要使得这 p 个差值的 最大值 最小。同时,你需要确保每个下标在这 p 个下标对中最多出现一次。

    对于一个下标对 i 和 j ,这一对的差值为 |nums[i] - nums[j]| ,其中 |x| 表示 x 的 绝对值 。

    请你返回 p 个下标对对应数值 最大差值 的 最小值 。

    示例 1:

    ```txt

    输入:nums = [10,1,2,7,1,3], p = 2

    输出:1

    解释:第一个下标对选择 1 和 4 ,第二个下标对选择 2 和 5 。

    最大差值为 max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1 。所以我们返回 1 。

    ```

    示例 2:

    ```txt

    输入:nums = [4,2,1,2], p = 1

    输出:0

    解释:选择下标 1 和 3 构成下标对。差值为 |2 - 2| = 0 ,这是最大差值的最小值。

    ```

    提示:

    • 1 <= nums.length <= 10^5

    • 0 <= nums[i] <= 10^9

    • 0 <= p <= (nums.length)/2

阅读全文 »

    6357. 最少得分子序列


    给你两个字符串 s 和 t 。

    你可以从字符串 t 中删除任意数目的字符。

    如果没有从字符串 t 中删除字符,那么得分为 0 ,否则:

    • 令 left 为删除字符中的最小下标。

    • 令 right 为删除字符中的最大下标。

    字符串的得分为 right - left + 1 。

    请你返回使 t 成为 s 子序列的最小得分。

    一个字符串的 子序列 是从原字符串中删除一些字符后(也可以一个也不删除),剩余字符不改变顺序得到的字符串。(比方说 "ace" 是 "***a***b***c***d***e***" 的子序列,但是 "aec" 不是)。

    示例 1:

    ```txt

    输入:s = "abacaba", t = "bzaa"

    输出:1

    解释:这个例子中,我们删除下标 1 处的字符 "z" (下标从 0 开始)。

    字符串 t 变为 "baa" ,它是字符串 "abacaba" 的子序列,得分为 1 - 1 + 1 = 1 。

    1 是能得到的最小得分。

    ```

    示例 2:

    ```txt

    输入:s = "cde", t = "xyz"

    输出:3

    解释:这个例子中,我们将下标为 0, 1 和 2 处的字符 "x" ,"y" 和 "z" 删除(下标从 0 开始)。

    字符串变成 "" ,它是字符串 "cde" 的子序列,得分为 2 - 0 + 1 = 3 。

    3 是能得到的最小得分。

    ```

    提示:

    • 1 <= s.length, t.length <= 10^5

    • s 和 t 都只包含小写英文字母。

阅读全文 »

    1802. 有界数组中指定下标处的最大值


    给你三个正整数 nindexmaxSum 。你需要构造一个同时满足下述所有条件的数组 nums(下标 从 0 开始 计数):

    • nums.length == n

    • nums[i]正整数 ,其中 0 <= i < n

    • abs(nums[i] - nums[i+1]) <= 1 ,其中 0 <= i < n-1

    • nums 中所有元素之和不超过 maxSum

    • nums[index] 的值被 最大化

    返回你所构造的数组中的 nums[index]

    注意:abs(x) 等于 x 的前提是 x >= 0 ;否则,abs(x) 等于 -x

    示例 1:

    ```txt

    输入:n = 4, index = 2, maxSum = 6

    输出:2

    解释:数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。

    ```

    示例 2:

    ```txt

    输入:n = 6, index = 1, maxSum = 10

    输出:3

    ```

    提示:

    • 1 <= n <= maxSum <= 10^9

    • 0 <= index < n

阅读全文 »

    3049. 标记所有下标的最早秒数 II


    给你两个下标从 1 开始的整数数组 nums 和 changeIndices ,数组的长度分别为 n 和 m 。

    一开始,nums 中所有下标都是未标记的,你的任务是标记 nums 中 所有 下标。

    从第 1 秒到第 m 秒(包括 第 m 秒),对于每一秒 s ,你可以执行以下操作 之一 :

    • 选择范围 [1, n] 中的一个下标 i ,并且将 nums[i] 减少 1 。

    • 将 nums[changeIndices[s]] 设置成任意的 非负 整数。

    • 选择范围 [1, n] 中的一个下标 i , 满足 nums[i] 等于 0, 并 标记 下标 i

    • 什么也不做。

    请你返回范围 [1, m] 中的一个整数,表示最优操作下,标记 nums 中 所有 下标的 最早秒数 ,如果无法标记所有下标,返回 -1 。

    示例 1:

    ```txt

    输入:nums = [3,2,3], changeIndices = [1,3,2,2,2,2,3]

    输出:6

    解释:这个例子中,我们总共有 7 秒。按照以下操作标记所有下标:

    第 1 秒:将 nums[changeIndices[1]] 变为 0 。nums 变为 [0,2,3] 。

    第 2 秒:将 nums[changeIndices[2]] 变为 0 。nums 变为 [0,2,0] 。

    第 3 秒:将 nums[changeIndices[3]] 变为 0 。nums 变为 [0,0,0] 。

    第 4 秒:标记下标 1 ,因为 nums[1] 等于 0 。

    第 5 秒:标记下标 2 ,因为 nums[2] 等于 0 。

    第 6 秒:标记下标 3 ,因为 nums[3] 等于 0 。

    现在所有下标已被标记。

    最早可以在第 6 秒标记所有下标。

    所以答案是 6 。

    ```

    示例 2:

    ```txt

    输入:nums = [0,0,1,2], changeIndices = [1,2,1,2,1,2,1,2]

    输出:7

    解释:这个例子中,我们总共有 8 秒。按照以下操作标记所有下标:

    第 1 秒:标记下标 1 ,因为 nums[1] 等于 0 。

    第 2 秒:标记下标 2 ,因为 nums[2] 等于 0 。

    第 3 秒:将 nums[4] 减少 1 。nums 变为 [0,0,1,1] 。

    第 4 秒:将 nums[4] 减少 1 。nums 变为 [0,0,1,0] 。

    第 5 秒:将 nums[3] 减少 1 。nums 变为 [0,0,0,0] 。

    第 6 秒:标记下标 3 ,因为 nums[3] 等于 0 。

    第 7 秒:标记下标 4 ,因为 nums[4] 等于 0 。

    现在所有下标已被标记。

    最早可以在第 7 秒标记所有下标。

    所以答案是 7 。

    ```

    示例 3:

    ```txt

    输入:nums = [1,2,3], changeIndices = [1,2,3]

    输出:-1

    解释:这个例子中,无法标记所有下标,因为我们没有足够的秒数。

    所以答案是 -1 。

    ```

    提示:

    • 1 <= n == nums.length <= 5000

    • 0 <= nums[i] <= 10^9

    • 1 <= m == changeIndices.length <= 5000

    • 1 <= changeIndices[i] <= n

阅读全文 »

    778. 水位上升的泳池中游泳


    在一个 n x n 的整数矩阵 grid 中,每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。

    当开始下雨时,在时间为 t 时,水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台,但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离,也就是默认在方格内部游动是不耗时的。当然,在你游泳的时候你必须待在坐标方格里面。

    你从坐标方格的左上平台 (0,0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间 。

    示例 1:

    ```txt

    输入: grid = [[0,2],[1,3]]

    输出: 3

    解释:

    时间为0时,你位于坐标方格的位置为 (0, 0)。

    此时你不能游向任意方向,因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。

    等时间到达 3 时,你才可以游向平台 (1, 1). 因为此时的水位是 3,坐标方格中的平台没有比水位 3 更高的,所以你可以游向坐标方格中的任意位置

    ```

    示例 2:

    ```txt

    输入: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]

    输出: 16

    解释: 最终的路线用加粗进行了标记。

    我们必须等到时间为 16,此时才能保证平台 (0, 0) 和 (4, 4) 是连通的

    ```

    提示:

    • n == grid.length

    • n == grid[i].length

    • 1 <= n <= 50

    • 0 <= grid[i][j] < n^2

    • grid[i][j] 中每个值 均无重复

阅读全文 »

    6367. 求出最多标记下标


    给你一个下标从 0 开始的整数数组 nums 。

    一开始,所有下标都没有被标记。你可以执行以下操作任意次:

    • 选择两个 互不相同且未标记 的下标 i 和 j ,满足 2 * nums[i] <= nums[j] ,标记下标 i 和 j 。

    请你执行上述操作任意次,返回 nums 中最多可以标记的下标数目。

    示例 1:

    ```txt

    输入:nums = [3,5,2,4]

    输出:2

    解释:第一次操作中,选择 i = 2 和 j = 1 ,操作可以执行的原因是 2 * nums[2] <= nums[1] ,标记下标 2 和 1 。

    没有其他更多可执行的操作,所以答案为 2 。

    ```

    示例 2:

    ```txt

    输入:nums = [9,2,5,4]

    输出:4

    解释:第一次操作中,选择 i = 3 和 j = 0 ,操作可以执行的原因是 2 * nums[3] <= nums[0] ,标记下标 3 和 0 。

    第二次操作中,选择 i = 1 和 j = 2 ,操作可以执行的原因是 2 * nums[1] <= nums[2] ,标记下标 1 和 2 。

    没有其他更多可执行的操作,所以答案为 4 。

    ```

    示例 3:

    ```txt

    输入:nums = [7,6,8]

    输出:0

    解释:没有任何可以执行的操作,所以答案为 0 。

    ```

    提示:

    • 1 &lt;= nums.length &lt;= 10^5

    • 1 &lt;= nums[i] &lt;= 10^9

阅读全文 »

    878. 第 N 个神奇数字


    一个正整数如果能被 ab 整除,那么它是神奇的。

    给定三个整数 na , b ,返回第 n 个神奇的数字。因为答案可能很大,所以返回答案  10^9 + 7 取模 后的值。

    示例 1:

    ```txt

    输入:n = 1, a = 2, b = 3

    输出:2

    ```

    示例 2:

    ```txt

    输入:n = 4, a = 2, b = 3

    输出:6

    ```

    提示:

    • 1 &lt;= n &lt;= 10^9

    • 2 &lt;= a, b &lt;= 4 * 10^4

阅读全文 »