CSDN周赛65期简要题解

2023-11-12

最近几期周赛里,貌似 Python 又变成 C 站的亲儿子了。输入形式是列表还不过瘾,现在输出形式也要求是列表,而且是连一个逗号、空格、中括号都不能少的 Python 标准列表形式。虽然对 Python 来说是信手拈来,但总要考虑一下其他编程语言选手的感受吧。纵观这么多在线评测网站,同类型的题目至少会要求譬如“按行输出,每行数字之间空格隔开”这样,而像 C 站这样输入输出的格式这么随意的,还真是独一家。长此以往,越来越多的人也不愿意参与了。


本期非编程题属于我的知识盲区,但正确答案并不难得到,和往常一样,这里就不废话了。

编程题:

第一题 数组排序

给你一个整数数组 nums ,请你将数组按照每个值的频率降序排序。如果有多个值的频率相同,请你按照数值本身将它们降序排序。 请你返回排序后的数组。

参数限制: 1 <= nums.length <= 100, -100 <= nums[i] <= 100

题目很简单,就是数组的两次排序,内置函数就能完成。但是离大谱的是本题没有用例。随便输入什么,然后点运行都显示 AC,但是却一分没有。我记得以前每次周赛前还会有个测试链接(我就曾因为发现了测试链接而被取消过成绩),难道现在已经没有人测试了吗?

就算是有用例,观察一下示例中的输入输出:

正如文章开头吐槽的那样,输出也要求列表形式 —— 估计能把 C 难受死。

不过一维列表应该还算 OK,中括号和逗号的位置都是固定的,就当组合成字符串输出了。而下一题,却要求二维列表也是以这个格式输出。

第二题 求解秩矩阵

给你一个 m x n 的矩阵 matrix ,请你返回一个新的矩阵 answer ,其中 answer[row][col] 是 matrix[row][col] 的秩。这里定义的每个元素的秩是一个整数,表示这个元素相对于其他元素的大小关系,它按照如下规则计算:

  1. 秩是从 1 开始的一个整数。
  2. 如果两个元素 p 和 q 在 同一行 或者 同一列 ,那么: 如果 p < q ,那么 rank(p) < rank(q) 如果 p == q ,那么 rank(p) == rank(q) 如果 p > q ,那么 rank(p) > rank(q) 秩 需要越 小 越好。

题目保证按照上面规则 answer 数组是唯一的。

参数说明: m == matrix.length n == matrix[i].length 1 <= m n <= 500 -10e9 <= matrix[row][col] <= 10e9

题目给出的三个示例:

而且离谱的是,如果用它提供的“自测”功能,把输入输出放进去,会发现示例中的数组没有空格,而正确答案的输出数组中元素之间却是要求有空格的,也就是 Python 那种列表输出方式。所以,即使千辛万苦做到示例的格式,从而通过了示例,也无法通过本题任何一个实际用例。

而这种输入输出简直就是为 Python 量身定制的,因为压根不需要考虑输出的问题:

matrix = eval(input())
# matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(matrix)
分析

抛开上面这种题目输出格式的问题不谈,其实本题考察的内容和数独很相似。如果把最终输出的结果是一个二维列表,里面每个元素都是相应位置的原数组的“秩”,要求满足条件的这个“秩”尽量要小,一个比较直观的办法,就是不断地从小到大依次去尝试每个数字的“秩”,直到符合条件为止。

拿示例中的 [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]] 为例,直观且暴力的方法就是:

  1. 先检查第一个元素 20,然后看同行同列有没有比它小的;
  2. 很显然,同行同列都有比它小的,-21 和 -19;
  3. 然后分别检查 -21 和 -19 所在的行有没有比他们更小的数字;
  4. -21 所在的列有更小的 -47,但 -19 所在的行和列都没有更小的了,所以 -19 的“秩” 为最小的 1;
  5. 继续检查 -47,它所在的行和列都没有更小的了,所以 -47 的“秩”也为最小的 1;
  6. 然后再回退一步,检查 -21,除了 -47 之外,同行同列没有比 -21 更小的数字了,所以我们暂时为它赋值“秩”为 2,因为我们不确定,其他地方是否也有 -21,但是却存在 -47 和 -21 之间的数字;
  7. 不断重复上述步骤,如果遇到第 6 步提到的冲突情况,则取更大的值,直到所有数字都满足要求。

