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

LeetCode --- 436周赛

题目列表

3446. 按对角线进行矩阵排序
3447. 将元素分配给有约束条件的组
3448. 统计可以被最后一个数位整除的子字符串数目
3449. 最大化游戏分数的最小值

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

在这里插入图片描述
直接模拟,遍历每一个斜对角线,获取斜对角线上的数字,排序后重新赋值即可。

这里教大家一个从右上角往左下角依次遍历斜对角线的方法,对于每一条对角线上的任意元素 g r i d [ i ] [ j ] grid[i][j] grid[i][j],我们会发现 i − j i-j ij 为一个定值,以 3 × 3 3\times 3 3×3 的矩阵为例,从右上角往左下角 i − j i-j ij 分别为 − 2 , − 1 , 0 , 1 , 2 -2,-1,0,1,2 2,1,0,1,2,只要加上一个偏移量 3 3 3,就会变成 1 , 2 , 3 , 4 , 5 1,2,3,4,5 1,2,3,4,5

由此可以推导出一个公式,对于一个 n × m n\times m n×m 的矩阵,令 k = m + i − j k=m+i-j k=m+ij,让 k = 1 , 2 , . . . , n + m − 1 k=1,2,...,n+m-1 k=1,2,...,n+m1,可以依次遍历每一条斜对角线,其中 i ∈ [ 0 , n − 1 ] , j = m + i − k i\in [0,n-1],j=m+i-k i[0,n1]j=m+ik

代码如下

// C++
class Solution {
public:vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size();// 令 k = m - j + i => j = m - k + i , i = k - m + j// 当 i = 0 时,j = m - k// 当 i = n - 1 时,j = m - k + n - 1for(int k = 1; k < n + m; k++){int min_j = max(m - k, 0); // 注意越界int max_j = min(m - k + n - 1, m - 1); // 注意越界vector<int> res;for(int j = min_j; j <= max_j; j++){res.push_back(grid[k - m + j][j]);}if(min_j > 0) ranges::sort(res);else ranges::sort(res, greater<>());for(int j = min_j; j <= max_j; j++){grid[k - m + j][j] = res[j - min_j];}}return grid;}
};
# Python
class Solution:# k = m + i - j# i = 0, j = m - k# i = n - 1, j = m - k + n - 1def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:n, m = len(grid), len(grid[0])for k in range(1, n+m):min_j = max(m - k, 0)max_j = min(m - k + n - 1, m - 1)res = [grid[k - m + j][j] for j in range(min_j, max_j + 1)]res.sort(reverse=min_j==0)for j, val in zip(range(min_j, max_j + 1), res):grid[k - m + j][j] = valreturn grid

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

在这里插入图片描述
我们可以优先计算出 e l e m e n t s elements elements 中数字的倍数情况,存放在 f [ x ] f[x] f[x] 中, f [ x ] = i f[x]=i f[x]=i 表示 x x x 能被 e l e m e n t s [ i ] elements[i] elements[i] 整除,如果有多个 i i i 符合条件,取最左边的那个,然后根据 f [ x ] f[x] f[x] 中的结果给 g r o u p s groups groups 中的数进行赋值即可,具体操作见代码,如下

// C++
class Solution {
public:vector<int> assignElements(vector<int>& groups, vector<int>& elements) {int n = groups.size(), m = elements.size();int mx = ranges::max(groups);vector<int> f(mx + 1, -1);// 时间复杂度分析// 当elements=[1,2,3,...,x]时,达到最坏时间复杂度//  mx/1+mx/2+...+mx/x//= mx(1+1/2+1/3+...+1/x)//= mx*log(x)for(int i = 0; i < m; i++){int x = elements[i];if(x > mx || f[x] != -1) continue;for(int j = 1; j < mx/x + 1; j++){if(f[x*j] == -1){f[x*j] = i;}}}vector<int> ans(n);for(int i = 0; i < n; i++){ans[i] = f[groups[i]];}return ans;}
};
# Python
class Solution:def assignElements(self, groups: List[int], elements: List[int]) -> List[int]:mx = max(groups)f = [-1] * (mx + 1)for i, x in enumerate(elements):if x > mx or f[x] != -1:continuefor j in range(x, mx+1, x):if f[j] < 0:f[j] = ireturn [f[x] for x in groups]

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

统计可以被最后一个数位整除的子字符串数目
题目思路:

  • 由于最后一位数的取值为 1 1 1~ 9 9 9,我们可以分别统计以这些数为结尾的数字对答案的贡献

  • 假设我们计算以 x x x 为结尾的数字对答案的贡献

