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

【1237. 找出给定方程的正整数解】

来源:力扣(LeetCode)

描述:

给你一个函数 f(x, y) 和一个目标结果 z,函数公式未知,请你计算方程 f(x,y) == z 所有可能的正整数 数对 xy。满足条件的结果数对可以按任意顺序返回。

尽管函数的具体式子未知,但它是单调递增函数,也就是说:

  • f(x, y) < f(x + 1, y)
  • f(x, y) < f(x, y + 1)

函数接口定义如下:

interface CustomFunction {
public:// Returns some positive integer f(x, y) for two positive integers x and y based on a formula.int f(int x, int y);
};

你的解决方案将按如下规则进行评判:

  • 判题程序有一个由 CustomFunction9 种实现组成的列表,以及一种为特定的 z 生成所有有效数对的答案的方法。
  • 判题程序接受两个输入:function_id(决定使用哪种实现测试你的代码)以及目标结果 z 。
  • 判题程序将会调用你实现的 findSolution 并将你的结果与答案进行比较。
  • 如果你的结果与答案相符,那么解决方案将被视作正确答案,即 Accepted

示例 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 <= function_id <= 9
  • 1 <= z <= 100
  • 题目保证 f(x, y) == z 的解处于 1 <= x, y <= 1000 的范围内。
  • 在 1 <= x, y <= 1000 的前提下,题目保证 f(x, y) 是一个 32 位有符号整数。

方法一:枚举

根据题目给出的 x 和 y 的取值范围,枚举所有的 x, y 数对,保存满足 f(x, y) = z 的数对,最后返回结果。

代码:

class Solution {
public:vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {vector<vector<int>> res;for (int x = 1; x <= 1000; x++) {for (int y = 1; y <= 1000; y++) {if (customfunction.f(x, y) == z) {res.push_back({x, y});}}}return res;}
};

执行用时:124 ms, 在所有 C++ 提交中击败了13.98%的用户
内存消耗:6.2 MB, 在所有 C++ 提交中击败了80.64%的用户
复杂度分析
时间复杂度:O(mn),其中 m 是 x 的取值数目,n 是 y 的取值数目。
空间复杂度:O(1)。返回值不计入空间复杂度。

方法二:二分查找

我们固定 x = x0​ 时,函数 g(y) = f(x0, y) 是单调递增函数,可以通过二分查找来判断是否存在 y = y0 ,使 g(y0) = f(x0, y0) = z 成立。

代码:

class Solution {
public:vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {vector<vector<int>> res;for (int x = 1; x <= 1000; x++) {int yleft = 1, yright = 1000;while (yleft <= yright) {int ymiddle = (yleft + yright) / 2;if (customfunction.f(x, ymiddle) == z) {res.push_back({x, ymiddle});break;}if (customfunction.f(x, ymiddle) > z) {yright = ymiddle - 1;} else {yleft = ymiddle + 1;}}}return res;}
};

执行用时:4 ms, 在所有 C++ 提交中击败了51.61%的用户
内存消耗:6.1 MB, 在所有 C++ 提交中击败了96.77%的用户
复杂度分析
时间复杂度:O(mlogn),其中 m 是 x 的取值数目,n 是 y 的取值数目。
空间复杂度:O(1)。返回值不计入空间复杂度。

方法三:双指针

假设 x1 < x2,且 f(x1, y1) = f(x2, y2) = z,显然有 y1 > y2。因此我们从小到大进行枚举 x,并且从大到小枚举 y,当固定 x 时,不需要重头开始枚举所有的 y,只需要从上次结束的值开始枚举即可。

代码:

class Solution {
public:vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {vector<vector<int>> res;for (int x = 1, y = 1000; x <= 1000 && y >= 1; x++) {while (y >= 1 && customfunction.f(x, y) > z) {y--;}if (y >= 1 && customfunction.f(x, y) == z) {res.push_back({x, y});}}return res;}
};

