[LeetCode]1237. 找出给定方程的正整数解
题目链接:https://leetcode.cn/problems/find-positive-integer-solution-for-a-given-equation/description/
题目描述:

样例1:
输入:function_id = 1, z = 5
输出:[[1,4],[2,3],[3,2],[4,1]]
解释:function_id = 1 暗含的函数式子为 f(x, y) = x + y
以下 x 和 y 满足 f(x, y) 等于 5:
x=1, y=4 -> f(1, 4) = 1 + 4 = 5
x=2, y=3 -> f(2, 3) = 2 + 3 = 5
x=3, y=2 -> f(3, 2) = 3 + 2 = 5
x=4, y=1 -> f(4, 1) = 4 + 1 = 5
样例2:
输入:function_id = 2, z = 5
输出:[[1,5],[5,1]]
解释:function_id = 2 暗含的函数式子为 f(x, y) = x * y
以下 x 和 y 满足 f(x, y) 等于 5:
x=1, y=5 -> f(1, 5) = 1 * 5 = 5
x=5, y=1 -> f(5, 1) = 5 * 1 = 5
题目限定:

方法1:暴力枚举
func findSolution(customFunction func(int, int) int, z int) [][]int {res := make([][]int, 0, 100)for x := 1; x <= 1000; x++ {for y := 1; y<= 1000; y++ {if customFunction(x,y) == z {temp := []int{x, y}res = append(res,temp)}}}return res
}
暴力枚举法每次都从开始找y,x最多枚举1000次,而y每次也会枚举1000次,因此,总的复杂度为O(x*y)。
方法2:枚举+二分查找
func findSolution(customFunction func(int, int) int, z int) (res [][]int) {for x := 1; x <= 1000; x++ {l, r := 1, 1000for l <= r {mid := (l+r)/2if customFunction(x,mid) == z {res = append(res, []int{x,mid})break} else if customFunction(x,mid) > z {r = mid -1 } else {l = mid + 1}}}return res
}
既然我们知道y每次都从头开始找比较慢,那么我们可以优化y的查找时间,利用二分查找即可将找y的复杂度降到log级别,因此总的时间复杂度为O(xlogy)。
当然,golang中也可以使用sort库的Search方法:
func findSolution(customFunction func(int, int) int, z int) (res [][]int) {for x := 1; x <= 1000; x++ {y := 1 + sort.Search(999, func(y int) bool {return customFunction(x, y+1) >= z})if customFunction(x,y) == z {res = append(res, []int{x,y})}}return res
}
同时需要注意Search的用法,是从[0,n)去查找的,所以类似我们是从0-999中查找出来的下标,最后加上1就表示从1到1000了:
// Search uses binary search to find and return the smallest index i
// in [0, n) at which f(i) is true, assuming that on the range [0, n),
// f(i) == true implies f(i+1) == true. That is, Search requires that
// f is false for some (possibly empty) prefix of the input range [0, n)
// and then true for the (possibly empty) remainder; Search returns
// the first true index. If there is no such index, Search returns n.
// (Note that the “not found” return value is not -1 as in, for instance,
方法3:双指针
func findSolution(customFunction func(int, int) int, z int) (res [][]int) {y := 1000for x := 1; x <= 1000; x++ {for ; y > 0 ; y-- {if customFunction(x,y) < z {break}if customFunction(x,y) == z {res = append(res, []int{x,y})break}}}return res
}
这种方法关键在于直接利用函数单调递增的特性,一个答案从前往后找,另一个答案从后往前找,下一次寻找一定是基于上一次的结果,因此会少很多次遍历,x最多遍历1000次,y总的遍历次数也最多1000次,因此总的时间复杂度为O(x+y)。
相关文章:
[LeetCode]1237. 找出给定方程的正整数解
题目链接:https://leetcode.cn/problems/find-positive-integer-solution-for-a-given-equation/description/ 题目描述: 样例1: 输入:function_id 1, z 5 输出:[[1,4],[2,3],[3,2],[4,1]] 解释:functi…...
【路径规划】基于A*算法和Dijkstra算法的路径规划(Python代码实现)
👨🎓个人主页:研学社的博客💥💥💞💞欢迎来到本博客❤️❤️💥💥🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密…...
蓝桥杯 stm32 PWM 设置占空比
本文代码使用 HAL 库。 文章目录 前言一、创建CubeMX 工程 ,占空比分析:二、相关函数:1. 获取 CNT函数2.设置CNT为 0 函数(计算器清零)3.开启TIM2_CH1的输入捕获中断函数4.TIM 回调函数三、设置上升沿,下降沿四、在lcd上显示 R40 占空比 详细代码五、设置占空比,输出 PW…...
React 合成事件理解
1 事件三个阶段 捕获、目标、处理 (具体百度,后面有空补全)2import React from "react";class Test extends React.Component {parentRef;childRef;constructor(props) {super(props);this.parentRef React.createRef();this.chil…...
202302|读书笔记——国图点滴
杂志剪影|看一本赚一本系列 anywhere 随心而行随心而动,极简相生复古文艺 热情洋溢 色彩斑斓 极致优雅 深邃魅力 新生绽放 灿若星空 异彩纷呈含苞待放 惊艳绽放 爱在云端 空中婚礼 暗夜浪漫 策马逐梦橘影相映 浆果红唇 梦幻无暇 永无止境浮光掠影 微酥清风低调奢华…...
Linux 操作系统原理 — NUMA 架构中的多线程调度开销与性能优化
目录 文章目录 目录前言NUMA 架构中的多线程性能开销1、跨 Node 的 Memory 访问开销2、跨 Core 的多线程 Cache 同步开销3、多线程上下文切换开销4、多线程模式切换开销5、中断处理的开销6、TLB 缓存失效的开销7、内存拷贝的开销NUMA 架构中的性能优化:使用多核编程代替多线程…...
OpenGL - 如何理解 VAO 与 VBO 之间的关系
系列文章目录 LearnOpenGL 笔记 - 入门 01 OpenGLLearnOpenGL 笔记 - 入门 02 创建窗口LearnOpenGL 笔记 - 入门 03 你好,窗口LearnOpenGL 笔记 - 入门 04 你好,三角形 文章目录系列文章目录1. 前言2. 渲染管线的入口 - 顶点着色器2.1 顶点着色器处理过…...
Linux中sed的使用
语法: sed [选项] [sed内置命令字符] [输入文件]选项: 参数说明-n取消默认色的输出常与sed内置命令p一起使用-i直接将修改结果写入文件,不用-i,sed修改的是内存数据-e多次编译,不需要管道符了-r支持正则扩展 sed的内…...
[软件工程导论(第六版)]第1章 软件工程学概述(复习笔记)
文章目录1.1 软件危机1.1.1 软件危机的介绍1.1.2 产生软件危机的原因1.1.3 消除软件危机的途径1.2 软件工程1.2.1 软件工程的介绍1.2.2 软件工程的基本原理1.2.3 软件工程方法学1.3 软件生命周期组成1.4 软件过程概念1.4.1 瀑布模型1.4.2 快速原型模型1.4.3 增量模型1.4.4 螺旋…...
ISP相关
Internet Service Provider,网络提供商/运营商,如电信、联通、移动等。 1. 与ISP互联的出口带宽 IDC或云提供商会与各运营商互联,互联的具体带宽数值一旦泄露,就会被恶意的攻击者利用。例如,若DDos攻击者知道了被攻击…...
vTESTstudio - VT System CAPL Functions - VT2004(续1)
成熟,就是某一个突如其来的时刻,把你的骄傲狠狠的踩到地上,任其开成花或者烂成泥。vtsStartStimulation - 启动激励输出功能:自动激励输出注意:在启动激励输出之前,一定要设置好输出模式Target:目标通道变量空间名称,例…...
WeakMap弱引用
let obj{name:张三} //{name:张三}这个对象能够被读取到,因为obj这个变量名对它的引用 //将引用覆盖掉 objnull //这个对象将会被从内存中移除,因为我们已经失去了对他的所有引用 let obj{name:张三} let arr[obj] objnull //对象{name:张三}不会…...
Springboot 使用quartz 定时任务 增删改查
前段时间公司项目用到了 定时任务 所以写了一篇定时任务的文章 ,浏览量还不错 , Springboot 整合定时任务 ) 所以就准备写第二篇, 如果你是一名Java工程师,你也可以会看到如下的页面 ,去添加定时任务 定时任务展示 :…...
华为OD机试 - 猜字谜(Python) | 机试题+算法思路 【2023】
最近更新的博客 华为OD机试 - 热点网络统计 | 备考思路,刷题要点,答疑 【新解法】 华为OD机试 - 查找单入口空闲区域 | 备考思路,刷题要点,答疑 【新解法】 华为OD机试 - 好朋友 | 备考思路,刷题要点,答疑 【新解法】 华为OD机试 - 找出同班小朋友 | 备考思路,刷题要点…...
Linux常用命令汇总
1、tcpdump抓包 tcpdump这个命令是用来抓包的,默认情况下这个命令是没有的,需要安装一下: yum install -y tcpdump 使用这个命令的时候最好是加上你网卡的名称,不然可能使用不了: tcpdump -nn -i {网卡名称} 网卡名称…...
1.TCP、UDP区别、TCP/IP七层、四层模型、应用层协议(计网)
文章目录1.OSI 七层模型是什么?每一层的作用是什么?2.TCP/IP 四层模型是什么?每一层的作用是什么?应用层(Application layer)传输层(Transport layer)网络层(Network lay…...
气敏电阻的原理,结构,分类及应用场景总结
🏡《总目录》 目录 1,概述2,结构3,工作原理4,分类4.1,加热方式分类4.2,材料分类4.3,氧化还原分类5,应用场景6,总结1,概述 气敏电阻是指电阻值随着环境中某种气体的浓度变化而变化的电阻,本文对其工作原理,结构,分类和应用场景进行总结。 2,结构 气敏电阻由防爆…...
实验10 拓扑排序与最短路径2022
A. DS图—图的最短路径(无框架)题目描述给出一个图的邻接矩阵,输入顶点v,用迪杰斯特拉算法求顶点v到其它顶点的最短路径。输入第一行输入t,表示有t个测试实例第二行输入顶点数n和n个顶点信息第三行起,每行输…...
C/C++每日一练(20230218)
目录 1. 整数转罗马数字 2. 跳跃游戏 II 3. 买卖股票的最佳时机 IV 1. 整数转罗马数字 罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。 字符 数值 I 1 V 5 X …...
【C语言】预编译
🚩write in front🚩 🔎大家好,我是謓泽,希望你看完之后,能对你有所帮助,不足请指正!共同学习交流🔎 🏅2021年度博客之星物联网与嵌入式开发TOP5࿵…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