    • 对于前 i i i 个字符组成的数字 S i − 1 S_{i-1} Si1,加上当前数字 s i s_i si,它的取模结果为 ( S i − 1 × 10 + s i ) % x = ( ( S i − 1 × 10 ) % x + s i ) % x = ( ( S i − 1 % x ) × 10 + s i ) % x (S_{i-1} \times 10 + s_i)\%x=((S_{i-1} \times 10)\%x+s_i)\%x=((S_{i-1}\%x) \times 10+s_i)\%x (Si1×10+si)%x=((Si1×10)%x+si)%x=((Si1%x)×10+si)%x
    • 从式子中我们可以看出,我们其实并不需要关心数字 S i − 1 S_{i-1} Si1 具体是多少,我们只要知道 S i − 1 % x S_{i-1}\%x Si1%x 的结果即可
    • f [ i ] [ j ] f[i][j] f[i][j] 表示数字 S i S_i Si x x x 后结果为 j j j 的所有数字个数
      • f [ i ] [ ( j × 10 + s i ) % x ] + f[i][(j\times10+s_i)\%x]\ + f[i][(j×10+si)%x] + = f [ i − 1 ] [ j ] =f[i-1][j] =f[i1][j] j ∈ [ 0 , x ) j\in[0,x) j[0,x) s i s_i si 和前面的 S i − 1 S_{i-1} Si1 合起来作为一个数
      • f [ i ] [ s i % x ] + f[i][s_i\%x]\ + f[i][si%x] + = 1 =1 =1 s i s_i si 单独作为一个数
    • s i = x s_i=x si=x 时,将 f [ i ] [ 0 ] f[i][0] f[i][0] 加入答案

代码如下

// C++
class Solution {
using LL = long long;
public:long long countSubstrings(string s) {int n = s.size();LL ans = 0;for(int x = 1; x < 10; x++){vector f(n + 1, vector<LL>(x));for(int i = 0; i < n; i++){int y = s[i] - '0';for(int j = 0; j < x; j++){f[i+1][(j*10+y)%x] += f[i][j];}f[i+1][y%x]++;if(y == x) ans += f[i+1][0];}}return ans;}
};
// 空间优化
class Solution {
using LL = long long;
public:long long countSubstrings(string s) {int n = s.size();LL ans = 0;for(int x = 1; x < 10; x++){vector<LL> f(x);for(int i = 0; i < n; i++){vector<LL> t(x);int y = s[i] - '0';for(int j = 0; j < x; j++){t[(j*10+y)%x] += f[j];}t[y%x]++;f = t;if(y == x) ans += f[0];}}return ans;}
};
# Python
class Solution:def countSubstrings(self, s: str) -> int:n = len(s)ans = 0for x in range(1, 10):f = [0] * xfor y in map(int, s):t = [0] * xfor j in range(x):t[(j*10+y)%x] += f[j]t[y%x] += 1f = tif x == y: ans += f[0]return ans

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

最大化游戏分数的最小值
最大化最小值,显然用二分来做。

