1、计数质数

MX = 5000000
is_prime = [1] * MX
is_prime[0] = is_prime[1]= 0
for i in range(2, MX):if is_prime[i]:for j in range(i * i, MX, i):is_prime[j] = 0class Solution:def countPrimes(self, n: int) -> int:return sum(is_prime[:n])

2、序列中不同最大公约数的数目

class Solution:def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:ans, mx = 0, max(nums)has = [False] * (mx + 1)for x in nums: has[x] = Truefor i in range(1, mx + 1):g = 0  # 0 和任何数 x 的最大公约数都是 xfor j in range(i, mx + 1, i):  # 枚举 i 的倍数 jif has[j]:  # 如果 j 在 nums 中g = gcd(g, j)  # 更新最大公约数if g == i:  # 找到一个答案(g 无法继续减小)ans += 1break  # 提前退出循环return ans

 3、子数组的最大 GCD-Sum

利用子数组gcd值为有限个的情况(复杂度为lgn),对每个gcd值使用最大长度数组进行匹配

class Solution:def maxGcdSum(self, nums: List[int], k: int) -> int:maxl = 0pre = [0]for num in nums:pre.append(pre[-1] + num)g = deque()for i, num in enumerate(nums):temp, s, si = deque(), num, iwhile g:n2, j = g.pop()if gcd(n2, s) < s:temp.appendleft((s, si))if i - si + 1 >= k:maxl = max(maxl, (pre[i + 1] - pre[si]) * s)s, si = gcd(n2, s), jelse:si = jelse:temp.appendleft((s, si))if i - si + 1 >= k:maxl = max(maxl, (pre[i + 1] - pre[si]) * s)g = tempreturn maxl
找到最接近目标值的函数值 与上述做法类似,利用子数组与运算结果为有限个(lgn)的性质,代码如下:
class Solution:def closestToTarget(self, arr: List[int], target: int) -> int:ans = abs(arr[0] - target)valid = {arr[0]}for num in arr:valid = {x & num for x in valid} | {num}ans = min(ans, min(abs(x - target) for x in valid))return ans

4、n 的第 k 个因子

class Solution:def kthFactor(self, n: int, k: int) -> int:count = 0factor = 1while factor * factor <= n:if n % factor == 0:count += 1if count == k:return factorfactor += 1factor -= 1if factor * factor == n:factor -= 1while factor > 0:if n % factor == 0:count += 1if count == k:return n // factorfactor -= 1return -1

5、分解质因数 --  分割数组使乘积互质

class Solution:def findValidSplit(self, nums: List[int]) -> int:left = {}  # left[p] 表示质数 p 首次出现的下标right = [0] * len(nums)  # right[i] 表示左端点为 i 的区间的右端点的最大值def f(p: int, i: int) -> None:if p in left:right[left[p]] = i  # 记录左端点 l 对应的右端点的最大值else:left[p] = i  # 第一次遇到质数 pfor i, x in enumerate(nums):d = 2while d * d <= x:  # 分解质因数if x % d == 0:f(d, i)x //= dwhile x % d == 0:x //= dd += 1if x > 1: f(x, i)max_r = 0for l, r in enumerate(right):if l > max_r:  # 最远可以遇到 max_rreturn max_r  # 也可以写 l-1max_r = max(max_r, r)return -1

使用前缀和 --  向下取整数对和、 统计美丽子字符串 II

6、统计可以被 K 整除的下标对数目

class Solution:def countPairs(self, nums: List[int], k: int) -> int:mx = max(max(nums), k)cnt = [0] * (mx + 1)for num in nums:cnt[num] += 1#统计每个数的倍数出现的次数for i in range(1, mx + 1):for j in range(2 * i, mx + 1, i):cnt[i] += cnt[j]res = 0for num in nums:res += cnt[k // gcd(k, num)]for num in nums:if num * num % k == 0:res -= 1return res // 2

  

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

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

相关文章

Java NIO FileChannel在大文件传输中的性能优化实践指南

