代码如诗

正在加载今日诗词....

0%

发表于 更新于 分类于

    982. 按位与为零的三元组

    给你一个整数数组 nums ，返回其中 按位与三元组 的数目。

    按位与三元组 是由下标 (i, j, k) 组成的三元组，并满足下述全部条件：

    • 0 <= i < nums.length

    • 0 <= j < nums.length

    • 0 <= k < nums.length

    • nums[i] & nums[j] & nums[k] == 0 ，其中 & 表示按位与运算符。

    示例 1：

    ```txt

    输入：nums = [2,1,3]

    输出：12

    解释：可以选出如下 i, j, k 三元组：

    (i=0, j=0, k=1) : 2 & 2 & 1

    (i=0, j=1, k=0) : 2 & 1 & 2

    (i=0, j=1, k=1) : 2 & 1 & 1

    (i=0, j=1, k=2) : 2 & 1 & 3

    (i=0, j=2, k=1) : 2 & 3 & 1

    (i=1, j=0, k=0) : 1 & 2 & 2

    (i=1, j=0, k=1) : 1 & 2 & 1

    (i=1, j=0, k=2) : 1 & 2 & 3

    (i=1, j=1, k=0) : 1 & 1 & 2

    (i=1, j=2, k=0) : 1 & 3 & 2

    (i=2, j=0, k=1) : 3 & 2 & 1

    (i=2, j=1, k=0) : 3 & 1 & 2

    ```

    示例 2：

    ```txt

    输入：nums = [0,0,0]

    输出：27

    ```

    提示：

    • 1 <= nums.length <= 1000

    • 0 <= nums[i] < 2^16

阅读全文 »

发表于 更新于 分类于

    2488. 统计中位数为 K 的子数组

    给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的 不同 整数组成。另给你一个正整数 k 。

    统计并返回 nums 中的 中位数 等于 k 的非空子数组的数目。

    注意：

    • 数组的中位数是按 递增 顺序排列后位于 中间 的那个元素，如果数组长度为偶数，则中位数是位于中间靠 左 的那个元素。

      • 例如，[2,3,1,4] 的中位数是 2 ，[8,4,3,5,1] 的中位数是 4 。

    • 子数组是数组中的一个连续部分。

    示例 1：

    ```txt

    输入：nums = [3,2,1,4,5], k = 4

    输出：3

    解释：中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。

    ```

    示例 2：

    ```txt

    输入：nums = [2,3,1], k = 3

    输出：1

    解释：[3] 是唯一一个中位数等于 3 的子数组。

    ```

    提示：

    • n == nums.length

    • 1 <= n <= 10^5

    • 1 <= nums[i], k <= n

    • nums 中的整数互不相同

阅读全文 »

发表于 更新于 分类于

    1960. 两个回文子字符串长度的最大乘积

    给你一个下标从 0 开始的字符串 s ，你需要找到两个 不重叠的回文 子字符串，它们的长度都必须为 奇数 ，使得它们长度的乘积最大。

    更正式地，你想要选择四个整数 i ，j ，k ，l ，使得 0 <= i <= j < k <= l < s.length ，且子字符串 s[i...j] 和 s[k...l] 都是回文串且长度为奇数。s[i...j] 表示下标从 i 到 j 且 包含 两端下标的子字符串。

    请你返回两个不重叠回文子字符串长度的 最大 乘积。

    回文字符串 指的是一个从前往后读和从后往前读一模一样的字符串。子字符串 指的是一个字符串中一段连续字符。

    示例 1：

    ```txt

    输入：s = "ababbb"

    输出：9

    解释：子字符串 "aba" 和 "bbb" 为奇数长度的回文串。乘积为 3 * 3 = 9 。

    ```

    示例 2：

    ```txt

    输入：s = "zaaaxbbby"

    输出：9

    解释：子字符串 "aaa" 和 "bbb" 为奇数长度的回文串。乘积为 3 * 3 = 9 。

    ```

    提示：

    • 2 <= s.length <= 10^5

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

阅读全文 »

