LeetCode --- 143周赛

题目列表

3345. 最小可整除数位乘积 I

3346. 执行操作后元素的最高频率 I

3347. 执行操作后元素的最高频率 II

3348. 最小可整除数位乘积 II

一、最小可整除数位成绩I

由于本题的数据范围比较小,我们直接暴力枚举即可,代码如下

class Solution {
public:int smallestNumber(int n, int t) {// 最多循环 10 次,一定能遇到一个带 0 的数字for(int i = n; ; i++){ int tmp = i;int res = 1;while(tmp){res *= (tmp % 10);tmp /= 10;}if(res % t == 0)return i;}return -1;}
};

二、执行操作后元素的最高频率 I & II

在numOperations的操作内,求出现频率最高的数字的出现次数。我们可以先计算出对于任意一个数,在不考虑操作次数的情况下,最多有多少个数字能变成它,然后与操作次数求min,再加上该数字本身出现的个数即可如何计算有多少个数字能变成它?这比较难算,我们可以换一个角度,对于给定的数字,它能变成哪些数字,我们是很容易求出的,而且它能变成的数字是一个区间,并且我们只要计算频率,所以只要对区间整体进行+1/-1的操作即可,很明显,用差分数组进行计算

由于本题的加强版数据范围太大,开数组会爆内存,所以用map来代替数组,map中记录出现变化的点的频率,这样那些频率不发生变化的点就不用遍历了,也大大降低了时间复杂度 ,代码如下

class Solution {
public:int maxFrequency(vector<int>& nums, int k, int numOperations) {int n = nums.size();unordered_map<int,int> cnt; // 统计数字出现次数// 由于数据范围太大,差分数组可以用 map 来代替,节省空间map<int,int> mp; // 统计有多少个数字能变成 yfor(auto x : nums){// 对于数字 x ,能变成 [x-k, x+k] 的任意一个数,但是变成本身不需要操作次数mp[x - k]++;mp[x]--; // 对于 x 本身来说,不需要进行操作mp[x + 1]++;mp[x + k + 1]--;cnt[x]++;}int ans = 0, pre = 0;for(auto [x, c] : mp){pre += c;ans = max(ans, min(pre, numOperations) + (cnt.count(x) ? cnt[x] : 0));}return ans;}
};

这题还有另外的空间复杂度为O(1)的解法。整体思路依旧不变:先计算出对于任意一个数,在不考虑操作次数的情况下,最多有多少个数字能变成它,关键在于我们需要正面解决如何计算有多少个数字能变成它?如何做?

首先,由于操作性质,肯定是相邻的数字更容易变成我们需要的数字,所以先将数组排序。然后我们将频率可能最大的数字分为两类:1、在 nums 数组中的数字  2、不在 nums 数组中的数字

  • 对于在 nums 中的数字 x ,我们可以通过二分计算出 [x-k,x+k] 中的数字个数 / 通过三指针计算出 [x-k,x+k] 中的数字,同时要统计 x 出现的次数 cnt[x],从而计算频率 min(right - left, numOperations + cnt[x]),其中 [left,right) 是在 [x-k,x+k] 内的数字下标区间
  • 对于不在 nums 中的数字, 我们只要维护以 x = nums[i] 为右端点的区间 [x - 2k,x] 内的数字个数即可,可以用滑动窗口计算