Java NIO FileChannel在大文件传输中的性能优化实践指南 在现代分布式系统中&#xff0c;海量数据的存储与传输成为常见需求。Java NIO引入的FileChannel提供了高效的文件读写能力&#xff0c;尤其适合大文件传输场景。本文从原理深度解析出发&#xff0c;结合生产环境实战经验…

SQLite Insert 语句详解

SQLite Insert 语句详解 SQLite 是一种轻量级的数据库管理系统,它以其简洁的设计、强大的功能和易于使用而闻名。在 SQLite 中,INSERT 语句用于向数据库表中添加新数据。本文将详细介绍 SQLite 的 INSERT 语句,包括其基本语法、使用方法以及一些高级特性。 基本语法 SQLi…

git更新内核补丁完整指南

Git操作完整指南 📋 目录 项目概述 Git基础配置 日常操作流程 补丁更新操作 分支管理 冲突解决 常见问题 最佳实践 命令速查表 🎯 项目概述 </

关于回归决策树CART生成算法中的最优化算法详解

首先&#xff0c;一共比如有M个特征&#xff0c;N个样本&#xff0c;对于每一个特征j&#xff0c;遍历其中的N个样本&#xff0c;得到N个值中&#xff0c;最小的值&#xff0c;作为这个特征的最优切分点&#xff0c;而其中的c1&#xff0c;c2是可以直接得到的。然后&#xff0c…

Ubuntu 环境下创建并启动一个 MediaMTX 的 systemd 服务

文章目录一、简介二、安装及使用三、创建系统服务小结一、简介 MediaMTX 是一个现代、高性能、跨平台的 流媒体服务器&#xff0c;主要用于接收、转发、转码和分发 音视频流&#xff0c;支持多种协议。它的前身是 rtsp-simple-server&#xff0c;后来重命名为 MediaMTX&#x…

在React中,函数式组件和类组件各有优缺点

函数式组件&#xff1a;无this&#xff0c;无生命周期&#xff0c;配合使用useEffect&#xff0c; 可使用Hooks。 类组件&#xff1a;有生命周期&#xff0c;状态管理&#xff0c;无Hooks&#xff0c;适用于需要明确生命周期方法和实例方法的场景。 函数式组件 优点&#xff1a…

【SketchUp插件推荐】Profile Builder 4.0 中文版下载安装使用教程(含语言设置图解)

一、插件简介 Profile Builder 4.0 是一款适用于 SketchUp 2017-2024 的高效参数化建模插件&#xff0c;中文名称为「参数化造型建模工具」。该插件基于参数化设计原理&#xff0c;允许用户通过简单的路径定义和参数设定&#xff0c;快速生成智能模型&#xff0c;从而大幅提高…

【小沐学GIS】基于Unity3d绘制三维数字地球Earth(Unity3d、OpenGL、GIS)

&#x1f37a;三维数字地球GIS系列相关文章如下&#x1f37a;&#xff1a;1【小沐学GIS】基于C绘制三维数字地球Earth&#xff08;OpenGL、glfw、glut&#xff09;第一期2【小沐学GIS】基于C绘制三维数字地球Earth&#xff08;OpenGL、glfw、glut&#xff09;第二期3【小沐学GI…

ARM汇编的一些编写和调用规范总结

ARM汇编在格式上有少数硬性要求&#xff0c;在排版上几乎没什么硬性要求&#xff0c;都不多&#xff0c;以下分别说明。格式要求 ARM 汇编有一些格式上的硬性要求&#xff0c;这些规则由汇编器&#xff08;如 GNU 的gas、ARM 官方的armasm&#xff09;强制执行&#xff0c;违反…

FastAPI框架下集成智谱大模型的RAG流式响应服务框架

RAG&#xff08;检索增强生成&#xff09;是结合检索与生成式 AI 的技术框架。核心逻辑是先从外部知识库精准检索相关信息&#xff0c;再将其作为上下文输入大模型生成回答。技术上依赖检索引擎&#xff08;如向量数据库、BM25&#xff09;、大语言模型&#xff08;如 GPT、LLa…