其实在这个过程中,我们就可以看出,满足要求的“秩”有以下两个特征:

  1. 相同数字的“秩”是一样的;
  2. 不同数字可以有相同的“秩”,只要它们在各自的行、列满足要求。

所以,类似深度搜索,我们可以使用递归来解决问题。结合上面直观暴力的方法,最终思路如下:

  1. 从任意一个数字开始检查,它的秩要比它所在行或列里比它小的数字里最大的“秩”加一;
  2. 如果它的下一个数字和它相等,则继续查找下一个;
  3. 行、列里满足条件的数字如果还没有“秩”,则进入递归,回到第 1 步;
  4. 如果行、列里没有比该数字更小的数字,则该数字的“秩”为一,递归返回。

上述递归的难点在于,每个数字要额外记录比它小的数字里最大的数字的位置。可以额外使用一个三维数组来记录,每个数字记录它的行和列里下一个数字的行列信息,或者就直接在每次查找的时候再排序进行查找。

第二个要注意的地方就是相等的数字的“秩”也相同,所以当某数字的下一个数字和自己相等时,如果它没有“秩”,则跳过,继续查找下一个,如果它已经有了“秩”,则直接返回,不执行加一操作。

本期客观因素太多,造成众多选手未能得分,并不是因为题目有多难,所以代码就不献丑了。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

CSDN周赛65期简要题解 的相关文章