  • 注意:一旦在 nums 数组中的数字的频率>= numOperations,直接返回即可,因为不在 nums 数组中的数字的频率最多是 numOperations

代码如下

class Solution {
public:int maxFrequency(vector<int>& nums, int k, int numOperations) {int n = nums.size();ranges::sort(nums);int l = 0, r = 0, ans = 0, cnt = 0;for(int i = 0; i < n; i++){int x = nums[i];cnt++;if(i < n - 1 && x == nums[i + 1])continue;while(r < n && nums[r] - nums[i] <= k)r++;while(nums[i] - nums[l] > k)l++;// [l, r)ans = max(ans, min(r - l, cnt + numOperations));cnt = 0;}if(ans >= numOperations) return ans;// [x-2k, x]for(int left = 0, right = 0; right < n; right++){while(nums[right] - nums[left] > 2*k)left++;ans = max(ans, right - left + 1);}return min(ans, numOperations); // 操作次数最大为numOperations}
};

三、最小可整除数位成绩 II

从小到大去枚举构造所有可能的结果,代码如下

class Solution {
public:string smallestNumber(string s, long long t) {long long tmp = t;for (int i = 9; i > 1; i--) { // 本质只要枚举 2 3 5 7 即可while (tmp % i == 0) {tmp /= i;}}if (tmp > 1) { // t 包含大于 7 的质因子,即有大于 10 的因子return "-1";}int n = s.length();vector<long long> left_t(n + 1); // 从左往右,记录在保持[0, i)不变的情况下,t剩余的值left_t[0] = t;int i0 = n - 1;for (int i = 0; i < n; i++) {if (s[i] == '0') { // 如果出现 0,则 [i, n) 的数字可以任意填写i0 = i;break;}left_t[i + 1] = left_t[i] / gcd(left_t[i], s[i] - '0');}if (left_t[n] == 1) { // s 的数位之积是 t 的倍数return s;}// 假设答案和 s 一样长// 思路:在保持高位不变的情况下,尽可能的将 大数字 放在低位for (int i = i0; i >= 0; i--) {while (++s[i] <= '9') {long long tt = left_t[i] / gcd(left_t[i], s[i] - '0'); // [i,n)需要让 tt 变为 1int k = 9; // 倒着枚举,尽量让大数字在低位for (int j = n - 1; j > i; j--) {while (tt % k) {k--;}tt /= k;s[j] = '0' + k;}if (tt == 1) {return s;}}}// 答案一定比 s 长,则将 t 中的因子从大到小,依次放在个位,十位...,少的位置补1string ans;for (int i = 9; i > 1; i--) {while (t % i == 0) {ans += '0' + i;t /= i;}}ans += string(max(n + 1 - (int) ans.length(), 0), '1');ranges::reverse(ans);return ans;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/473234.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

从建立TRUST到实现FAIR:可持续海洋经济的数据管理

1. 引言 随着我们对信息管理方式的信任&#xff0c;我们的社会对数字化数据的以来呈指数级增长。为了跟上大数据的需求&#xff0c;通过不断的努力和持续实践&#xff0c;对“good”数据管理方式的共识也在不断发展和演变。 加拿大正在建设国家基础设施和服务以及研究数据管理…

微服务即时通讯系统的实现(客户端)----(2)

目录 1. 将protobuf引入项目当中2. 前后端交互接口定义2.1 核心PB类2.2 HTTP接口定义2.3 websocket接口定义 3. 核心数据结构和PB之间的转换4. 设计数据中心DataCenter类5. 网络通信5.1 定义NetClient类5.2 引入HTTP5.3 引入websocket 6. 小结7. 搭建测试服务器7.1 创建项目7.2…

SpringBoot集成itext导出PDF

添加依赖 <!-- PDF导出 --><dependency><groupId>com.itextpdf</groupId><artifactId>itextpdf</artifactId><version>5.5.11</version></dependency><dependency><groupId>com.itextpdf</groupId>&l…

[ACTF2020]Upload 1--详细解析

信息收集 题目告诉我们是一道upload&#xff0c;也就是文件上传漏洞题目。 进入界面&#xff0c;是一个灯泡&#xff0c;将鼠标放在图标上就会出现文件上传的相应位置&#xff1a; 思路 文件上传漏洞&#xff0c;先看看有没有前端校验。 在js源码中找到了前端校验&#xff…

针对股票评论的情感分类器

&#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;编程探索专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2024年11月16日13点39分 神秘男子影, 秘而不宣藏。 泣意深不见, 男子自持重, 子夜独自沉。 论文链接 点击开启你的论文编程之旅…

大数据-226 离线数仓 - Flume 优化配置 自定义拦截器 拦截原理 了 拦截器实现 Java

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; Java篇开始了&#xff01; 目前开始更新 MyBatis&#xff0c;一起深入浅出&#xff01; 目前已经更新到了&#xff1a; Hadoop&#xff0…

【工具插件类教学】在 Unity 中使用 iTextSharp 实现 PDF 文件生成与导出

目录 一、准备工作 1. 安装 iTextSharp 2. 准备资源文件 二、创建 ExportPDFTool 脚本 1、初始化 PDF 文件,设置字体 2、添加标题、内容、表格和图片 三、使用工具类生成 PDF 四、源码地址 在 Unity 项目中,我们有时会需要生成带有文本、表格和图片的 PDF 文件,以便…

【Node.js】使用 Node.js 需要了解多少 JavaScript?

在现代开发中&#xff0c;Node.js 已经成为了构建高性能、可扩展的服务器端应用的必备工具。作为一个基于 JavaScript 的运行时环境&#xff0c;Node.js 使得开发者能够使用同一种语言来编写前后端代码&#xff0c;这在全栈开发中尤为重要。那么&#xff0c;使用 Node.js 开发时…

GRE做题笔记(零散的个人经验)

locomotive机车By 1813, the Luddite resistance had all but vanished. all but表示“几乎完全”的程度&#xff0c;或者表示排除piston活塞attributed to 归因于how a sportsperson accounted for their own experience of stress 运动员如何解释自己的压力经历 &#xff0c;…

Android OpenGL ES详解——实例化

目录 一、实例化 1、背景 2、概念 实例化、实例数量 gl_InstanceID 应用举例 二、实例化数组 1、概念 2、应用举例 三、应用举例——小行星带 1、不使用实例化 2、使用实例化 四、总结 一、实例化 1、背景 假如你有一个有许多模型的场景&#xff0c;而这些模型的…

Python3.11.9+selenium,选择证书用多线程+键盘enter解决

Python3.11.9+selenium,选择证书用多线程+键盘enter解决 1、遇到问题:弹出证书选择,无法点击确定 import pyautogui pyautogui.press(enter) 键盘enter也无法点击 2、解决办法:用多线程解决同时执行click链接和Enter点击证书的确定 1、点击操作 # # 通过文本链接文本…

[Android]相关属性功能的裁剪

1.将home界面的search bar 移除 /src/com/android/launcher3/graphics/LauncherPreviewRenderer.java // Add first page QSBif (FeatureFlags.QSB_ON_FIRST_SCREEN) {CellLayout firstScreen mWorkspaceScreens.get(FIRST_SCREEN_ID);View qsb mHomeElementInflater.infla…

linux笔记(防火墙)

一、概述 防火墙的作用 在 Linux 系统中&#xff0c;防火墙用于控制进出系统的网络流量&#xff0c;基于预定义的安全规则允许或拒绝数据包&#xff0c;从而保护系统免受未经授权的访问、恶意攻击&#xff0c;并确保网络服务的安全运行。 二、常见的 Linux 防火墙软件 iptabl…

WebRTC视频 03 - 视频采集类 VideoCaptureDS 上篇

WebRTC视频 01 - 视频采集整体架构 WebRTC视频 02 - 视频采集类 VideoCaptureModule [WebRTC视频 03 - 视频采集类 VideoCaptureDS 上篇]&#xff08;本文&#xff09; WebRTC视频 04 - 视频采集类 VideoCaptureDS 中篇 WebRTC视频 05 - 视频采集类 VideoCaptureDS 下篇 一、前…

高光谱深度学习调研

综述 高光谱深度学习只有小综述&#xff0c;没有大综述。小综述里面场景分类、目标检测的综述比较多。 Wang C, Liu B, Liu L, et al. A review of deep learning used in the hyperspectral image analysis for agriculture[J]. Artificial Intelligence Review, 2021, 54(7)…

计算机视觉 1-8章 (硕士)

文章目录 零、前言1.先行课程&#xff1a;python、深度学习、数字图像处理2.查文献3.环境安装 第一章&#xff1a;概论1.计算机视觉的概念2.机器学习 第二章&#xff1a;图像处理相关基础1.图像的概念2.图像处理3.滤波器4.卷积神经网络CNN5.图像的多层表示&#xff1a;图像金字…

24-Ingest Pipeline Painless Script

将文档中的tags字段按照逗号&#xff08;,&#xff09;分隔符进行分割。 同时为文档&#xff0c;增加一个字段。blog查看量 DELETE tech_blogs#Blog数据&#xff0c;包含3个字段&#xff0c;tags用逗号间隔 PUT tech_blogs/_doc/1 {"title":"Introducing big …

【ubuntu18.04】vm虚拟机复制粘贴键不能用-最后无奈换版本

我是ubuntu16版本的 之前费老大劲安装的vmware tools结果不能用 我又卸载掉&#xff0c;安装了open-vm-tools 首先删除VMware tools sudo vmware-uninstall-tools.pl sudo rm -rf /usr/lib/vmware-tools sudo apt-get autoremove open-vm-tools --purge再下载open-vm-tools s…

Android Mobile Network Settings | APN 菜单加载异常

问题 从log看是有创建APN对应的Controller&#xff08;功能逻辑是ok的&#xff09;&#xff0c;但是Mobile Network Settings无法显示&#xff08;UI异常&#xff09;。 相关术语&#xff1a; GSM&#xff08;Global System for Mobile Communications&#xff09; 全球移动…

AndroidStudio-Activity的生命周期

一、Avtivity的启动和结束 从当前页面跳到新页面&#xff0c;跳转代码如下&#xff1a; startActivity(new Intent(源页面.this&#xff0c;目标页面.class))&#xff1b; 从当前页面回到上一个页面&#xff0c;相当于关闭当前页面&#xff0c;返回代码如下&#xff1a; finis…