基于深度学习的胸部 X 光图像肺炎分类系统(三)

目录 二分类胸片判断&#xff1a; 1. 数据加载时指定了两类标签 2. 损失函数用了二分类专用的 3. 输出层只有 1 个神经元&#xff0c;用了sigmoid激活函数 4. 预测时用 0.5 作为分类阈值 二分类胸片判断&#xff1a; import numpy as np import matplotlib.pyplot as plt f…

深入理解 BIO、NIO、AIO

目录 一、同步与非同步 二、阻塞与非阻塞 三、BIO&#xff08;Blocking I/O&#xff0c;阻塞I/O&#xff09; 四、NIO&#xff08;Non-blocking I/O&#xff0c;非阻塞I/O&#xff09; 五、AIO&#xff08;Asynchronous I/O&#xff0c;异步I/O&#xff09; 同步阻塞&…

电脑无法识别固态硬盘怎么办?

随着固态硬盘&#xff08;SSD&#xff09;越来越普及&#xff0c;不少用户在给电脑更换、加装SSD时会遇到一个让人头大的问题——电脑识别不了固态硬盘。可能是开不了机&#xff0c;或者在“此电脑”中找不到硬盘&#xff0c;甚至连系统安装界面都提示“找不到驱动器”。这时候…

Kingbasepostgis 安装实践

文章目录前言一、安装准备1.1 部署方案规划1.2 SELINUX、防火墙状态检查1.3 操作系统时间检查1.4 创建用户及密码1.5 目录创建1.6 操作系统参数配置1.6.1 配置limits.conf文件二、安装2.1 上传安装包以及license授权文件2.2 拷贝安装文件2.3 命令行方式安装2.3.1简介2.3.2 许可…

移动端设备能部署的llm

mlc-llm 内置RedPajama hf示例模型 TheBloke/Mistral-7B-Instruct-v0.2-GGUF https://github.com/mlc-ai/mlc-llm/tree/main llama.cpp https://github.com/ggml-org/llama.cpp reference --- MLC-LLM&#xff1a;大模型如何部署到浏览器 / 手机&#xff1f;完整流程复现…

Ubuntu硬盘挂载

一、在 Ubuntu 中&#xff0c;你可以用以下命令快速查看 所有已连接但尚未挂载的硬盘和分区&#xff1a;lsblk -o NAME,SIZE,FSTYPE,MOUNTPOINT,UUID输出中 MOUNTPOINT 为空的行&#xff0c;就是 未挂载的分区。sda ├─sda1 500M ext4 /boot ├─sda2 1.8T ntfs └─sda3 …

JavaScript -Socket5代理使用

axios 安装两个包 socks-proxy-agent&#xff0c;axios const { SocksProxyAgent } require(socks-proxy-agent); const axios require(axios);const socks5Axios axios.create();const socks5 () > {const socks5Agent new SocksProxyAgent("socks5://112.194.8…

[特殊字符] 从数据库无法访问到成功修复崩溃表:一次 MySQL 故障排查实录

一次典型的 MySQL 故障排查与修复全过程&#xff0c;涵盖登录失败、表崩溃、innodb_force_recovery 救援、坏表剔除与数据恢复等关键操作。一、问题背景某业务系统运行多年&#xff0c;数据库使用的是 MySQL 8.0.18&#xff0c;近期在一次服务器重启后&#xff0c;发现无法正常…

【Agent】API Reference Manual(API 参考手册)

https://github.com/Intelligent-Internet/CommonGround/blob/main/docs/framework/03-api-reference.md 以下是这份 API Reference Manual(API 参考手册) 的完整中文翻译: API 参考手册 版本:0.1 目录 概览 1.1 API 目的 1.2 通信协议与核心概念 HTTP API 2.1 POST /se…

LeetCode Hot 100 全排列

给定一个不含重复数字的数组 nums &#xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。示例 1&#xff1a;输入&#xff1a;nums [1,2,3] 输出&#xff1a;[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2&#xff1a;输入&#xff1a;nums [0,1]…