执行用时:4 ms, 在所有 C++ 提交中击败了51.61%的用户
内存消耗:6.3 MB, 在所有 C++ 提交中击败了17.20%的用户
复杂度分析
时间复杂度:O(m+n),其中 m 是 x 的取值数目,n 是 y 的取值数目。
空间复杂度:O(1)。返回值不计入空间复杂度。
author:LeetCode-Solution

相关文章:

【1237. 找出给定方程的正整数解】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一个函数 f(x, y) 和一个目标结果 z&#xff0c;函数公式未知&#xff0c;请你计算方程 f(x,y) z 所有可能的正整数 数对 x 和 y。满足条件的结果数对可以按任意顺序返回。 尽管函数的具体式子…...

java基础学习 day41(继承中成员变量和成员方法的访问特点,方法的重写)

继承中&#xff0c;成员变量的访问特点 a. name前什么都不加&#xff0c;name变量的访问采用就近原则&#xff0c;先在局部变量中查找&#xff0c;若没找到&#xff0c;继续在本类的成员变量中查找&#xff0c;若没找到&#xff0c;继续在直接父类的成员变量中查找&#xff0c…...

【c语言进阶】深度剖析整形数据

&#x1f680;write in front&#x1f680; &#x1f4dc;所属专栏&#xff1a; &#x1f6f0;️博客主页&#xff1a;睿睿的博客主页 &#x1f6f0;️代码仓库&#xff1a;&#x1f389;VS2022_C语言仓库 &#x1f3a1;您的点赞、关注、收藏、评论&#xff0c;是对我最大的激励…...

【信息系统项目管理师】项目管理十大知识领域记忆敲出(采购风险沟通干系人)

【信息系统项目管理师】项目管理十大知识领域记忆敲出&#xff08;采购风险沟通干系人&#xff09; 这里写目录标题【信息系统项目管理师】项目管理十大知识领域记忆敲出&#xff08;采购风险沟通干系人&#xff09;一.项目采购管理记忆敲出1.合同管理&#xff1a;2.规划采购管…...

[LeetCode 1237]找出给定方程的正整数解

题目描述 题目链接&#xff1a;[LeetCode 1237]找出给定方程的正整数解 给你一个函数 f(x, y) 和一个目标结果 z&#xff0c;函数公式未知&#xff0c;请你计算方程 f(x,y) z 所有可能的正整数 数对 x 和 y。满足条件的结果数对可以按任意顺序返回。 尽管函数的具体式子未知…...

6.2 构建 RESTful 应用接口

第6章 构建 RESTful 服务 6.1 RESTful 简介 6.2 构建 RESTful 应用接口 6.3 使用 Swagger 生成 Web API 文档 6.4 实战&#xff1a;实现 Web API 版本控制 6.2 构建 RESTful 应用接口 6.2.1 Spring Boot 对 RESTful 的支持 Spring Boot 提供的spring-boot-starter-web组件完全…...

20230218英语学习

How Italian Artist’s Mild Colors Dominate World of Design 温柔的“莫兰迪色”&#xff0c;如何引领设计时尚&#xff1f; The Morandi color scheme has become an across-the-board fashion that now prevails in the world of design.Soft and sophisticated Morandi c…...

Linux单一服务管理systemctl

基本上systemd这个启动服务机制只有systemctl命令来处理&#xff0c;所以全部的操作都需要使用systemctl systemctl管理单一服务 一般来说服务的启动有两个阶段&#xff0c;一个是开机是否启动&#xff0c;以及现在是否启动 systemctl【command】【unit】 command主要有&…...

【GStreamer 】 TX1中CPU和GPU解码显示海康相机RTSP流

大家好&#xff0c;我是虎哥&#xff0c;今天找了一套海康的相机&#xff0c;想后续测试一下DeepStream用网络相机RTSP流做输入看看后续目标识别和分类。但是还是想先实时看看视频&#xff0c;当然&#xff0c;可以选择VLC去查看&#xff0c;顺道我也用GStreamer 来测试了一下&…...

匿名内部类、Lambda表达式、方法引用对比分析

文章目录一、匿名内部类1. 语法格式2. 使用方法① 传统方式② 匿名内部类方式二、Lambda表达式1. 语法格式2. 使用方法① 匿名内部类方式② Lambda表达式方式三、方法引用1. 语法格式2. 使用方法① 类型的静态方法引用② 类型的构造方法引用③ 类型的实例方法引用④ 对象的实例…...