发表于 更新于 分类于

    1825. 求出 MK 平均值

    给你两个整数 m 和 k ，以及数据流形式的若干整数。你需要实现一个数据结构，计算这个数据流的 MK 平均值 。

    MK 平均值 按照如下步骤计算：

    1. 如果数据流中的整数少于 m 个，MK 平均值 为 -1 ，否则将数据流中最后 m 个元素拷贝到一个独立的容器中。

    2. 从这个容器中删除最小的 k 个数和最大的 k 个数。

    3. 计算剩余元素的平均值，并 向下取整到最近的整数 。

    请你实现 MKAverage 类：

    • MKAverage(int m, int k) 用一个空的数据流和两个整数 m 和 k 初始化 MKAverage 对象。

    • void addElement(int num) 往数据流中插入一个新的元素 num 。

    • int calculateMKAverage() 对当前的数据流计算并返回 MK 平均数 ，结果需 向下取整到最近的整数 。

    示例 1：

    ```txt

    输入：

    ["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"]

    [[3, 1], [3], [1], [], [10], [], [5], [5], [5], []]

    输出：

    [null, null, null, -1, null, 3, null, null, null, 5]

    解释：

    MKAverage obj = new MKAverage(3, 1);

    obj.addElement(3); // 当前元素为 [3]

    obj.addElement(1); // 当前元素为 [3,1]

    obj.calculateMKAverage(); // 返回 -1 ，因为 m = 3 ，但数据流中只有 2 个元素

    obj.addElement(10); // 当前元素为 [3,1,10]

    obj.calculateMKAverage(); // 最后 3 个元素为 [3,1,10]

                          // 删除最小以及最大的 1 个元素后，容器为 [3]                      // [3] 的平均值等于 3/1 = 3 ，故返回 3

    obj.addElement(5); // 当前元素为 [3,1,10,5]

    obj.addElement(5); // 当前元素为 [3,1,10,5,5]

    obj.addElement(5); // 当前元素为 [3,1,10,5,5,5]

    obj.calculateMKAverage(); // 最后 3 个元素为 [5,5,5]

                          // 删除最小以及最大的 1 个元素后，容器为 [5]                      // [5] 的平均值等于 5/1 = 5 ，故返回 5

    ```

    提示：

    • 3 <= m <= 10^5

    • 1 <= k*2 < m

    • 1 <= num <= 10^5

    • addElement 与 calculateMKAverage 总操作次数不超过 10^5 次。

阅读全文 »

发表于 更新于 分类于

    1172. 餐盘栈

    我们把无限数量 ∞ 的栈排成一行，按从左到右的次序从 0 开始编号。每个栈的的最大容量 capacity 都相同。

    实现一个叫「餐盘」的类 DinnerPlates：

    • DinnerPlates(int capacity) - 给出栈的最大容量 capacity。

    • void push(int val) - 将给出的正整数 val 推入 从左往右第一个 没有满的栈。

    • int pop() - 返回 从右往左第一个 非空栈顶部的值，并将其从栈中删除；如果所有的栈都是空的，请返回 -1。

    • int popAtStack(int index) - 返回编号 index 的栈顶部的值，并将其从栈中删除；如果编号 index 的栈是空的，请返回 -1。

    示例：

    ```txt

    输入：

    ["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]

    [[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]

    输出：

    [null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

    解释：

    DinnerPlates D = DinnerPlates(2); // 初始化，栈最大容量 capacity = 2

    D.push(1);

    D.push(2);

    D.push(3);

    D.push(4);

    D.push(5); // 栈的现状为： 2  4

    1  3  5

                                    ﹈ ﹈ ﹈

    D.popAtStack(0); // 返回 2。栈的现状为：  4

                                          1  3  5                                      ﹈ ﹈ ﹈

    D.push(20); // 栈的现状为： 20 4

    1  3  5

                                   ﹈ ﹈ ﹈

    D.push(21); // 栈的现状为： 20 4 21

    1  3  5

                                   ﹈ ﹈ ﹈

    D.popAtStack(0); // 返回 20。栈的现状为： 4 21

                                            1  3  5                                        ﹈ ﹈ ﹈

    D.popAtStack(2); // 返回 21。栈的现状为： 4

                                            1  3  5                                        ﹈ ﹈ ﹈

    D.pop() // 返回 5。栈的现状为： 4

                                            1  3                                        ﹈ ﹈

    D.pop() // 返回 4。栈的现状为： 1 3 

                                           ﹈ ﹈

    D.pop() // 返回 3。栈的现状为： 1 

                                           ﹈

    D.pop() // 返回 1。现在没有栈。

    D.pop() // 返回 -1。仍然没有栈。

    ```

    提示：

    • 1 <= capacity <= 20000

    • 1 <= val <= 20000

    • 0 <= index <= 100000

    • 最多会对 push，pop，和 popAtStack 进行 200000 次调用。

