碎片杂文
🌀周赛小结：leetcode第323场周赛
00 分钟
2022-12-11
2023-3-4
type
status
date
slug
summary
tags
category
icon
password
Property
Mar 4, 2023 02:36 AM
先放排名，确实还是很菜。。
notion image

第一题：

6257. 删除每行中的最大值

❓
给你一个 m x n 大小的矩阵 grid ，由若干正整数组成。
执行下述操作，直到 grid 变为空矩阵：
  • 从每一行删除值最大的元素。如果存在多个这样的值，删除其中任何一个。
  • 将删除元素中的最大值与答案相加。
注意 每执行一次操作，矩阵中列的数据就会减 1 。
返回执行上述操作后的答案。
示例 1：
notion image
输入：grid = [[1,2,4],[3,3,1]] 输出：8 解释：上图展示在每一步中需要移除的值。 - 在第一步操作中，从第一行删除 4 ，从第二行删除 3（注意，有两个单元格中的值为 3 ，我们可以删除任一）。在答案上加 4 。 - 在第二步操作中，从第一行删除 2 ，从第二行删除 3 。在答案上加 3 。 - 在第三步操作中，从第一行删除 1 ，从第二行删除 1 。在答案上加 1 。 最终，答案 = 4 + 3 + 1 = 8 。
示例 2：
notion image
输入：grid = [[10]] 输出：10 解释：上图展示在每一步中需要移除的值。 - 在第一步操作中，从第一行删除 10 。在答案上加 10 。 最终，答案 = 10 。
提示：
  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 1 <= grid[i][j] <= 100
就是找出每一行的最大值，然后在每次找出的每一次挑选出的每一行的最大值中的最大值
由于数据量级太小，这题怎么做都行，我就每次排序翻转找最大值（图省事），没什么好说的，直接放代码，当然还有很多可以优化的空间：

第二题：

6258. 数组中最长的方波

  • 题目难度Medium
❓
给你一个整数数组 nums 。如果 nums 的子序列满足下述条件，则认为该子序列是一个 方波 ：
  • 子序列的长度至少为 2 ，并且
  • 将子序列从小到大排序 之后 ，除第一个元素外，每个元素都是前一个元素的 平方 。
返回 nums 中 最长方波 的长度，如果不存在 方波 则返回 -1 。
子序列 也是一个数组，可以由另一个数组删除一些或不删除元素且不改变剩余元素的顺序得到。
示例 1 ：
输入：nums = [4,3,6,16,8,2] 输出：3 解释：选出子序列 [4,16,2] 。排序后，得到 [2,4,16] 。 - 4 = 2 * 2. - 16 = 4 * 4. 因此，[4,16,2] 是一个方波. 可以证明长度为 4 的子序列都不是方波。
示例 2 ：
输入：nums = [2,3,5,6,7] 输出：-1 解释：nums 不存在方波，所以返回 -1 。
提示：
  • 2 <= nums.length <= 10^5
  • 2 <= nums[i] <= 10^5
其实就是一个排序加哈希表，注意如果不想考虑开方的问题的话，可以倒着遍历
做的时候其实一下就想到了，但是中间觉得并查集也可以做，就耽误了一些时间。
做的时候有一些整数溢出情况没考虑到，下次要注意
如果从小到大枚举的话不会出现爆int的问题，但是开方的话我个人觉得有些问题(开方函数不会写 😂)

第三题：

6259. 设计内存分配器

  • 题目难度Medium
❓
给你一个整数 n ，表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。
请你设计一个具备以下功能的内存分配器：
  1. 分配 一块大小为 size 的连续空闲内存单元并赋 id mID 。
  1. 释放 给定 id mID 对应的所有内存单元。
注意：
  • 多个块可以被分配到同一个 mID 。
  • 你必须释放 mID 对应的所有内存单元，即便这些内存单元被分配在不同的块中。
实现 Allocator 类：
  • Allocator(int n) 使用一个大小为 n 的内存数组初始化 Allocator 对象。
  • int allocate(int size, int mID) 找出大小为 size 个连续空闲内存单元且位于 最左侧 的块，分配并赋 id mID 。返回块的第一个下标。如果不存在这样的块，返回 1 。
  • int free(int mID) 释放 id mID 对应的所有内存单元。返回释放的内存单元数目。
示例：
输入 ["Allocator", "allocate", "allocate", "allocate", "free", "allocate", "allocate", "allocate", "free", "allocate", "free"] [[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], [7]] 输出 [null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0] 解释 Allocator loc = new Allocator(10); // 初始化一个大小为 10 的内存数组，所有内存单元都是空闲的。 loc.allocate(1, 1); // 最左侧的块的第一个下标是 0 。内存数组变为 [1, , , , , , , , , ]。返回 0 。 loc.allocate(1, 2); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,2, , , , , , , , ]。返回 1 。 loc.allocate(1, 3); // 最左侧的块的第一个下标是 2 。内存数组变为 [1,2,3, , , , , , , ]。返回 2 。 loc.free(2); // 释放 mID 为 2 的所有内存单元。内存数组变为 [1, ,3, , , , , , , ] 。返回 1 ，因为只有 1 个 mID 为 2 的内存单元。 loc.allocate(3, 4); // 最左侧的块的第一个下标是 3 。内存数组变为 [1, ,3,4,4,4, , , , ]。返回 3 。 loc.allocate(1, 1); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,1,3,4,4,4, , , , ]。返回 1 。 loc.allocate(1, 1); // 最左侧的块的第一个下标是 6 。内存数组变为 [1,1,3,4,4,4,1, , , ]。返回 6 。 loc.free(1); // 释放 mID 为 1 的所有内存单元。内存数组变为 [ , ,3,4,4,4,, , , ] 。返回 3 ，因为有 3 个 mID 为 1 的内存单元。 loc.allocate(10, 2); // 无法找出长度为 10 个连续空闲内存单元的空闲块，所有返回 -1 。 loc.free(7); // 释放 mID 为 7 的所有内存单元。内存数组保持原状，因为不存在 mID 为 7 的内存单元。返回 0 。
提示：
  • 1 <= n, size, mID <= 1000
  • 最多调用 allocate 和 free 方法 1000 次