ESXi主机CVE-2021-21972漏洞复现安全处置建议

一、漏洞简介 vSphere 是 VMware 推出的虚拟化平台套件&#xff0c;包含 ESXi、vCenter Server 等一系列的软件。其中 vCenter Server 为 ESXi 的控制中心&#xff0c;可从单一控制点统一管理数据中心的所有 vSphere 主机和虚拟机。 vSphere Client&#xff08;HTML5&#xf…...

研报精选230217

目录 【行业230217毕马威】奢侈品行业新气象【行业230217国信证券】医药生物行业2023年2月投资策略&#xff1a;持续关注疫后复苏和创新两大主线【行业230217国金证券】航空锻造&#xff1a;稳定格局筑专业化壁垒&#xff0c;顺势而为拓产业链深度【个股230217西南证券_招商轮船…...

c++11 标准模板(STL)(std::unordered_set)(一)

定义于头文件 <unordered_set> template< class Key, class Hash std::hash<Key>, class KeyEqual std::equal_to<Key>, class Allocator std::allocator<Key> > class unordered_set;(1)(C11 起)namespace pmr { templ…...

【C语言进阶】你听说过柔性数组吗?

&#x1f466;个人主页&#xff1a;Weraphael ✍&#x1f3fb;作者简介&#xff1a;目前是C语言学习者 ✈️专栏&#xff1a;C语言航路 &#x1f40b; 希望大家多多支持&#xff0c;咱一起进步&#xff01;&#x1f601; 如果文章对你有帮助的话 欢迎 评论&#x1f4ac; 点赞&a…...

[LeetCode]1237. 找出给定方程的正整数解

题目链接&#xff1a;https://leetcode.cn/problems/find-positive-integer-solution-for-a-given-equation/description/ 题目描述&#xff1a; 样例1&#xff1a; 输入&#xff1a;function_id 1, z 5 输出&#xff1a;[[1,4],[2,3],[3,2],[4,1]] 解释&#xff1a;functi…...

【路径规划】基于A*算法和Dijkstra算法的路径规划(Python代码实现)

&#x1f468;‍&#x1f393;个人主页&#xff1a;研学社的博客&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5;&#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密…...

蓝桥杯 stm32 PWM 设置占空比

本文代码使用 HAL 库。 文章目录 前言一、创建CubeMX 工程 ,占空比分析:二、相关函数:1. 获取 CNT函数2.设置CNT为 0 函数(计算器清零)3.开启TIM2_CH1的输入捕获中断函数4.TIM 回调函数三、设置上升沿,下降沿四、在lcd上显示 R40 占空比 详细代码五、设置占空比,输出 PW…...

React 合成事件理解

1 事件三个阶段 捕获、目标、处理 &#xff08;具体百度&#xff0c;后面有空补全&#xff09;2import React from "react";class Test extends React.Component {parentRef;childRef;constructor(props) {super(props);this.parentRef React.createRef();this.chil…...

202302|读书笔记——国图点滴

杂志剪影|看一本赚一本系列 anywhere 随心而行随心而动&#xff0c;极简相生复古文艺 热情洋溢 色彩斑斓 极致优雅 深邃魅力 新生绽放 灿若星空 异彩纷呈含苞待放 惊艳绽放 爱在云端 空中婚礼 暗夜浪漫 策马逐梦橘影相映 浆果红唇 梦幻无暇 永无止境浮光掠影 微酥清风低调奢华…...

Linux 操作系统原理 — NUMA 架构中的多线程调度开销与性能优化

目录 文章目录 目录前言NUMA 架构中的多线程性能开销1、跨 Node 的 Memory 访问开销2、跨 Core 的多线程 Cache 同步开销3、多线程上下文切换开销4、多线程模式切换开销5、中断处理的开销6、TLB 缓存失效的开销7、内存拷贝的开销NUMA 架构中的性能优化:使用多核编程代替多线程…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...

LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)

在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...