当前位置：首页 > news >正文

第436场周赛：按对角线进行矩阵排序、将元素分配给有约束条件的组、统计可以被最后一个数位整除的子字符串数目、最大化游戏分数的最小值

news 来源：原创 2025/5/21 1:41:42

Q1、按对角线进行矩阵排序

1、题目描述

给你一个大小为 n x n 的整数方阵 grid。返回一个经过如下调整的矩阵：

左下角三角形（包括中间对角线）的对角线按 非递增顺序 排序。
右上角三角形 的对角线按 非递减顺序 排序。

2、解题思路

遍历所有对角线：

主对角线及以下的对角线：从 (i,0) 开始遍历 (i=0,1,...,n-1)，这些对角线需要降序排序。
主对角线右侧的对角线：从 (0,j) 开始遍历 (j=1,2,...,n-1)，这些对角线需要升序排序。

对每条对角线进行排序：

提取当前对角线的所有元素存入数组 v。
按照题目要求对 v 进行排序。
按照对角线的顺序，将排序后的 v 放回 grid。

3、代码实现

class Solution {
public:vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {int n = grid.size(); // 矩阵大小// 处理左下角三角形 (含主对角线) :非递增排序for (int i = 0; i < n; ++i) {sortDiagonal(grid, i, 0, false);}// 处理右上角三角形: 非递减排序for (int j = 1; j < n; ++j) {sortDiagonal(grid, 0, j, true);}return grid;}private:/*** @brief 对矩阵的某条对角线进行排序** @param grid 矩阵* @param row  当前对角线起点的行索引* @param col  当前对角线起点的列索引* @param increasing 是否升序排序（true: 升序, false: 降序）*/void sortDiagonal(vector<vector<int>>& grid, int row, int col, bool increasing) {int n = grid.size();vector<int> v; // 存储对角线元素int i = row, j = col;// 收集当前对角线上的所有元素while (i < n && j < n) {v.push_back(grid[i++][j++]);}// 按照要求排序if (increasing) {sort(v.begin(), v.end()); // 升序排序} else {sort(v.rbegin(), v.rend()); // 降序排序}// 将排序后的元素放回原来的对角线位置i = row, j = col;int idx = 0;while (i < n && j < n) {grid[i++][j++] = v[idx++];}}
};

在这里插入图片描述

4、复杂度分析

时间复杂度分析：

总共有 2n-1 条对角线，每条对角线至多 n 个元素。
每条对角线排序需要 O(n log n)，所以总的时间复杂度为 O(n² log n)。

Q2、将元素分配给有约束条件的组

1、题目描述

给你一个整数数组 groups，其中 groups[i] 表示第 i 组的大小。另给你一个整数数组 elements。

请你根据以下规则为每个组分配一个元素：

如果 groups[i] 能被 elements[j] 整除，则元素 j 可以分配给组 i。
如果有多个元素满足条件，则分配下标最小的元素 j 。
如果没有元素满足条件，则分配 -1 。

返回一个整数数组 assigned，其中 assigned[i] 是分配给组 i 的元素的索引，若无合适的元素，则为 -1。

**注意：**一个元素可以分配给多个组。

2、解题思路

预处理 elements：

记录 元素值 val 的最小索引 j，使用 unordered_map<int, int> 存储 {元素值 -> 最小索引}。
用 set<int> 维护所有可用 elements。

遍历 groups，查找可整除元素的最小索引：

优化方式：只检查 groups[i] 的 所有因数（因数成对出现）。
在 set<int> 里查找因数 d 和 groups[i] / d，找到最小索引。

时间复杂度分析：

预处理 elements：O(m)。
遍历 groups：O(n * sqrt(groups[i]))，因数分解至多 sqrt(groups[i]) 次。
总复杂度：约 O(n log max(groups[i]) + m)，可接受。

3、代码实现

class Solution {
public:vector<int> assignElements(vector<int>& groups, vector<int>& elements) {int n = groups.size();int m = elements.size();vector<int> ret(n, -1); // 结果数组, 初始值为 -1unordered_map<int, int> elementIndex; // 记录元素值 -> 最小索引set<int> elementSet;                  // 记录所有可用的元素值// 预处理 elements, 记录每个元素的最小索引for (int j = 0; j < m; ++j) {if (elementIndex.find(elements[j]) == elementIndex.end()) {elementIndex[elements[j]] = j; // 只存最小索引}elementSet.insert(elements[j]); // 记录存在的元素}// 遍历 groups, 寻找最小可用元素索引for (int i = 0; i < n; ++i) {int minIndex = -1; // 记录当前 groups[i] 可选元素的最小索引// 枚举 groups[i] 的因数 dfor (int d = 1; d * d <= groups[i]; ++d) {if (groups[i] % d == 0) {// 可能的两个因数: d 和 groups[i] / dint factor1 = d, factor2 = groups[i] / d;// 检查因数 factor1 是否在元素集中, 更新最小索引if (elementSet.count(factor1) &&(minIndex == -1 || elementIndex[factor1] < minIndex)) {minIndex = elementIndex[factor1];}// 检查因数 factor2// 是否在元素集中, 更新最小索引 (避免重复检查相等因数)if (factor1 != factor2 && elementSet.count(factor2) &&(minIndex == -1 || elementIndex[factor2] < minIndex)) {minIndex = elementIndex[factor2];}}}ret[i] = minIndex; // 存储当前组的最优元素索引}return ret;}
};

在这里插入图片描述

4、复杂度分析

步骤	操作	时间复杂度
预处理 `elements`	存入 `unordered_map` & `set`	`O(m)`
遍历 `groups`	`O(n)`
计算 `groups[i]` 的所有因数	`O(sqrt(groups[i]))`
查找因数是否存在	`O(1)`
总复杂度	`O(n log max(groups[i]) + m)`

Q3、统计可以被最后一个数位整除的子字符串数目

1、题目描述

给你一个只包含数字的字符串 s 。

请你返回 s 的最后一位不是 0 的子字符串中，可以被子字符串最后一位整除的数目。

子字符串 是一个字符串里面一段连续非空的字符序列。

**注意：**子字符串可以有前导 0 。

2、解题思路

维护 remainderCount 结构

remainderCount[mod][rem] 记录当前处理到的前缀中，对 mod 取模后余数为 rem 的子串个数。

遍历字符串 s

逐个处理字符 digit，它可以作为新子串的起点，也可以扩展已有子串。
对 mod = 1 到 9 进行遍历：
- 计算 digit % mod，即 digit 本身作为单个子串的余数。
- 对于已有的前缀余数 rem，计算新的 newRem = (rem * 10 + digit) % mod，并更新 remainderCount[mod]。
- 统计 digit 作为子串结尾且余数 0 的情况，加到 totalCount。

时间复杂度

由于 mod 只有 1~9，每次更新 O(9)，整体复杂度 O(9 * n) ≈ O(n)，可以高效处理较长字符串。

3、代码实现

class Solution {
public:long long countSubstrings(string s) {long long totalCount = 0;array<int, 9> remainderCount[10]{}; // 记录模 1~9 下的余数分布// 遍历字符串中的每个数字for (char ch : s) {int digit = ch - '0'; // 当前数字// 计算所有 1~9 的模数for (int mod = 1; mod <= 9; mod++) {array<int, 9> newCount{};  // 存储新的余数分布newCount[digit % mod] = 1; // 单独当前字符作为子串// 遍历当前模数 mod 下所有可能的余数for (int rem = 0; rem < mod; rem++) {int newRem = (rem * 10 + digit) % mod; // 计算新的余数newCount[newRem] += remainderCount[mod][rem]; // 更新计数}// 更新模 mod 的余数统计remainderCount[mod] = newCount;}// 统计以当前 digit 结尾的符合条件的子串数量totalCount += remainderCount[digit][0];}return totalCount;}
};

在这里插入图片描述

4、复杂度分析

操作	复杂度
遍历字符串	O(n)
遍历 `mod = 1~9`	O(9)
遍历 `rem = 0~mod`	O(9)
总复杂度	*O(9 n) ≈ O(n)**

Q4、最大化游戏分数的最小值

1、题目描述

给你一个长度为 n 的数组 points 和一个整数 m 。同时有另外一个长度为 n 的数组 gameScore ，其中 gameScore[i] 表示第 i 个游戏得到的分数。一开始对于所有的 i 都有 gameScore[i] == 0 。

你开始于下标 -1 处，该下标在数组以外（在下标 0 前面一个位置）。你可以执行至多 m 次操作，每一次操作中，你可以执行以下两个操作之一：

将下标增加 1 ，同时将 points[i] 添加到 gameScore[i] 。
将下标减少 1 ，同时将 points[i] 添加到 gameScore[i] 。

注意，在第一次移动以后，下标必须始终保持在数组范围以内。

请你返回至多 m 次操作以后，gameScore 里面最小值最大为多少。

2、解题思路

(1) 采用二分查找

我们要找到最大的 minScore，使得 gameScore 的最小值至少是 minScore。由于 minScore 取值范围较大，我们可以 二分查找 这个值。

为什么可以用二分查找？

minScore 设定得越高，满足条件的难度就越大。
我们可以通过一个 canAchieve(minScore) 函数来验证是否能在 m 次操作内实现 gameScore[i] >= minScore。

(2) 设计 canAchieve(minScore) 检查函数

对于 canAchieve(minScore)，我们的目标是检查 是否可以通过最多 m 次操作，使得所有 gameScore[i] 至少为 minScore。

核心逻辑

遍历数组 points，计算需要的步数 stepsNeeded：
- 如果 gameScore[i] 需要至少达到 minScore，那么 stepsNeeded 至少为：
  