随机推荐

  • delphi 获取有输入焦点的活动窗口信息

    var wintext array 0 MAXBYTE of Char WdChar array of Char focuswhd THandle processId Pointer threadid Cardinal GUITHREADI
  • c语言入门---调试技巧

    目录 什么是bug 调试是什么 调试的基本步骤是什么 调试是什么 调试的基本步骤是什么 Debug和release的区别 windows的调试介绍 调试的准备 调试的操作 1 F5 2 F9 3 F10 4 F11 调试的时候查看程序当前的
  • kali linux基本命令

    文章目录 shell 什么是shell 查看shell shell与终端的区别 VIM编辑器 Linux常用命令 shell 什么是shell 在计算机科学中 shell俗称外壳 能够接收用户的命令并翻译给操作系统执行 是用户与操作系统 内
  • CryptoPP的LC_RNG算法的使用

    随机数发生器是密码学的一个重要原语 密码学库CryptoPP中提供了一些随机数发生器算法 如下图所示 今天 介绍一些其中LC RNG算法的使用 该库中的LC RNG算法就是著名的线性同余发生器算法 该算法由于执行效率高而被广泛使用 C语言库
  • @Conditional 初学

    点击 Conditional Target ElementType TYPE ElementType METHOD Retention RetentionPolicy RUNTIME Documented public interface
  • win10安装Tensorflow1.14.0 CUP版

    安装cpu版本 python3 6 12 tensorflow1 14 0 numpy1 16 0 python tensorflow 和 numpy之间版本要相对应 这很重要 不然可能会装不上 这是尝试了4天后的可行搭配 目 录 预备备
  • 代码题-判断循环依赖

    interface Module name string imports Module const moduleC Module name moduleC const moduleB Module name moduleB imports
  • 【ORACLE性能分析和优化思路学习笔记02:什么时候需要对性能进行干预】

    背景 近期负责的一些单位 一些数据库节点总是出现宕机或者自动重启 之前简单接触过oracle RAC数据库的一些管理 但是对性能分析和优化研究不深 这次实在是没办法了 DBA协调不动 只能自己出马了 好在自己有一定的基础 上手很快 现在对学
  • pytorch常见问题

    1 pytorch 的 dataloader 在读取数据时 设置了较大的 batchsize 和 num workers 然后训练一段时间报错 RuntimeError Too many open files Communication w
  • LeetCode 414. 第三大的数-C语言

    LeetCode 414 第三大的数 C语言 题目描述 解题思路 1 设置数组max 3 用于保存前三大的值 初始化为LONG MIN意为最小值 2 遍历数组对前三大的值进行更新 3 判断max 2 是否存在 若不存在直接返回max 0 代
  • 笔记本电脑切换不到投影仪 问题 解决方法

    我的笔记本是ati显卡的 在某次切换到投影仪的时候 出现问题 无法正确应用您所选择的以下设置 请更改设置并重试 外部监视器或投影仪 电视机 分辨率 颜色质量 无法正确应用您所选择的以下设置 请更改设置并重试 显示配置 解决思路 公司还有一个
  • Neo-reGeorg正向代理配合kali使用

    Neo reGeorg正向代理配合kali使用 一 Neo reGeorg介绍 在了解Neo reGeorg之前 首先应该知道大名鼎鼎的项目 https github com sensepost reGeorg 其用于开启目标服务器到本地的
  • 数据存储的随想

    文章目录 数据分布的演变 数据的使用 总结 数据分布的演变 数据分布就是一个关于数据存放在哪里的问题 数据存储的地方不是固定的 随着应用规模的扩大 为了治理的方便 会适时地调整 其中就会包括数据存储的调整 数据与应用部署在同一台设备 在早期
  • ACCESS的VBA中如何打开文件对话框并获取选中文件的路径

    在 ACCESS 的 VBA 中 可以使用 FileDialog 对象的 Show 方法来打开文件对话框 并使用 SelectedItems 属性来获取选中文件的路径 例如 Dim fd As FileDialog Set fd Appli
  • C/C++ 报错提示 “表达式必须包含类类型” 与 “不可访问”

    今天给大家分享两个常见的错误 定义对象 调用函数 时提示 表达式必须包含类类型 的报错 对象调用函数时提示 不可访问 的报错 一 表达式必须包含类类型 这种报错会出现在两种情况 类没有数据成员时 使用类定义对象时带括号了 定义类时以指针方式
  • MySQL重装——Database initialization failed错误处理

    卸载MySQL 笔者由于跟着网上的教程将MySQL安装到了C盘 忘记了可以走更改路径这条路 在卸载MySQL的路上一去不复返 试过网上诸多重装方案 大体均为以下步骤 控制面板卸载MySQL 删除注册表 删除ProgramData Appli
  • 导出文件:window.open()

    导出文件 window open globalBus emit loading const Download http window location host DI activity orderExcel actId this actId
  • Python-ElasticSearch客户端的封装(聚合查询、统计查询、全量数据)

    目录 ES Python客户端介绍 封装代码 测试代码 参考 ES Python客户端介绍 官方提供了两个客户端elasticsearch elasticsearch dsl pip install elasticsearch pip in
  • Flink1.13.0 + Hudi 0.11.1 + Hive2.1.1 + presto0.273.3 + yanagishima 18.0

    摘要 flink1 13 0 整合 Hudi 0 11 1 通过FlinkSQL程序 FlinkSQL命令行对Hudi的MOR及COW进行批量写 流式写 流式读取 批量读取 通过flink sql cdc flink sql kafka f
  • CSDN周赛65期简要题解

    最近几期周赛里 貌似 Python 又变成 C 站的亲儿子了 输入形式是列表还不过瘾 现在输出形式也要求是列表 而且是连一个逗号 空格 中括号都不能少的 Python 标准列表形式 虽然对 Python 来说是信手拈来 但总要考虑一下其他编