这个题真是写了改，改了写，浪费了不少精力和时间，最后的版本完成的过程实际上才四分钟。。。
由于数据量比较小，所以可以直接枚举遍历
下边是ac代码：
y总说mallocLab可以用平衡树维护，以后要试试。。

第四题：

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

  • 题目难度Hard
❓
给你一个大小为 m x n 的整数矩阵 grid 和一个大小为 k 的数组 queries 。
找出一个大小为 k 的数组 answer ，且满足对于每个整数 queres[i] ，你从矩阵 左上角 单元格开始，重复以下过程：
  • 如果 queries[i] 严格 大于你当前所处位置单元格，如果该单元格是第一次访问，则获得 1 分，并且你可以移动到所有 4 个方向（上、下、左、右）上任一 相邻 单元格。
  • 否则，你不能获得任何分，并且结束这一过程。
在过程结束后，answer[i] 是你可以获得的最大分数。注意，对于每个查询，你可以访问同一个单元格 多次 。
返回结果数组 answer 。
示例 1：
notion image
输入：grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2] 输出：[5,8,1] 解释：上图展示了每个查询中访问并获得分数的单元格。
示例 2：
notion image
输入：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 <= 105
  • k == queries.length
  • 1 <= k <= 104
  • 1 <= grid[i][j], queries[i] <= 106
这个题没做出来。。
联通块问题，用并查集做结果出现了重复计数的问题，没有时间进行修改了，说明对并查集的经典模型还是不熟悉，下去重复背 😭
这题采用的是离线 + 并查集的做法
首先有几个问题要解决：
  1. 什么是离线？
      2. 💡
      在线和离线可以简单的理解为对于所有的操作是否需要读入完毕
      在线的要求是可以不用先知道所有的操作(类似询问、修改)，边读入边执行，类似“走一步，做一步”的思想。即所有的询问是依次给出的，在返回第 k 个询问的答案之前，不会获得第 k+1个询问。
      离线则与在线相反，要求必须知道所有的操作，类似"记录所有步，回头再做”的思想，一般用Query[ ]记录所有操作。对于一道题目会给出若干询问，而这些询问是全部提前给出的，也就是说，你不必按照询问的顺序依次对它们进行处理，而是可以按照某种顺序（例如全序、偏序（拓扑序）、树的 DFS 序等）或者把所有询问看成一个整体（例如整体二分、莫队算法等）进行处理。
  1. 为什么要进行离线？
      2. 💡
      对于任意的查询queries[i]的answer[i]为： 从grid[0][0]开始往上下左右出发，可以到达的单元格个数 (遍历网格时的约束为：单元格要严格小于queries[i])。
      假如queries[i] <= queries[j]，那么一定有answer[i]<= answer[j]。 因为queries[i]小于等于queries[j]，说明在queries[i]约束下可以到达的单元格，对于queries[j]约束同样可以到达，但是反之却不一定；
      因此，我们可以先将queries[]按照值从小到大排序(同时记录每个查询值在queries原始数组中下标)； 然后从小的约束(查询)queries[i]开始，从grid[0][0]出发遍历grid，计算满足约束queries[i]，可以到达的单元格数目； 对于之后更大的约束(查询)queries[i+1]，不需要重新从grid[0][0]出发遍历grid，只需要从上次遍历的边界开始出发，计算满足约束queries[i+1]可以到达的单元格数目即可
      例如： 对于grid = | 1 | 2 | 3 | | 2 | 5 | 7 | | 3 | 5 | 1 |
      当queries[x] = 2 时，从grid[0][0]出发可以达到的单元格有grid[0][0]。不可到达的边界有grid[0][1]和grid[1][0]；因此答案为1； 当queries[x+1] = 5 时，从上次的不可到达边界(grid[0][1]和grid[1][0])出发，新的可以达到的单元格有grid[0][1],grid[0][2],grid[1][0]和grid[2][0]。不可到达的边界有grid[1][1], grid[1][2]和grid[2][1]；因此答案为1+4=5 当queries[x+2] = 6 时，从上次的不可到达边界(grid[1][1], grid[1][2]和grid[2][1])出发，新的可以达到的单元格有grid[1][1],grid[2][1]和grid[2][2]。因此答案等于1+4+3=8；
      ac代码：
      好像不如用优先队列快，但是实在没精力学了，等下次遇到类似的题了学习一下优先队列做法🥱🥱🥱
       
       

总结：

  • 手速太慢
  • 思路不够活跃，缺乏新题训练
  • 基础知识还不够，很多题型名词甚至没见过（离线等）
总的来说还是有所进步，加油~ 🥳
上一篇
《Operatring System：Three Easy Pieces》第九章 调度：比例份额
下一篇
动态规划：整数划分
评论
Loading...