  $\text{stepsNeeded} = \frac{\text{minScore} + \text{points}[i] - 1}{\text{points}[i]}$
- 这里是 (minScore + points[i] - 1) / points[i]，是为了确保 上取整 计算 stepsNeeded。
考虑 m 次操作是否足够
- 每次向前移动 1 次后可以返回，因此每个 stepsNeeded 会消耗 $\times \text{stepsNeeded} - 1$ 次操作。
- 如果 remainingMoves < 0，说明 m 次操作不够，返回 false。

(3) 二分查找 minScore 的最大值

left = 0，right = (m + 1) / 2 * *min_element(points.begin(), points.end()) + 1：
- right 设定为 points 数组中最小元素乘 (m+1)/2，这是最极端情况下 minScore 可能达到的最大值。
通过二分查找找到最大的 minScore 使 canAchieve(minScore) == true。

3、代码实现

class Solution {
public:long long maxScore(vector<int>& points, int m) {// 二分查找检查函数, 判断是否能达到 minScoreauto canAchieve = [&](long long minScore) -> bool {int n = points.size(), remainingMoves = m, prevSteps = 0;for (int i = 0; i < n; i++) {// 计算需要多少次操作, 使 gameScore[i] >= minScoreint stepsNeeded =(minScore + points[i] - 1) / points[i] - prevSteps;// 最后一个元素已经满足if (i == n - 1 && stepsNeeded <= 0) {break;}stepsNeeded = max(stepsNeeded, 1); // 至少要前进 1 步// 计算所需的操作次数remainingMoves -= 2 * stepsNeeded - 1; // 左右横跳操作if (remainingMoves < 0) {return false; // 操作次数不够}prevSteps = stepsNeeded - 1; // 预留下一次操作}return true;};// 设定二分查找的搜索范围long long left = 0;long long right = 1LL * (m + 1) / 2 * *min_element(points.begin(), points.end()) + 1;while (left + 1 < right) {long long mid = left + (right - left) / 2;if (canAchieve(mid)) {left = mid; // 尝试更大的 minScore} else {right = mid; // 降低 minScore}}return left;}
};

在这里插入图片描述

4、复杂度分析

二分查找部分：O(log V)，其中 V 是 right 的初始值，大约是 O(log(m))。
canAchieve() 计算：O(n)，因为我们需要遍历 points 数组。
整体复杂度：O(n log m)，对于 n = 10^5，m = 10^9 级别的数据，依然可以接受。

第436场周赛：按对角线进行矩阵排序、将元素分配给有约束条件的组、统计可以被最后一个数位整除的子字符串数目、最大化游戏分数的最小值

Q1、按对角线进行矩阵排序 1、题目描述给你一个大小为 n x n 的整数方阵 grid。返回一个经过如下调整的矩阵： 左下角三角形（包括中间对角线）的对角线按非递增顺序排序。右上角三角形的对角线按非递减顺序排序。 2、解题思路遍历所…...

编程日记 2025/5/21 1:41:42

DeepSeek vs. ChatGPT：不同的诞生时间，对人工智能发展的不同影响

DeepSeek vs. ChatGPT：不同的诞生时间，对人工智能发展的不同影响 ChatGPT 和 DeepSeek 诞生于不同的时间节点，代表了人工智能不同阶段的发展方向。它们在技术、应用以及对AI发展趋势的影响方面各有侧重。 1. 诞生时间与背景 ChatGPT&#x…...

编程日记 2025/5/21 0:28:54

chrome-base 如何实现一个BindOnce

考虑一个问题： worker_thread.task_runner()->PostDelayedTask(FROM_HERE, base::BindOnce(&Ref::Foo, ref, 1), base::Milliseconds(1000)); BindOnce 是如何实现的呢？ 翻看源码：base\functional\bind.h 写的非常简洁 // Bind a…...

编程日记 2025/5/21 0:26:18

代码随想录算法训练营day38

代码随想录算法训练营 —day38 文章目录代码随想录算法训练营前言一、322. 零钱兑换二维dp数组二、279.完全平方数二维dp数组三、139. 单词拆分多重背包背包问题总结问题类型递推公式遍历顺序前言今天是算法营的第38天，希望自己能够坚持下来！ 今日…...

编程日记 2025/5/19 9:57:24

对接DeepSeek

其实，整个对接过程很简单，就四步，获取key，找到接口文档，接口测试，代码对接。获取 KEY https://platform.deepseek.com/transactions 直接付款就是了（现在官网暂停充值2025年2月7日&#xff0…...

编程日记 2025/5/21 0:57:46

【学术投稿-第六届新材料与清洁能源国际学术会议（ICAMCE 2025）】组织与结构：HTML中的＜fieldset＞与＜legend＞标签解析

官网：www.icceam.com 简介第六届新材料与清洁能源国际学术会议（ICAMCE 2025）将于2025年2月21-23日在郑州隆重举行。清洁能源、新材料是当今工业发展中最重要、最有潜力的领域之一。而新型材料又是新能源的基础和保证。本会议主要围绕“清洁…...

编程日记 2025/5/21 0:36:44

网络安全行业的冬天

冬天已经来了，春天还会远吗？2022年10月28日，各个安全大厂相继发布了财报，纵观2022年前三季度9个月，三六零亏了19亿，奇安信亏了11亿，深信服亏了6亿，天融信亏了4亿，安恒亏了…...

编程日记 2025/5/20 14:44:13

PlantUml常用语法

PlantUml常用语法，将从类图、流程图和序列图这三种最常用的图表类型开始。类图基础语法在 PlantUML 中创建类图时，你可以定义类（Class）、接口（Interface）以及它们之间的关系，如继承&#…...

编程日记 2025/5/21 1:21:14

【开源免费】基于SpringBoot+Vue.JS网上服装商城（JAVA毕业设计）

本文项目编号 T 185 ，文末自助获取源码 \color{red}{T185，文末自助获取源码} T185，文末自助获取源码目录一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程四、功能截图五、文案资料5.1 选题背景5.2 国内…...

编程日记 2025/5/20 10:47:18

力扣LeetCode: 80 删除有序数组中的重复项Ⅱ

题目： 给你一个有序数组 nums ，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件…...

编程日记 2025/5/21 1:09:07

Linux之kernel(4)netlink通信

Linux内核(04)之netlink通信 Author: Once Day Date: 2023年1月3日一位热衷于Linux学习和开发的菜鸟，试图谱写一场冒险之旅，也许终点只是一场白日梦… 漫漫长路，有人对你微笑过嘛… 全系列文章可查看专栏: Linux内核知识_Once-Day的博客-…...

编程日记 2025/5/20 23:36:34

autMan奥特曼机器人-对接deepseek教程

一、安装插件ChatGPT 符合openai api协议的大模型均可使用此插件，包括chatgpt-4/chatgpt-3.5-turbo，可自定义服务地址和模型，指令：gpt，要求Python3.7以上，使用官方库https://github.com/openai/openai-pyt…...

编程日记 2025/5/20 14:55:34

Java 大视界 -- Java 大数据在智能政务中的应用与服务创新（78）

💖亲爱的朋友们，热烈欢迎来到青云交的博客！能与诸位在此相逢，我倍感荣幸。在这飞速更迭的时代，我们都渴望一方心灵净土，而我的博客正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识，也…...

编程日记 2025/5/20 6:16:02

错误信息 resttemplate I/O error on GET request for “https://21.24.6.6:9443/authn-api/v5/oauth/token”: java.security.cert.CertificateException: No subject alternative names present; nested exception is javax.net.ssl.SSLHandshakeException: java.security.c…...

编程日记 2025/5/19 23:50:16

自动化测试

import os import pyautogui# 将鼠标移动到屏幕坐标 (100, 100) 位置，移动时间为 1 秒 pyautogui.moveTo(100, 100, duration1)# 将鼠标从当前位置向右移动 50 像素，向下移动 50 像素，移动时间为 0.5 秒 pyautogui.moveRel(50, 50, duration0…...

编程日记 2025/5/21 0:54:55

【C编程问题集中营】使用数组指针时容易踩得坑

【C编程问题集中营】使用数组指针时容易踩得坑文章目录【C编程问题集中营】使用数组指针时容易踩得坑一、获取数组首地址二、应用场景举例2.1 正常场景2.2 异常场景三、总结一、获取数组首地址一维数组的首地址即数组第一个元素的指针，常用的获取一维数组首地…...

编程日记 2025/5/20 14:09:01

【分布式理论8】分布式调用之：四种IO模型

文章目录一. 四种IO模型1. 同步阻塞 IO（Blocking IO）2. 同步非阻塞 IO（Non-blocking IO）3. IO 多路复用（IO Multiplexing）4. 异步 IO（Asynchronous IO）在 RPC 中的作用5. 总结选择…...

编程日记 2025/5/21 1:13:46

MySQL 库建表数量有限制吗？

问：MySQL 库建表数量有限制吗？ 答：无限制官方文档： MySQL has no limit on the number of databases. The underlying file system may have a limit on the number of directories. MySQL has no limit on the number of tabl…...

编程日记 2025/5/20 23:32:37

使用OpenGL自己定义一个button，响应鼠标消息：掠过、点击、拖动

button需要有一个外观外观大小跟随窗口改变，采用纯色背景、纯色文字文字大小跟随窗口改变 button需要获得鼠标消息掠过鼠标掠过时 button 出现阴影，鼠标掠过后 button 阴影消失点击点击后进入相应事件拖动改变图标所在位置需要在g…...

编程日记 2025/5/20 23:29:28

基础入门-网站协议身份鉴权OAuth2安全Token令牌JWT值Authirization标头

知识点： 1、网站协议-http/https安全差异（抓包） 2、身份鉴权-HTTP头&OAuth2&JWT&Token 一、演示案例-网站协议-http&https-安全测试差异性 1、加密方式 HTTP：使用明文传输，数据在传输过程中可以被…...

编程日记 2025/5/20 13:06:42

【Python】元组

个人主页：GUIQU. 归属专栏：Python 文章目录 1. 元组的本质与基础概念1.1 不可变序列的意义1.2 元组与数学概念的联系 2. 元组的创建方式详解2.1 标准创建形式2.2 单元素元组的特殊处理2.3 使用 tuple() 函数进行转换 3. 元组的基本操作深入剖析3.1 索引操…...

编程日记 2025/5/21 0:34:12

深度求索与DeepSeek-R1：探索人工智能的新纪元

深度求索与DeepSeek-R1：探索人工智能的新纪元引言在当今快速发展的科技领域，尤其是人工智能（AI）方面，每隔一段时间就会出现一款革命性的产品或技术，彻底改变我们对这一领域的认知。2025年初&#xff0c…...

编程日记 2025/5/20 23:19:27

java: framework from BLL、DAL、IDAL、MODEL、Factory using oracle

oracel 21c sql: -- 创建 School 表 CREATE TABLE School (SchoolId CHAR(5) NOT NULL,SchoolName NVARCHAR2(500) NOT NULL,SchoolTelNo VARCHAR2(8) NULL,PRIMARY KEY (SchoolId) );CREATE OR REPLACE PROCEDURE addschool(p_school_id IN CHAR,p_school_name IN NVARCHAR2,p…...

编程日记 2025/5/20 22:48:05

Q1、按对角线进行矩阵排序

1、题目描述

2、解题思路

3、代码实现

4、复杂度分析

Q2、将元素分配给有约束条件的组

1、题目描述

2、解题思路

3、代码实现

4、复杂度分析

Q3、统计可以被最后一个数位整除的子字符串数目

1、题目描述

2、解题思路

3、代码实现

4、复杂度分析

Q4、最大化游戏分数的最小值

1、题目描述

2、解题思路

3、代码实现

4、复杂度分析

相关文章：