  • 是否具有单调性?显然具备,因为 g a m e S c o r e m i n gameScore_{min} gameScoremin 越大,则每个下标位 + + + = p o i n t s [ i ] =points[i] =points[i] 的操作次数就会变多,则总操作数就会更容易超过 m m m,故可以用二分
  • c h e c k check check 函数如何写?这里有个结论:对于任意一种下标移动顺序,都能变成若干组左右来回横跳的形式。所以我们可以贪心的让左边的下标先满足条件,然后再考虑后面的位置,即我们先考虑通过 0 → 1 、 1 → 0 0 \rightarrow 1、1 \rightarrow 0 0110 0 0 0 先满足条件,在用 1 → 2 、 2 → 1 1 \rightarrow 2、2 \rightarrow 1 1221 1 1 1 满足条件,同样的方式让 2 、 3 、 . . . 、 n − 1 2、3、...、n-1 23...n1 依次满足条件,看总操作次数是否 > m >m >m

代码如下

// C++
class Solution {
using LL = long long;
public:long long maxScore(vector<int>& points, int m) {int n = points.size();auto check = [&](LL k)->bool{if(k == 0) return true;int s = m, pre = 0; // pre 表示为了解决 i - 1 位置,进行反复横跳之后,对 i 位置已经进行的 += points[i] 操作次数for(int i = 0; i < n; i++){int ops = (k - 1) / points[i] + 1 - pre; // 需要走 ops 次if(i == n - 1 && ops <= 0)break;ops = max(1, ops); // 从 i-1 移动到 i,需要至少 1 次操作s -= 2 * (ops - 1) + 1;if(s < 0) return false;pre = ops - 1;}return true;};// (m + 1)/2 表示只有两个数时,第一个数进行的操作次数,这里我们默认将最小值放在这一位,得到一个上限LL l = 0, r = 1LL * (m + 1) / 2 * ranges::min(points);while(l <= r){LL mid = l + (r - l)/2;if(check(mid)) l = mid + 1;else r = mid - 1;}return r;}
};
# Python
class Solution:def maxScore(self, points: List[int], m: int) -> int:n = len(points)def check(k:int)->int:if k == 0: return Trues = mpre = 0for i, x in enumerate(points):ops = (k - 1) // x + 1 - preif i == n - 1 and ops <= 0:return Trueops = max(ops, 1)s -= 2 * ops - 1if s < 0: return Falsepre = ops - 1return Truel , r = 0, (m + 1) // 2 * min(points)while l <= r:mid = l + (r - l) // 2if check(mid):l = mid + 1else:r = mid - 1return r

相关文章:

LeetCode --- 436周赛

题目列表 3446. 按对角线进行矩阵排序 3447. 将元素分配给有约束条件的组 3448. 统计可以被最后一个数位整除的子字符串数目 3449. 最大化游戏分数的最小值 一、按对角线进行矩阵排序 直接模拟&#xff0c;遍历每一个斜对角线&#xff0c;获取斜对角线上的数字&#xff0c;排…...

用easyExcel如何实现?

要使提供的 ExcelModelListener 类来解析 Excel 文件并实现批量存储数据库的功能&#xff0c;需要结合 EasyExcel 库来读取 Excel 数据。具体来说&#xff0c;可以使用 EasyExcel.read() 方法来读取 Excel 文件&#xff0c;并指定 ExcelModelListener 作为事件监听器。 下面是…...

从 X86 到 ARM :工控机迁移中的核心问题剖析

在工业控制领域&#xff0c;技术的不断演进促使着工控机从 X86 架构向 ARM 架构迁移。然而&#xff0c;这一过程并非一帆风顺&#xff0c;面临着诸多关键挑战。 首先&#xff0c;软件兼容性是一个重要问题。许多基于 X86 架构开发的工业控制软件可能无法直接在 ARM 架构上运行…...

大模型DeepSeek-R1学习

学习路线 机器学习-> 深度学习-> 强化学习-> 深度强化学习 大模型演进分支 微调&#xff1a; SFT 监督学习蒸馏&#xff1a;把大模型作为导师训练小模型RLHF&#xff1a;基于人类反馈的强化学习 PPO 近端策略优化 油门 - 重要性采样 权重 * 打分刹车 - clip 修剪…...

【STM32】H743的以太网MAC控制器的一个特殊功能

调试743的MAC&#xff0c;翻阅手册的时候&#xff0c;发现了一个有意思的功能 混杂模式 H743的MAC控制器&#xff0c;可以设置为混杂模式&#xff0c;这就意味着它可以做一些网络监控的应用&#xff0c;譬如连接具备端口镜像功能的交换机&#xff0c;然后直接代替PC实现网络数据…...

关于“i18n“在vue中的使用

关于"i18n"在vue中的使用 <!-- vue2中 --> <template><div>{{ $t("This campaign has expired.") }}}}</div> </template> <script> export default {created() {this.onLoading();},methods: {onLoading () {this.$…...

前缀树算法篇:前缀信息的巧妙获取

前缀树算法篇&#xff1a;前缀信息的巧妙获取 那么前缀树算法是一个非常常用的算法&#xff0c;那么在介绍我们前缀树具体的原理以及实现上&#xff0c;我们先来说一下我们前缀树所应用的一个场景&#xff0c;那么在一个字符串的数据集合当中&#xff0c;那么我们查询我们某个字…...

DVSI使用SenseGlove为开发虚拟现实场景技能培训

虚拟现实场景技能培训能够有效提升被培训者的技能熟练度&#xff0c;使其在现实世界中经历类似事件时第一时间做出正确反映&#xff0c;从而大大降低因缺乏相关技能经验所造成的财产、人员、时间损失。 DVSI&#xff08;Digital Voice Systems Inc&#xff09;是一家美国数字化…...

VSCode + Continue 实现AI编程助理

安装VS Code 直接官网下载安装&#xff0c;反正是免费的。 安装VS插件Continue 直接在插件市场中搜索&#xff0c; Continue&#xff0c;第一个就是了。 配置Chat Model 点击Add Chat model后进行选择&#xff1a; 选择Ollama后&#xff0c;需要点击下面的config file : 由于…...

【PHP的static】

关于静态属性 最简单直接&#xff1a;静态方法也是一样 看了很多关于静态和动态的说法&#xff0c;无非是从 调用方式&#xff0c; 类访问实例变量&#xff0c; 访问静态变量&#xff0c; 需不要实例化这几个方向&#xff0c;太空了。问使用场景&#xff0c;好一点的 能说个…...

考研操作系统----操作系统的概念定义功能和目标(仅仅作为王道哔站课程讲义作用)

目录 操作系统的概念定义功能和目标 操作系统的四个特征 操作系统的分类 ​编辑 操作系统的运行机制 系统调用 操作系统体系结构 操作系统引导 虚拟机 操作系统的概念定义功能和目标 什么是操作系统&#xff1a; 操作系统是指控制和管理整个计算机系统的软硬件资源&…...

从360度全景照片到高质量3D场景:介绍SC-Omnigs 3D重建系统

在当今的数字化时代,3D重建技术正在迅速发展,并广泛应用于文旅、空间智能和3D重建等领域。为了简化360度全景相机拍摄数据的处理流程,提高3D场景重建的质量和效率,我们开发了一款专门处理360度全景相机数据的3D重建系统——SC-Omnigs。本文将详细介绍这一系统的功能、特点及…...

前沿技术新趋势:值得关注的创新发展

量子通信是一种新兴的通信技术。它基于量子力学的原理&#xff0c;特别是量子叠加和量子纠缠。量子通信的核心在于量子比特qubits&#xff09;&#xff0c;与传统的比特不同&#xff0c;量子比特可以同时处于多种状态。这种特性使得信息的传输更为安全。 量子通信技术的最大优…...

算法跟练第十一弹——二叉树

文章目录 part01 递归遍历1.1 二叉树的前序遍历1.2 二叉树的中序遍历1.3 二叉树的后序遍历 part02 迭代遍历2.1 二叉树的前序遍历2.2 二叉树的中序遍历2.3 二叉树的后序遍历 part03 层序遍历3.1 二叉树的层序遍历3.2 二叉树的层序遍历II3.3 二叉树的右视图 归纳获取双重链表的第…...

机器学习(李宏毅)——BERT

一、前言 本文章作为学习2023年《李宏毅机器学习课程》的笔记&#xff0c;感谢台湾大学李宏毅教授的课程&#xff0c;respect&#xff01;&#xff01;&#xff01; 读这篇文章必须先了解self-attention、Transformer&#xff0c;可参阅我其他文章。 二、大纲 BERT简介self-…...

新数据结构(7)——Object

Object类是所有类的父类&#xff0c;在 Java 中&#xff0c;每个类都直接或间接地继承自Object类&#xff0c;也就是说所有类都是object类的子类可以使用Object里的方法。 equals()和hashCode()是Java中Object类所包含的两个关键方法&#xff0c;下面将介绍两个方法。 和equa…...

云计算基础

环境准备 配置虚拟机安装docker 前提安装 步骤命令效果图 安装docker-compose 前提安装 步骤效果图 安装gitea 步骤命令效果图 执行docker-compose命令浏览器初始gitea配置浏览器登录gitea创建组织创建仓库 Drone安装 步骤效果图 非自动化部署 nginx安装redis安装jdk安装…...

利用kali linux 进行自动化渗透测试

本方案旨在自动化创建渗透测试全流程 一、架构 1.智能信息收集体系 class IntelligentOSINT:def __init__(self, target):self.target targetself.intelligence_sources [OSINT_Platforms,DeepWeb_Crawlers, SocialMedia_Trackers,ML_Correlation_Engine]def advanced_col…...

【Vue中BUG解决】npm error path git

报错内容如下&#xff1a; 从错误信息可知&#xff0c;这是一个 ENOENT&#xff08;No Entry&#xff0c;即找不到文件或目录&#xff09;错误&#xff0c;并且与 git 相关。具体来说&#xff0c;npm 在尝试调用 git 时&#xff0c;无法找到 git 可执行文件&#xff0c;下面为…...

GPT-4o微调SFT及强化学习DPO数据集构建

假设&#xff0c;已经标注的训练数据集df包含了提示词、输入和输出三列。 构建微调SFT的数据集代码如下&#xff1a; data [] for x in df.values:prompt x[1]user_content x[2]assistant_content x[3]data.append({"messages": [{"role": "sys…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

ArcGIS Pro+ArcGIS给你的地图加上北回归线!

今天来看ArcGIS Pro和ArcGIS中如何给制作的中国地图或者其他大范围地图加上北回归线。 我们将在ArcGIS Pro和ArcGIS中一同介绍。 1 ArcGIS Pro中设置北回归线 1、在ArcGIS Pro中初步设置好经纬格网等&#xff0c;设置经线、纬线都以10间隔显示。 2、需要插入背会归线&#xf…...