阅读全文 »

发表于 更新于 分类于

    1697. 检查边长度限制的路径是否存在

    给你一个 n 个点组成的无向图边集 edgeList ，其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边。请注意，两个点之间可能有 超过一条边 。

    给你一个查询数组queries ，其中 queries[j] = [pj, qj, limitj] ，你的任务是对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径，且这条路径上的每一条边都 严格小于 limitj 。

    请你返回一个 布尔数组 answer ，其中 answer.length == queries.length ，当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false 。

    示例 1：

    https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/12/19/h.png

    ```

    输入：n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]

    输出：[false,true]

    解释：上图为给定的输入数据。注意到 0 和 1 之间有两条重边，分别为 2 和 16 。

    对于第一个查询，0 和 1 之间没有小于 2 的边，所以我们返回 false 。

    对于第二个查询，有一条路径（0 -> 1 -> 2）两条边都小于 5 ，所以这个查询我们返回 true 。

    ```

    示例 2：

    https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/12/19/q.png

    ```

    输入：n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]

    输出：[true,false]

    解释：上图为给定数据。

    ```

    提示：

    • 2 <= n <= 10^5

    • 1 <= edgeList.length, queries.length <= 10^5

    • edgeList[i].length == 3

    • queries[j].length == 3

    • 0 <= ui, vi, pj, qj <= n - 1

    • ui != vi

    • pj != qj

    • 1 <= disi, limitj <= 10^9

    • 两个点之间可能有 多条 边。

阅读全文 »

发表于 更新于 分类于

    2503. 矩阵查询可获得的最大分数

    给你一个大小为 m x n 的整数矩阵 grid 和一个大小为 k 的数组 queries 。

    找出一个大小为 k 的数组 answer ，且满足对于每个整数 queres[i] ，你从矩阵 左上角 单元格开始，重复以下过程：

    • 如果 queries[i] 严格 大于你当前所处位置单元格，如果该单元格是第一次访问，则获得 1 分，并且你可以移动到所有 4 个方向（上、下、左、右）上任一 相邻 单元格。

    • 否则，你不能获得任何分，并且结束这一过程。

    在过程结束后，answer[i] 是你可以获得的最大分数。注意，对于每个查询，你可以访问同一个单元格 多次 。

    返回结果数组 answer 。

    示例 1：

    https://assets.leetcode.com/uploads/2022/10/19/yetgriddrawio.png

    ```

    输入：grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]

    输出：[5,8,1]

    解释：上图展示了每个查询中访问并获得分数的单元格。

    ```

    示例 2：

    https://assets.leetcode.com/uploads/2022/10/20/yetgriddrawio-2.png

    ```

    输入：grid = [[5,2,1],[1,1,2]], queries = [3]

    输出：[0]

    解释：无法获得分数，因为左上角单元格的值大于等于 3 。

    ```

    提示：

    • m == grid.length

    • n == grid[i].length

    • 2 <= m, n <= 1000

    • 4 <= m * n <= 10^5

    • k == queries.length

    • 1 <= k <= 10^4

    • 1 <= grid[i][j], queries[i] <= 10^6

阅读全文 »